Automated route determination
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.
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.