Automated route determination

• US 20040042405A1
• 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,649,975 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• 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;

using the routing system to determine a preferred route from the origin to the destination by identifying at least one no-outlet link in the routing graph; and

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

2. The method of claim 1 wherein the no-outlet link is a link that enters a no-outlet region.

3. The method of claim 1 wherein the no-outlet link is a link that lies within a no-outlet region.

4. The method of claim 1 wherein determining a preferred route comprises determining a preferred route without considering a preferred route that includes the identified no-outlet link.

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 a no-outlet link in a routing graph, the method comprising:

accessing routing data for one or more links in a routing graph that includes two or more nodes and one or more directed links; and

identifying a no-outlet link based on the accessed routing data.

11. The method of claim 10 further comprising identifying a link within a no-outlet region.

12. The method of claim 10 wherein routing data comprises one or more travel prohibitions for a link.

13. The method of claim 12 wherein the one or more travel prohibitions for a link comprises one or more of a gate restricting access to the link, a one-way travel restriction for the link, or a dead-end link that does not connects with one another link.

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;

use the routing system to determine a preferred route from the origin to the destination by identifying at least one no-outlet link in the routing graph; and

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

15. The medium or signal of claim 14 wherein the no-outlet link is a link that enters a no-outlet region.

16. The medium or signal of claim 14 wherein the no-outlet link is a link that lies within a no-outlet region.

17. The medium or signal of claim 14 wherein the one or more code segments configured to determine a preferred route comprise one or more code segments configured to determine a preferred route without considering a preferred route that includes the identified no-outlet link.

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 communicating the preferred route comprises communicating 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 a no-outlet link in a routing graph, the medium or signal comprising one or more code segments configured to:

access routing data for one or more links in a routing graph that includes two or more nodes and one or more directed links; and

identify a no-outlet link based on the accessed routing data.

24. The medium or signal of claim 23 further comprising one or more code segments configured to identify a link within a no-outlet region.

25. The medium or signal of claim 23 wherein routing data comprises one or more travel prohibitions for a link.

26. The medium or signal of claim 23 wherein the one or more travel prohibitions for a link comprises one or more of a gate restricting access to the link, a one-way travel restriction for the link, or a dead-end link that does not connects with one another link.

27. 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 and including two or more nodes and one or more links; and

determine a preferred route from the origin to the destination by identifying at least one no-outlet link in the routing graph; and

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

28. The system of claim 27 wherein the no-outlet link is a link that enters a no-outlet region.

29. The system of claim 27 wherein the no-outlet link is a link that lies within a no-outlet region.

30. The system of claim 27 wherein determining a preferred route comprises determining a preferred route without considering a preferred route that includes the identified no-outlet link.

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 communicating the preferred route comprises communicating the preferred route over a connection that is established using the Internet.

36. A system for identifying a no-outlet link in a routing graph, the system configured to:

access routing data for one or more links in a routing graph that includes two or more nodes and one or more directed links; and

identify a no-outlet link based on the accessed routing data.

37. The system of claim 36 further configured to identify a link within a no-outlet region.

38. The system of claim 36 wherein routing data comprises one or more travel prohibitions for a link.

39. The system of claim 38 wherein the one or more travel prohibitions for a link comprises one or more of a gate restricting access to the link, a one-way travel restriction for the link, or a dead-end link that does not connects with one another link.