Systems, devices, and methods for searching and booking ride-shared trips

A computer implemented method for optimizing electronically booking ride share trips, the method comprising:

• storing ride sharing records with itineraries including a plurality of legs on a data storage device;
• maintaining a data structure storing additional variant trip booking options, each variant trip booking option automatically generated based on a seed trip;
• receiving a trip booking request for a passenger at a processor;
• parse the trip booking request to determine the seed trip and generate the additional variant trip booking options to expand a search domain associated with the trip booking request;
• populating the data structure representing the expanded search domain with the automatically generated trip booking options, at least one trip booking option representing a different variant trip generated by varying at least one of pickup time, arrival time, pickup location, and drop off location of the trip booking request;
• segregating, the additional trip booking options of the expanded search domain into a plurality of sub-search domains for parallel processing using separate processes, threads, or cores of one or more additional processors or the processor;
• computing, using the separate processes, threads, or cores for at least two of the plurality of sub-search domains of the additional trip booking options to reduce an overall impact on system resources, objective values for the trip booking options, each trip booking option temporarily assigned to a vehicle to compute a corresponding objective value, the objective value being a metric output by an objective function of parameters, the parameters representing one or more of a level of ride share or efficiency, violation of passenger(s) targeted pickup time, violation of passenger(s) targeted arrive-before time, route deviation, vehicle operating cost, in-transit operating cost, vehicle itinerary and vehicle distance/time travelled;
• and
• responsive to the objective values computed using the separate processes, threads, or cores, generating a heuristically optimized data set of one or more retained trip booking options, heuristically transforming the expanded search domain to generate the constrained data set of the one or more retained trip booking options by removing at least one trip booking option from the generated trip booking options;
• transmitting the one or more retained trip booking options for display on an interface application of an electronic device.

A computer implemented system for heuristically optimizing electronically booked ride share trips, the system comprising:

• a data storage device storing ride sharing records with itineraries including a plurality of legs and maintaining a data structure storing additional variant trip booking options, each variant trip booking option automatically generated based on a seed trip;
• a processor configured to:
• receive a trip booking request for a passenger, the trip booking request defining passenger constraints including a desired pickup time or drop off time;
• parse the trip booking request to determine the seed trip and generate the additional variant trip booking options to expand a search domain associated with the trip booking request;
• populate the data structure representing the expanded search domain with the automatically generated additional trip booking options, at least one trip booking option temporarily assigned to a vehicle, the additional trip booking options providing a set of pick up times that differ by a time frequency to cover a time range based on the desired pickup time or drop off time;
• segregate, the additional trip booking options of the expanded search domain into a plurality of sub-search domains for parallel processing using separate processes, threads, or cores of one or more additional processors or the processor;
• compute, using the separate processes, threads, or cores for at least two sub-search domains of the plurality of sub-search domains of the additional trip booking options to reduce an overall impact on system resources, objective values for the trip booking options, each trip booking option temporarily assigned to the vehicle to compute a corresponding objective value, the objective value being a metric output by an objective function of parameters, the parameters representing one or more of a level of ride share or efficiency, violation of passenger(s) targeted pickup time, violation of passenger(s) targeted arrive-before time, route deviation, vehicle operating cost, in-transit operating cost, vehicle itinerary and vehicle distance travelled, and time travelled;
• responsive to the computed objective values, heuristically transform the expanded search domain by removing at least one trip booking option;
• transmit the one or more retained trip booking options for display on an interface application of an electronic device to confirm a trip booking option from the one or more retained trip booking options;
• re-compute the objective function for the confirmed trip booking option;
• assign a vehicle to fulfill the confirmed trip booking option based on the re-computed objective function;
• dynamically update an itinerary for the vehicle assigned to fulfill the confirmed trip booking option to add the confirmed trip booking option to the itinerary;
• and
• trigger transmission of a notification of the confirmed trip booking option and a portion of the itinerary to a device linked to the vehicle assigned to fulfill the confirmed trip booking option.