NAVIGATION SYSTEM WITH CONSTRAINED RESOURCE ROUTE PLANNING OPTIMIZER AND METHOD OF OPERATION THEREOF

• US 20120173135A1
• Filed: 12/29/2011
• Published: 07/05/2012
• Est. Priority Date: 12/30/2010
• Status: Active Grant

• Current Assignee: TeleNav Incorporated
• Original Assignee: TeleNav Incorporated
• Inventors: Gutman, Ronald David
• Granted Patent: US 8,626,436 B2
• Time in Patent Office: Days
• US Class Current: 701/408
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G01C 21/3469 Fuel consumption; Energy use; Emission aspects

Abstract

A method of operation of a navigation system includes: setting a predetermined arrival level for arriving at a replenishment location; calculating an estimated arrival level for arriving at the replenishment location; generating target location based on the estimated arrival level meeting or exceeding the predetermined arrival level; and generating a travel route to a destination based on selecting the replenishment location from the target location for displaying on a device.

Claims

1. A method of operation of a navigation system comprising:

setting a predetermined arrival level for arriving at a replenishment location;

calculating an estimated arrival level for arriving at the replenishment location;

generating a target location based on the estimated arrival level meeting or exceeding the predetermined arrival level; and

generating a travel route to a destination based on selecting the replenishment location from the target location for displaying on a device.

2. The method as claimed in claim 1 further comprising:

calculating a predetermined distance for reaching the replenishment location;

calculating a section distance for reaching the replenishment location; and

wherein generating the target location includes selecting the replenishment location based on the section distance meeting or exceeding the predetermined distance for at least reaching the replenishment location.

3. The method as claimed in claim 1 further comprising:

calculating a current location estimated level at the replenishment location;

calculating an estimated consumption level for traversing one or more travel sections; and

wherein generating the target location includes selecting the replenishment location based on the current location estimated level meeting or exceeding the estimated consumption level.

4. The method as claimed in claim 1 further comprising:

calculating an allotted alternate transportation travel time for traversing an alternate transportation route to reach the replenishment location;

calculating an estimated alternate transportation time for traversing the alternate transportation route to reach the replenishment location; and

wherein generating the target location includes selecting the replenishment location based on the allotted alternate transportation travel time meeting or exceeding the estimated alternate transportation time.

5. The method as claimed in claim 1 further comprising:

calculating an estimated sectional travel time for traversing one or more travel sections; and

wherein generating the target location includes;

comparing the estimated sectional travel time for traversing each of the travel sections; and

selecting the replenishment location with the shortest of the estimated sectional travel time for traversing each of the travel sections.

6. The method as claimed in claim 1 further comprising:

calculating an estimated sectional financial cost for traversing one or more travel sections; and

wherein generating the target location includes;

comparing the estimated sectional financial cost for traversing each of the travel sections; and

selecting the replenishment location with the lowest of the estimated sectional financial cost for traversing each of the travel sections.

7. The method as claimed in claim 1 wherein generating the travel route includes generating a reverse travel route from the destination to a start location based on selecting the replenishment location from the target location.

8. The method as claimed in claim 1 wherein generating the travel route includes generating a reverse travel route from the destination to a start location based on selecting an intermediate stop from the target location.

9. The method as claimed in claim 1 wherein generating the travel route to the destination based on the target location includes:

identifying the destination from the target location; and

generating the travel route through the replenishment location, an intermediate stop, or a combination thereof to the destination.

10. The method as claimed in claim 1 wherein generating the travel route to the destination based on the target location includes:

identifying the replenishment location from the target location; and

generating the travel route to the replenishment location.

11. The method as claimed in claim 1 wherein generating the travel route to the destination based on the target location includes:

identifying an intermediate stop from the target location; and

generating the travel route to the intermediate stop.

12. A method of operation of a navigation system comprising:

setting a predetermined arrival level for arriving at a replenishment location;

calculating an estimated arrival level for arriving at the replenishment location;

generating a target location based on the estimated arrival level meeting or exceeding the predetermined arrival level;

identifying the replenishment location from the target location; and

generating a travel route through the replenishment location to a destination for displaying on a device.

13. The method as claimed in claim 12 further comprising generating a reverse travel route (24) from the destination through the replenishment location for reaching a start location.

14. The method as claimed in claim 12 wherein:

setting the predetermined arrival level includes setting the predetermined arrival level for arriving at the destination;

calculating the estimated arrival level includes calculating the estimated arrival level for arriving at the destination; and

generating the target location includes selecting the destination based on the estimated arrival level meeting or exceeding the predetermined arrival level.

15. The method as claimed in claim 12 wherein:

setting the predetermined arrival level includes setting the predetermined arrival level for arriving at an intermediate stop;

calculating the estimated arrival level includes calculating the estimated arrival level for arriving at the intermediate stop; and

generating the target location includes selecting the intermediate stop based on the estimated arrival level meeting or exceeding the predetermined arrival level.

16. The method as claimed in claim 12 further comprising:

calculating a current location estimated level at the destination;

calculating an estimated consumption level for traversing a travel section; and

wherein generating the target location includes selecting the destination based on the current location estimated level meeting or exceeding the estimated consumption level.

17. The method as claimed in claim 12 further comprising:

calculating a current location estimated level at an intermediate stop;

calculating an estimated consumption level for traversing a travel section; and

wherein generating the target location includes selecting the intermediate stop based on the current location estimated level meeting or exceeding the estimated consumption level.

18. The method as claimed in claim 12 further comprising:

calculating a predetermined distance for reaching the destination;

calculating a section distance for reaching the destination; and

wherein generating the target location includes selecting the destination based on the section distance meeting or exceeding the predetermined distance.

19. The method as claimed in claim 12 further comprising:

calculating a predetermined distance for reaching an intermediate stop;

calculating a section distance for reaching the intermediate stop; and

wherein generating the target location includes selecting the intermediate stop based on the section distance meeting or exceeding the predetermined distance.

20. The method as claimed in claim 12 further comprising:

calculating an allotted alternate transportation travel time for traversing an alternate transportation route to reach the destination;

calculating an estimated alternate transportation time for traversing the alternate transportation route to reach the destination; and

wherein generating the target location includes selecting the destination based on the allotted alternate transportation travel time meeting or exceeding the estimated alternate transportation time.

21. The method as claimed in claim 12 further comprising:

calculating an allotted alternate transportation travel time for traversing an alternate transportation route to reach an intermediate stop;

calculating an estimated alternate transportation time for traversing the alternate transportation route to reach the intermediate stop; and

wherein generating the target location includes selecting the intermediate stop based on the allotted alternate transportation travel time meeting or exceeding the estimated alternate transportation time.

22. The method as claimed in claim 12 further comprising:

calculating an estimated sectional travel time for traversing one or more travel sections; and

wherein generating the target location includes;

comparing the estimated sectional travel time for traversing each of the travel sections; and

selecting the destination with the shortest of the estimated sectional travel time for traversing each of the travel sections.

23. The method as claimed in claim 12 further comprising:

calculating an estimated sectional travel time for traversing one or more travel sections; and

wherein generating the target location includes;

comparing the estimated sectional travel time for traversing each of the travel sections; and

selecting an intermediate stop with the shortest of the estimated sectional travel time for traversing each of the travel sections.

24. The method as claimed in claim 12 further comprising:

calculating an estimated sectional financial cost for traversing one or more travel sections; and

wherein generating the target location includes;

comparing the estimated sectional financial cost for traversing each of the travel sections; and

selecting the destination with the lowest of the estimated sectional financial cost for traversing each of the travel sections.

25. The method as claimed in claim 12 further comprising:

calculating an estimated sectional financial cost for traversing one or more travel sections; and

wherein generating the target location includes;

comparing the estimated sectional financial cost for traversing each of the travel sections; and

selecting an intermediate stop with the lowest of the estimated sectional financial cost for traversing each of the travel sections.

26. A navigation system comprising:

a predetermined level module for setting a predetermined arrival level for arriving at a replenishment location;

a calculator pre-computation submodule, coupled to the predetermined level module, for calculating an estimated arrival level for arriving at the replenishment location;

a return pre-computation submodule, coupled to the predetermined level module, for generating a target location based on the estimated arrival level meeting or exceeding the predetermined arrival level; and

a route planning module, coupled to the return pre-computation submodule, for generating a travel route to a destination based on selecting the replenishment location from the target location for displaying on a device.

27. The system as claimed in claim 26 further comprising:

a predetermined distance calculator module, coupled to the predetermined level module, for calculating a predetermined distance for reaching the replenishment location;

a distance pruning submodule, coupled to the predetermined distance calculator module, for calculating a section distance for reaching the replenishment location; and

an aggregator pre-computation submodule, coupled to the distance pruning submodule, for selecting the replenishment location based on the section distance meeting or exceeding the predetermined distance for at least reaching the replenishment location.

28. The system as claimed in claim 26 wherein:

the calculator pre-computation submodule is for calculating a current location estimated level at the replenishment location; and

further comprising;

a pre-computation module, coupled to the predetermined level module, for calculating an estimated consumption level for traversing a travel section; and

an aggregator pre-computation submodule, coupled to the predetermined level module, for selecting the replenishment location based on the current location estimated level meeting or exceeding the estimated consumption level.

29. The system as claimed in claim 26 further comprising:

a safe charge pre-computation submodule, coupled to the predetermined level module, for calculating an allotted alternate transportation travel time for traversing an alternate transportation route to reach the replenishment location;

a pre-computation module, coupled to the predetermined level module, for calculating an estimated alternate transportation time for traversing the alternate transportation route to reach the replenishment location; and

an aggregator pre-computation submodule, coupled to the predetermined level module, for selecting the replenishment location based on the allotted alternate transportation travel time meeting or exceeding the estimated alternate transportation time.

30. The system as claimed in claim 26 wherein:

the calculator pre-computation submodule is for calculating an estimated sectional travel time for traversing one or more travel sections; and

further comprising;

a cost pre-computation submodule, coupled to the predetermined level module, for comparing the estimated sectional travel time for traversing each of the travel sections; and

an aggregator pre-computation submodule, coupled to the predetermined level module, for selecting the replenishment location with the shortest of the estimated sectional travel time for traversing each of the travel sections.

31. The system as claimed in claim 26 wherein:

the calculator pre-computation submodule is for calculating an estimated sectional financial cost for traversing one or more travel sections; and

further comprising;

a cost pre-computation submodule, coupled to the predetermined level module, for comparing the estimated sectional financial cost for traversing each of the travel sections; and

an aggregator pre-computation submodule, coupled to the predetermined level module, for selecting the replenishment location with the lowest of the estimated sectional financial cost for traversing each of the travel sections.

32. The system as claimed in claim 26 wherein the route planning module is for generating a reverse travel route from the destination to a start location based on selecting the replenishment location from the target location.

33. The system as claimed in claim 26 wherein the route planning module is for generating a reverse travel route from the destination to a start location based on selecting an intermediate stop from the target location.

34. The system as claimed in claim 26 wherein the route planning module includes:

a destination uni-directional submodule for identifying the destination from the target location; and

a constructor uni-directional submodule for generating the travel route through the replenishment location, an intermediate stop, or a combination thereof to the destination.

35. The system as claimed in claim 26 wherein the route planning module includes:

an identifier uni-directional submodule for identifying the replenishment location from the target location; and

a constructor uni-directional submodule for generating the travel route to the replenishment location.

36. The system as claimed in claim 26 wherein the route planning module includes:

a destination uni-directional submodule for identifying an intermediate stop from the target location; and

a constructor uni-directional submodule for generating the travel route to the intermediate stop.

37. The system as claimed in claim 26 further comprising:

a destination uni-directional submodule, coupled to the predetermined level module, for identifying the replenishment location from the target location; and

wherein;

the route planning module is for generating the travel route through the replenishment location to the destination for displaying on the device.

38. The system as claimed in claim 37 wherein the route planning module is for generating a reverse travel route (24) from the destination through the replenishment location for reaching a start location.

39. The system as claimed in claim 37 wherein the return pre-computation submodule is for selecting the destination based on the estimated arrival level meeting or exceeding the predetermined arrival level.

40. The system as claimed in claim 37 wherein the return pre-computation submodule is for selecting an intermediate stop based on the estimated arrival level meeting or exceeding the predetermined arrival level.

41. The system as claimed in claim 37 further comprising:

a pre-computation module, coupled to the predetermined level module, for calculating a current location estimated level at the destination;

wherein;

the calculator pre-computation submodule is for calculating an estimated consumption level for traversing a travel section; and

the pre-computation module is for selecting the destination based on the current location estimated level meeting or exceeding the estimated consumption level.

42. The system as claimed in claim 37 further comprising:

a pre-computation module, coupled to the predetermined level module, for calculating a current location estimated level at an intermediate stop;

wherein;

the calculator pre-computation submodule is for calculating an estimated consumption level for traversing a travel section; and

the pre-computation module is for selecting the intermediate stop based on the current location estimated level meeting or exceeding the estimated consumption level.

43. The system as claimed in claim 37 further comprising:

a predetermined distance calculator module, coupled to the predetermined level module, for calculating a predetermined distance for reaching the destination;

a distance pruning submodule, coupled to the predetermined distance calculator module, for calculating a section distance for reaching the destination; and

an aggregator pre-computation submodule, coupled to the predetermined distance calculator module, for selecting the destination based on the section distance meeting or exceeding the predetermined distance.

44. The system as claimed in claim 37 further comprising:

a predetermined distance calculator module, coupled to the predetermined level module, for calculating a predetermined distance for reaching an intermediate stop;

a distance pruning submodule, coupled to the predetermined distance calculator module, for calculating a section distance for reaching the intermediate stop; and

an aggregator pre-computation submodule, coupled to the predetermined distance calculator module, for selecting the intermediate stop based on the section distance meeting or exceeding the predetermined distance.

45. The system as claimed in claim 37 further comprising:

a safe charge pre-computation submodule, coupled to the predetermined level module, for calculating an allotted alternate transportation travel time for traversing an alternate transportation route to reach the destination;

a pre-computation module, coupled to the predetermined level module, for calculating an estimated alternate transportation time for traversing the alternate transportation route to reach the destination; and

an aggregator pre-computation submodule, coupled to the predetermined level module, for selecting the destination based on the allotted alternate transportation travel time meeting or exceeding the estimated alternate transportation time.

46. The system as claimed in claim 37 further comprising:

a safe charge pre-computation submodule, coupled to the predetermined level module, for calculating an allotted alternate transportation travel time for traversing an alternate transportation route to reach an intermediate stop;

a pre-computation module, coupled to the predetermined level module, for calculating an estimated alternate transportation time for traversing the alternate transportation route to reach the intermediate stop; and

an aggregator pre-computation submodule, coupled to the predetermined level module, for selecting the intermediate stop based on the allotted alternate transportation travel time meeting or exceeding the estimated alternate transportation time.

47. The system as claimed in claim 37 wherein:

the calculator pre-computation submodule is for calculating an estimated sectional travel time for traversing one or more travel sections; and

further comprising;

a cost pre-computation submodule, coupled to the predetermined level module, for comparing the estimated sectional travel time for traversing each of the travel sections; and

an aggregator pre-computation submodule, coupled to the predetermined level module, for selecting the destination with the shortest of the estimated sectional travel time for traversing each of the travel sections.

48. The system as claimed in claim 37 wherein:

the calculator pre-computation submodule is for calculating an estimated sectional travel time for traversing one or more travel sections; and

further comprising;

a cost pre-computation submodule, coupled to the predetermined level module, for comparing the estimated sectional travel time for traversing each of the travel sections; and

an aggregator pre-computation submodule, coupled to the predetermined level module, for selecting an intermediate stop with the shortest of the estimated sectional travel time for traversing each of the travel sections.

49. The system as claimed in claim 37 wherein:

the calculator pre-computation submodule is for calculating an estimated sectional financial cost for traversing one or more travel sections; and

further comprising;

a cost pre-computation submodule, coupled to the predetermined level module, for comparing the estimated sectional financial cost for traversing each of the travel sections; and

an aggregator pre-computation submodule, coupled to the predetermined level module, for selecting the destination with the lowest of the estimated sectional financial cost for traversing each of the travel sections.

50. The system as claimed in claim 37 wherein:

the calculator pre-computation submodule is for calculating an estimated sectional financial cost for traversing one or more travel sections; and

further comprising;

a cost pre-computation submodule, coupled to the predetermined level module, for comparing the estimated sectional financial cost for traversing each of the travel sections; and

an aggregator pre-computation submodule, coupled to the predetermined level module, for selecting an intermediate stop with the lowest of the estimated sectional financial cost for traversing each of the travel sections.