Automated route determination

• US 10,697,785 B2
• Filed: 02/17/2014
• Issued: 06/30/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/182,227
• Publication Number:
  US 20140163879A1
• Time in Patent Office: 2,325 Days
• Field of Search: 701117, 701533, 701532, 701410, 701400, 701538, 701540, 701541, 340988, 340990, 340995, 34099519
• 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, the method comprising:

obtaining, by at least one processor of a navigation device, information associated with a routing graph representative of a road network,

the routing graph comprising a plurality of nodes and one or more route links connecting pairs of the plurality of nodes,

the plurality of nodes comprising an origin node and a destination node, and

each route link, of the one or more route links, comprising route link data indicating whether each route link enters a no-outlet region;

determining, by the at least one processor of the navigation device and based on the route link data, that a particular route link of the one or more route links enters the no-outlet region;

determining, by the at least one processor of the navigation device and as a result of determining that the particular route link enters the no-outlet region, whether the destination node lies within the no-outlet region; and

as a result of determining that the destination node does not lie within the no-outlet region;

discontinuing, by the at least one processor of the navigation device, processing of the particular route link;

or

as a result of determining that the destination node lies within the no-outlet region;

determining, by the at least one processor of the navigation device, a preferred route between the origin node and the destination node, and

providing, by the at least one processor of the navigation device and for presentation on a display, information associated with the preferred route.

2. The computer-implemented method of claim 1, further comprising:

selecting the particular route link based on one or more preferences of a user.

3. The computer-implemented method of claim 1, further comprising:

selecting the particular route link based on a density of route links within a geographic region associated with the navigation device.

4. The computer-implemented method of claim 1, where the particular route link is a first route link, and

where the computer-implemented method further comprises:

identifying a second route link of the one or more route links based on determining that the destination node does not lie within the no-outlet region; and

determining, based on route link data for the second route link, that the second route link enters another no-outlet region.

5. The computer-implemented method of claim 4, further comprising:

determining whether the destination node lies within the no-outlet region based on determining that the second route link enters the no-outlet region; and

generating the preferred route between the origin node and the destination node based on determining that the destination node lies within the no-outlet region including.

6. The computer-implemented method of claim 1, wherein at least one of the one or more route links corresponds to a road within the road network, and at least one of the one or more route links represents an intersection of roads within the road network.

7. The computer-implemented method of claim 1, further comprising:

computing a cost for traversing the preferred route based on at least a cost for traversing the particular route link.

8. The computer-implemented method of claim 7, further comprising:

obtaining information identifying a predetermined cost for traversing the particular route link; and

computing the cost for traversing the preferred route based on at least the predetermined cost.

9. The computer-implemented method of claim 7, further comprising:

identifying an intersection associated with the particular route link,

the identified intersection corresponding to a node of the routing graph;

determining an intersection cost associated with traversing the identified intersection based on at least one of;

a stop level associated with the intersection,

a waiting time associated with the stop level,

a road geometry associated with the intersection, or

a maneuver associated with the intersection; and

computing the cost associated with traversing the particular route link based on at least the determined intersection cost.

20. The computer-implemented method of claim 1, further comprising:

determining whether two-way travel is permitted along the particular route link, and

determining whether the origin node is a terminal node based on two-way travel being permitted along the particular route link.

10. A navigation apparatus, comprising:

a storage device that stores a set of instructions; and

at least one processor to execute the set of instructions to;

obtain information associated with a routing graph representative of a road network,

the routing graph comprising a plurality of nodes and one or more route links connecting pairs of the plurality of nodes,

the plurality of nodes comprising an origin node and a destination node, and

each route link of the one or more route links comprising route link data indicating whether each route link enters a no-outlet region;

determine, based on the route link data, that a particular route link of the one or more route links enters the no-outlet region;

determine, as a result of determining that the particular route link enters the no-outlet region, whether the destination node lies within the no-outlet region; and

as a result of determining that the destination node does not lie within the no-outlet region;

discontinue processing of the particular route link;

or

as a result of determining that the destination node lies within the no-outlet region;

determine a preferred route between the origin node and the destination node, and

provide, for presentation on a display, information associated with the preferred route.

11. The navigation apparatus of claim 10, wherein the at least one processor is further to:

generate an electronic instruction to transmit information identifying at least the preferred route to a device of a user.

12. The navigation apparatus of claim 11, wherein the at least one processor is further to:

select the particular route link based on one or more preferences of the user.

13. The navigation apparatus of claim 11, wherein the at least one processor is further to:

select the particular route link based on a density of route links within a geographic region associated with the device.

14. The navigation apparatus of claim 10, wherein the particular route link is a first route link, and

wherein the at least one processor is further to:

identify a second route link of the one or more route links from the routing graph based on determining that the destination node does not lie within the no-outlet region;

determine, based on route link data for the second route link, that the second route link enters another no-outlet region;

determine whether the destination node lies within the other no-outlet region based on determining that the second route link enters the other no-outlet region; and

generate the preferred route based on determining that the destination node lies within the other no-outlet region.

15. The navigation apparatus of claim 10, wherein at least one of the one or more route links corresponds to a road within the road network, and at least one of the one or more route links represents an intersection of roads within the road network.

16. The navigation apparatus of claim 10, wherein the at least one processor is further to:

compute a cost for traversing the preferred route based on at least a cost for traversing the particular route link.

17. The navigation apparatus of claim 16, wherein the at least one processor is further to:

obtain information identifying a predetermined cost for traversing the particular route link; and

compute the cost for traversing the preferred route based on at least the predetermined cost.

18. The navigation apparatus of claim 17, wherein the at least one processor is further to:

identify an intersection associated with the particular route link,

the identified intersection corresponding to a node of the routing graph;

determine an intersection cost associated with traversing the identified intersection based on at least one of;

a stop level associated with the intersection,

a waiting time associated with the stop level,

a road geometry associated with the intersection, or

a maneuver associated with the intersection; and

compute the cost associated with traversing the particular route link based on at least the determined intersection cost.

21. The navigation apparatus of claim 10, wherein the at least one processor is further to:

generate the route link data indicating whether the particular route link enters the no-outlet region by;

determining whether two-way travel is permitted along the particular route link; and

determining whether the origin node is a terminal node based on two-way travel being permitted along the particular route link.

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

one or more instructions that, when executed by at least one processor, cause the at least one processor to;

obtain information associated with a routing graph representative of a road network,

the routing graph comprising a plurality of nodes and one or more route links connecting pairs of the plurality of nodes,

the plurality of nodes comprising an origin node and a destination node, and

each route link comprising route link data indicating whether each route link enters a no-outlet region;

determine, based on the route link data, that a particular route link of the one or more route links enters the no-outlet region;

determine, as a result of determining that the particular route link enters the no-outlet region, whether the destination node lies within the no-outlet region; and

as a result of determining that the destination node does not lie within the no-outlet region;

discontinue processing of the particular route link;

or

as a result of determining that the destination node lies within the no-outlet region;

determine a preferred route between the origin node and the destination node, and

provide, for presentation on a display, information associated with the preferred route.