Method and system for scheduling vehicles along routes in a transportation system

• US 9,746,332 B2
• Filed: 08/27/2015
• Issued: 08/29/2017
• Est. Priority Date: 08/27/2015
• Status: Active Grant

• Current Assignee: Conduent Business Services, LLC (Conduent, Inc.)
• Original Assignee: Conduent Business Services, LLC (Conduent, Inc.)
• Inventors: Mukherjee, Koyel, Kumar, Ankit, Manohar, Pallavi, Edakunni, Narayanan Unny, Jat, Sharmistha
• Primary Examiner(s): MOYER, DALE S
• Application Number:
  US14/837,070
• Publication Number:
  US 20170059334A1
• Time in Patent Office: 733 Days
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G07B 15/02 taking into account a variable factor such as distance or time, e.g. for passenger transport, parking systems or car rental systems G07B15/06 takes precedence; taximeters G07B13/00; parking meters per se G07F17/24; car rental systems per se G07B15/00
• CPC Class Codes: G08G 1/0129 for creating historical data or processing based on historical data
• CPC Class Codes: G08G 1/127 to a central station ; Indicators in a central station
• CPC Class Codes: G08G 1/202 Dispatching vehicles on the basis of a location, e.g. taxi dispatching

Abstract

The disclosed embodiments illustrate methods and systems for scheduling one or more first vehicles along a route in a transportation system. The method includes determining one or more demands pertaining to a commutation along a route, where the route comprises at least one pair of stations such that there is a unique path between the pair of stations. The method further includes determining a set of constraints associated with the transportation system. The set of constraints are based on at least a count of second vehicles plying on one or more routes in the transportation system at a time instance, a capacity of a first vehicle, and a performance metric of the transportation system. Further, the method includes determining a count of first vehicles, for plying along the route at the time instance, based on at least the set of constraints.

Claims

1. A method for scheduling one or more first vehicles along a route in a transportation system, the method comprising:

determining, by one or more processors, one or more demands pertaining to a commutation along the route, wherein the route comprises at least one pair of stations such that there is a unique path between the pair of stations;

determining, by the one or more processors, a set of constraints associated with the transportation system, wherein determining the set of constraints comprises at least;

determining, at a comparator of the one or more processors, whether a count of second vehicles, plying on one or more routes in the transportation system at a time instance, is less than a count of total vehicles,

determining whether a capacity of a first vehicle is at least less than a count of the one or more demands; and

determining whether a performance metric of the transportation system meets a predefined threshold, wherein the predefined threshold is a target performance metric for at least one of an expected revenue, a passenger index, a revenue index, and a total profit; and

determining, by the one or more processors, a count of first vehicles, for plying along the route at the time instance, based on at least the set of constraints.

2. The method of claim 1, wherein the transportation system corresponds to at least one or more of a public transportation system, a freight logistic system, a commercial shared ride services system, and a private transportation system.

3. The method of claim 1, further comprising:

selecting, by the one or more processors, the route, from one or more routes, based on at least one or more of a time of day, a traffic congestion on the one or more routes, the count of the one or more demands in the one or more routes, and an expected revenue from each of the one or more routes.

4. The method of claim 1, wherein the pair of stations comprises at least a source station and a destination station.

5. The method of claim 1, wherein the one or more demands are determined, by the one or more processors, based on at least a historical demand, a real time demand, or a pre-book demand.

6. The method of claim 5, wherein the one or more demands are indicative of the commutation by one or more commuters between the pair of stations in the route.

7. The method of claim 1, wherein the set of constraints further comprises determining, by the one or more processors, a tolerance time of a commuter associated with a demand, wherein the tolerance time is indicative of a time duration up to which the commuter waits for the first vehicle on a station along the route.

8. The method of claim 1, wherein the performance metric comprises at least one of a passenger kilometer index (PKI) and a revenue kilometer index (RKI).

9. The method of claim 8, wherein the performance metric is determined based on at least one or more of a fare charged to each commuter for traveling between the pair of stations along the route, a cost incurred by the transportation system for the plying of the first vehicle along the route, and a cost of one or more crews associated with the first vehicle.

10. The method of claim 9, wherein the fare is either a flat rate or is dependent upon the route and a time of travel in a day.

11. The method of claim 1, wherein the count of first vehicles is determined, by the one or more processors, by applying an Integer Linear Programming (ILP) technique on at least the set of constraints.

12. The method of claim 11, further comprising:

determining, by the one or more processors, the count of first vehicles by utilizing a Greedy algorithm, when the one or more demands comprise at least a real time demand.

13. The method of claim 1, further comprising:

transmitting, by the one or more processors, information to a computing device in the first vehicle, wherein the information is indicative of at least the plying of the first vehicle along the route at the time instance.

14. A system for scheduling one or more first vehicles along a route in a transportation system, the system comprising:

one or more processors configured to;

determine one or more demands pertaining to a commutation along the route, wherein the route comprises at least one pair of stations such that there is a unique path between the pair of stations;

determine a set of constraints associated with the transportation system, wherein the determination of the set of constraints comprises at least;

a determination of whether a count of second vehicles, plying on one or more routes in the transportation system at a time instance, is less than a count of total vehicles,

a determination of whether a capacity of a first vehicle is at least less than a count of the one or more demands,

a determination of a tolerance time of a commuter associated with the one or more demands, the tolerance time being a time duration threshold up to which threshold a commuter will wait for the one or more first vehicles at a station along the route, and

a determination of whether a performance metric of the transportation system meets a predefined threshold; and

determine a count of first vehicles, for plying along the route at the time instance, based on at least the set of constraints.

15. The system of claim 14, wherein the one or more processors are further configured to:

select the route, from one or more routes, based on at least one or more of a time of a day, a traffic congestion on the one or more routes, the count of the one or more demands in the one or more routes, and an expected revenue from each of the one or more routes.

16. The system of claim 14, wherein the one or more processors are further configured to determine the one or more demands based on at least a historical demand, a real time demand, or a pre-book demand.

17. The system of claim 14, wherein the one or more processors are further configured to:

determine the performance metric based on at least one or more of a fare charged to each commuter for traveling between the pair of stations along the route, a cost incurred by the transportation system for the plying of the first vehicle along the route, and a cost of one or more crews associated with the first vehicle.

18. The system of claim 14, wherein the one or more processors are further configured to:

determine the count of first vehicles by applying at least an Integer Linear Programming (ILP) technique or a Greedy algorithm on at least the set of constraints.

19. The system of claim 14, wherein the one or more processors are further configured to:

transmit information to a computing device in the first vehicle, wherein the information is indicative of at least the plying of the first vehicle along the route at the time instance.

20. A computer program product for use with a computer, the computer program product comprising a non-transitory computer readable medium, wherein the non-transitory computer readable medium stores a computer program code for scheduling one or more first vehicles along a route in a transportation system, wherein the computer program code is executable by one or more processors to:

determine one or more demands pertaining to a commutation along the route, wherein the route comprises at least one pair of stations such that there is a unique path between the pair of stations;

determine a set of constraints associated with the transportation system, wherein the determination of the set of constraints comprises at least;

a determination of whether a count of second vehicles, plying on one or more routes in the transportation system at a time instance, is less than a count of total vehicles,

a determination of whether a capacity of a first vehicle is at least less than a count of the one or more demands, and

a determination of whether a performance metric of the transportation system meets a predefined threshold, wherein the predefined threshold is a target performance metric for at least one of a passenger index and a revenue index;

determine a count of first vehicles, for plying along the route at the time instance, based on at least the set of constraints; and

transmit information to a computing device in the first vehicle, wherein the information is indicative of at least the plying of the first vehicle along the route at the time instance.