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,[1] 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. The objective of the VRP is to minimize the total route cost.
Determining the optimal solution is an NP-hard problem in combinatorial optimization, so in practice, heuristic and deterministic methods have been developed that find acceptably good solutions for the VRP.
Overview
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. In computational complexity theory, this problem is known to be NP-hard.[2]
- 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.
- Open Vehicle Routing Problem (OVRP): Vehicles are not required to return to the depot.
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.
Although VRP is related to the Job Shop Scheduling Problem, the two problems are typically solved using different techniques.[3]
Free software for solving VRP
| Name (alphabetically) |
License | API language | Brief info |
|---|---|---|---|
| jsprit | LGPL | Java | lightweight, java based, open source toolkit for solving rich VRPs. link An Excel-compatible user interface for jsprit is available with mapping, reporting and route editing functionality. link |
| Open-VRP | LLGPL | Lisp | Open-VRP for Lisp, hosted on Github. link |
| OptaPlanner | Apache License | Java | Open Source Java constraint solver (optaplanner.org) with VRP examples. |
| SYMPHONY | Common Public License 1.0 | Open-source solver for mixed-integer linear programs (MILPs) with support for VRPs. link | |
| VRP Spreadsheet Solver | Creative Commons Attribution 4.0 International License | Microsoft Excel and VBA based open source solver, with a link to public GIS for data retrieval. link Video tutorial link | |
| vrphlibrary (VRPH) | Common Public License 1.0 | Home page of open source VRPH software link and hosting page on COIN-OR link. | |
| vroom | ? | Open source libraries for the VRP and dynamic VRP. link |
See also
- Chinese postman problem
- Travelling salesman problem
- Intelligent Water Drops algorithm
- Vehicle rescheduling problem
References
- ↑ Dantzig, George Bernard; Ramser, John Hubert (October 1959). "The Truck Dispatching Problem" (PDF). Management Science 6 (1): 80–91. doi:10.1287/mnsc.6.1.80.
- ↑ Beck, Prosser, Selensky, 2003; p.2 left
- ↑ Beck, J.C.; Prosser, P.; Selensky, E. (2003). "Vehicle routing and job shop scheduling: What’s the difference" (PDF). Proceedings of the 13th International Conference on Artificial Intelligence Planning and Scheduling.
Further reading
- 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.
External links
- The VRP Web - Extensive information, test instances and various VRP variants
- Vehicle Routing Software Survey - an INFORMS review
- Demo applet of a genetic algorithm solving TSPs and VRPTW problems
- Demo of a genetic algorithm solving VRP initialized with Clark & Wright savings heuristic
- Routyn - commercial software for solving VRPs
- Optimo Route - commercial CVRPTW solver