Dynamic route updating for refueling based on route deviation metrics

• US 9,880,020 B1
• Filed: 04/06/2015
• Issued: 01/30/2018
• Est. Priority Date: 07/19/2009
• Status: Active Grant

• Current Assignee: Aaron Emigh
• Original Assignee: Aaron Emigh
• Inventors: Emigh, Aaron
• Primary Examiner(s): To, Tuan C
• Application Number:
  US14/679,043
• Time in Patent Office: 1,030 Days
• 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 trip routing include determining a set of refueling stations, each of which is less than a threshold distance of deviation from a route; determining a fuel price and a deviation cost for each of the set of refueling stations, wherein the deviation cost is based on a unit distance of deviation from the route for each respective refueling station; calculating an imputed cost for each of the set of refueling stations, wherein the imputed cost is based on a combination of the fuel price and the corresponding deviation cost at each respective refueling station; selecting a first refueling station from among the set of refueling stations, wherein the first refueling station has a minimum imputed cost; updating the route to include the first refueling station; and presenting information relating to the updated route.

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;

determining a first candidate set of refueling stations accessible from the route, wherein each of the refueling stations within the first candidate set of refueling stations accessible from the route is less than a first threshold distance of deviation from the route;

determining a fuel price associated with each of the first candidate set of refueling stations;

calculating a deviation cost for each of the first candidate set of refueling stations accessible from the route, 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;

calculating an imputed cost for each of the first candidate set of refueling stations accessible from the route, wherein the imputed cost is based on a combination of the fuel price at each respective refueling station among the first candidate set of refueling stations accessible from the route and the corresponding deviation cost for each respective refueling station among the first candidate set of refueling stations accessible from the route;

selecting a first refueling station from among the first candidate set of refueling stations, 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;

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 determining a current location, and using the current location as the first point.

4. 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 is retrieved from an online source.

5. 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 is provided by a user.

6. 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 is provided by an approved vendor.

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

8. The method of claim 7, wherein the second candidate set of refueling stations is the first candidate set of refueling stations accessible from the route.

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

10. The method of claim 1, wherein the combination of the fuel price at each respective refueling station among the first candidate set of refueling stations accessible from the route and the corresponding deviation cost for each respective refueling station among the first candidate set of refueling stations accessible from the route includes adding the expected refueling cost at each respective refueling station among the first candidate set of refueling stations accessible from the route and the corresponding deviation cost for each respective refueling station among the first candidate set of refueling stations accessible from the route.

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

12. 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;

determine a first candidate set of refueling stations accessible from the route, wherein each of the refueling stations within the first candidate set of refueling stations accessible from the route is less than a first threshold distance of deviation from the route;

determine a fuel price associated with each of the first candidate set of refueling stations;

calculate a deviation cost for each of the first candidate set of refueling stations accessible from the route, 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;

calculate an imputed cost for each of the first candidate set of refueling stations accessible from the route, wherein the imputed cost is based on a combination of the fuel price at each respective refueling station among the first candidate set of refueling stations accessible from the route and the corresponding deviation cost for each respective refueling station among the first candidate set of refueling stations accessible from the route;

select a first refueling station from among the first candidate set of refueling stations, 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;

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.

13. The system of claim 12, wherein the hardware processor is further configured to determine a second candidate set of refueling stations from among the first candidate set of refueling stations accessible from the route, present information relating to each refueling station among the second candidate set of refueling stations, and receive a selection of the first refueling station from among the second candidate set of refueling stations.

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

15. The system of claim 12, wherein the combination of the fuel price at each respective refueling station among the first candidate set of refueling stations accessible from the route and the corresponding deviation cost for each respective refueling station among the first candidate set of refueling stations accessible from the route includes adding the expected refueling cost at each respective refueling station among the first candidate set of refueling stations accessible from the route and the corresponding deviation cost for each respective refueling station among the first candidate set of refueling stations accessible from the route.

16. The system of claim 12, wherein updating the route to include the first refueling station includes routing from the starting location to the first refueling station and from the first refueling station to the destination location.

17. 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;

determining a first candidate set of refueling stations accessible from the route, wherein each of the refueling stations within the first candidate set of refueling stations accessible from the route is less than a first threshold distance of deviation from the route;

determining a fuel price associated with each of the first candidate set of refueling stations;

calculating a deviation cost for each of the first candidate set of refueling stations accessible from the route, 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;

calculating an imputed cost for each of the first candidate set of refueling stations accessible from the route, wherein the imputed cost is based on a combination of the fuel price at each respective refueling station among the first candidate set of refueling stations accessible from the route and the corresponding deviation cost for each respective refueling station among the first candidate set of refueling stations accessible from the route;

selecting a first refueling station from among the first candidate set of refueling stations, 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;

updating the route to include the first refueling station; and

presenting information relating to the updated route.

18. The computer program product of claim 17, further comprising computer instructions for determining a second candidate set of refueling stations from among the first candidate set of refueling stations accessible from the route, 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.

19. The computer program product of claim 17, wherein the combination of the fuel price at each respective refueling station among the first candidate set of refueling stations accessible from the route and the corresponding deviation cost for each respective refueling station among the first candidate set of refueling stations accessible from the route includes adding the expected refueling cost at each respective refueling station among the first candidate set of refueling stations accessible from the route and the corresponding deviation cost for each respective refueling station among the first candidate set of refueling stations accessible from the route.

20. The computer program product of claim 17, wherein updating the route to include the first refueling station includes routing from the starting location to the first refueling station and from the first refueling station to the destination location.