AUTOMATED ROUTE DETERMINATION
7 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.
102 Citations
63 Claims
-
1-39. -39. (canceled)
-
40. 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, each link representing a road and each node representing an intersection that includes at least one road; using the routing system to identify an intersection to be considered in generating a preferred route; using the routing system to select a first value, corresponding to the likelihood of stopping in traversing a first exit of the identified intersection, as the intersection cost of the identified intersection, the selection being based upon data describing; the first value corresponding to the likelihood of stopping in traversing a first exit of the identified intersection, and a second value corresponding to the likelihood of stopping in traversing a second exit of the identified intersection; using the routing system to determine the preferred route from the origin to the destination based at least in part upon the first intersection cost of the identified intersection; and communicating the preferred route from the routing system to a user system. - View Dependent Claims (41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52)
-
-
53. A computer-readable medium having embodied thereon a computer program, the computer program comprising one or more code segments that, when executed, cause a computer to:
-
use 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, each link representing a road and each node representing an intersection that includes at least one road; use the routing system to identify an intersection to be considered in generating a preferred route; use the routing system to select a first value, corresponding to the likelihood of stopping in traversing a first exit of the identified intersection, as the intersection cost of the identified intersection, the selection being based upon data describing; the first value corresponding to the likelihood of stopping in traversing a first exit of the identified intersection, and a second value corresponding to the likelihood of stopping in traversing a second exit of the identified intersection; use the routing system to determine the preferred route from the origin to the destination based at least in part upon the first intersection cost of the identified intersection; and communicate the preferred route from the routing system to a user system. - View Dependent Claims (54, 55, 56, 57, 58, 59, 60, 61, 62)
-
-
63. 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, each link representing a road and each node representing an intersection that includes at least one road; using the routing system to identify an intersection to be considered in generating a preferred route; means for using the routing system to select a first value, corresponding to the likelihood of stopping in traversing a first exit of the identified intersection, as the intersection cost of the identified intersection, the selection being based upon data describing; the first value corresponding to the likelihood of stopping in traversing a first exit of the identified intersection, and a second value corresponding to the likelihood of stopping in traversing a second exit of the identified intersection; using the routing system to determine the preferred route from the origin to the destination based at least in part upon the first intersection cost of the identified intersection; and communicating the preferred route from the routing system to a user system.
-
Specification