Shortest Travel Path Determination Using Critical Start Time Points

• US 20140058674A1
• Filed: 08/23/2013
• Published: 02/27/2014
• 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
• Granted Patent: US 9,285,218 B2
• Time in Patent Office: Days
• US Class Current: 701/533
• 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;

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; and

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

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 3 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.

5. The method of claim 1 further comprising generating a user interface displaying a plurality of shortest routes from the source to the destination, each shortest route displayed with at least one start time at which the route is the shortest route from the source to the destination.

7. The method of claim 1 wherein displaying the user interface comprises displaying a plurality of shortest paths from the source to the destination, each shortest path displayed with a variance of transit times along the path.

6. The method of 1 further comprising:

determining a transit time along the shortest route 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

displaying a user interface indicating the variance in the transit times along the shortest route.

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

separately determining the shortest path from a source to a destination for 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.

9. The computer-readable storage medium of claim 8 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 9 wherein identifying a start time for which a shortest path should be separately determined comprises:

determining transit times from the 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.

11. The computer-readable storage medium of claim 10 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.

12. The computer-readable storage medium of claim 8 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.

13. The computer-readable storage medium of claim 12 further comprising generating a user interface providing a plurality of shortest paths and at least one range of start times for each shortest path.

14. The computer-readable storage medium of claim 13 wherein the user interface provides at least two ranges of start times for one of the shortest paths.

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

16. 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 containing 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; and

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.

17. The routing system of claim 16 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.

18. The routing system of claim 16 further comprising generating a user interface that displays two different shortest paths for two different starting times.

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

20. The routing system of claim 16 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.

21. A method comprising:

receiving a starting location;

receiving an ending location;

receiving a future start time; and

identifying a shortest path from the starting location to the ending location when leaving the starting location at the future start time.