How to Build and Evaluate a Solution Method: An Illustration for the Vehicle Routing Problem

Authors: Nicolas Zufferey

Abstract:

The vehicle routing problem (VRP) is a famous combinatorial optimization problem. Because of its well-known difficulty, metaheuristics are the most appropriate methods to tackle large and realistic instances. The goal of this paper is to highlight the key ideas for designing VRP metaheuristics according to the following criteria: efficiency, speed, robustness, and ability to take advantage of the problem structure. Such elements can obviously be used to build solution methods for other combinatorial optimization problems, at least in the deterministic field.

Keywords: Vehicle routing problem, Metaheuristics, Combinatorial optimization.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1328946

References:

[1] Dantzig, G. B. and Ramser, J. H. 1959. The truck dispatching problem. Management Science 6, 80-91.
[2] Toth, P. and Vigo, D. 1998a. Fleet Management and Logistics. Kluwer, Boston, Chapter Exact solution of the vehicle routing problem, 1-31.
[3] Golden, B. L., Wasil, E. A., Kelly, J. P., and Chao, I.-M. 1998. Fleet Management and Logistics. Kluwer, Boston, Chapter Metaheuristics in vehicle routing, 33-56.
[4] Cordeau, J.-F., Gendreau, M., Laporte, G., Potvin, J.-Y., and Semet, F. 2002. A Guide to Vehicle Routing Heuristics. Journal of the Operational Research Society 53 (5), 512-522.
[5] Laporte, G. and Semet, F. 2002. The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, Chapter Classical heuristics for the capacitated VRP, 109-128.
[6] Gendreau, M., Laporte, G., and Potvin, J.-Y. 2002. The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, Chapter Metaheuristics for the VRP, 129-154.
[7] Cordeau, J.-F. and Laporte, G. 2004. Metaheuristic Optimization via Memory and Evolution: Tabu Search and Scatter Search. Kluwer, Boston, Chapter Tabu search heuristics for the vehicle routing problem, 145-163.
[8] Cordeau, J.-F., Gendreau, M., Hertz, A., Laporte, G., and Sormany, J.-S. 2005. Logistics Systems: Design and Optimization. Springer, Chapter New Heuristics for the Vehicle Routing Problem, 270-297.
[9] Nemhauser, G. and Wolsey, L. 1988. Integer and Combinatorial Optimization. John Wiley & Sons.
[10] Garey, M. and Johnson, D. 1979. Computer and Intractability: a Guide to the Theory of NP-Completeness. Freeman, San Francisco.
[11] Gendreau, M., Potvin, J.-Y., Handbook of Metaheuristics, Springer, 2010.
[12] Glover, F. 1989. Tabu search - part I. ORSA Journal on Computing 1, 190-205.
[13] Aarts, E. H. I. and Laarhoven, P. J. M. 1985. Statistical cooling: A general approach to combinatorial optimization problems. Philips Journal of Research 40, 193-226.
[14] Hajek, B. 1988. Cooling schedules for optimal annealing. Mathematics of Operations Research 13, 311-329.
[15] Faigle, U. and Kern, W. 1992. Some convergence results for probabilistic tabu search. ORSA Journal on Computing 4, 32-37.
[16] Glover, F. and Hanafi, S. 2002. Tabu Search and Finite Convergence. Discrete Applied Mathematics 119 (1-2), 3-36.
[17] N. Zufferey, Metaheuristics: some Principles for an Efficient Design, Computer Technology and Applications 3 (6), 446-462, 2012
[18] Gendreau, M., Hertz, A., and Laporte, G. 1994. A tabu search heuristic for the vehicle routing problem. Management Science 40, 1276-1290.
[19] Mohr, R. and Henderson, T. C. 1977. Arc and Path Consistency Revisited. Artificial Intelligence 28, 225-233.
[20] Bessière, C. 1994. Arc-Consistency and Arc-Consistency Again. Artificial Intelligence 65, 179-190.
[21] Taillard, E. D. 1993. Parallel iterative search methods for vehicle routing problems. Networks 23, 661-673.
[22] Toth, P. and Vigo, D. 1998b. The granular tabu search (and its application to the vehicle routing problem). Tech. Rep. OR-98-9, DEIS - Univertity of Bologna - Italy.
[23] Xu, J. and Kelly, J. 1996. A Network Flow-Based Tabu Search Heuristic for the Vehicle Routing Problem. Transportation Science 30, 379-393.
[24] Lin, S. 1965. Computer solutions of the traveling salesman problem. Bell System Technical Journal 44, 2245-2269.
[25] Osman, I. H. 1993. Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem. Annals of Operations Research 41, 421-451.
[26] Robusté, F., Daganzo, C. F., and Souleyrette, R. 1990. Implementing vehicle routing models. Transportation Research, Part B: methodological 24 (4), 263-286.
[27] Rego, C. and Roucairol, C. 1996. Meta-Heuristics: Theory and Applications. Kluwer, Boston, Chapter A Parallel Tabu Search Algorithm Using Ejection Chains for the Vehicle Routing Problem, 661-675.
[28] Hoos, H. H. 1998. Stochastic Local Search - Methods, Models, Applications. Ph.D. thesis, Darmstadt University of Technology.
[29] Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. 1983. Optimization by simulated annealing. Science 220 (5498), 671-680.
[30] Mladenovic, N. and Hansen, P. 1997. Variable neighborhood search. Computers & Operations Research 24, 1097-1100.
[31] Mattfeld, D. C, Bierwirth, C., and Kopfer H. 1999. A search space analysis of the job shop scheduling problem. Annals of Operations Research 86, 441-453.
[32] Prins. 2004. A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research 31, 1985-2002.
[33] Gendreau, M., Hertz, A., and Laporte, G. 1992. New insertion and postoptimization procedures for the traveling salesman problem. Operations Research 40, 1086-1094.
[34] Cheng, R., Gen, M., and Tsujimura, Y. 1999. A tutorial survey of jobshop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies. Computers & Industrial Engineering 36, 343-364.
[35] Rochat, Y. and Taillard, E. 1995. Probabilistic diversification and intensification in local search for vehicle routing. Journal of Heuristics 1, 147-167.
[36] Tarantilis, C.-D. and Kiranoudis, C. T. 2002. Bone Route: An adaptive memory-based method for effective fleet management. Annals of Operations Research 115, 227-241.