Automated route determination

• US 8,649,975 B2
• Filed: 09/30/2002
• Issued: 02/11/2014
• Est. Priority Date: 08/29/2002
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: MapQuest, Inc. (Apollo Global Management, Inc.)
• Inventors: Nesbitt, David W.
• Primary Examiner(s): MANCHO, RONNIE M
• Application Number:
  US10/259,793
• Publication Number:
  US 20040042405A1
• Time in Patent Office: 4,152 Days
• Field of Search: 340/995.14, 340/988, 701/201, 701/206, 701/208, 701/214, 701/400, 701/409, 701/420, 701/421, 701/451, 701/468, 701/204, 701/202, 701/200, 701/205, 701/410, 701/437, 701/532, 701/533
• US Class Current: 701/437
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments

Abstract

A preferred route may be determined from an origin location to a destination location. The determination is made by processing directed links (e.g., one-way edges) in a graph that includes one or more links and two or more nodes. The determination of a preferred route may include an estimate of the time required at one or more intersections along alternative. Individual routing preferences, such as a preference of a rural over an urban route, also may be considered. Techniques are described that may help reduce the time required to identify a preferred route, including the identification and removal of no outlet routes before processing the directed links and techniques using particular data formats.

Claims

1. A method for determining a preferred route using a computer-implemented routing system, the method comprising:

using a routing system to access an origin and a destination in a routing graph representing a network of roads and including two or more nodes and one or more links;

determining that a first link is included among a set of multiple links in a no-outlet region, wherein the set of multiple links can be exited only by traversing the first link used to enter the set of multiple links;

using the routing system to determine a preferred route from the origin to the destination, wherein the routing system excludes the first link based on the determination that the first link is included among the set of multiple links which can be exited only by traversing the first link used to enter the set of multiple links; and

communicating the preferred route from the routing system to a user.

2. The method of claim 1 wherein the first link is a link that enters the multiple links.

3. The method of claim 1 wherein the first link is a link that lies within the set of multiple links.

4. The method of claim 1 wherein determining a preferred route comprises determining a preferred route by excluding from further consideration a route that includes the first link based on the determination that the first link is included among the set of multiple links which can be exited only by traversing the first link used to enter the set of multiple links.

5. The method of claim 1 wherein the preferred route is a preferred route for driving a vehicle from the origin to the destination.

6. The method of claim 1 wherein the preferred route is a preferred route for walking from the origin to the destination.

7. The method of claim 1 wherein the routing system comprises a routing system provided through an Internet service provider.

8. The method of claim 1 wherein communicating the preferred route from the routing system to the user includes communicating the preferred route from the routing system to a user system.

9. The method of claim 1 wherein communicating the preferred route comprises communicating the preferred route over a connection that is established using the Internet.

14. The method of claim 1 further comprising discontinuing further consideration of the first link based on the determination that the first link is included among the set of multiple links which can be exited only by traversing the first link used to enter the set of multiple links.

15. The method of claim 14 wherein discontinuing further consideration of the first link includes averting determination of a cost for the first link which would be determined if the first link had not been determined to be included among the set of multiple links.

10. A computer-implemented method for identifying a link in a routing graph, the method comprising:

accessing routing data for one or more links in a routing graph including a stored indication that a first link is included among a set of multiple links in a no-outlet region, which can be exited only by traversing the first link used to enter the set of multiple links; and

identifying, by accessing the routing data, that the first link is included among the set of multiple links in the no-outlet region, wherein the set of multiple links can be exited only by traversing the first link used to enter the set of multiple links; and

in response to the identification that the first link is included among the set of multiple links which can be exited only by traversing a link used to enter the set of multiple links, excluding the first link from further consideration in determining a route.

11. The method of claim 10 wherein the routing data comprises one or more travel prohibitions for the first link.

12. The method of claim 10 further comprising discontinuing further consideration of the first link based on the identification that the first link is included among the set of multiple links which can be exited only by traversing the first link used to enter the set of multiple links.

13. The method of claim 12 wherein discontinuing further consideration of the first link includes averting determination of a cost for the first link which would be determined if the first link had not been determined to be included among the set of multiple links.

16. A method for determining a preferred route using a computer-implemented routing system, the method comprising:

using a routing system to access an origin and a destination in a routing graph representing a network of roads and including two or more nodes and one or more links;

identifying a first link for consideration;

determining that the first link is included among a set of multiple links in a no-outlet region, which can be exited only by traversing the first link used to enter the set of multiple links;

determining, in response to the determination that the first link is included among the set of multiple links, whether the destination is among the set of multiple links;

in response to the determinations that the first link is included among the set of multiple links and the destination is not among the set of multiple links, excluding the first link from the network of roads, and using the routing system to determine a preferred route from the origin to the destination based on the network of roads excluding the first link; and

communicating the preferred route from the routing system to a user.