Optimum route planning for service vehicles

• US 7,778,773 B2
• Filed: 05/02/2007
• Issued: 08/17/2010
• Est. Priority Date: 05/02/2007
• Status: Active Grant

• Current Assignee: Four Batons Wireless LLC
• Original Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson), Toshiba Corporation
• Inventors: Yaqub, Raziq, Fajardo, Victor
• Primary Examiner(s): ARTHUR JEANGLAUDE, GERTRUDE
• Application Number:
  US11/743,261
• Publication Number:
  US 20080275643A1
• Time in Patent Office: 1,203 Days
• Field of Search: 701/200, 701/201, 701208-211, 701214-215, 701/300, 342/357.1, 342/357.06, 342/357.07, 342/357.09, 705/1, 705/28, 340/995.19
• US Class Current: 701/209
• 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: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

Transportation costs are minimized with a novel system for optimizing a route for a service vehicle, for example, a package delivery van. Based upon static and dynamic information, a computer on board the service vehicle determines an optimum route for the vehicle to travel between multiple locations. The computer on board the service vehicle communicates wirelessly to receive any pertinent dynamic information which has changed (e.g., traffic congestion, the presence of a customer at a deliver location, or a modification of location). The computer then recalculates the optimum route for the vehicle and guides the driver of the vehicle in accordance with the newly determined optimum route. The on board computer continues to check for any updates, and recalculates the optimum route throughout the day. Thus, the optimum route may be selected based upon the latest available information white avoiding heavy signal traffic on the wireless network.

Claims

1. An optimum route planning system for a vehicle, comprising:

an on-board computer located on board the vehicle and having access to destination information of multiple destinations to which the vehicle is to travel and road map information, the on-board computer calculating an initial optimum route the vehicle is to travel, including determining an order of the multiple destinations to which the vehicle is to travel;

a user interface to communicate the calculated optimum route to an operator of the vehicle;

a wireless communication system receiving updated information and communicating the same to the on-board computer;

wherein upon receipt of the updated information, the computer again calculates an optimum route based on the destination information, the road map information and the updated information.

2. The optimum route planning system of claim 1, wherein the updated information is updated destination information modifying destinations to which the vehicle is to travel.

3. The optimum route planning system of claim 2, wherein the vehicle is a service delivery vehicle, and the updated destination information includes a new destination for a product delivery or pickup.

4. The optimum route planning system of claim 2, wherein the updated destination information includes the removal or modification of a destination from the multiple destinations of the destination information accessible to the on-board computer.

5. The optimum route planning system of claim 1, wherein the updated information is traffic congestion information.

6. The optimum route planning system of claim 1, wherein the updated information is addressee location information indicating a location of an addressee of a deliverable.

7. The optimum route planning system of claim 6, wherein the on-board computer determines whether or not the addressee location information corresponds to a desired destination of the multiple destinations, and if not, determines whether or not the destination information should be modified and a new optimum route calculated.

8. The optimum route planning system of claim 7, wherein the new optimum route calculation disregards destinations of the multiple destinations the vehicle has already visited.

9. The optimum route planning system of claim 6, wherein the addressee location information is used to modify a destination of the multiple destinations and a new optimum route is calculated as a function of the modified destination information.

10. The optimum route planning system of claim 6, wherein the location information is received wirelessly from a server at a control center.

11. The optimum route planning system of claim 6, wherein the deliverable is one of a product, mail, service, or sales.

12. The optimum route planning system of claim 1, wherein the updated information is received via a short messaging service of a cell phone and is used to modify a destination of the multiple destinations, and the computer calculates a new optimum route as a function of the modified destination.

13. The optimum route planning system of claim 1, wherein the on-board computer uses one of ant colony optimization algorithm, a Dijkstra algorithm, and a combination thereof to calculate an optimum route.

26. The optimum route planning system of claim 2, wherein the updated destination information is rescheduling information indicating time restrictions of when a deliverable may be delivered.

14. A method for optimizing a route for a vehicle, comprising:

(a) obtaining initial destination information including locations of multiple destinations,

(b) calculating, on board the vehicle, an initial optimum route between the multiple destinations, including determining an order to travel to the multiple destinations,

(c) communicating the initial optimum route to the operator of the vehicle,

(d) after steps (a)-(c), wirelessly receiving updated destination information,

(e) calculating, on board the vehicle, an updated optimum route as a function of the updated destination information, and

(f) communicating the updated optimum route to the operator of the vehicle.

15. The method of claim 14, wherein updated destination information adds a new destination to the multiple destinations and step (e) includes calculating an optimum route as a function of the new destination and the destinations of the multiple destinations the vehicle has not yet visited.

16. The method of claim 15, wherein the destinations the vehicle has not yet visited are determined automatically by using GPS information of the vehicle.

17. The method of claim 14, wherein the updated destination information is a modification of the multiple destinations and step (e) includes calculating an optimum route as a function of the modification and the destinations of the multiple destinations the vehicle has not yet visited.

18. The method of claim 17, wherein the destinations the vehicle has not yet visited are determined automatically by using GPS information of the vehicle.

19. The method of claim 14, wherein the updated destination information is a cancelled destination canceling a destination from the multiple destinations, and step (e) includes calculating an optimum route as a function of the cancelled destination and the destinations of the multiple destinations the vehicle has not yet visited.

20. The method of claim 19, wherein the destinations the vehicle has not yet visited are determined automatically by using GPS information of the vehicle.

21. The method of claim 14, wherein the updated destination information is transmitted to the vehicle from a control center.

22. The method of claim 14, wherein the updated destination information is transmitted to the vehicle from an addressee associated with the destination.

23. The method of claim 22, wherein the addressee transmits the updated destination information directly to the vehicle with a cellular phone.

24. The method of claim 22, wherein the addressee transmits the updated destination information to the vehicle via the control center.

25. The method of claim 14, wherein the updated destination information is rescheduling information indicating time restrictions of when a deliverable may be delivered.