Method for computing fastest route on road networks with dynamic traffic information
Inventors
Assignees
Max Planck Gesellschaft zur Foerderung der Wissenschaften • New Jersey Institute of Technology
Publication Number
US-12276515-B2
Publication Date
2025-04-15
Expiration Date
2040-02-14
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Abstract
A method and system that utilizes an admissible heuristic to determine the fastest-path between two points on a road map is disclosed. The method and system are based in part on a set of separators disposed on the map and represented by line segments, either independent or organized into hierarchical tree structures and based on recursive spatial subdivision. A preprocessing step computes a vector of values per road junction based on the separators that is then stored with the map and used to efficiently compute a high-quality heuristic to be used at a query stage. The heuristic scales well to any map size, resulting in a very efficient determination of fastest-path queries between points at all distances. The implementation is economically feasible and the resulting query speeds are significantly faster than other known heuristics and other state-of-the-art systems used for computing fastest-paths on maps.
Core Innovation
The invention provides a method and system for determining the fastest route between two points in large road networks using an admissible heuristic based on a set of separators represented as line segments. These separators can be organized into hierarchical structures such as binary trees (Local Separator Heuristic, LSH) or quadtrees (Quadtree Separator Heuristic, QSH), allowing for efficient preprocessing and storage of minimal cost values per road junction. These stored vectors are then leveraged during online queries to compute high-quality heuristic estimates that significantly accelerate fastest-path searches using the A* algorithm.
The problem addressed is the inefficient and slow computation of fastest routes in large and dynamic road networks due to the exhaustive search methods employed by existing navigation systems. Traditional algorithms often require traversing large portions of the graph and rely on significant storage, which becomes impractical as the complexity and size of the road network increases, especially when real-time traffic data updates cause frequent changes in edge costs.
The disclosed solution introduces a preprocessing stage that computes, for each road junction, a vector of minimal-cost values to the defined set of separators. These values are stored with the map data and used during queries to provide a scalable and efficient heuristic for the A* algorithm. The approach includes multiple types of separator heuristics: Global Separator Heuristic (GSH), which uses global map separators, LSH which uses recursively defined hierarchical separators, and QSH based on quadtree structures. Each method offers trade-offs between storage and heuristic quality, with the hierarchical approaches, especially LSH, providing better scalability and significantly improved response time compared to existing methods.
Claims Coverage
The independent claims define several inventive features related to preprocessing and using separator-based heuristics for fastest-path determination, both as a process and as a computer-readable medium.
Storing separator trees with minimal cost values in preprocessing for fastest path determination
Involves the construction of a separator tree during a preprocessing step and the association of at least one minimal cost value to each node or road junction. These values are stored for later use during an online query, enabling computation of a local separator heuristic (LSH) function. The response to the online query utilizes both the stored separator tree and the heuristic function calculated post-preprocessing to determine a fast path, improving the response over a classical A* algorithm that does not use this heuristic.
Computer-readable medium storing separator tree and vectors enabling efficient heuristic computation
Describes a non-transitory computer-readable medium that stores code for constructing, via a preprocessing step, a separator tree with minimal cost values per road junction. The code enables storing the resulting vectors, and, when responding to an online query, utilizes the set of separators and stored vectors to compute the heuristic function for fastest-path determination. The claim also specifies an improved response versus a classical A* algorithm not using this heuristic.
The inventive features focus on preprocessing a road network to compute and store separator-based cost vectors, either as part of a method or a computer-readable medium, to enable efficient, scalable, and improved heuristic fastest-path computation during online queries.
Stated Advantages
Allows significantly more efficient computation of fastest routes in large road networks under dynamic traffic conditions, reducing latency and providing quicker responses.
Reduces storage and data usage compared to current navigation technologies, making the implementation economically feasible.
Scales well to any map size, maintaining high-quality heuristic performance with minimal data storage.
Significantly accelerates query speeds for fastest-path calculations compared to other known heuristics and state-of-the-art systems.
Documented Applications
Determination of fastest travel routes in large road networks for online navigation systems using dynamic traffic information.
Applicable to any minimal-cost problem on graphs, such as shortest path searches in communication networks, social networks, and road maps.
Interested in licensing this patent?