System and method for efficient routing on a network in the presence of multiple-edge restrictions and other constraints

• US 8,214,142 B2
• Filed: 09/26/2011
• Issued: 07/03/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
• Primary Examiner(s): Mawari, Redhwan K
• Application Number:
  US13/245,610
• Publication Number:
  US 20120016582A1
• Time in Patent Office: 281 Days
• Field of Search: 701/117, 701/410, 701/532, 370/352, 370/351, 340/425, 340/572.1, 340/995.19, 340/573.4
• US Class Current: 701/408
• 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 overall 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 at least one cost value 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 a selected edge connects a first one of the plurality of nodes and a second one of the plurality of nodes in the model of the geographical area, wherein the selected edge is assigned a first cost value representing a first 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 to travel;

determining, using the computer system, whether the selected edge is part of a multi-edge constraint;

in response to determining that the selected edge is part of a multi-edge constraint, subdividing, using the computer system, the model into two or more universes, wherein a universe comprises one or more of the plurality of nodes, wherein the universes are configured to be merged or discarded when a node at an end of the multi-edge constraint is found;

assigning at least one of the universes to each of the nodes encountered, wherein a first universe is assigned to the starting location, and wherein a second universe other than the first universe is assigned to a second node when the second node is a start or continuation of the multi-edge constraint, or when the second node is a neighbor of the start of the multi-edge constraint;

assigning, using the computer system, a second cost value to the selected edge based on which universes the first node and the second node connected by the selected edge are in;

determining, using the computer system, universe driving routes for the two or more universes, wherein the universe driving routes each comprise a first ordered set of the plurality of edges, wherein the second cost assigned to the selected edge depends at least in part on which of the universes the first node and second node connected by the selected edge are located in;

determining, using the computer system, one or more geographical area driving routes for the vehicle traveling between the starting location of the vehicle and the destination location where the vehicle is to travel, wherein the one or more geographical area driving routes comprise a second ordered set of the plurality of edges, wherein the selected edge connects one or more of the universe driving routes associated with the first node to one or more of the universe driving routes associated with the second node;

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

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

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

thereby enabling determination of the overall driving route for the vehicle traveling between the starting location and the destination location in a geographical area with multi-edge constraints.

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 first cost value assigned to the selected edge in the model represents at least one of a time cost for the vehicle to travel along the geographical roadway represented by the selected edge, a monetary cost for the vehicle to travel along the geographical roadway represented by the selected edge, and a distance for the vehicle to travel along the geographical roadway represented by the selected edge.

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

5. The computer-implemented method of claim 1, wherein the 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 one of the geographical roadways.

6. 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.

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

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

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

10. 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 geographical area driving route.

11. The computer-implemented method of claim 1, wherein the selecting the geographical area driving route with the lowest calculated total cost value comprises selecting the geographical area driving route for the vehicle that minimizes a 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.

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

13. 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.

14. The computer-implemented method of claim 13, wherein the cost value is travel time, and wherein the selected geographical area driving route for each of the plurality of vehicles minimizes a total travel time for the plurality of vehicles as a whole while not necessarily minimizing the travel time of an individual vehicle.

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

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