Amazon.com, Inc.
Techniques for route planning optimization

Abstract:

System and methods are provided for utilizing abstract navigation graphs for route planning purposes. An abstract navigation graph may be generated from a commercially provided navigation graph. One or more maneuver edges may be provided within the abstract navigation graph. Historical location data associated with one or more route traversals may be utilized to identify traversal times for each edge. The traversal times for each edge may be analyzed to identify traversal times for each maneuver edge of the abstract navigation graph. Accordingly, the abstract navigation graph may be utilized for route planning purposes where the traversal times for the maneuver edges impose a time penalty for performing a maneuver. In this manner, maneuver edges of the abstract navigation graph may provide improvements over conventional navigation planning techniques by more accurately representing traversal times than conventional navigation graphs.