Automated route determination

• US 20040052239A1
• Filed: 09/30/2002
• Published: 03/18/2004
• Est. Priority Date: 08/29/2002
• Status: Abandoned Application

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Inventors: Nesbitt, David W.
• Application Number:
  US10/259,788
• Publication Number:
  US 20040052239A1
• Time in Patent Office: Days
• US Class Current: 370/349
• 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, each link 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 based at least in part upon an intersection cost for at least one intersection in the routing graph; and

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

2. The method of claim 1 wherein the intersection cost is based on geometry of the intersection of one or more roads.

3. The method of claim 1 wherein the intersection comprises one or more of an intersection with a turn restriction, a false intersection, a ferry, a ramp-to-ramp transition, a merge from a ramp to a non-ramp, an exit from a non-ramp to a ramp, a first limited-access link to a second limited-access link, a limited-access link to a non-limited access link, an intersection with three links, or an intersection with four or more links.

4. The method of claim 1 wherein the intersection cost is based on a stop level of the intersection.

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 the routing system and the user system use the same processor.

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.

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

accessing routing data for a routing graph that includes at least three nodes, at least two links, each link being connected to two nodes;

determining at least one intersection cost for traversing from a first link to a second link through a node that is connected both to the first link and the second link, each turn cost being based on the accessed routing data; and

associating the intersection cost of traversing from a first link to a second link with the routing data accessed.

11. The method of claim 10 wherein the intersection cost is based on geometry of the intersection.

12. The method of claim 10 wherein the intersection comprises one or more of an intersection with a turn restriction, a false intersection, a ferry, a ramp-to-ramp transition, a merge from a ramp to a non-ramp, an exit from a non-ramp to a ramp, a first limited-access link to a second limited-access link, a limited-access link to a non-limited access link, an intersection with three links, or an intersection with four or more links.

13. The method of claim 10 wherein the intersection cost is based on a stop level of the intersection in which the turn is located.

14. 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 and including two or more nodes and one or more links, each link 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 based at least in part upon an intersection cost for at least one intersection in the routing graph; and

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

15. The medium or signal of claim 14 wherein the intersection cost is based on geometry of the intersection of one or more roads.

16. The medium or signal of claim 14 wherein the intersection comprises one or more of an intersection with a turn restriction, a false intersection, a ferry, a ramp-to-ramp transition, a merge from a ramp to a non-ramp, an exit from a non-ramp to a ramp, a first limited-access link to a second limited-access link, a limited-access link to a non-limited access link, an intersection with three links, or an intersection with four or more links.

17. The medium or signal of claim 14 wherein the intersection cost is based on a stop level of the intersection.

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

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

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

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

22. The medium or signal of claim 14 wherein the one or more code segments configured to communicate the preferred route comprise one or more code'"'"'segments to communicate the preferred route over a connection that is established using the Internet.

23. A computer-readable medium or propagated signal having embodied thereon a computer program configured to identify an intersection cost for an intersection in a routing graph, the medium or signal comprising one or more code segments configured to:

access routing data for a routing graph that includes at least three nodes, at least two links, each link being connected to two nodes;

determine at least one intersection cost for traversing from a first link to a second link through a node that is connected both to the first link and the second link, each turn cost being based on the accessed routing data; and

associate the intersection cost of traversing from a first link to a second link with the routing data accessed.

24. The medium or signal of claim 23 wherein the intersection cost is based on geometry of the intersection.

25. The medium or signal of claim 23 wherein the intersection comprises one or more of an intersection with a turn restriction, a false intersection, a ferry, a ramp-to-ramp transition, a merge from a ramp to a non-ramp, an exit from a non-ramp to a ramp, a first limited-access link to a second limited-access link, a limited-access link to a non-limited access link, an intersection with three links, or an intersection with four or more links.

26. The medium or signal of claim 23 wherein the intersection cost is based on a stop level of the intersection in which the turn is located.

27. A system for determining a preferred route, the system configured 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, each link 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 based at least in part upon an intersection cost for at least one intersection in the routing graph; and

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

28. The system of claim 27 wherein the intersection cost is based on geometry of the intersection of one or more roads.

29. The system of claim 27 wherein the intersection comprises one or more of an intersection with a turn restriction, a false intersection, a ferry, a ramp-to-ramp transition, a merge from a ramp to a non-ramp, an exit from a non-ramp to a ramp, a first limited-access link to a second limited-access link, a limited-access link to a non-limited access link, an intersection with three links, or an intersection with four or more links.

30. The system of claim 27 wherein the intersection cost is based on a stop level of the intersection.

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

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

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

34. The system of claim 27 wherein the routing system and the user system use the same processor.

35. The system of claim 27 wherein the system is configured to communicate the preferred route over a connection that is established using the Internet.

36. A system for identifying an intersection cost for an intersection in a routing graph, the system configured to:

access routing data for a routing graph that includes at least three nodes, at least two links, each link being connected to two nodes;

determine at least one intersection cost for traversing from a first link to a second link through a node that is connected both to the first link and the second link, each turn cost being based on the accessed routing data; and

associate the intersection cost of traversing from a first link to a second link with the routing data accessed.

37. The system of claim 36 wherein the intersection cost is based on geometry of the intersection.

38. The system of claim 36 wherein the intersection comprises one or more of an intersection with a turn restriction, a false intersection, a ferry, a ramp-to-ramp transition, a merge from a ramp to a non-ramp, an exit from a non-ramp to a ramp, a first limited-access link to a second limited-access link, a limited-access link to a non-limited access link, an intersection with three links, or an intersection with four or more links.

39. The system of claim 36 wherein the intersection cost is based on a stop level of the intersection in which the turn is located.