Energy Efficient Routing Using An Impedance Factor

• US 20120271542A1
• Filed: 04/25/2011
• Published: 10/25/2012
• Est. Priority Date: 04/25/2011
• Status: Active Grant

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: Navteq North America LLC (HERE Holding Corporation)
• Inventors: Swingley, Finn A., Lindsay, Matthew G., Spelbrink, Justin M., Arcot, Praveen J.
• Granted Patent: US 8,554,473 B2
• Time in Patent Office: Days
• US Class Current: 701/411
• CPC Class Codes: G01C 21/3469 Fuel consumption; Energy use; Emission aspects
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G06V 20/582 of traffic signs

Abstract

A method and system for calculating an energy efficient route is disclosed. A route calculation application calculates one or more routes from an origin to a destination. For each of the routes, the route calculation application uses impedance factor data associated with each segment in the route. The impedance factor is calculated using probe data when the probe data is available for a road segment. When probe data is unavailable, the impedance factor is calculated using machine learning techniques that analyze the results of the impedance factor classifications for road segments having probe data.

Claims

1. A computer-implemented method for calculating road segment cost for energy efficient routing, comprising:

selecting a road segment with associated probe data;

dividing the road segment into a plurality of sub-segments;

calculating an average speed for each of the sub-segments using the probe data;

calculating a speed slope for each sub-segment, wherein the speed slope equals the average speed of the sub-segment less the average speed of an adjacent sub-segment divided by the average speed of the sub-segment (speed slope=(avg. speed s_i−

avg. speed s_i+1)/avg. speed s_i);

calculating a sum of speed slopes by adding the speed slope values for only those sub-segments having a negative value of speed slope; and

classifying the road segment based on the sum of speed slopes.

2. The method of claim 1, further comprising converting the sum of speed slopes to an absolute value prior to classifying the road segment.

3. The method of claim 1, further comprising storing data representing the classification of the road segment in a map database.

4. The method of claim 3, wherein the classification of the road segment stored in the map database is used as a segment cost during route calculation.

5. The method of claim 3, wherein the classification of the road segment stored in the map database is used to identify errors in the map database.

6. The method of claim 1, wherein the road segments are classified with an impedance factor of VERY HIGH, HIGH, MEDIUM, LOW, or VERY LOW.

7. The method of claim 6, wherein a road segment classified as VERY HIGH has a sum of speed slopes value greater than a road segment classified as HIGH.

8. The method of claim 6, wherein a road segment classified as HIGH has a sum of speed slopes value greater than a road segment classified as MEDIUM.

9. The method of claim 6, wherein a road segment classified as MEDIUM has a sum of speed slopes value greater than a road segment classified as LOW.

10. The method of claim 6, wherein a road segment classified as LOW has a sum of speed slopes value greater than a road segment classified as VERY LOW.

11. The method of claim 1, wherein the road segments are classified with more than one impedance factor.

12. A computer-implemented method for calculating road segment cost for energy efficient routing, comprising:

selecting a sample of road segments, wherein the road segments in the sample have been classified with one of a plurality of impedance factors, wherein an impedance factor represents a probability that a vehicle needs to decelerate while traveling on the road segment;

calculating a probability that a road segment in the sample has been classified with a particular impedance factor;

calculating a conditional probability of each impedance factor for a plurality of map database attributes;

calculating entropy of the plurality of impedance factors;

calculating conditional entropy for each of the plurality of map database attributes;

calculating the information gain using the entropy and the conditional entropy calculations;

creating a decision tree based on the information gain calculation; and

classifying the road segment based on the decision tree.

13. The method of claim 12, further comprising dividing the sample of road segments by functional class of the road segments.

14. The method of claim 12, wherein the map data attributes include speed category, lane category, controlled access, ramp, and cross streets.

15. The method of claim 12, further comprising storing data representing the classification of the road segment in a map database.

16. The method of claim 15, wherein the classification of the road segment stored in the map database is used as a segment cost during route calculation.

17. The method of claim 15, wherein the classification of the road segment stored in the map database is used to identify errors in the map database.

18. The method of claim 12, wherein the road segments are classified with an impedance factor of VERY HIGH, HIGH, MEDIUM, LOW, or VERY LOW.

19. A computer-implemented method for calculating an energy efficient route, comprising:

obtaining an origin and a destination associated with a road network; and

calculating an energy efficient route from the origin to the destination using a routing algorithm, wherein the routing algorithm uses impedance factors for road segments being evaluated by the routing algorithm, wherein the impedance factors represent a probability that a vehicle needs to decelerate while traveling on the road segment.

20. A navigation system that calculates an energy efficient route, comprising:

a user interface that allows a user to request route information from a first location to a second location;

a geographic database containing road segment records that include data that represent roads in the geographic area that includes the first and second locations, wherein the road segment records include an impedance factor associated with a road segment, wherein the impedance factor represents a probability that a vehicle needs to decelerate while traveling on the road segment; and

a processor that executes a route calculation application that calculates a route that minimizes energy consumption when traveling from the first location to the second location, wherein the route is calculated using segment costs, and wherein the segment costs are based on the impedance factor.