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

• US 20020120396A1
• Filed: 02/27/2001
• Published: 08/29/2002
• Est. Priority Date: 02/27/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yu, Philip S., Moskowitz, Paul Andrew, Boies, Stephen J., Greene, David Perry, Dinkin, Samuel H.
• Granted Patent: US 6,615,133 B2
• Time in Patent Office: Days
• 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. These characteristics provide an indicator to a traveler of the most probable experience they will encounter when traveling along a route under various conditions. Thus, a more complete determination of an optimum route may be determined in view of preferences of a user and experiences of other travelers, than the mere determination of shortest route or shortest travel time as in the prior art.

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.

2. The method of claim 1, wherein the route criteria reflect a travel experience desired by an operator of the vehicle.

3. The method of claim 1, wherein the route criteria include one or more of shortest travel time, shortest travel distance, avoid high crime areas, avoid high traffic ticket areas, and avoid high accident areas.

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

5. 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, criminal activity information, traffic law enforcement information, accident information, and temporal information.

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

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

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

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

10. 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:

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.

11. The method of claim 10, 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.

12. The method of claim 10, 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.

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

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

16. The apparatus of claim 15, wherein the route criteria reflect a travel experience desired by an operator of the vehicle.

17. The apparatus of claim 15, wherein the route criteria include one or more of shortest travel time, shortest travel distance, avoid high crime areas, avoid high traffic ticket areas, and avoid high accident areas.

18. The apparatus of claim 15, 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.

19. The apparatus of claim 15, wherein the historical data for a plurality of routes includes one or more of traffic condition information, road condition information, criminal activity information, traffic law enforcement information, accident information, and temporal information.

20. The apparatus of claim 15, 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.

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

22. The apparatus of claim 15, wherein the one or more historical data suppliers includes one or more of a weather information supplier, a criminal activity information supplier, a traffic condition information supplier, a road condition information supplier, a traffic law enforcement information supplier, and an accident information supplier.

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

24. The apparatus of claim 15, 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.

25. The apparatus of claim 24, 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.

26. The apparatus of claim 24, 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.

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

28. The apparatus of claim 15, 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.

30. The computer program product of claim 29, wherein the route criteria reflect a travel experience desired by an operator of the vehicle.

31. The computer program product of claim 29, wherein the route criteria include one or more of shortest travel time, shortest travel distance, avoid high crime areas, avoid high traffic ticket areas, and avoid high accident areas.

32. The computer program product of claim 29, 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.

33. The computer program product of claim 29, wherein the historical data for a plurality of routes includes one or more of traffic condition information, road condition information, criminal activity information, traffic law enforcement information, accident information, and temporal information.

34. The computer program product of claim 29, 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.

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

36. The computer program product of claim 29, wherein the one or more historical data suppliers includes one or more of a weather information supplier, a criminal activity information supplier, a traffic condition information supplier, a road condition information supplier, a traffic law enforcement information supplier, and an accident information supplier.

37. The computer program product of claim 29, 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.

38. The computer program product of claim 37, 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.

39. The computer program product of claim 37, 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.

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

41. The computer program product of claim 29, 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.

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

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