Method for computing fastest route on road networks with dynamic traffic information
US12276515B2 · kind B2 · utility
Assignees
Inventors
Key dates
| Filing date | Feb 14, 2020 |
| Grant date | Apr 15, 2025 |
| Priority date | — |
| Expiry date | Feb 16, 2044 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/9537
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.