Methods, devices and map databases for green routing

• US 10,175,058 B2
• Filed: 12/22/2008
• Issued: 01/08/2019
• Est. Priority Date: 12/22/2008
• Status: Active Grant

• Current Assignee: Tomtom Global Content B.V (TomTom NV)
• Original Assignee: Tomtom Global Content B.V (TomTom NV)
• Inventors: Wilson, Christopher Kenneth Hoover
• Primary Examiner(s): Black, Thomas G
• Assistant Examiner(s): Kong, Sze-Hon
• Application Number:
  US13/122,750
• Publication Number:
  US 20120022781A1
• Time in Patent Office: 3,669 Days
• Field of Search: 701410, 701411, 701414, 701415, 701423, 701425, 701533, 703 23, 703 25, 703410, 703414, 703424
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries
• 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

Abstract

In at least one embodiment, a method is disclosed that includes determining algorithmically a a plurality of vehicle cost values for traveling a plurality of road segments in a vehicle based at least in part on vehicle cost data derived at least in part from position derivative data obtained from at least one vehicle that traveled the road segments (S1); associating each of the plurality of road segments with at least one of the vehicle cost values (S2); and storing the determined vehicle cost values in a memory device (S3). In at least one embodiment, a method for determining a route of travel from a first location to a second location is disclosed. Other embodiments include a map database, storable on a storage medium; a device including a memory (230) storing a map database, a processor (210) and an output device (260); and a device for use in a vehicle, where the device includes a GPS receiver (250), a memory (230) and a processor (210).

Claims

1. A method for determining a route of travel from a first location to a second location for a vehicle using a navigation device installed in the vehicle and comprising a memory, a processor communicatively coupled to the memory, and a display, wherein the memory stores a map database including information about a plurality of road segments of a digital map, and wherein the method comprises:

retrieving a plurality of vehicle cost values, the retrieving including acquiring the plurality of vehicle cost values from the map database, the map database having at least one corresponding vehicle cost value associated with each road segment of the plurality of road segments, each vehicle cost value being representative of an expected energy or fuel consumption of a vehicle of a given type travelling along a corresponding road segment at a corresponding time of the day, wherein the vehicle cost values were computed based at least in part on information about trips made by one or more probe vehicles on road segments of the plurality of road segments, the information about the trips made by the one or more probe vehicles based on which the vehicle cost values were computed comprising information about average accelerations and jerks made by the probe vehicles while traveling on the road segments of the plurality of road segments;

determining, by the navigation device, a selected route of travel from the first location to the second location from among a plurality of possible routes between the first location and the second location at a specified time of day, each possible route comprising a plurality of road segments, the determining comprising;

calculating a total cost of each possible route based at least in part on data about the vehicle and the associated vehicle cost values for the specified time of day for each of the plurality of road segments in the possible route; and

identifying, as the selected route of travel, the possible route having a minimum total cost, such that the selected route of travel has a lowest total expected energy or fuel consumption of the vehicle travelling between the first location and the second location; and

outputting onto the display to a user of the navigation device the selected route of travel and vehicle operation information for the user to operate the vehicle along the selected route of travel to reduce the total expected energy or fuel consumption.

2. The method of claim 1, wherein the information about trips made by one or more probe vehicles on road segments of the plurality of road segments comprises information about elevations of the road segments of the plurality of road segments.

3. The method of claim 2, wherein the information about the elevations of the road segments of the plurality of road segments comprises average elevations of the road segments of the plurality of road segments.

4. The method of claim 2, wherein the information about the elevations of the road segments of the plurality of road segments comprises changes in elevation for the road segments of the plurality of road segments.

5. The method of claim 1, wherein the vehicle cost values were further computed based on information about road segment conditions for road segments of the plurality of road segments, the road segment conditions selected from the group consisting of:

(i) a repair condition of the road segment;

(ii) the material of the road segment; and

(iii) a frictional coefficient of the road surface of the road segment.

6. The method of claim 1, wherein the vehicle cost values were further computed based at least in part on information about the one or more probe vehicles, the information comprising at least one of:

a weight of the probe vehicle;

a propulsion system in the probe vehicle;

a type of the probe vehicle;

a grade of fuel being used in the probe vehicle;

a make of the probe vehicle; and

a drag coefficient of the probe vehicle.

7. The method of claim 1, wherein the vehicle cost data is acquired from at least one of:

(i) GNSS data about a probe vehicle;

(ii) sensors on a probe vehicle; and

(iii) an on-board diagnostic (OBD) connection of a probe vehicle.

8. The method of claim 1, wherein the identifying, as the selected route of travel, a possible route comprises identifying a possible route for which a total travel time does not exceed a fastest of the possible routes by more than a specified amount of time.

9. The method of claim 1, wherein the identifying, as the selected route of travel, a possible route comprises identifying a possible route for which a total travel distance does not exceed a shortest of the possible routes by more than a specified amount of distance.

10. The method of claim 1, wherein the determining the selected of the route of travel is based on additional data including at least one of weather data or traffic data.

13. A non-transitory computer-readable medium which stores a set of instructions which when executed performs the method of claim 1.

11. A navigation device operable in a vehicle, comprising:

a memory to store a map database, the map database including information about a plurality of road segments and at least one corresponding vehicle cost value associated with each road segment of the plurality of road segments, each vehicle cost value being representative of an expected energy or fuel consumption of a vehicle of a given type travelling along a corresponding road segment at a corresponding time of the day, wherein the vehicle cost values were computed based at least in part on information about trips made by one or more probe vehicles on road segments of the plurality of road segments, the information about the trips made by the one or more probe vehicles based on which the vehicle cost values were computed comprising information about average accelerations and jerks made by the probe vehicles while traveling on the road segments of the plurality of road segments;

a processor communicatively coupled to the memory and configured to determine a selected route of travel from a first location to a second location from among a plurality of possible routes between the first location and the second location at a specified time of day, each possible route comprising a plurality of road segments, the determining comprising;

calculating a total cost of each possible route based at least in part on data about the vehicle and the associated vehicle cost values for the specified time of day for each of the plurality of road segments in the possible route; and

identifying, as the selected route of travel, the possible route having a minimum total cost, such that the selected route of travel has a lowest total expected energy or fuel consumption of the vehicle travelling between the first location and the second location; and

a display controlled by the processor to output the selected route of travel and vehicle operation information for a user of the navigation device to operate the vehicle along the selected route of travel to reduce the total expected energy or fuel consumption.

12. The device of claim 11, wherein the determining the selected route of travel is based on additional data including at least one of weather data or traffic data.