Method and System for Calculating an Energy Efficient Route

• US 20120179362A1
• Filed: 01/11/2011
• Published: 07/12/2012
• Est. Priority Date: 01/11/2011
• Status: Active Grant

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: Navteq North America LLC (HERE Holding Corporation)
• Inventors: Stille, Johannes
• Granted Patent: US 8,543,328 B2
• Time in Patent Office: Days
• US Class Current: 701/410
• CPC Class Codes: G01C 21/3469 Fuel consumption; Energy use; Emission aspects

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 segment cost data associated with each segment in the route. The segment cost is calculated by adjusting an energy consumption value by subtracting a bias term for each segment with known slope data. The bias term causes segment costs associated with segments having a slope that can be traveled with typical efficiency, a zero slope, and an unknown slope to be substantially the same. The bias term also causes the segment cost associated with a segment with a slope that can be traveled efficiently to be less than the segment cost associated with a segment with unknown slope, and the segment cost associated with a segment with a slope that causes inefficient travel to be greater than the segment cost associated with a segment with unknown slope.

Claims

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

obtaining an energy consumption value for a road segment;

determining whether slope data is available for the road segment;

if slope data is available for the road segment, adjusting the energy consumption value by subtracting a bias amount, wherein the bias amount is equal to the road segment'"'"'s altitude difference multiplied by an energy factor; and

using the adjusted energy consumption value as a segment cost during route calculation.

2. The method of claim 1, wherein obtaining an energy consumption value includes using a lookup table of energy consumption values.

3. The method of claim 2, wherein the data in the lookup table is collected as vehicles travel on the road segment.

4. The method of claim 1, wherein obtaining an energy consumption value includes physical modeling of the road segment.

5. The method of claim 1, wherein if slope data is not available for the road segment, further comprising using the energy consumption value as the segment cost during route calculation.

6. The method of claim 1, wherein the energy factor is a derivative of energy consumption with respect to the altitude difference at a typical speed and zero slope.

7. The method of claim 1, wherein the energy factor is e=m*g*η

_typical, where m is vehicle mass, g is the Earth'"'"'s gravity, and η

_typical is typical efficiency of an engine.

8. 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 segment costs for road segments being evaluated by the routing algorithm, wherein if slope data is available for a road segment the segment cost for the road segment is equal to an energy consumption value less a bias amount, and wherein if slope data is not available for the road segment the segment cost for the road segment is equal to the energy consumption value.

9. The method of claim 8, wherein the bias amount is equal to the road segment'"'"'s altitude difference multiplied by an energy factor.

10. The method of claim 9, wherein the energy factor is a derivative of energy consumption with respect to the altitude difference at a typical speed and zero slope.

11. The method of claim 9, wherein the energy factor is e=m*g*η

_typical, where m is vehicle mass, g is the Earth'"'"'s gravity, and η

_typical is typical efficiency of an engine.

12. The method of claim 9, wherein the energy factor is chosen to maximize minimum energy consumed per distance.

13. The method of claim 9, wherein the energy factor is chosen so that the segment cost is positive for the road segments.

14. The method of claim 8, wherein the bias amount is equal to f(h₂)−

f(h₁), where f is a monotonically increasing function, h₂ is an altitude of an end of the road segment, and h₁ is an altitude of a start of the road segment.

15. The method of claim 8, wherein the bias amount is equal to f(v₂)−

f(v₁), where v₁ and v₂ are the start and end nodes for the road segment, and f maps the nodes to real numbers.

16. The method of claim 8, wherein if slope data is not available for the road segment the segment cost for the road segment is equal to the energy consumption value plus a penalty factor.

17. The method of claim 16, wherein the penalty factor is equal to a cost associated with traveling on a road segment with a slight uphill slope.

18. 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 segment costs for road segments being evaluated by the routing algorithm, wherein if speed data is available for start and end of a road segment, the segment cost for the road segment is equal an energy consumption value for the road segment less a bias amount equal to a difference of start speed squared and end speed squared multiplied by an energy factor, wherein the energy consumption value includes energy needed for acceleration or gained by deceleration while traveling on the road segment.

19. 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 map database that includes geographic data for a geographic area that includes the first and second locations, wherein the geographic database includes slope data for some road segments that represent roads in the geographic area; 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, wherein the segment costs for road segments having associated slope data are calculated by subtracting a bias amount from an energy consumption value, and wherein the bias amount is equal to the road segment'"'"'s altitude difference multiplied by an energy factor.

20. The navigation system of claim 19, wherein the route calculation application minimizes energy consumption in combination with at least one other criterion selected from the group consisting of distance and speed.