System and method for efficient routing on a network in the presence of multiple-edge restrictions and other constraints
US8214142B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Sep 26, 2011 |
| Grant date | Jul 3, 2012 |
| Priority date | — |
| Expiry date | Sep 26, 2031 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG01C21/3446
- WIPO fieldMeasurement
- WIPO sectorInstruments
Abstract
Embodiments provide systems and methods that find the quickest route between two locations on a graph with multi-edge constraints in a time and space efficient manner. In some embodiments, Dijkstra's algorithm is split into separate universes when a) a multiple-edge constraint is reached, and b) along each edge of a multi-edge constraint. In some embodiments, the split is performed for the purpose of finding the quickest (i.e. lowest weighted) route to the intersection(s) at the end of the constraints. These universes, in some embodiments, are merged or discarded when the intersection at the end of the constraint is found. Using these systems and methods, in some embodiments, the shortest path between two locations of a multi-edge constrained road network can be efficiently determined.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.