SYSTEM AND METHOD FOR EFFICIENT ROUTING ON A NETWORK IN THE PRESENCE OF MULTIPLE-EDGE RESTRICTIONS AND OTHER CONSTRAINTS

• US 20100153005A1
• Filed: 12/08/2009
• Published: 06/17/2010
• Est. Priority Date: 12/11/2008
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Telogis Incorporated (Verizon Communications Inc.)
• Inventors: MASON, Ralph James, CERECKE, Carl David James, MITCHELL, David John
• Granted Patent: US 8,423,283 B2
• Time in Patent Office: Days
• US Class Current: 701/201
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

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.

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.

2. The method of claim 1, wherein the cost for a route is based on the cost for utilizing each edge of the route, and wherein the cost for an edge of a route is based on the cost for utilizing the edge between the universes of the nodes the edge connects.

3. The method of claim 1, further comprising assigning at least one universe to each node connected to an edge of a route, wherein a first universe is assigned to the starting node, and wherein a universe other than the first universe is assigned to a node when the node is a start or continuation of a multi-edge constraint.

4. The method of claim 1, further comprising generating a signal, using the computer system, to facilitate following the selected route to the destination node.

5. The method of claim 4, wherein the signal is human perceivable.

6. The method of claim 4, wherein the signal is transmitted to a second computer system over a network.

7. The method of claim 6, wherein the second computer system generates a human perceivable signal based on the signal received over the network.

8. The method of claim 1, wherein the edges represent streets, the nodes represent street intersections, the starting node represents a user'"'"'s current location, and the destination node represents the user'"'"'s desired destination.

9. The method of claim 1, wherein the cost for a route is the amount of time needed to travel the route.

10. The method of claim 1, wherein the cost for a route is the amount of money needed to travel the route.

11. The method of claim 1, wherein the cost for a route is the total distance of the route.

12. The method of claim 1, wherein the cost or a route is dynamic.

13. The method of claim 12, wherein the cost for a route changes based on the time of day.

14. The method of claim 12, wherein the cost for a route changes based on the type of vehicle used to travel the route.

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.

16. The computer readable medium of claim 15, wherein the cost for a route is based on the cost for utilizing each edge of the route, and wherein the cost for an edge of a route is based on the cost for utilizing the edge between the universes of the nodes the edge connects.

17. The computer readable medium of claim 15, further comprising program instructions to assign at least one universe to each node connected to an edge of a route, wherein a first universe is assigned to the starting node, and wherein a universe other than the first universe is assigned to a node when the node is a start or continuation of a multi-edge constraint.

18. The computer readable medium of claim 15, further comprising program instructions for causing a computer system to generate a signal to facilitate following the selected route to the destination node.

19. The computer readable medium of claim 18, wherein the signal is human perceivable.

20. The computer readable medium of claim 18, further comprising program instructions for transmitting the signal to a second computer system over a network.

21. The computer readable medium of claim 20, wherein the second computer system generates a human perceivable signal based on the signal received over the network.

22. The computer readable medium of claim 15, wherein the edges represent streets, the nodes represent street intersections, the starting node represents a user'"'"'s current location, and the destination node represents the user'"'"'s desired destination.

23. The computer readable medium of claim 15, wherein the cost for a route is the amount of time needed to travel the route.

24. The computer readable medium of claim 15, wherein the cost for a route is the amount of money needed to travel the route.

25. The computer readable medium of claim 15, wherein the cost for a route is the total distance of the route.

26. The computer readable medium of claim 15, wherein the cost for a route changes based on the time of day.

27. The computer readable medium of claim 15, wherein the cost for a route changes based on the type of vehicle used to travel the route.