Shortest travel path determination using critical start time points

• US 9,285,218 B2
• Filed: 08/23/2013
• Issued: 03/15/2016
• Est. Priority Date: 08/24/2012
• Status: Active Grant

• Current Assignee: Regents of The University of Minnesota (University of Minnesota)
• Original Assignee: Regents of The University of Minnesota (University of Minnesota)
• Inventors: Shekhar, Shashi, Gunturi, Venkata Maruti Viswanath, Yang, KwangSoo
• Primary Examiner(s): Black, Thomas G
• Assistant Examiner(s): Lewandroski, Sara
• Application Number:
  US13/974,777
• Publication Number:
  US 20140058674A1
• Time in Patent Office: 935 Days
• Field of Search: 701/410, 701/411, 701/416, 701/418, 701/420, 701/421, 701/425, 701/465, 701/467, 701/533
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

A shortest path from a source to a destination for a current start time in a set of start times is determined. A processor identifies a critical start time in the set of start times that is temporally separated from the current start time by at least one intermediate start time. The shortest path from the source to the destination for the current start time is set as the shortest path for the at least one intermediate start time without separately determining the shortest path for the at least one intermediate start time. A different shortest path is determined from the source to the destination for the critical start time.

Claims

1. A method comprising:

obtaining a set of start times;

determining a shortest path from a source to a destination for a current start time in the set of start times;

a processor identifying a critical start time in the set of start times temporally separated from the current start time by at least one intermediate start time in the set of start times wherein identifying a critical start time comprises;

identifying a shortest path from the source to a current node;

identifying at least two edges that extend from the current node;

for each edge that extends from the current node, determining path functions that indicate an earliest arrival time for traveling from the source to an end of the edge opposite the current node for each start time in the set of start times after the current start time;

comparing each of the path functions for each edge at each start time after the current start time; and

identifying each start time at which the edge with the earliest path function changes as a critical start time;

setting the shortest path from the source to the destination for the current start time as the shortest path for the at least one intermediate start time without separately determining the shortest path for the at least one intermediate start time;

determining a different shortest path from the source to the destination for the critical start time than for the current start time; and

generating a user interface displaying a plurality of shortest paths from the source to the destination.

2. The method of claim 1 wherein identifying a critical start time comprises identifying the critical start time while determining the shortest path from the source to the destination for the current start time.

3. The method of claim 2 wherein determining a shortest path for the current start time comprises:

retrieving a temporally detailed map providing nodes that include the source and the destination, edges between nodes, and transit times for travelling across each edge at different times; and

beginning from the source at the current start time, identifying a series of edges between the source and the destination that together provide the shortest transit time from the source to the destination.

4. The method of claim 1 wherein generating the user interface comprises displaying each shortest path with a variance of transit times along the path.

5. The method of claim 1 wherein generating a user interface displaying a plurality of shortest paths from the source to the destination comprises displaying each shortest path with at least one start time at which the path is the shortest path from the source to the destination.

6. The method of 1 further comprising:

determining a transit time along the shortest path determined for the current start time at each of the start times in the set of start times;

determining the mean of the transit times;

determining the variance of the transit times; and

generating a user interface indicating the variance in the transit times along the shortest path.

7. A computer-readable storage medium having instructions stored thereon that when executed by a processor cause the processor to perform steps comprising:

identifying start times for which a shortest path should be separately determined through steps comprising;

determining transit times from a source to two separate locations for a plurality of different start times; and

designating each start time at which the transit time to one of the two locations changes from being shorter than the transit time to the other of the two locations to being longer than the transit time to the other of the two locations as a critical start time for which a shortest path should be separately determined;

separately determining the shortest path from a source to a destination for all of the critical start times but fewer than all of a plurality of possible start times;

for each start time that a shortest path is not separately determined, assigning a shortest path from the source to the destination that was separately determined for a start time that precedes the start time; and

generating a user interface displaying a plurality of shortest paths from the source to the destination.

8. The computer-readable storage medium of claim 7 wherein determining a shortest path comprises iteratively expanding paths wherein during each iteration, a path with a shortest transit time from the source is selected for expansion.

9. The computer-readable storage medium of claim 7 further comprising identifying a start time for which a shortest path should be separately determined when determining a shortest path from the source to the destination for another start time.

10. The computer-readable storage medium of claim 7 further comprising determining a variance in a transit time of each shortest path and wherein generating a user interface comprising providing the variance of each shortest path.

11. The computer-readable storage medium of claim 7 wherein assigning a shortest path from the source to the destination that was separately determined for a start time that precedes the start time comprises assigning the shortest path to a range of start times.

12. The computer-readable storage medium of claim 11 wherein generating a user interface further comprises providing at least one range of start times for each shortest path.

13. The computer-readable storage medium of claim 12 wherein generating the user interface further comprises providing at least two ranges of start times for one of the shortest paths.

14. A routing system comprising:

a memory containing a list of possible start times for traveling from a source to a destination across a network of edges;

a processor selecting an earliest start time from the list of possible start times and determining path functions for paths in the network to identify a shortest path from the source to the destination for the earliest start time;

the processor using the path functions to generate a second list of start times, the second list of start times limited to start times when the shortest path will change;

the processor performing an iteration to identify a shortest path from the source to the destination for each start time in the second list of start times;

the processor setting the shortest path for start times in the list of possible start times that are not in the second list of start times without performing the iteration; and

generating a user interface that displays two different shortest paths for two different starting times.

15. The routing system of claim 14 wherein generating the user interface further comprises including ranges of starting times for each shortest path.

16. The routing system of claim 14 further comprising determining a measure of variations in the transit time of a shortest path associated with different start times and generating a user interface that displays the measure.

17. The routing system of claim 14 wherein using the path functions to identify start times when the shortest path will change comprises:

determining path functions for each of the start times in the list of possible start times for two partial paths that each begin at the source; and

identifying a start time as a start time when the shortest path will change by identifying a start time at which the path function for one of the two partial paths becomes earlier than the path function for the other of the two partial paths.