Automated route determination
First Claim
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;
determining that a first link is included among a set of multiple links in a no-outlet region, wherein the set of multiple links can be exited only by traversing the first link used to enter the set of multiple links;
using the routing system to determine a preferred route from the origin to the destination, wherein the routing system excludes the first link based on the determination that the first link is included among the set of multiple links which can be exited only by traversing the first link used to enter the set of multiple links; and
communicating the preferred route from the routing system to a user.
8 Assignments
0 Petitions
Accused Products
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.
-
Citations
16 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; determining that a first link is included among a set of multiple links in a no-outlet region, wherein the set of multiple links can be exited only by traversing the first link used to enter the set of multiple links; using the routing system to determine a preferred route from the origin to the destination, wherein the routing system excludes the first link based on the determination that the first link is included among the set of multiple links which can be exited only by traversing the first link used to enter the set of multiple links; and communicating the preferred route from the routing system to a user. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 14, 15)
-
-
10. A computer-implemented method for identifying a link in a routing graph, the method comprising:
-
accessing routing data for one or more links in a routing graph including a stored indication that a first link is included among a set of multiple links in a no-outlet region, which can be exited only by traversing the first link used to enter the set of multiple links; and identifying, by accessing the routing data, that the first link is included among the set of multiple links in the no-outlet region, wherein the set of multiple links can be exited only by traversing the first link used to enter the set of multiple links; and in response to the identification that the first link is included among the set of multiple links which can be exited only by traversing a link used to enter the set of multiple links, excluding the first link from further consideration in determining a route. - View Dependent Claims (11, 12, 13)
-
-
16. 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; identifying a first link for consideration; determining that the first link is included among a set of multiple links in a no-outlet region, which can be exited only by traversing the first link used to enter the set of multiple links; determining, in response to the determination that the first link is included among the set of multiple links, whether the destination is among the set of multiple links; in response to the determinations that the first link is included among the set of multiple links and the destination is not among the set of multiple links, excluding the first link from the network of roads, and using the routing system to determine a preferred route from the origin to the destination based on the network of roads excluding the first link; and communicating the preferred route from the routing system to a user.
-
Specification