System and method for estimating impedance time through a road network
First Claim
1. A method for estimating an impedance time through a node at an intersection between roads in a roadway network, comprising:
- identifying characteristic information for roads intersecting at a node in a roadway network, said characteristic information describing at least one feature concerning an associated road; and
estimating an impedance time associated with potential delays by traffic traveling through the node based on the characteristic information for the roads intersecting at the node, wherein said identifying step comprises obtaining intersection angle information identifying an angle between the roads intersecting at the node, said intersection angle information representing at least a portion of the characteristic information.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and apparatus are provided for estimating an impedance through a node at an intersection between roads in a roadway network. The impedance may be measured in time or distance, for example. Characteristic information describes at least one feature of the intersecting roads. One or more pieces of characteristic information may impact the impedance of traffic through an intersection and are used to estimate the impedance through the node. Examples of characteristic information are speed information, road-type, network routing level, intersection angle information, one-way, and cross traffic turn information. An impedance factor, or a cost, is assigned to each piece of characteristic information. The cost may be positive if the characteristic information adds impedance to the node, or negative if the characteristic information subtracts impedance from the node.
72 Citations
18 Claims
-
1. A method for estimating an impedance time through a node at an intersection between roads in a roadway network, comprising:
-
identifying characteristic information for roads intersecting at a node in a roadway network, said characteristic information describing at least one feature concerning an associated road; and
estimating an impedance time associated with potential delays by traffic traveling through the node based on the characteristic information for the roads intersecting at the node, wherein said identifying step comprises obtaining intersection angle information identifying an angle between the roads intersecting at the node, said intersection angle information representing at least a portion of the characteristic information.
-
-
2. A method for estimating an impedance time through a node at an intersection between roads in a roadway network, comprising:
-
identifying characteristic information for roads intersecting at a node in a roadway network, said characteristic information describing at least one feature concerning an associated road; and
estimating an impedance time associated with potential delays by traffic traveling through the node based on the characteristic information for the roads intersecting at the node, wherein said identifying step comprises obtaining cross traffic turn information identifying whether a desired route through the node crosses oncoming traffic, said cross traffic turn information representing at least a portion of the characteristic information.
-
-
3. A method for calculating a navigation route between first and second geographic locations through a roadway network of roads intersecting at nodes, comprising:
-
providing a data structure having data indicative of a roadway network of roads intersecting at intersection nodes, said data including feature data indicative of traffic characteristics for associated roads;
calculating a route impedance for navigation route through said roadway network between first and second geographic locations based on said feature data;
determining node impedances for intersection nodes though which the navigation route travels based on said feature data, said intersection nodes representing locations along the navigation route at which roads followed by the navigation route intersect other roads; and
utilizing said node impedance and route impedance to calculate the navigation route, wherein said determining step includes obtaining intersection angle information identifying an angle between roads meeting at the intersection node, said node impedance being determined based at least partially on said intersection angle information.
-
-
4. A method for calculating a navigation route between first and second geographic locations through a roadway network of roads intersecting at nodes, comprising:
-
providing a data structure having data indicative of a roadway network of roads intersecting at intersection nodes, said data including feature data indicative of traffic characteristics for associated roads;
calculating a route impedance for a navigation route through said roadway network between first and second geographic locations based on said feature data;
determining node impedances for intersection nodes though which the navigation route travels based on said feature data, said intersection nodes representing locations along the navigation route at which roads followed by the navigation route intersect other roads; and
utilizing said node impedance and route impedance to calculate the navigation route, wherein said determining step includes obtaining cross traffic turn information identifying whether the navigation route crosses on-coming traffic when passing through an associated intersection node, said node impedance being determined based at least partially on said cross traffic turn information.
-
-
5. A method for calculating a navigation route between first and second geographic locations through a roadway network of roads intersection at nodes, comprising:
-
providing a data structure having data indicative of a roadway network of roads intersecting at intersection nodes, said data including feature data indicative of traffic characteristics for associated roads;
calculating a route impedance for a navigation route through said roadway network between first and second geographic locations based on said feature data;
determining node impedances for intersection nodes through which the navigation route travels based on said feature data, said intersection nodes representing locations along the navigation route at which roads followed by the navigation route intersect other roads; and
utilizing said node impedance and route impedance to calculate the navigation route, wherein said determining step includes assigning a turn penalty to the node impedance when the navigation route crosses on-coming traffic when passing through a corresponding intersection node.
-
-
6. A method for calculating a navigation route between first and second geographic locations through a roadway network of roads intersecting at nodes, comprising:
-
providing a data structure having data indicative of a roadway network of roads intersecting at intersection nodes, said data including feature data indicative of traffic characteristics for associated roads;
calculating a route impedance for a navigation route through said roadway network between first and second geographic locations based on said feature data;
determining node impedances for intersection nodes though which the navigation route travels based on said feature data, said intersection nodes representing locations along the navigation route at which roads followed by the navigation route intersect other roads;
identifying when the navigation route travels through neighborhood roads in a residential geographic area remote from said first and second geographic locations;
including a neighborhood penalty with one of said route and node impedances based on said identification step; and
utilizing said node impedance and route impedance to calculate the navigation route.
-
-
7. A method for calculating a navigation route between first and second geographic locations through a roadway network of roads intersecting at nodes, comprising:
-
providing a data structure having data indicative of a roadway network of roads intersecting at intersection nodes, said data including feature data indicative of traffic characteristics for associated roads;
calculating a route impedance for a navigation route through said roadway network between first and second geographic locations based on said feature data;
determining node impedances for intersection nodes though which the navigation route travels based on said feature data, said intersection nodes representing locations along the navigation route at which roads followed by the navigation route intersect other roads;
including a neighborhood penalty with one of said route and node impedances when the navigation route travels through neighborhood roads in a residential geographic area intermediate said first and second geographic locations; and
utilizing said node impedance and route impedance to calculate the navigation route.
-
-
8. A method for calculating a navigation route between first and second geographic locations through a roadway network of roads intersecting at nodes, comprising:
-
providing a data structure having data indicative of a roadway network of roads intersecting at intersection nodes, said data including feature data indicative of traffic characteristics for associated roads;
calculating a route impedance for a navigation route through said roadway network between first and second geographic locations based on said feature data;
determining node impedances for intersection nodes though which the navigation route travels based on said feature data, said intersection nodes representing locations along the navigation route at which roads followed by the navigation route intersect other roads;
identifying when the navigation route travels along an exit ramp from a first road directly onto an entry ramp back onto the first road;
including an exit/entry ramp penalty in one of said node and route impedances based on said identification step; and
utilizing said node impedance and route impedance to calculate the navigation route.
-
-
9. A method for calculating a navigation route between first and second geographic locations through a roadway network of roads intersecting at nodes, comprising:
-
providing a data structure having data indicative of a roadway network of roads intersecting at intersection nodes, said data including feature data indicative of traffic characteristics for associated roads;
calculating a route impedance for a navigation route through said roadway network between first and second geographic locations based on said feature data;
determining node impedances for intersection nodes though which the navigation route travels based on said feature data, said intersection nodes representing locations along the navigation route at which roads followed by the navigation route intersect other roads;
including an exit/entry ramp penalty with one of said route and node impedances when the navigation route travels along an exit ramp from a first road directly onto an entry ramp back onto the first road; and
utilizing said node impedance and route impedance to calculate the navigation route.
-
-
10. A navigation device comprising;
-
memory for at least temporarily storing at least a portion of a data structure having data indicative of a roadway network of roads intersecting at nodes, said data structure including feature data indicative of traffic characteristics for associated roads, said memory stores feature data indicative of intersection angle information identifying an angle between roads intersecting at a node through which the route travels; and
a processor accessing said memory and calculating, from said data structure, a route through said roadway network between geographic locations based on data indicative of route impedances associated with selected roads in the roadway network, said processor estimating node impedances for intersection nodes through which the route travels, said processor estimating node impedances based on said intersection angle information, said processor utilizing said route impedance and node impedance to calculate the route.
-
-
11. A navigation device comprising:
-
memory for at least temporarily storing at least a portion of data structure having data indicative of a roadway network of roads intersecting at nodes, said data structure including feature data indicative of traffic characteristics for associated roads, said memory storing feature data indicative of cross traffic turn information identifying whether a desired route through a node crosses on-coming traffic; and
a processor accessing said memory and calculating, from said data structure, a route through said roadway network between geographic locations based on data indicative of route impedances associated with selected roads in the roadway network, said processor estimating node impedances for intersection nodes through which the route travels, said processor estimating node impedances based on said cross traffic turn information, said processor utilizing said route impedance and node impedance to calculate the route.
-
-
12. A navigation system comprising:
-
a storage unit holding a data structure having data indicative of roads in a roadway network and intersections of said roads at nodes;
a route calculation module calculating a planned route over the roadway network between source and destination locations based on the data structure held in the storage unit, said route calculation module avoiding said ramp shortcuts; and
a correction module for identifying undesirable shortcuts constituting predefined paths along said roads and through said nodes in said roadway network route that, while reducing an overall distance traveled by a planned route, are to be avoided in said planned route between said source and destination locations, said correction module identifying ramp shortcuts along an exit ramp and entrance ramp of a road, said route calculation module avoiding said undesirable shortcuts.
-
-
13. A navigation system comprising:
-
a storage unit holding a data structure having data indicative of roads in a roadway network and intersections of said roads at nodes;
a route calculation module calculating a planned route over the roadway network between source and destination locations based on the data structure held in the storage unit; and
a correction module for identifying undesirable shortcuts constituting predefined paths along said roads and through said nodes in said roadway network route that, while reducing an overall distance traveled by a planned route, are to be avoided in said planned route between said source and destination locations, said route calculation module avoiding said undesirable shortcuts, said correction module identifying neighborhood shortcuts through residential roads in said roadway network where said residential roads do not directly connect with either one of said source and destination locations, said route calculation module avoiding said neighborhood shortcuts.
-
-
14. A navigation system comprising:
-
a storage unit holding a data structure having data indicative of roads in a roadway network and intersections of said roads at nodes;
a route calculation module calculating a planned route over the roadway network between source and destination locations based on the data structure held in the storage unit; and
a correction module for identifying undesirable shortcuts constituting predefined paths along said roads and through said nodes in said roadway network route that, while reducing an overall distance traveled by a planned route, are to be avoided in said planned route between said source and destination locations, said route calculation module avoiding said undesirable shortcuts, wherein said correction module includes a neighborhood progression module identifying when said planned route travels along residential roads located remote from said source and destination locations, said route calculation module updating said route to avoid residential roads that are remote from said source and destination locations based on neighborhood information received from said neighborhood progression module.
-
-
15. A navigation system comprising:
-
a storage unit holding a data structure having data indicative of roads in a roadway network and intersections of said roads at nodes;
a route calculation module calculating a planned route over the roadway network between source and destination locations based on the data structure held in the storage unit; and
a correction module for identifying undesirable shortcuts constituting predefined paths along said roads and through said nodes in said roadway network route that, while reducing an overall distance traveled by a planned route, are to be avoided in said planned route between said source and destination, said route calculation module avoiding said undesirable shortcuts, wherein said route calculation module adds one of a distance and time penalty to potential routes that include at least one of exit/entrance ramp shortcuts and neighborhood shortcuts.
-
-
16. A computer program embodied on a computer-readable medium for estimating an impedance time through a node at an intersection between roads in a roadway network, comprising:
-
an identification source code segment identifying characteristic information for roads intersecting at a node in a roadway network, said characteristic information describing at least one feature concerning an associated road;
an estimation source code segment estimating an impedance time associated with potential delays by traffic traveling through the node based on the characteristic information for the roads intersecting at the node;
a source code segment obtaining a speed band associated with each road intersecting at the node, the speed band identifying a speed range in which traffic travels on the associated road; and
a source code segment determining a speed differential between the speed bands, the speed differential representing a relative change between speed ranges of the roads intersecting at the node, the speed differential representing at least a portion of the characteristic information.
-
-
17. A computer program embodied on a computer-readable medium for estimating an impedance time through a node at an intersection between roads a roadway network, comprising:
-
an identification source code segment identifying characteristic information for roads intersecting at a node in a roadway network, said characteristic information describing at least one feature concerning an associated road, said identification source code segment obtains intersection angle information identifying an angle between the roads intersecting at the node, said intersection angle information representing at least a portion of the characteristic information; and
an estimation source code segment estimating an impedance time associated with potential delays by traffic traveling through the node based on the characteristic information for the roads intersecting at the node.
-
-
18. A computer program embodied on a computer-readable medium for estimating an impedance time through a node at an intersection between roads in a roadway network, comprising:
-
an identification source code segment identifying characteristic information for roads intersecting at a node in a roadway network, said characteristic information describing at least one feature concerning an associated road, said identification source code segment obtains cross traffic turn information identifying whether a desired route through the node crosses oncoming traffic, said cross traffic turn information representing at least a portion of the characteristic information; and
an estimation source code segment estimating an impedance time associated with potential delays by traffic traveling through the node based on the characteristic information for the roads intersecting at the node.
-
Specification