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

• US 10,248,913 B1
• Filed: 01/13/2017
• Issued: 04/02/2019
• Est. Priority Date: 01/13/2016
• Status: Active Grant

• Current Assignee: Transit Labs, Inc.
• Original Assignee: Transit Labs, Inc.
• Inventors: Gururajan, Prem, Parent, Simon, Bailey, Alexander, Maki, Darren
• Primary Examiner(s): Joseph, Tonya
• Application Number:
  US15/406,178
• Time in Patent Office: 809 Days
• Field of Search: 705 5
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: G06Q 50/40 Business processes related to the transportation industry shipping G06Q10/083

Abstract

Embodiments relate to systems and methods for electronically booking ride share trips. The systems and methods can involve a data storage device storing ride sharing records with itineraries including a plurality of legs. The systems and methods can involve at least one 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. The at least one processor is configured to generate trip booking options from available ride sharing itineraries, each trip booking option including a leg that satisfies the passenger constraints of the trip booking request. The at least one processor is configured to compute objective values for the trip booking options and remove at least one trip booking option based on a comparison of its objective value and temporal proximity to at least one other trip booking option. The at least one processor is configured to transmit the retained trip booking options for display and confirmation at an interface application of an electronic device.

Claims

1. A computer implemented system for 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;

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, each 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 based on at least one of the passenger constraints;

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 each sub-search domain 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 travelled, and time travelled;

responsive to the objective values computed using the separate processes, threads, or cores, heuristically transform the expanded search domain to generate a constrained data set of one or more retained trip booking options by removing at least one trip booking option from the generated trip booking options based on a comparison of its objective value and temporal proximity to at least one other trip booking option, wherein the temporal proximity of the at least one trip booking option to the at least one other trip booking option is a time difference between a pickup time or a drop off time of the at least one trip booking option and pickup time or a drop-off time of the at least one other trip booking option; and

transmit the one or more retained trip booking options for display on an interface application of an electronic device to confirm a selected trip booking option from the one or more retained trip booking options, the selected trip booking option identified at least partly using the interface application of the electronic device.

2. The system of claim 1, wherein the processor is further configured to:

determine that the requested pickup time of the trip booking request is for the present time;

compare objective values of at least two trip options having a pickup time within a time window of the present time;

retain the trip option that is at a later time in order to increase the likelihood of improving the objective value through an improvement in one or more of level of ride share or efficiency, route deviation, vehicle operating cost, vehicle distance travelled, and time travelled.

3. The system of claim 1, wherein the processor is further configured to:

compare objective values of at least two trip options that are within a time window of each other; and

determine that one trip option'"'"'s objective value is worse than another trip booking option'"'"'s objective value; and

remove the said trip option with a worse objective value.

4. The system of claim 1, wherein each trip booking option indicates a pickup time based on a time interval or time frequency, wherein the trip booking options provide different pick up times that differ based on the time interval or the time frequency, wherein the trip booking options provide the different pick up times across a time range.

5. The system of claim 4, wherein each trip booking option has a corresponding trip length duration, wherein the processor is further configured to vary the time interval or the time frequency as a factor of the trip length of duration, a shorter trip length of duration indicating a shorter time interval or time frequency, a longer trip length of duration indicating a longer time interval or time frequency.

6. The system of claim 1, wherein the processor is configured to compute and aggregate a set of metrics to compute a combined objective value.

7. The system of claim 1, wherein the level of ride share or efficiency indicates multiple unrelated passengers in the vehicle assigned to the trip booking option for at least part of the trip.

8. The system of claim 1, wherein the passenger constraints include a desired pickup time, wherein the violation of passenger(s) desired pickup time is a difference between an estimated pickup time for a given trip booking option and the desired pickup time.

9. The system of claim 1, where in the passenger constraints included desired arrive before time, wherein the violation of passenger(s) desired arrive-before time is a difference between an estimated arrival time for a given trip booking option and the desired arrive before time.

10. The system of claim 1, wherein the vehicle operating cost includes a cost of operation of one or more vehicles that are impacted by a given trip booking option, the cost of operation based on an operating fee that includes at least one of mileage and an operating time and by the one or more vehicles that are impacted by a given trip booking option.

11. The system of claim 1, wherein the in-transit operating cost includes an estimated cost for one or more vehicles that are impacted by a given trip booking option to complete pickups and drop-offs for the trip booking option and excluding any idle time of one or more vehicles that are impacted by a given trip booking option.

12. The system of claim 1, wherein the objective value is computed based on a metric of relative delay caused by ride-sharing, the relative delay being based on a travel delay that is a difference between an estimated travel time for a given trip booking option and an estimated travel time between a pick up location and a drop off location based on a more direct route.

13. The system of claim 1, wherein the processor is further configured to compute an objective value for the confirmed trip booking option based on a temporary assignment to a first vehicle, re-compute an objective value for the confirmed trip booking option based on a second vehicle;

assign the second vehicle to fulfill the confirmed trip booking option based on the re-computed objective value, and trigger transmission of a notification of the confirmed trip booking option to a device linked to the second vehicle, wherein the second vehicle may be different than the first vehicle.

20. The system of claim 1, wherein the electronic communication of the legs of the trip booking option to the assigned vehicles causes dynamic adjustment of one or more ride-sharing itineraries that are currently in-transit, causing one or more insertions or one or more removals of each leg into the one or more ride-sharing itineraries that are currently in-transit.

21. The system of claim 1, wherein a sub-objective function is computed independently for each vehicle of the plurality of vehicles, and the objective function is an aggregate of the sub-objective functions.

22. The system of claim 1, wherein a sub-objective function is computed independently for each parameter of the parameters, and the objective function is an aggregate of the sub-objective functions.

23. The system of claim 20, wherein the processor is further configured to, responsive to the dynamic adjustment of the one or more ride-sharing itineraries that are currently in-transit, re-compute the objective functions.

24. The system of claim 1, wherein the trip booking options include at least two trip booking options having corresponding pickup locations or drop off locations proximate within a pre-defined distance from one another, and the retained trip booking options includes at least one of the two trip booking options having corresponding pickup locations or drop off locations proximate within a pre-defined distance from one another.

25. The system of claim 1, wherein the temporarily assignment of each trip booking option to the vehicle includes segregating two or more vehicle itineraries into one or more subgroups based on a level of a similarity match between each of the vehicle itineraries, and the objective functions for each subgroup is computed using separate processes, threads, or cores.

26. The system of claim 1, wherein the objective function comprises weights and the parameters:

Weight1*Parameter1+Weight2*Parameter2+ . . . WeightN*ParameterN

wherein WeightM corresponds to an Mth weight of the weights and ParameterM corresponds to Mth parameters of the parameters, M being an integer between 1 and N, N being an integer greater than 2.

14. 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, each 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 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;

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 based on the at least one trip booking option'"'"'s objective value and temporal proximity to at least one other trip booking option, wherein the temporal proximity of the at least one trip booking option to the at least one other trip booking option is a time difference between a pickup time or a drop off time of the at least one trip booking option and pickup time or a drop-off time of the at least one other trip booking option;

transmitting the one or more retained trip booking options for display on an interface application of an electronic device to confirm a selected trip booking option from the one or more retained trip booking options, the selected trip booking option identified at least partly using the interface application of the electronic device; and

confirming a trip booking option of the retained trip booking options.

15. The method of claim 14, wherein the trip booking request includes a desired pickup time includes:

determining that the desired pickup time of the trip booking request is for a present time;

comparing objective values of at least two trip options within a time window of the present time;

retaining the trip option that is at a later time in order to increase the likelihood of improving the objective value.

16. The method of claim 14, further comprising:

comparing objective values of at least two trip options that are within a specific time of each other,

determining that one trip option'"'"'s objective value is worse than another; and

removing the said trip option with a worse objective value.

17. 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, each 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 each sub-search domain 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 based on a comparison of its objective value and temporal proximity to at least one other trip booking option to generate a constrained data set of one or more retained trip booking options, wherein the temporal proximity of the at least one trip booking option to the at least one other trip booking option is a time difference between a pickup time or a drop off time of the at least one trip booking option and pickup time or a drop-off time of the at least one other 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 selected trip booking option from the one or more retained trip booking options, the selected trip booking option identified at least partly using the interface application of the electronic device;

confirm a selected 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.

18. The system of claim 17, wherein the processor is further configured to receive a cancellation of the confirmed trip booking option, dynamically update the itinerary to remove the confirmed trip booking option from the itinerary, trigger transmission of a notification of the cancellation and a portion of the itinerary to the device.

19. The system of claim 17, wherein the processor is further configured to compare objective values of at least two trip options that are within a specific time of each other;

determine that one trip option'"'"'s objective value is worse than another; and

;

remove the said trip option with a worse objective value.