System and method for efficient routing on a network in the presence of multiple-edge restrictions and other constraints
US8886453B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jun 17, 2011 |
| Grant date | Nov 11, 2014 |
| Priority date | — |
| Expiry date | Sep 4, 2031 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG08G1/20
- 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 intersect ion(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.