Method and system for calculating least-cost routes based on historical fuel efficiency, street mapping and location based services

• US 7,778,769 B2
• Filed: 11/27/2006
• Issued: 08/17/2010
• Est. Priority Date: 11/27/2006
• Status: Active Grant

• Current Assignee: Slingshot IOT LLC
• Original Assignee: International Business Machines Corporation
• Inventors: Martine, Michael Jack, McConnell, Kevin C., Boss, Gregory Jensen, Hamilton, Rick Allen II, Miller, John Williams
• Primary Examiner(s): Camby; Richard M.
• Application Number:
  US11/563,418
• Publication Number:
  US 20080125958A1
• Time in Patent Office: 1,359 Days
• Field of Search: 701/123, 701 29- 36, 701/213, 701200-209
• US Class Current: 701/123
• CPC Class Codes: G01C 21/3469 Fuel consumption; Energy use; Emission aspects
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

This disclosure outlines a method, which enables a vehicle driver to achieve increased fuel efficiency by implementing least-cost route planning based on terrain data and derived from advanced mapping, logging and location based services. Actual fuel efficiency is recorded and correlated by vehicle conditions, time of day and date, and then referenced to achieve the most accurate least-cost route plan for the intended destination.

Claims

1. A method for calculating least-cost travel routes based on fuel efficiency and current traveling conditions comprising the steps of:

receiving information about a proposed trip;

retrieving historical trip data about previous trips having the same or similar characteristics to the proposed trip;

prioritizing the retrieved historical data according to historical trips that more closely matched the information of the proposed trip;

calculating an estimated fuel efficiency for a proposed trip based on current trip information and information from a historical trip; and

conveying this estimated fuel efficiency to a driver.

2. The method for calculating least-cost travel routes as described in claim 1 further comprising before said retrieving historical trip data step, the step of generating a database of historical data about a plurality of trips.

3. The method for calculating least-cost travel routes as described in claim 2 wherein said database generating step further comprises the steps of:

recording trip information for a particular trip at a particular vehicle used in the trip, this information including start and end locations of the trip, distance of the trip, vehicle make and model, time of day and date of the trip;

calculating performance information for the particular trip, the calculated information including the actual miles per gallon of the vehicle during the particular trip; and

storing recorded and calculated information about the particular trip in a database location, the information for this particular trip forming one entry in the database.

4. The method for calculating least-cost travel routes as described in claim 3 wherein in said trip recording, the distance of the trip is calculated from start and end times for the particular trip.

5. The method for calculating least-cost travel routes as described in claim 1 wherein said prioritizing step further comprises the steps of:

identifying start and end locations for a proposed trip;

searching a database of historical trip entries for entries having the same or similar start and end locations as the proposed trip;

storing all historical trip entries having the same or similar start and end locations as the proposed trip;

identifying from the stored database entries having the same or similar start and end locations as the proposed trip, entries with the same or similar vehicle type as a vehicle to be used in the proposed trip;

storing the identified entries with the same or similar vehicle type as a vehicle to be used in the proposed trip; and

identifying from the stored identified entries with the same or similar vehicle type as a vehicle to be used in the proposed trip, entries with the same or similar travel times.

6. The method for calculating least-cost travel routes as described in claim 1 wherein said prioritizing step further comprises the steps of:

retrieving trips from the database that have the same starting location and destination location of the proposed trip;

determining two or more alternate trip routes between the trip starting location and the trip destination location from the retrieved data; and

sorting retrieved historical trip data by alternate trip routes.

7. The method for calculating least-cost travel routes as described in claim 6 wherein said sorting step further comprises the steps of:

examining a historical trip retrieved from the database;

matching the retrieved with one of the alternate trip routes;

storing that record according to the trip route it matches; and

determining whether there are any more retrieved trips to examine.

8. The method for calculating least-cost travel routes as described in claim 7 wherein said calculating an estimate fuel efficiency step further comprises the steps of:

retrieving a record sorted and stored according to a trip route;

inputting information from the retrieved record and current trip information into an optimization algorithm and performing fuel efficiency and optimization for the proposed trip based on the retrieved record; and

storing the result of the optimization algorithm.

9. The method for calculating least-cost travel routes as described in claim 8 further comprising after said storing step, the steps of,

determining whether there is another record from a set of sorted and stored records;

and

displaying optimization results for records in the set of sorted and stored records when there are no more records in the set.

10. The method for calculating least-cost travel routes as described in claim 8 further comprising after said storing step, the steps of:

determining whether there is another record from a set of sorted and stored records;

retrieving a next a sorted and stored record from the set, when there is at least one record still in the set;

inputting information from the retrieved record and current trip information into an optimization algorithm and performing fuel efficiency and optimization for the proposed trip based on the retrieved record; and

storing the result of the optimization algorithm.

11. A computer program product in a computer readable storage medium for calculating least-cost travel routes based on fuel efficiency and current traveling conditions comprising:

instructions for receiving information about a proposed trip;

instructions for retrieving historical trip data about previous trips having the same or similar characteristics to the proposed trip;

instructions for prioritizing the retrieved historical data according to historical trips that more closely matched the information of the proposed trip;

instructions for calculating an estimated fuel efficiency for a proposed trip based on current trip information and information from a historical trip; and

instructions for conveying this estimated fuel efficiency to a driver.

12. The computer program product for calculating least-cost travel routes as described in claim 11 further comprising before said retrieving historical trip data instructions, instructions for generating a database of historical data about a plurality of trips.

13. The computer program product for calculating least-cost travel routes as described in claim 12 wherein said database generating instructions further comprise instructions for:

recording trip information for a particular trip at a particular vehicle used in the trip, this information including start and end locations of the trip, distance of the trip, vehicle make and model, time of day and date of the trip;

calculating performance information for the particular trip, the calculated information including the actual miles per gallon of the vehicle during the particular trip; and

storing recorded and calculated information about the particular trip in a database location, the information for this particular trip forming one entry in the database.

14. The computer program product for calculating least-cost travel routes as described in claim 11 wherein said prioritizing instructions further comprise instructions for:

identifying start and end locations for a proposed trip;

searching a database of historical trip entries for entries having the same or similar start and end locations as the proposed trip;

storing all historical trip entries having the same or similar start and end locations as the proposed trip;

identifying from the stored database entries having the same or similar start and end locations as the proposed trip, entries with the same or similar vehicle type as a vehicle to be used in the proposed trip;

storing the identified entries with the same or similar vehicle type as a vehicle to be used in the proposed trip; and

identifying from the stored identified entries with the same or similar vehicle type as a vehicle to be used in the proposed trip, entries with the same or similar travel times.

15. The computer program product for calculating least-cost travel routes as described in claim 11 wherein said prioritizing step further comprising instructions for:

retrieving trips from the database that have the same starting location and destination location of the proposed trip;

determining two or more alternate trip routes between the trip starting location and the trip destination location from the retrieved data; and

sorting retrieved historical trip data by alternate trip routes.

16. The computer program product for calculating least-cost travel routes as described in claim 15 wherein said sorting step further comprising instructions for:

examining a historical trip retrieved from the database;

matching the retrieved with one of the alternate trip routes;

storing that record according to the trip route it matches; and

determining whether there are any more retrieved trips to examine.

17. The computer program product for calculating least-cost travel routes as described in claim 16 wherein said calculating an estimate fuel efficiency step further comprising instructions for:

retrieving a record sorted and stored according to a trip route;

inputting information from the retrieved record and current trip information into an optimization algorithm and performing fuel efficiency and optimization for the proposed trip based on the retrieved record; and

storing the result of the optimization algorithm.

18. A system for calculating least-cost travel routes based on fuel efficiency and current traveling conditions comprising:

a database containing historical data about trips between various destinations;

a remote module positioned within a motor vehicle capable of recording and transmitting to the database information about a current trip;

an optimization algorithm for calculating a fuel efficiency trip information; and

a display device for displaying fuel efficiency optimization information.

19. The system for calculating least-cost travel routes based on fuel efficiency and current travel conditions as described in claim 18 further comprising a global positioning module.

20. The system for calculating least-cost travel routes based on fuel efficiency and current travel conditions as described in claim 18 further comprising a global communication network, said network providing a means for system components.