Automated route determination

• US 10,551,203 B2
• Filed: 01/13/2014
• Issued: 02/04/2020
• Est. Priority Date: 08/29/2002
• Status: Expired due to Term

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Inventors: Nesbitt, David W.
• Primary Examiner(s): Mancho, Ronnie M
• Application Number:
  US14/153,929
• Publication Number:
  US 20140129141A1
• Time in Patent Office: 2,213 Days
• Field of Search: 701532, 701533, 701117, 701400, 340988, 340990, 340995
• 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 navigation device comprising:

a memory having processor-readable instructions stored therein; and

a processor to execute the processor-readable instructions to;

access information regarding an origin and information regarding a destination in a routing graph representing a network of roads,

the origin and the destination each being represented by a link or a node, and

the routing graph including a first plurality of links,

each link, of the first plurality of links, joining two nodes;

determine whether a distance between a first link, of the first plurality of links and adjacent to an end node, and the destination is within a predetermined distance;

determine, when the distance between the first link and the destination is not within the predetermined distance, whether the first link is used to enter a second plurality of links in a no-outlet region,

the second plurality of links being exited only by traversing the first link used to enter the second plurality of links;

determine, based on determining that the first link is used to enter the no-outlet region, whether the destination is located within the no-outlet region;

add the first link to an adjacency set based on determining that the destination is located within the no-outlet region;

identify a second link, of the first plurality of links, adjacent to the end node;

determine that the second link is not entering the no-outlet region;

add the second link to the adjacency set;

determine a recommended route from the origin to the destination using the adjacency set list; and

cause a presentation processor to provide, for display, the recommended route.

2. The navigation device of claim 1, wherein the recommended route is a route for driving a vehicle from the origin to the destination.

3. The navigation device of claim 1, wherein the recommended route is a route for walking from the origin to the destination.

4. The navigation device of claim 1, wherein the no-outlet region represents a dead-end.

5. The navigation device of claim 1, wherein the processor is further to:

determine a waiting time required at one or more intersections along alternative routes.

6. The navigation device of claim 1, wherein the processor is further to:

process routing preferences received from a user.

7. The navigation device of claim 6, wherein the routing preferences comprise a preference to avoid an urban route or a rural route.

8. The navigation device of claim 1, wherein the processor is further to:

calculate a cost associated with travelling along each of the first plurality of links.

9. The navigation device of claim 8, wherein a link having a left exit has a higher cost than a link having a right exit.

10. The navigation device of claim 1, wherein the recommended route is based on shortest travel time.

11. A non-transitory computer-readable medium storing instructions, the instructions comprising:

one or more instructions, that when executed by one or more processors, cause the one or more processors to;

utilize a routing system to access information regarding an origin and information regarding a destination in a routing graph representing a network of roads and including two or more nodes and one or more links,

determine whether a distance between a first directed link, adjacent to a node, and the destination is within a predetermined distance;

determine, when the distance between the first directed link and the destination is not within the predetermined distance, whether the first directed link is included among a set of multiple links in a no-outlet region,

the set of multiple links being exited only by traversing the first directed link used to enter the set of multiple links;

determine, based on determining that the first directed link is used to enter the no-outlet region, whether the destination is located within the no-outlet region;

add the first directed link to an adjacency set based on determining that the destination is located within the no-outlet region;

identify a second directed link adjacent to the node;

determine that the second directed link is not entering the no-outlet region;

add the second directed link to the adjacency set;

utilize the routing system to determine a preferred route from the origin to the destination using the adjacency set; and

cause a presentation processor to provide, for display, the preferred route.

12. The non-transitory computer-readable medium of claim 11, wherein the no-outlet region represents a dead-end.

13. The non-transitory computer-readable medium of claim 11, wherein the one or more instructions, when executed by the one or more processors, further cause the one or more processors to:

determine a waiting time required at one or more intersections along alternative routes.

14. The non-transitory computer-readable medium of claim 11, wherein the one or more instructions, when executed by the one or more processors, further cause the one or more processors to:

process routing preferences received from a user.

15. A method comprising:

accessing, by a navigation device, information regarding an origin and information regarding a destination in a routing graph representing a network of roads,

the origin and destination each being represented by a link or a node, and

the routing graph including a first plurality of links,

each link, of the first plurality of links, joining two nodes;

determining, by the navigation device, whether a distance between a first link, of the first plurality of links and adjacent to an end node, and the destination is within a predetermined distance;

determining, by the navigation device and when the distance between the first link and the destination is not within the predetermined distance, whether the first link is used to enter a second plurality of links in a no-outlet region,

the second plurality of links being exited only by traversing the first link used to enter the second plurality of links;

determining, by the navigation device and based on determining that the first link is used to enter the no-outlet region, whether the destination is located within the no-outlet region;

adding, by the navigation device, the first link to an adjacency set based on determining that the destination is located within the no-outlet region;

identifying, by the navigation device, a second link, of the first plurality of links, adjacent to the end node;

determining, by the navigation device, that the second link does not enter the no-outlet region;

determining, by the navigation device, a cost for the second link based on determining that the second link is not entering the no-outlet region;

adding, by the navigation device, the second link to the adjacency set based on determining the cost for the second link;

determining, by the navigation device, a recommended route from the origin to the destination using the adjacency set; and

causing, by the navigation device, a presentation processor to provide, for display, the recommended route.

16. The method of claim 15, further comprising:

calculating a cost associated with each of the first plurality of links.

17. The method of claim 15, further comprising:

determining a waiting time required at one or more intersections along alternative routes.

18. The method of claim 15, further comprising:

processing routing preferences received from a user.

19. The method of claim 15, wherein the recommended route is based on shortest travel time.

20. The method of claim 15, wherein a link having a left exit has a higher cost than a link having a right exit.