SYSTEM AND METHOD FOR EFFICIENT ROUTING ON A NETWORK IN THE PRESENCE OF MULTIPLE-EDGE RESTRICTIONS AND OTHER CONSTRAINTS
First Claim
1. A method for determining an optimal route between a starting node and a destination node in a graph, the graph comprising a plurality of nodes and a plurality of edges, wherein each edge connects two nodes in the graph and has a cost, the method comprising:
- accessing, using a computer system, the graph;
determining, using the computer system, at least one route between the starting node and the destination node, each route comprising an ordered set of the edges, wherein an edge of a route connects a universe of a first node with a universe of a second node;
determining, using the computer system, a cost for each of the at least one routes; and
selecting, using the computer system, the route from the at least one routes with the lowest cost.
9 Assignments
0 Petitions
Accused Products
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.
-
Citations
27 Claims
-
1. A method for determining an optimal route between a starting node and a destination node in a graph, the graph comprising a plurality of nodes and a plurality of edges, wherein each edge connects two nodes in the graph and has a cost, the method comprising:
-
accessing, using a computer system, the graph; determining, using the computer system, at least one route between the starting node and the destination node, each route comprising an ordered set of the edges, wherein an edge of a route connects a universe of a first node with a universe of a second node; determining, using the computer system, a cost for each of the at least one routes; and selecting, using the computer system, the route from the at least one routes with the lowest cost. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. A computer readable medium having program instructions to determine an optimal route between a starting node and a destination node in a graph, the graph comprising a plurality of nodes and a plurality of edges, wherein each edge connects two nodes in the graph and has a cost, the computer readable medium comprising:
-
program instructions for determining at least one route between the starting node and the destination node, each route comprising an ordered set of the edges, wherein an edge of a route connects a universe of a first node with a universe of a second node; program instructions for determining a cost for each of the at least one routes; and program instructions for selecting the route from the at least one routes with the lowest cost. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27)
-
Specification