Method and system for calculating an energy efficient route

• US 8,543,328 B2
• Filed: 01/11/2011
• Issued: 09/24/2013
• Est. Priority Date: 01/11/2011
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navteq B.V.
• Inventors: Stille, Johannes
• Primary Examiner(s): Mawari, Redhwan K
• Application Number:
  US13/004,149
• Publication Number:
  US 20120179362A1
• Time in Patent Office: 987 Days
• Field of Search: 701/123, 701/25, 701/410, 701/19, 340/988, 340/990
• US Class Current: 701/408
• 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 plurality of road segments;

determining whether slope data is available for the plurality of road segments;

calculating a first segment cost for a first road segment of the plurality of road segments in response to slope data being available for the first road segment by subtracting a bias amount from the energy consumption value for the first road segment, wherein the bias amount is equal to the first road segment'"'"'s altitude difference multiplied by an energy factor;

calculating a second segment cost for a second road segment of the plurality of road segments in response to slope data being unavailable for the second road segment, wherein the second segment cost equals the energy consumption value for the second road segment; and

using the first segment cost and the second 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 first road segment or the second road segment.

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

5. 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.

6. 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.

17. The method of claim 1, wherein the energy factor is chosen such that a segment cost for each of the plurality of segments is positive.

7. 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 a first segment cost for a first road segment and a second segment cost for a second road segment,

wherein if slope data is available for the first road segment, the first segment cost for the first road segment is equal to an energy consumption value less a bias amount, wherein the bias amount is equal to an altitude difference of the first road segment multiplied by an energy factor, and

wherein if slope data is not available for the second road segment, the second segment cost for the second road segment is based on the energy consumption value for the second road segment.

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

9. The method of claim 7, 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.

10. The method of claim 7, wherein the energy factor is chosen to maximize minimum cost per distance.

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

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

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

14. 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 first road segment, the segment cost for the first road segment is equal an energy consumption value for the first road segment less a bias amount equal to a difference of start speed squared and end speed squared multiplied by an energy factor, and otherwise, the segment cost for a second segment equals the energy consumption value for the second road segment,

wherein the energy consumption value for the first road segment includes energy needed for acceleration or gained by deceleration while traveling on the first road segment, and

wherein the routing algorithm uses the segment cost for the first road segment and the segment cost for the second road segment.

15. 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, wherein the segment costs for road segments not having associated slope data are set equal to the energy consumption value, and wherein the bias amount is equal to the road segment'"'"'s altitude difference multiplied by an energy factor.

16. The navigation system of claim 15, 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.