Apparatus, system, method and computer program product for determining an optimum route based on historical information

• US 6,615,133 B2
• Filed: 02/27/2001
• Issued: 09/02/2003
• Est. Priority Date: 02/27/2001
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yu, Philip S., Dinkin, Samuel H., Moskowitz, Paul Andrew, Boies, Stephen J., Greene, David Perry
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): To, Tuan C
• Application Number:
  US09/794,275
• Publication Number:
  US 20020120396A1
• Time in Patent Office: 917 Days
• Field of Search: 701/209, 701/210, 701/211, 701/202, 701/117, 701/207, 701/201, 701/208, 701/200, 701/212, 701/214, 455/456, 340/988, 340/990, 340/995, 340/905, 340/994, 345/353
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

An apparatus, system, method and computer program product for determining optimum routing of vehicles based on historical information as well as user preferences and current travel conditions. Historical data is compiled and statistically analyzed to determiner characteristics of each possible route between two points. The characteristic information is then used along with user preference information and current travel condition information to determine an optimum route between the two points.

Claims

1. A method of determining a route from a starting position to a destination position for a vehicle, comprising:

obtaining route criteria for selecting a route;

obtaining historical data for a plurality of routes; and

selecting a route from the starting position to the destination position based on a comparison of the route criteria to the historical data for a plurality of routes, wherein selecting a route from the starting position to the destination position based on a comparison of the route criteria to the historical data for a plurality of routes includes;

calculating a score for each of the plurality of routes based on a comparison of the route criteria to the historical data for each of the plurality of routes;

comparing the scores for each of the plurality of routes; and

selecting a route based on the comparison of the scores for each of the plurality of routes.

2. The method of claim 1, wherein calculating a score for each route of the plurality of routes includes weighing scores for each of a plurality of legs that compromise the route based on the route criteria.

3. The method of claim 1, further comprising obtaining current environmental condition information, wherein selecting a route from the starting position to the destination position includes selecting the route based on a comparison of the route criteria, the current environmental condition information and the historical data for a plurality of routes.

4. The method of claim 1, wherein the historical data for a plurality of routes includes one or more of traffic condition information, road condition information, accident information, and temporal information.

5. The method of claim 1, wherein the plurality of routes are partitioned into legs, and wherein the historical data is historical data for each leg of the plurality of routes.

6. The method of claim 1, wherein the historical data is obtained from one or more historical data suppliers.

7. The method of claim 1, wherein the one or more historical data suppliers includes one or more of a weather information supplier, a traffic condition information supplier, a road condition information supplier, and an accident information supplier.

8. The method of claim 1, wherein the historical information is uploaded from a vehicle to a vehicle routing server when the vehicle completes a portion of a route.

9. The method of claim 1, wherein calculating a score for each of the plurality of routes includes for each route, summing scores for each of a plurality of legs that comprise the route.

10. The method of claim 1, further comprising weighting the scores for each of the plurality of routes based on at least one of current environmental conditions and current temporal conditions.

11. The method of claim 1, further comprising weighting the scores for each of the plurality of routes based on the route criteria.

12. The method of claim 1, wherein selecting a route from the starting position to the destination position based on a comparison of the route criteria to the historical data for a plurality of routes includes using at least one of a neural network, an expert system, a rule based system, an inference engine, and a data mining technique.

13. The method of claim 2, wherein the weighing is further based on at least one of current environmental conditions and current temporal conditions.

14. An apparatus for determining a route from a starting position to a destination position for a vehicle, comprising:

means for obtaining route criteria for selecting a route;

means for obtaining historical data for a plurality of routes; and

means for selecting a route from the starting position to the destination position based on a comparison of the route criteria to the historical data for a plurality of routes, wherein the means for selecting a route from the starting position to the destination position based on a comparison of the route criteria to the historical data for a plurality of routes includes;

means for calculating a score for each of the plurality of routes based on a comparison of the route criteria to the historical data for each of the plurality of routes;

means for comparing the scores for each of the plurality of routes; and

means for selecting a route based on the comparison of the scores for each of the plurality of routes.

15. The apparatus of claim 14, wherein calculating a score for each route of the plurality of routes includes weighting scores for each of a plurality of legs that comprise the route based on the route criteria.

16. The apparatus of claim 14, further comprising means for obtaining current environmental condition information, wherein the means for selecting a route from the starting position to the destination position includes means for selecting the route based on a comparison of the route criteria, the current environmental condition information and the historical data for a plurality of routes.

17. The apparatus of claim 14, wherein the historical data for a plurality of routes includes one or more of traffic condition information, road condition information, accident information, and temporal information.

18. The apparatus of claim 14, wherein the plurality of routes are partitioned into legs, and wherein the historical data is historical data for each leg of the plurality of routes.

19. The apparatus of claim 14, wherein the historical data is obtained from one or more historical data suppliers.

20. The apparatus of claim 14, wherein the one or more historical data suppliers includes one or more of a weather information supplier, a traffic condition information supplier, a road condition information supplier, and an accident information supplier.

21. The apparatus of claim 14, wherein the historical information is uploaded from a vehicle to a vehicle routing server when the vehicle completes a portion of a route.

22. The apparatus of claim 14, wherein the means for calculating a score for each of the plurality of routes includes means for summing, for each route, scores for each of a plurality of legs that comprise the route.

23. The apparatus of claim 14, further comprising means for weighting the scores for each of the plurality of routes based on at least one of current environmental conditions and current temporal conditions.

24. The apparatus of claim 14, further comprising means for weighting the scores for each of the plurality of routes based on the route criteria.

25. The apparatus of claim 14, wherein the means for selecting a route from the starting position to the destination position based on a comparison of the route criteria to the historical data for a plurality of routes includes at least one of a neural network, an expert system, a rule based system, an inference engine, and a data mining technique.

26. The method of claim 15, wherein the weighing is further based on at least one of current environmental conditions and current temporal conditions.

27. A computer program product in a computer readable medium for determining a route from a starting position to a destination position for a vehicle, comprising:

first instructions for obtaining route criteria for selecting a route;

second instructions for obtaining historical data for a plurality of route of routes; and

third instructions for selecting a route from the starting position to the destination position based on a comparison of the route criteria to the historical data for a plurality of routes, wherein the third instructions include;

instructions for calculating a score for each of the plurality of routes based on a comparison of the route criteria to the historical data for each of the plurality of routes;

instructions for comparing the scores for each of the plurality of routes; and

instructions for selecting a route based on the comparison of the scores for each of the plurality of routes.

28. The computer program product of claim 27, wherein calculating a score for each route of the plurality of routes includes weighting scores for each of a plurality of legs that comprise the route based on the route criteria.

29. The computer program product of claim 27, further comprising fourth instructions for obtaining current environmental condition information, wherein the third instructions for selecting a route from the starting position to the destination position includes instructions for selecting the route based on a comparison of the route criteria, the current environmental condition information and the historical data for a plurality of routes.

30. The computer program product of claim 27, wherein the historical data for a plurality of routes includes one or more of traffic condition information, road condition information, accident information, and temporal information.

31. The computer program product of claim 27, wherein the instructions for calculating a score for each of the plurality of routes includes instructions for summing, for each route, scores for each of a plurality of legs that comprise the route.

32. The computer program product of claim 27, further comprising instructions for weighting the scores for each of the plurality of routes based on at least one of current environmental conditions and current temporal conditions.

33. The computer program product of claim 27, further comprising instructions for weighting the scores for each of the plurality of routes based on the route criteria.

34. The computer program product of claim 27, wherein the third instructions include instructions for using at least one of a neural network, an expert system, a rule based system, an inference engine, and a data mining technique.

35. The method of claim 28, wherein the weighing if further based on at least one of current environmental conditions and current temporal conditions.

36. The computer program product of claim 27, wherein the plurality of routes are partitioned into legs, and wherein the historical data is historical data for each leg of the plurality of routes.

37. The computer program product of claim 27, wherein the historical data is obtained from one or more historical data suppliers.

38. The computer program product of claim 27, wherein the one or more historical data suppliers includes one or more of a weather information supplier, a traffic condition information supplier, a road condition information supplier, and an accident information supplier.