Fuel cost optimized routing

• US 9,002,632 B1
• Filed: 07/19/2010
• Issued: 04/07/2015
• Est. Priority Date: 07/19/2009
• Status: Expired due to Fees

• Current Assignee: Aaron T. Emigh
• Original Assignee: Aaron T. Emigh
• Inventors: Emigh, Aaron T.
• Primary Examiner(s): To, Tuan C.
• Application Number:
  US12/839,388
• Time in Patent Office: 1,723 Days
• Field of Search: 701/401, 701/411, 340/995.19
• US Class Current: 701/411
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• 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/36 Input/output arrangements for on-board computers
• CPC Class Codes: G01C 21/3697 Output of additional, non-guidance related information, e.g. low fuel level G01C21/3679 takes precedence
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0631 Item recommendations

Abstract

In some embodiments, techniques for routing a trip include determining a route that includes a starting location and a destination location, receiving information relating to an expected possible range of travel from a first point in the route, determining at least one refueling station accessible from the route within the expected possible range, determining at least one fuel price associated with the at least one refueling stations within the expected possible range, selecting a first refueling station, based at least in part on a first fuel price associated with the first refueling station, wherein the first fuel price is less than a second fuel price associated with a second refueling station, and updating the route to include the first refueling station.

Claims

1. A method for routing a trip, comprising:

executing instructions on a hardware processor to determine a route, wherein the route includes a starting location and a destination location;

receiving information relating to an expected possible vehicular range of travel from a first point in the route;

determining a first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point, wherein each of the refueling stations within the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point is less than a first threshold distance of deviation from the route, and wherein a projected gas tank level at each respective potential refueling at each of the refueling stations within the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point is at most a refueling threshold gas tank level;

determining a fuel price associated with each of the first candidate set of refueling stations within the expected possible vehicular range along the route from the first point;

calculating a deviation cost for each of the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point, wherein the deviation cost is based on a unit distance of deviation from the route for each respective refueling station among the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point;

calculating an imputed cost for each of the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point, wherein the imputed cost is based on a combination of an expected refueling cost at each respective refueling station among the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point and a corresponding deviation cost for each respective refueling station among the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point;

selecting a first refueling station from among the first candidate set of refueling stations within the expected possible range along the route from the first point, wherein the first refueling station has a minimum imputed cost of any refueling station among the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point;

executing instructions on the hardware processor to update the route to include the first refueling station; and

presenting information relating to the updated route.

2. The method of claim 1, performed at a vehicular navigation system.

3. The method of claim 1, further comprising calculating the expected possible vehicular range of travel from the first point in the route.

4. The method of claim 3, wherein the information relating to the expected possible vehicular range of travel from the first point in the route includes a fuel level of a vehicle.

5. The method of claim 3, wherein the information relating to the expected possible vehicular range of travel from the first point in the route includes information relating to a fuel efficiency of a vehicle.

6. The method of claim 5, wherein calculating the expected possible vehicular range of travel from the first point in the route includes multiplying the fuel efficiency of the vehicle by an efficiency factor relating to a segment of the route.

7. The method of claim 1, wherein the first point is the starting location.

8. The method of claim 1, further comprising determining a current location, and using the current location as the first point.

9. The method of claim 1, further comprising detecting a current fuel level associated with a vehicle, and using the current fuel level associated with the vehicle as at least part of the information relating to the expected possible vehicular range of travel from the first point in the route.

10. The method of claim 1, wherein the expected possible vehicular range of travel from the first point in the route relates to a threshold amount of fuel, wherein the expected possible range of travel from the first point in the route corresponds to a furthest range of travel such that an expected level of fuel at the expected possible range of travel from the first point in the route is at least the threshold.

11. The method of claim 1, further comprising determining that the destination location is not within the expected possible vehicular range along the route from the first point.

12. The method of claim 1, wherein a fuel price associated with at least one of the refueling stations among the first candidate set of refueling stations within the expected possible vehicular range along the route from the first point is retrieved from an online source.

13. The method of claim 1, wherein a fuel price associated with at least one of the refueling stations among the first candidate set of refueling stations within the expected possible vehicular range along the route from the first point is provided by a user.

14. The method of claim 1, wherein a fuel price associated with at least one of the refueling stations among the first candidate set of refueling stations within the expected possible vehicular range along the route from the first point is provided by an approved vendor.

15. The method of claim 1, wherein updating the route to include the first refueling station includes routing from the first point to the first refueling station and from the first refueling station to the destination location.

16. The method of claim 1, further comprising determining a second candidate set of refueling stations from among the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point, presenting information relating to each refueling station among the second candidate set of refueling stations, and receiving a selection of the first refueling station from among the second candidate set of refueling stations.

17. The method of claim 16, wherein the information relating to each refueling station among the second candidate set of refueling stations includes a brand, pricing, and a deviation distance.

18. The method of claim 1, wherein the combination of an expected refueling cost at each respective refueling station among the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point and a corresponding deviation cost for each respective refueling station among the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point includes adding the expected refueling cost at each respective refueling station among the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point and the corresponding deviation cost for each respective refueling station among the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point.

19. A system for routing a trip, comprising:

a processor configured to;

determine a route, wherein the route includes a starting location and a destination location;

receive information relating to an expected possible vehicular range of travel from a first point in the route;

determine a first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point, wherein each of the refueling stations within the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point is less than a first threshold distance of deviation from the route, and wherein a projected gas tank level at each respective potential refueling at each of the refueling stations within the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point is at most a refueling threshold gas tank level;

determine a fuel price associated with each of the first candidate set of refueling stations within the expected possible vehicular range along the route from the first point;

calculate a deviation cost for each of the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point wherein the deviation cost is based on a unit distance of deviation from the route for each respective refueling station among the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point;

calculate an imputed cost for each of the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point, wherein the imputed cost is based on a combination of an expected refueling cost at each respective refueling station among the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point and a corresponding deviation cost for each respective refueling station among the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point;

select a first refueling station from among the first candidate set of refueling stations within the expected possible range along the route from the first point, wherein the first refueling station has a minimum imputed cost of any refueling station among the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point;

update the route to include the first refueling station; and

present information relating to the updated route; and

a memory coupled with the processor, wherein the memory provides instructions to the processor.

20. A computer program product for routing a trip, the computer program product being embodied in a non-transitory computer readable medium and comprising computer instructions for:

determining a route, wherein the route includes a starting location and a destination location;

receiving information relating to an expected possible vehicular range of travel from a first point in the route;

determining a first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point, wherein each of the refueling stations within the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point is less than a first threshold distance of deviation from the route, and wherein a projected gas tank level at each respective potential refueling at each of the refueling stations within the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point is at most a refueling threshold gas tank level;

determining a fuel price associated with each of the first candidate set of refueling stations within the expected possible vehicular range along the route from the first point;

calculating a deviation cost for each of the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point, wherein the deviation cost is based on a unit distance of deviation from the route for each respective refueling station among the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point;

calculating an imputed cost for each of the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point, wherein the imputed cost is based on a combination of an expected refueling cost at each respective refueling station among the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point and a corresponding deviation cost for each respective refueling station among the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point;

selecting a first refueling station from among the first candidate set of refueling stations within the expected possible range along the route from the first point, wherein the first refueling station has a minimum imputed cost of any refueling station among the first candidate set of refueling stations accessible from the route within the expected possible vehicular range along the route from the first point;

updating the route to include the first refueling station; and

presenting information relating to the updated route.