Automated route determination

• US 8,655,583 B2
• Filed: 07/19/2013
• Issued: 02/18/2014
• Est. Priority Date: 08/29/2002
• Status: Expired due to Term

• 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:
  US13/946,884
• Publication Number:
  US 20130304381A1
• Time in Patent Office: 214 Days
• Field of Search: 701/204, 701/202, 701/200, 701/205, 701/400, 701/410, 701/420, 701/421, 701/437, 701/468, 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 computer-implemented method for determining a preferred route, the method comprising the following operations performed by a routing system including at least one processor:

accessing, from a memory device, 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;

identifying a first intersection to be considered in generating a preferred route;

determining whether a first link of the first intersection enters a no-outlet region; and

generating the preferred route, wherein generating the preferred route comprises excluding at least a first link of the first intersection based on whether the first link enters a no-outlet region.

2. The method of claim 1, further comprising:

using the routing system to determine a cost of traversing the first link of the first intersection.

3. The method of claim 2, wherein the cost is associated with the likelihood of stopping in traversing the first link of the first intersection.

4. The method of claim 1, further comprising:

using the routing system to determine whether the destination lies within the no-outlet region; and

in response to determining that the destination does not lie within the no-outlet region, using the routing system to exclude, from the preferred route, links that enter the no-outlet region.

5. The method of claim 1, further comprising:

using the routing system to determine whether the destination lies within the no-outlet region; and

in response to determining that the destination does not lie within the no-outlet region, continue generating the preferred route without determining a cost of the first link.

6. The method of claim 1, further comprising:

using the routing system to determine whether the destination lies within the no-outlet region; and

in response to determining that the destination lies within the no-outlet region, determine a cost of traversing the first link of the first intersection.

7. The method of claim 1, further comprising:

using the routing system to determine whether the first link is within a predetermined distance from the destination; and

in response to determining that the first link is not within the predetermined distance, using the routing system to exclude, from the preferred route, the first link.

8. The method of claim 1, further comprising:

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

9. The computer-readable medium of claim 1, further comprising one or more code segments that, when executed, cause the processor to:

use the routing system to determine whether the destination lies within the no-outlet region; and

in response to determining that the destination lies within the no-outlet region, use the routing system to determine a cost of traversing the first link of the first intersection.

10. A computer-readable medium for determining a preferred route, having embodied thereon a computer program, the computer program comprising one or more code segments performed by a routing system including at least one processor that, when executed, cause the processor to:

use the routing system to access, from a memory device, 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 identify a first intersection to be considered in generating a preferred route;

use the routing system to determine whether a first link of the first intersection enters a no-outlet region; and

use the routing system to generate the preferred route, wherein generating the preferred route comprises excluding at least a first link of the first intersection based on whether the first link enters a no-outlet region.

11. The computer-readable medium of claim 10, further comprising one or more code segments that, when executed, cause the processor to:

use the routing system to determine a cost of traversing the first link of the first intersection.

12. The computer-readable medium of claim 10, further comprising one or more code segments that, when executed, cause the processor to:

use the routing system to determine whether the destination lies within the no-outlet region; and

in response to determining that the destination does not lie within the no-outlet region, use the routing system to exclude, from the preferred route, links that enter the no-outlet region.

13. The computer-readable medium of claim 10, further comprising one or more code segments that, when executed, cause the processor to:

use the routing system to determine whether the destination lies within the no-outlet region; and

in response to determining that the destination does not lie within the no-outlet region, use the routing system to continue generating the preferred route without determining a cost of the first link.

14. The computer-readable medium of claim 10, further comprising one or more code segments that, when executed, cause the processor to:

use the routing system to determine whether the first link is within a predetermined distance from the destination; and

in response to determining that the first link is not within the predetermined distance, use the routing system to exclude, from the preferred route, the first link.

15. A routing system for determining a preferred route, the routing system including at least one processor performing the following operations:

accessing, from a memory device, 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;

identifying a first intersection to be considered in generating a preferred route;

determining whether a first link of the first intersection enters a no-outlet region; and

generating the preferred route, wherein generating the preferred route comprises excluding at least a first link of the first intersection based on whether the first link enters a no-outlet region.

16. The system of claim 15, including at least one processor performing the following operations:

using the routing system to determine a cost of traversing the first link of the first intersection.

17. The system of claim 15, including at least one processor performing the following operations:

using the routing system to determine whether the destination lies within the no-outlet region; and

in response to determining that the destination does not lie within the no-outlet region, using the routing system to exclude, from the preferred route, links that enter the no-outlet region.

18. The system of claim 15, including at least one processor performing the following operations:

using the routing system to determine whether the destination lies within the no-outlet region; and

in response to determining that the destination does not lie within the no-outlet region, continue generating the preferred route without determining a cost of the first link.

19. The system of claim 15, including at least one processor performing the following operations:

using the routing system to determine whether the destination lies within the no-outlet region; and

in response to determining that the destination lies within the no-outlet region, determine a cost of traversing the first link of the first intersection.

20. The system of claim 15, including at least one processor performing the following operations:

using the routing system to determine whether the first link is within a predetermined distance from the destination; and

in response to determining that the first link is not within the predetermined distance, using the routing system to exclude, from the preferred route, the first link.