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

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.


Authors:



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.