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

• US 20120016582A1
• Filed: 09/26/2011
• Published: 01/19/2012
• 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: CERECKE, CARL DAVID JAMES, Mitchell, David John, Mason, Ralph James
• Granted Patent: US 8,214,142 B2
• Time in Patent Office: Days
• US Class Current: 701/410
• 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 computer-implemented method for determining an optimal driving route for a vehicle traveling between a starting location of the vehicle and a destination location of the vehicle in a geographical area, the geographical area comprising a plurality of geographical locations and a plurality of geographical roadways, wherein each geographical roadway connects two geographical locations in the geographical area and has a cost for the vehicle to travel along the geographical roadway, the computer-implemented method comprising:

accessing, using a computer system, a model from a computer accessible storage repository, the model representing the geographical area in which the vehicle is traveling, the model comprising a plurality of nodes representing the geographical locations in the geographical area, and a plurality of edges representing the geographical roadways of the geographical area, wherein each edge connects two nodes in the model of the geographical area, wherein each edge is assigned a cost value representing the cost for the vehicle to travel along the geographical roadway;

accessing, using the computer system, the starting location of the vehicle and the destination location where the vehicle is scheduled to travel;

determining, using the computer system, at one or more driving routes for the vehicle traveling between the starting location of the vehicle and the destination location where the vehicle is scheduled to travel, each driving route comprising an ordered set of the edges, wherein an edge of a driving route connects a first universe of a first location of the vehicle with a second universe of a second location of the vehicle, wherein universes represent possible paths toward the destination location and comprise at least one multi-edge constraint and each edge of a multi-edge constraint;

calculating, using the computer system, a total cost value for each of the one or more driving routes, wherein the total cost value is a summation of cost values for edges used for a driving route; and

selecting, using the computer system, a driving route from the one or more driving routes with the lowest calculated cost value,

wherein the computer system comprises at least a processor and a storage device.

2. The computer-implemented method of claim 1, wherein the computer system comprises one or more computer systems connected via a network connection.

3. The computer-implemented method of claim 1, wherein the cost value assigned to edges in the model represent at least one of a time cost for the vehicle to travel along a roadway represented by the edge, a monetary cost for the vehicle to travel along a roadway represented by the edge, and a distance for the vehicle to travel along a roadway represented by the edge.

4. The computer-implemented method of claim 1, wherein the starting location represents the current location of the vehicle and the destination location represents the desired destination.

5. The computer-implemented method of claim 1, wherein universes are created when a multi-edge constraint is identified or along each of a multi-edge constraint.

6. The computer-implemented method of claim 1, wherein a multi-edge constraint represents one or more edges having a restriction that is dependent on another edge.

7. The computer-implemented method of claim 1, wherein a multi-edge constraint represents at least one of a no u-turn restriction, a no-left turn restriction, or a no-right turn restriction in a geographical roadway.

8. The computer-implemented method of claim 1, further comprising assigning at least one universe to each node connected to an edge of a driving 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.

9. The computer-implemented method of claim 1, further comprising generating direction data, using the computer system, to facilitate following the selected driving route to the destination location.

10. The computer-implemented method of claim 9, further comprising transmitting over a network the generated direction data to a second computer system in the vehicle.

11. The computer-implemented method of claim 10, further comprising causing the second computer system to generate a human perceivable message based on the generated direction data received over the network.

12. The computer-implemented method of claim 11, wherein the human perceivable message is a visual output.

13. The computer-implemented method of claim 12, wherein the visual output comprises a map presented on a display.

14. The computer-implemented method of claim 11, wherein the human perceivable message is an audible output.

15. The computer-implemented method of claim 1, further comprising communicating, using the computer system, with the vehicle and one or more additional vehicles to obtain updated cost values to revise the selected driving route.

16. The computer-implemented method of claim 1, wherein the selecting the driving route with the lowest calculated cost value comprises selecting the driving route for the vehicle that minimizes the total travel time for a group of vehicles as a whole, wherein the group of vehicles includes the vehicle and at least one or more additional vehicles.

17. The computer-implemented method of claim 1, further comprising transmitting the selected driving route to a mobile device in the vehicle.

18. The computer-implemented method of claim 17, wherein the mobile device is a handheld device.

19. The computer-implemented method of claim 17, wherein the mobile device is a navigation system.

20. The computer-implemented method of claim 1, wherein the selecting the driving route further comprises selecting a unique driving route for a plurality of vehicles.

21. The computer-implemented method of claim 20, wherein the cost value is travel time, and wherein the selected routes for each of the plurality of vehicles minimizes the total travel time for the plurality of vehicles as a whole while not necessarily minimizing the travel time of an individual vehicle.

22. The computer-implemented method of claim 1, wherein the cost value for each edge changes based on the time of day.

23. The computer-implemented method of claim 1, wherein the cost value for each edge changes based on the type of vehicle.

24. The computer-implemented method of claim 23, wherein the cost value is infinite when the vehicle is prohibited from traveling on an edge representing a particular roadway.

25. The computer-implemented method of claim 1, wherein the cost value for each edge changes based on rush hour traffic.

26. The computer-implemented method of claim 1, wherein the cost value for each edge is dynamically assigned.

27. The computer-implemented method of claim 1, wherein the cost value assigned to each edge is generated based on data received from a plurality of vehicles traveling in the geographical area.

28. The computer-implemented method of claim 1, wherein universes are configured to be merged or discarded when the node at the end of a constraint is located.

29. The computer-implemented method of claim 1, wherein the starting location of the vehicle is determined by a user inputting data into the computer system.

30. The computer-implemented method of claim 1, wherein the starting location of the vehicle is determined by a global positioning device.