Energy efficient routing using an impedance factor

• US 9,109,914 B2
• Filed: 08/08/2013
• Issued: 08/18/2015
• Est. Priority Date: 04/25/2011
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Arcot, Praveen J., Spelbrink, Justin M., Swingley, Finn A., Lindsay, Matthew G.
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): MOTT, ADAM R
• Application Number:
  US13/962,687
• Publication Number:
  US 20130322694A1
• Time in Patent Office: 740 Days
• Field of Search: 701/117, 701/119, 701/409, 701/411, 701/414, 701/139
• US Class Current: 1/1
• 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:

receiving probe data collected via a probe for one or more vehicles traveling along a road;

selecting a road segment with associated probe data;

dividing the road segment into sub-segments;

calculating, using a processor, an average speed for each sub-segment using the probe data;

calculating, using the processor, a speed slope for each sub-segment as a function of an average speed of the sub-segment and an average speed of at least one adjacent sub-segment;

calculating, using the processor, a sum of speed slopes by adding the speed slope values for 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 a classification of the road segment in a map database.

4. The method of claim 1, 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 configured 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. The method of claim 1, 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.

13. A method for calculating an energy efficient route, the method comprising:

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

calculating a probability value that a vehicle decelerates while traveling on each individual segment of a plurality of road segments;

selecting, from the plurality of road segments, a selected road segment with associated probe data;

receiving probe data collected via a probe for the vehicle traveling along the selected road segment;

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

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

calculating a speed slope for each of the plurality of sub-segment as a function of an average speed of the sub-segment and an average speed of at least one adjacent sub-segment; and

calculating, using a processor, an energy efficient route from the origin to the destination using a routing algorithm that evaluates the plurality of road segments,

wherein the routing algorithm uses the probability values for the plurality of road segments being evaluated by the routing algorithm.

14. The method of claim 13, further comprising:

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.

15. The method of claim 14, further comprising:

converting the sum of speed slopes to an absolute value prior to classifying the road segment.

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

17. The method of claim 13, wherein at least one of the plurality of road segments is bidirectional, and a first probability value of the probability values is assigned to a first direction of the at least one of the plurality of road segments and a second probability value of the probability values is assigned to a second direction of the at least one of the plurality of road segments.

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

a probe configured to receive probe data collected for a vehicle traveling along a route from a first location to a second location;

a geographic database containing road segment records that include data that represent roads in a geographic area that includes the route from the first location to the second location,

wherein the road segment records include an impedance factor associated with a road segment,

wherein the impedance factor represents a probability that the vehicle decelerates while traveling within 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,

wherein the processor is configured to calculate the impedance factor by dividing the road segment into a plurality of sub-segments and calculating an average speed for each of the plurality of sub-segments using the probe data,

wherein the processor is configured to calculate a speed slope for each sub-segment as a function of an average speed of the sub-segment and an average speed of at least one adjacent sub-segment.

19. The navigation system of claim 18, wherein the processor is configured to calculate a sum of speed slopes by adding the speed slope values for only those sub-segments having a negative value of speed slope, and classify the road segment based on the sum of speed slopes.