Vehicle Routing Problem (VRP)
by Wolfgang Garn
( Last update: 20.07.2007)
Introduction
A fleet of vehicles supplies customers. Each vehicle has a certain capacity
and each customer has a certain demand. Further on there exists a depot(s) and
a distance (length, cost, time) matrix between the customers.
We look for optimal vehicle routes (minimum distance or number of vehicles).
The VRP is a
Nonlinear Programming (NP) problem.
The special cases of the VRP result in other popular problems like the
Traveling Salesman Problem (TSP) or even
Scheduling .
Links
-
NEO and Auren !!! ( This site must be recommended to anyone interested in VRP)
(very good!!! with lots of good links - 27.2.2004, any time I look
at it, it is more impressive. Author: University of Málaga by Bernabé Dorronsoro Díaz and Auren
(below are some copies of pages from the site with few changes because I could not print it on the original site properly yet)))
-
Vehicle Routing Problem - The Evolutionary Way
(Problem, Genetic Vehicle Representation - 27.2.2004)
-
Vehicle Routing
- Branch Cut and Price Applications ( 11.12.2002)
-
Vehicle Routing Problems
(Solution Techniques, Tutorial, References- 4.12.2002)
-
Quantitative Analysis of Two Capacitated Vehicle Routing Algorithms
( html - 4.12.2002)
-
The Vehicle Routing Problem
( html - 4.12.2002, Schulze)
-
National Institute of Standards and Technology -
NIST
-
Zentrum für Paralleles Rechnen
ZPR (working group, problem)
-
Wiki: Vehicle Routing (still under construction[20.07.2007]) -
Wiki
- Management Science -
Networks & Vehicle Routing
Related Papers
-
Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems
( PDF )
-
Solution of a Min-Max Vehicle Routing Problem
( PDF )
-
Genetic Algorithms for the Vehicle Routing Problem with Time Windows
( PDF )
-
Vehicle Routing Problem: Doing it the Evolutionary Way
( PDF )
-
A Location Based Heuristic for General Routing Problems
( PS , DVI )
-
On the Capacitated Vehicle Routing Problem
( PDF )
-
A Shortest Path Approach to the Multiple-Vehicle Routing Problem
with Split Pick-Ups
( PDF )
-
The Very Offline k-Vehicle Routing Problem in Tress ( PS )
-
Approximation algorithms for time-dependent orienteering ( PS )
-
An Improved Approximation Ration for the Minimum Latency Problem
( PS , PDF )
-
Faster Approximation Algorithms for the Minimum Latency Problem
( PS )
- VRP with Time Windows
- A Reactive Method for Real Time Dynamic Vehicle Routing Problem (
PS )
- Heuristic Methods for Vehicle Routing Problem with Time Windows (
PS )
- Probabilistic Analysis and Practical Algorithms for the Vehicle Routing Problem with Time Windows
( PS , DVI )
- The VRP with Time Windows
( PS )
Classic Papers
- Scheduling of Vehicles from a central depot to a number of delivery points ( August 1962, G.Clarke, J.W.Wright)
Books
There exist a few good papers, which enable you to implement VRP algorithms
straigth away. Most papers provide you with ideas and results.
Domschkes book assists you well to implement a VRP.
- Domschke, Logistik: Rundreisen und Touren
(about 70 pages about the VRP topic, classifies VRP, shows some of the most
famous implementations and gives references in the context), Best book to this topic
I found so far.
(Amazon:
1,
2,
3
)
- Paolo Toth and Daniele Vigo, The Vehicle Routing Problem
published by SIAM - Monographs on Discrete Mathematics and Applications, 2002
(Amazon)
- Teodor Gabriel Crainic and Gilbert Laporte, Fleet Management and Logistics
published by Kluwer Academic Publishers, 2004
(Amazon)
- Ahuja, Magnanti, Orlin, Network Flows
a couple of pages about the specific topic and a good introduction
into the general way of solving such problems, beautifully written
- Nemhauser, Wolsey, Integer and Combinatorial Optimization
does not treat the VRP, but the TSP and belongs to the classic books in this field.
- Rosen Discrete and Combinatorial Mathematics
Describes a wee bit about the VRP, but a very comprehensive book and good
for looking up something.
- Atallah, Algorithms and Theory of Computation handbook
Describes the TSP and lots of other important topics
- Evans, Minieka, Optimization Algorithms for Networks and Graphs
includes at least three pages about the topic in a clear, simple but somtime superficial way
- Bertsekas, Nonlinear Programming
only for "hard-core" mathematicans, pretty sophisticated
If you know of any other VRP book please send me an E-Mail
Commercial Software
A comrehensive survey can be found at
ORMS - VR .
Free Software (Code)
A comrehensive survey can be found at
ORMS - VR .
Variants
There are several different variants of the VRP.
- Capcitated Vehicle Routing Problem (CVRP)
This is the homogeneous VRP.
- Multiple Depot VRP (MDVRP)
The customers get their deliveries from several depots.
- VRP with Time Windows (VRPTW)
In case a time window (starttime, endtime, servicetime) is associated to each customer.
- Stochastic VRP (SVRP)
If any component has a random behaviour.
- Periodic VRP (PVRP)
If the delivery is in some days.
- Split Delivery VRP (SDVRP)
Several vehicles serve a customer.
- VRP with Backhauls (VRPB)
When the vehicle must pick something up from the customer AFTER ALL deliveries are done.
- VRP with Pick-Ups and Deliveries (VRPPD)
If the vehicle picks something up and delivers it to the customer.