| IDSIA - Istituto Dalle Molle di Studi sull'Intelligenza Artificiale | Monaldo Mastrolilli |
| About Vehicle Routing Problems | ||
| Solution Techniques for VRP | ||
| Tutorials | ||
| References | ||
| Slides (COURSE on Vehicle Routing Problems) |
The most elementary version of the vehicle routing problem is the capacitated vehicle routing problem (CVRP). The CVRP is described as follows: n customers must be served from a unique depot. Each customer asks for a quantity qi of goods (i = 1,..., n) and a vehicle of capacity Q is available to deliver goods. Since the vehicle capacity is limited, the vehicle has to periodically return to the depot for reloading. In the CVRP, it is not possible to split customer delivery. Therefore, a CVRP solution is a collection of tours where each customer is visited only once and the total tour demand is at most Q.
From a graph theoretical point of view the CVRP may be stated as follows: Let G = (C,L) be a complete graph with node set C = (co, c1, c2,..., cn) and arc set L = (ci, cj): ci, cj Î C, i ¹ j. In this graph model, co is the depot and the other nodes are the customers to be served. Each node is associated with a fixed quantity qi of goods to be delivered (a quantity qo = 0 is associated to the depot co). To each arc (ci, cj) is associated a value tij representing the travel time between ci and cj. The goal is to find a set of tours of minimum total travel time. Each tour starts from and terminates at the depot co, each node ci (i = 1,..., n) must be visited exactly once, and the quantity of goods to be delivered on a route should never exceed the vehicle capacity Q.
An important extension of the CVRP is the vehicle routing problem with
time windows (VRPTW). In addition to the mentioned CVRP features, this
problem includes, for the depot and for each customer ci (i = 0,..., n)
a time window [bi, ei] during which the customer has to be served (with
b0 the earliest start time and e0 the latest return time of each vehicle
to the depot). The tours are performed by a fleet of v identical vehicles.
The additional constraints are that the service beginning time at each
node ci (i = 1,..., n) must be greater than or equal to bi, the beginning
of the time window, and the arrival time at each node ci must be lower
than or equal to ei, the end of the time window. In case the arrival time
is less than bi, the vehicle has to wait till the beginning of the time
window before starting servicing the customer. In the literature the fleet
size v is often a variable and a very common objective is to minimize v.
Usually, two different solutions with the same number of vehicles are ranked
by alternative objectives such as the total traveling time or total delivery
time (including waiting and service times).
Exact Approach
Tutorials
- M. Gendreau, G. Laporte, J.Y. Potvin, Vehicle routing: modern heuristics, in Local Search in Combinatorial Optimizations, pp. 311--336, edited by E. Aarts and J.K. Lenstra, Wiley, 1997.
- G. Kindervater, M. Savelsbergh, Vehicle routing: handling edge exchanges, in Local Search in Combinatorial Optimizations, pp. 337--360, edited by E. Aarts and J.K. Lenstra, Wiley, 1997.
- Gambardella L.M., Taillard E., Agazzi G., MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows , In D. Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimization. McGraw-Hill, 1999 (Also available as, Tech. Rep. IDSIA-06-99 , IDSIA, Lugano, Switzerland).
If you miss your favourite reference or if you know any reference that should be in the list please send me an e-mail (monaldo@idsia.ch). I will complete the list. References
1. P. Badeau, M. Gendreau, F. Guertin, J.-Y. Potvin, É. D. Taillard, A Parallel Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows, Transportation Research-C 5, 1997, 109-122.
2. Bentley J.L., “Fast algorithms for geometric traveling salesman problem,” ORSA Journal on Computing, vol. 4, pp. 387–411, 1992.
3. W. C. Chiang, R. Russel, Hybrid Heuristics for the Vehicle Routing Problem with Time Windows, Working Paper, Department of Quantitative Methods, University of Tulsa, OK, USA, 1993.
4. Clark G, Wright, J.W., Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12, 568-581, 1964.
5. Fiala F., Vehicle Routing Problems, GMD-Mitteilungen, 46, Boon, 1978.
6. Fisher M. L., Optimal Solution of Vehicle Routing Problems Using Minimum K-trees, Operations Research 42, 1994, 626-642.
7. Fisher M. L., Jaikumur R., A generalized assignment heuristic for vehicle routing, Network 11, 109-124, 1981.
8. Flood M. M., The Traveling Salesman Problem, Operations Research 4, 1956, 61-75.
9. Gambardella L.M, Taillard E., Agazzi G., MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows , In D. Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimization. McGraw-Hill, London, UK, pp. 63-76, 1999.
10. Johnson, D.S., L.A. McGeoch. 1997. The traveling salesman problem: a case study, E. H. Aarts, J. K. Lenstra, eds. Local Search in Combinatorial Optimization. John Wiley & Sons, Chichester, UK. 215–310.
11. P. Kilby, P. Prosser, P. Shaw, Guided Local Search for the Vehicle Routing Problems With Time Windows, in Meta-heuristics: Advances and Trends in Local Search for Optimization, S.Voss, S. Martello, I.H. Osman and C.Roucairol (eds.), Kluwer Academic Publishers, Boston, 1999, 473-486.
12. Kindervater, G.A.P., M.W.P. Savelsbergh. 1997. Vehicle routing: handling edge exchanges, E. H. Aarts, J. K. Lenstra, eds. Local Search in Combinatorial Optimization. John Wiley & Sons, Chichester, UK. 311–336.
13. Laporte G. Gendreau M., Potvin J-Y., Semet F., Classical amd Modern Heuristics for the vehicle routing problem, International Transaction in Operational Research, vol. 7, pp. 285-300, 2000.
14. O. Martin, S.W. Otto, and E.W. Felten, “Large-step Markov chains for the TSP incorporating local search heuristics,” Operations Research Letters, vol. 11, pp. 219-224, 1992.
15. Papadimitriou C., Steiglitz K. Combinatorial optimization : algorithms and complexity by, Prentice-Hall, New Jersey, 1982
16. J.-Y. Potvin, S. Bengio, The Vehicle Routing Problem with Time Windows - Part II: Genetic Search, INFORMS Journal of Computing 8, 1996, 165-172.
17. C. Rego, C. Roucairol, A Parallel Tabu Search Algorithm Using Ejection Chains for the Vehicle Routing Problem, in Meta-heuristics: Theory and applications, I.H. Osman, J. Kelly (eds.), Kluwer Academic Publishers, Boston, 1996, 661-675.
18. Y. Rochat, É. D. Taillard, Probabilistic Diversification and Intensification in Local Search for Vehicle Routing, Journal of Heuristics 1, 1995, 147-167.
19. M. Solomon, Algorithms for the Vehicle Routing and Scheduling Problem with Time Window Constraints, Operations Research 35, 1987, 254-365.
20. P. Shaw, Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems, Proceedings of the Fourth International Conference on Principles and Practice of Constraint Programming (CP '98), M. Maher and J.-F. Puget (eds.), Springer-Verlag, 1998, 417-431.
21. É. D. Taillard, Parallel Iterative Search Methods for Vehicle Routing Problems, Networks 23, 1993, 661673.
22. É. D. Taillard, P. Badeau, M. Gendreau, F. Guertin, J.-Y. Potvin, A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows, Transportation Science 31, 1997, 170-186.
23. S. R. Thangiah, I. H. Osman, T. Sun, Hybrid Genetic Algorithm Simulated Annealing and Tabu Search Methods for Vehicle Routing Problem with Time Windows, Technical Report 27, Computer Science Department, Slippery Rock University, 1994.
24. P. Toth, D. Vigo, The Granular Tabu Search (and its Application to the Vehicle Routing Problem), Technical Report, Dipartimento di Elettronica, Informatica e Sistemistica, Università di Bologna, Italy, 1998.
25. J. Xu, J. Kelly, A Network Flow-Based Tabu Search Heuristic for the Vehicle Routing Problem, Transportation Science 30, 1996, 379-393.