Hedging risk in journey planning

• US 9,459,108 B2
• Filed: 08/31/2012
• Issued: 10/04/2016
• Est. Priority Date: 08/31/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Berlingerio, Michele, Botea, Adi I., Bouillet, Eric P., Calabrese, Francesco, Deleris, Lea A., Gresh, Donna L., Verscheure, Olivier
• Primary Examiner(s): PATEL, SHARDUL D
• Application Number:
  US13/600,996
• Publication Number:
  US 20140067254A1
• Time in Patent Office: 1,495 Days
• Field of Search: 701/400, 701/410, 701/426, 701/533, 342/463
• US Class Current: 1/1
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01C 21/3423 Multimodal routing, i.e. combining two or more modes of transportation, where the modes can be any of, e.g. driving, walking, cycling, public transport
• 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/36 Input/output arrangements for on-board computers
• CPC Class Codes: G08G 7/00 Traffic control systems for simultaneous control of two or more different kinds of craft

Abstract

Embodiments of the disclosure include a computer system for journey planning, the computer system includes a journey planning server configured to perform a method. The method includes receiving a journey planning request, the journey planning request having an origin and a destination in a transportation network. The method also includes calculating an optimized journey plan by identifying a plurality of routes through the transportation network from the origin to the destination and determining an uncertainty associated with each of the plurality of routes. Calculating an optimized journey plan also includes evaluating a robustness of each of the plurality of routes to the uncertainty associated with each of the plurality of routes and selecting the optimized journey plan based on the journey planning request and the robustness of each of the plurality of routes.

Claims

1. A computer system for journey planning, the computer system comprising:

a journey planning server having a processor, the processor configured to perform a method comprising;

receiving a journey planning request, the journey planning request comprising an origin and a destination in a transportation network;

receiving and storing information from the multi-modal transportation network regarding a state of one or more pieces of transportation equipment in the multi-modal transportation network, wherein the state of one or more pieces of equipment comprises at least one of on-schedule, off-schedule, and out-of-service;

calculating, by a processor, an optimized journey plan, wherein calculating the optimized journey plan comprises;

identifying a plurality of routes through the transportation network from the origin to the destination;

determining an uncertainty associated with each of the plurality of routes, wherein the uncertainty comprises a variability of a travel time along each route, wherein the variability is based on an expected travel time, a mode travel time, a median travel time and a standard deviation;

evaluating a robustness of each of the plurality of routes to the uncertainty associated with each of the plurality of routes; and

selecting the optimized journey plan based on the journey planning request and the robustness of each of the plurality of routes.

2. The computer system of claim 1, wherein the journey planning request further comprises an optimization request and wherein selecting the optimized journey plan is further based on the optimization request.

3. The computer system of claim 2, the optimization request comprises a worst case arrival time.

4. The computer system of claim 2, the optimization request comprises a most consistent arrival time.

5. The computer system of claim 1, wherein determining an uncertainty associated with each of the plurality of routes is based on a historical data associated with the transportation network.

6. The computer system of claim 1, wherein evaluating a robustness of each of the plurality of routes to the uncertainty associated with each of the plurality of routes includes determining a worst case travel time for each of the plurality of routes and an expected travel time for each of the plurality of routes.

7. The computer system of claim 1, wherein at least one of the plurality of routes through the transportation network from the origin to the destination includes multiple contingent branches.

12. The computer program product of claim 7, wherein determining an uncertainty associated with each of the plurality of routes is based on a historical data associated with the transportation network.

13. The computer program product of claim 7, wherein evaluating a robustness of each of the plurality of routes to the uncertainty associated with each of the plurality of routes includes determining a worst case travel time for each of the plurality of routes and an expected travel time for each of the plurality of routes.

14. The computer program product of claim 7, wherein at least one of the plurality of routes through the transportation network from the origin to the destination includes multiple contingent branches.

8. A computer program product for journey planning, the computer program product comprising:

a non-transitory computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising;

computer readable program code configured for;

receiving a journey planning request, the journey planning request comprising an origin and a destination in the multi-modal transportation network;

receiving and storing information from the multi-modal transportation network regarding a state of one or more pieces of transportation equipment in the multi-modal transportation network, wherein the state of one or more pieces of equipment comprises at least one of on-schedule, off-schedule, and out-of-service;

calculating, by a processor, an optimized journey plan, wherein calculating the optimized journey plan comprises;

identifying a plurality of routes through the transportation network from the origin to the destination;

determining an uncertainty associated with each of the plurality of routes, wherein the uncertainty comprises a variability of a travel time along each route, wherein the variability is based on an expected travel time, a mode travel time, a median travel time and a standard deviation;

evaluating a robustness of each of the plurality of routes to the uncertainty associated with each of the plurality of routes; and

selecting the optimized journey plan based on the journey planning request and the robustness of each of the plurality of routes.

9. The computer program product of claim 8, wherein the journey planning request further comprises an optimization request and wherein selecting the optimized journey plan is further based on the optimization request.

10. The computer program product of claim 9, the optimization request comprises a worst case arrival time.

11. The computer program product of claim 9, the optimization request comprises a most consistent arrival time.