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

• US 8,423,283 B2
• Filed: 12/08/2009
• Issued: 04/16/2013
• 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:
  US12/633,481
• Publication Number:
  US 20100153005A1
• Time in Patent Office: 1,225 Days
• Field of Search: 701/117, 701/416, 701/532
• US Class Current: 701/400
• 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 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, the method comprising:

by a computer system comprising computer hardware;

accessing 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;

accessing a start node of the plurality of nodes, the start node representing the starting location of the vehicle;

accessing a destination node of the plurality of nodes, the destination node representing the destination location where the vehicle is to travel;

searching successive nodes from the start node to identify a route from the start node to the destination node, the successive nodes being connected by successive edges of the plurality of edges;

determining whether a selected edge of the successive edges is part of a multi-edge constraint that cannot be traversed by said searching;

in response to determining that the selected edge is part of a multi-edge constraint, subdividing the model into two or more universes, wherein each of the universes comprises a subset of the plurality of nodes, wherein said subdividing the model into two or more universes comprises assigning a first one of the two or more universes to one of the successive nodes that is a start or continuation of the multi-edge constraint or that is a neighbor of a node at the start of the multi-edge constraint;

separately identifying universe driving routes within the two or more universes, wherein the universe driving routes each comprise an ordered subset of the plurality of edges; and

combining at least some of the universe driving routes to produce an overall driving route from the start node to the destination node.

2. The 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 one of the geographical roadways.

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

4. The method of claim 3, further comprising transmitting over a network the generated direction data to a second computer system in the vehicle.

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

6. The method of claim 5, wherein the human perceivable message is a visual output.

7. The method of claim 1, wherein said combining at least some of the universe driving routes to produce the overall driving route comprises combining a portion of the universe driving routes 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.

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

9. The method of claim 1, wherein the starting location of the vehicle is determined by a global positioning device.