Vehicle routing problem
The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem seeking to service a number of customers with a fleet of vehicles. Proposed by Dantzig and Ramser in 1959, VRP is an important problem in the fields of transportation, distribution and logistics. Often the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. Implicit is the goal of minimizing the cost of distributing the goods. Many methods have been developed for searching for good solutions to the problem, but for all but the smallest problems, finding global minimum for the cost function is computationally complex.
Several variations and specializations of the vehicle routing problem exist:
- Vehicle Routing Problem with Pickup and Delivery (VRPPD): A number of goods need to be moved from certain pickup locations to other delivery locations. The goal is to find optimal routes for a fleet of vehicles to visit the pickup and drop-off locations.
- Vehicle Routing Problem with LIFO: Similar to the VRPPD, except an additional restriction is placed on the loading of the vehicles: at any delivery location, the item being delivered must be the item most recently picked up. This scheme reduces the loading and unloading times at delivery locations because there is no need to temporarily unload items other than the ones that should be dropped off.
- Vehicle Routing Problem with Time Windows (VRPTW): The delivery locations have time windows within which the deliveries (or visits) must be made.
- Capacitated Vehicle Routing Problem (with or without Time Windows): CVRP or CVRPTW. The vehicles have limited carrying capacity of the goods that must be delivered.
- Vehicle Routing Problem with Multiple Trips (VRPMT): The vehicles can do more than one route.
Several software vendors have built software products to solve the various VRP problems. Numerous articles are available for more detail on their research and results.
Why is it hard?
To the casual observer the vehicle routing problem does not seem to present many difficulties — surely it is just a case of trying all combinations of visits and seeing which one is best (shortest/fastest/cheapest/etc)?
However it is easy to demonstrate just how difficult vehicle routing problems can be. Imagine a vehicle that has to deliver to 3 different locations A, B & C. The "problem" is to decide which order the vehicle should visit each location to minimise the overall travel distance.
There are 6 possible solutions:
So, the simplistic approach is to consider all 6 cases, work out the distance travelled for each one and choose the shortest. (Actually often only 3 of the cases need to be considered because the distance A-B-C is likely to be the same as the distance C-B-A, unless one-way streets are involved.)
This simple problem would take a modern computer almost no time to solve. However the difficulty increases surprisingly quickly as the number of deliveries increases:
- 4 locations have 24 possible solutions
- 5 locations have 120 possible solutions
- 6 locations have 720 possible solutions
N locations have N x (N-1) x (N-2) x .... 3 x 2 x 1 possible solutions. This is known as a factorial dependence. For a parcel delivery van that makes 80-100 deliveries in a day, the number of possible routes is very large. The typical expression is "more than the number of atoms in the universe," and this is a fair reflection. The simplistic approach of trying all possible combinations would therefore take "longer than the lifetime of the universe" to come up with an answer.
- Dantzig, George Bernard; Ramser, John Hubert (October 1959). "The Truck Dispatching Problem". Management Science 6 (1): 80–91.
- Beck, J.C.; Prosser, P.; Selensky, E. (2003). "Vehicle routing and job shop scheduling: What’s the difference". Proceedings of the 13th International Conference on Artificial Intelligence Planning and Scheduling.
- http://www.mjc2.com/logistics-planning-complexity.htm Why is logistics planning hard?
- Oliveira, H.C.B.de; Vasconcelos, G.C. (2008). "A hybrid search method for the vehicle routing problem with time windows". Annals of Operations Research. Retrieved 2009-01-29.
- Frazzoli, E.; Bullo, F. (2004). "Decentralized algorithms for vehicle routing in a stochastic time-varying environment". Decision and Control, 2004. CDC. 43rd IEEE Conference on 4.
- Psaraftis, H.N. (1988). "Dynamic vehicle routing problems". Vehicle Routing: Methods and Studies 16: 223–248.
- Bertsimas, D.J.; Van Ryzin, G. (1991). "A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane". Operations Research 39 (4): 601–615. doi:10.1287/opre.39.4.601. JSTOR 171167.
- Toth, P.; Vigo, D. (2001). The Vehicle Routing Problem. Philadelphia: Siam. ISBN 0-89871-579-2.