Automated route determination

• US 20040044466A1
• Filed: 09/30/2002
• Published: 03/04/2004
• 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.
• Granted Patent: US 8,560,223 B2
• Time in Patent Office: Days
• US Class Current: 701/202
• 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 including two or more nodes and one or more directed links, each directed link being associated with a direction of travel from a starting node to an ending node and representing a road and each node representing an intersection that includes at least one road;

using the routing system to determine a preferred route from the origin to the destination by using at least one directed link; and

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

2. The method of claim 1 wherein determining a preferred route from the origin to the destination by using at least one directed link comprises determining a preferred route from the origin to the destination by comparing the density of directed links in a first region of the routing graph to the density of directed links in a second region of the routing group.

3. The method of claim 1 wherein determining a preferred route from the origin to the destination by using at least one directed link comprises determining a preferred route from the origin to the destination by applying a factor to a speed associated with a particular directed link based on the density of directed links in a region of the routing graph in which the particular directed link is located.

4. The method of claim 1 wherein determining a preferred route from the origin to the destination by using at least one directed link comprises determining a preferred route from the origin to the destination by using directed link information for at least one directed link.

5. The method of claim 4 wherein the directed link information includes one or more of a cost associated with the directed link, whether the directed link enters a no-outlet region, whether the directed link lies within a no-outlet region, and an intersection cost for each directed link-to-link transition.

6. The method of claim 4 wherein determining a preferred route from the origin to the destination by using at least one directed link comprises determining a preferred route from the origin to the destination by using node information for at least one node.

7. The method of claim 6 wherein the node information includes one or more directed links that link to the node, the number of driveable links that link to from the node, and the total number of links that link to the node.

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

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

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

11. The method of claim 1 wherein the routing system and the user system use the same processor.

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

13. A computer-readable medium or propagated signal having embodied thereon a computer program configured to determine a preferred route using a computer-implemented routing system, the medium or signal comprising one or more code segments configured to:

use a routing system to access an origin and a destination in a routing graph representing a network of roads including two or more nodes and one or more directed links, each directed link being associated with a direction of travel from a starting node to an ending node and representing a road and each node representing an intersection that includes at least one road;

use the routing system to determine a preferred route from the origin to the destination by using at least one directed link; and

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

14. The medium or signal of claim 13 wherein determining a preferred route from the origin to the destination by using at least one directed link comprises determining a preferred route from the origin to the destination by comparing the density of directed links in a first region of the routing graph to the density of directed links in a second region of the routing group.

15. The medium or signal of claim 13 wherein determining a preferred route from the origin to the destination by using at least one directed link comprises determining a preferred route from the origin to the destination by applying a factor to a speed associated with a particular directed link based on the density of directed links in a region of the routing graph in which the particular directed link is located.

16. The medium or signal of claim 13 wherein determining a preferred route from the origin to the destination by using at least one directed link comprises determining a preferred route from the origin to the destination by using directed link information for at least one directed link.

17. The medium or signal of claim 16 wherein the directed link information includes one or more of a cost associated with the directed link, whether the directed link enters a no-outlet region, whether the directed link lies within a no-outlet region, and an intersection cost for each directed link-to-link transition.

18. The medium or signal of claim 16 wherein determining a preferred route from the origin to the destination by using at least one directed link comprises determining a preferred route from the origin to the destination by using node information for at least one node.

19. The medium or signal of claim 18 wherein the node information includes one or more directed links that link to the node, the number of driveable links to from the node, and the total number of links that link to the node.

20. The medium or signal of claim 13 wherein the preferred route is a preferred route for driving a vehicle from the origin to the destination.

21. The medium or signal of claim 13 wherein the preferred route is a preferred route for walking from the origin to the destination.

22. The medium or signal of claim 13 wherein the routing system comprises a routing system provided through an Internet service provider.

23. The medium or signal of claim 13 wherein the routing system and the user system use the same processor.

24. The medium or signal of claim 13 wherein communicating the preferred route comprises communicating the preferred route over a connection that is established using the Internet.

25. A system for determining a preferred route using a computer-implemented routing system, the system configured to:

access an origin and a destination in a routing graph representing a network of roads including two or more nodes and one or more directed links, each directed link being associated with a direction of travel from a starting node to an ending node and representing a road and each node representing an intersection that includes at least one road;

determine a preferred route from the origin to the destination by using at least one directed link; and

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

26. The system of claim 25 wherein determining a preferred route from the origin to the destination by using at least one directed link comprises determining a preferred route from the origin to the destination by comparing the density of directed links in a first region of the routing graph to the density of directed links in a second region of the routing group.

27. The system of claim 25 wherein determining a preferred route from the origin to the destination by using at least one directed link comprises determining a preferred route from the origin to the destination by applying a factor to a speed associated with a particular directed link based on the density of directed links in a region of the routing graph in which the particular directed link is located.

28. The system of claim 25 wherein determining a preferred route from the origin to the destination by using at least one directed link comprises determining a preferred route from the origin to the destination by using directed link information for at least one directed link.

29. The system of claim 28 wherein the directed link information includes one or more of a cost associated with the directed link, whether the directed link enters a no-outlet region, whether the directed link lies within a no-outlet region, and an intersection cost for each directed link-to-link transition.

30. The system of claim 28 wherein determining a preferred route from the origin to the destination by using at least one directed link comprises determining a preferred route from the origin to the destination by using node information for at least one node.

31. The system of claim 30 wherein the node information includes one or more directed links that link to the node, the number of driveable links that link to from the node, and the total number of links that link to the node.

32. The system of claim 25 wherein the preferred route is a preferred route for driving a vehicle from the origin to the destination.

33. The system of claim 25 wherein the preferred route is a preferred route for walking from the origin to the destination.

34. The system of claim 25 wherein the routing system comprises a routing system provided through an Internet service provider.

35. The system of claim 25 wherein the routing system and the user system use the same processor.

36. The system of claim 25 wherein communicating the preferred route comprises communicating the preferred route over a connection that is established using the Internet.