Shortest travel path determination using critical start time points
First Claim
Patent Images
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
17 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. - View Dependent Claims (2, 3, 4, 5)
-
-
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. - View Dependent Claims (8, 9, 10, 11, 12, 13)
-
-
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. - View Dependent Claims (15, 16, 17)
-
Specification