×

Solving the vehicle routing problem with adaptive memory programming methodology. (English) Zbl 1116.90119

Summary: We develop an adaptive memory programming method for solving the capacitated vehicle routing problem called Solutions’ Elite PArts Search (SEPAS). This iterative method, first generates initial solutions via a systematic diversification technique and stores their routes in an adaptive memory. Subsequently, a constructive heuristic merges route components (called elite parts) from those in the adaptive memory. Finally, a tabu search approach improves the heuristically constructed solution and the adaptive memory is appropriately updated. SEPAS has been tested on two benchmark data sets and provides high quality solutions in short computational times for all problem instances. The method reaches several new best solutions for benchmark instances with a large number of customers.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
90B06 Transportation, logistics and supply chain management
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Laporte, G.; Gendreau, M.; Potvin, J.-. Y.; Semet, F., Classical and modern heuristics for the vehicle routing problem, International Transactions on Operational Research, 7, 285-300 (2000)
[2] Toth P, Vigo D. The vehicle routing problem. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002.; Toth P, Vigo D. The vehicle routing problem. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002. · Zbl 0979.00026
[3] Toth, P.; Vigo, D., Exact solutions of the vehicle routing problem, (Crainic, T. G.; Laporte, G., Fleet management and logistics (1998), Kluwer: Kluwer Boston), 1-31 · Zbl 0966.90009
[4] Gendreau M, Laporte G, Potvin J-Y. Metaheuristics for the VRP. In: Toth P, Vigo D, editors. The vehicle routing problem. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002. p. 129-54.; Gendreau M, Laporte G, Potvin J-Y. Metaheuristics for the VRP. In: Toth P, Vigo D, editors. The vehicle routing problem. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002. p. 129-54. · Zbl 1076.90545
[5] Rochat, Y.; Taillard, E. D., Probabilistic diversification and intensification in local search for vehicle routing, Journal of Heuristics, 1, 147-167 (1995) · Zbl 0857.90032
[6] Hertz, A.; Kobler, D., A framework for the description of evolutionary algorithms, European Journal of Operational Research, 126, 1, 1-12 (2000) · Zbl 0970.90122
[7] Moscato, P.; Cotta, C., A gentle introduction to memetic algorithms, (Glover, F.; Kochenberger, G., Handbook of metaheuristics (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Boston), 1-56
[8] Resende, M.; Ribeiro, C., Greedy randomized adaptive search procedures, (Glover, F.; Kochenberger, G., Handbook of metaheuristics (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Boston) · Zbl 1102.90384
[9] Gambardella, L. M.; Taillard, E. D.; Dorigo, M., Ant colonies for the quadratic assignment problem, Journal of the Operational Research Society, 50, 167-176 (1999) · Zbl 1054.90621
[10] Laguna, M., Scatter search, (Pardalos, P. M.; Resende, M. G.C., Handbook of applied optimization (2002), Oxford University Press: Oxford University Press New York), 183-193
[11] Taillard, E.; Gambardella, L. M.; Gendreau, M.; Potvin, J.-. Y., Adaptive memory programming: a unified view of metaheuristics, European Journal of Operational Research, 135, 1-16 (2001) · Zbl 1051.90032
[12] Tarantilis, C. D.; Kiranoudis, C. T., BoneRoute: an adaptive memory-based method for effective fleet management, Annals of Operations Research, 115, 1, 227-241 (2002) · Zbl 1013.90020
[13] Christofides, N.; Mingozzi, A.; Toth, P., The vehicle routing problem, (Christofides, N.; Mingozzi, A.; Toth, P.; Sandi, C., Combinatorial optimization (1979), Wiley: Wiley Chichester), 315-338
[14] Golden, B. L.; Wasil, E. A.; Kelly, J. P.; Chao, I. M., The impact of metaheuristics on solving the vehicle routing problem: algorithms, problem sets, and computational results, (Crainic, T. G.; Laporte, G., Fleet management and logistics (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Boston), 33-56 · Zbl 0997.90021
[15] Glover, F., A template for scatter search and path relinking, (Hao, J.-. K.; Lutton, E.; Ronald, E.; Schoenauer, M.; Snyers, D., Artificial Evolution. Lecture notes in computer science (1998), Springer: Springer Berlin), 13-54
[16] Paessens, H., The savings algorithm for the vehicle routing problem, European Journal of Operational Research, 34, 336-344 (1988) · Zbl 0635.90047
[17] Taillard, E. D., Parallel iterative search methods for vehicle routing problems, Networks, 23, 661-672 (1993) · Zbl 0804.90045
[18] Rego, C., Node-ejection chains for the vehicle routing problem: sequential and parallel algorithms, Parallel Computing, 27, 3, 201-222 (2001) · Zbl 0969.68176
[19] Rego C, Leão P. A scatter search tutorial for graph-based permutation problems. Research Paper HCES-10-00, Hearin Center for Enterprise Science, University of Mississippi, USA; 2000.; Rego C, Leão P. A scatter search tutorial for graph-based permutation problems. Research Paper HCES-10-00, Hearin Center for Enterprise Science, University of Mississippi, USA; 2000.
[20] Lin, S., Computer solutions of the traveling salesman problem, Bell Lab Technical Journal, 44, 2245-2269 (1965) · Zbl 0136.14705
[21] Glover, F.; Laguna, M., Tabu search (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 0930.90083
[22] Cordeau, J.-. F.; Gendreau, M.; Laporte, G.; Potvin, J.-. Y.; Semet, F., A guide to vehicle routing heuristics, Journal of the Operational Research Society, 53, 512-522 (2002) · Zbl 1099.90506
[23] Osman, I. H., Metastrategy simulated annealing and tabu search algorithms for combinatorial optimisation problems, Annals of Operational Research, 41, 421-451 (1993) · Zbl 0775.90153
[24] Gendreau, M.; Hertz, A.; Laporte, G., A tabu search heuristic for the vehicle routing problem, Management Science, 40, 1276-1290 (1994) · Zbl 0822.90053
[25] Xu, J.; Kelly, J. P., A new network flow-based tabu search heuristic for the vehicle routing problem, Transportation Science, 30, 379-393 (1996) · Zbl 0879.90086
[26] Toth, P.; Vigo, D., The granular tabu search (and its application to the vehicle routing problem), INFORMS Journal on Computing, 15, 4, 333-348 (2003) · Zbl 1238.90141
[27] Rego, C., A subpath ejection method for the vehicle routing problem, Management Science, 44, 1447-1459 (1998) · Zbl 0989.90522
[28] Barbarosoglu, G.; Ozgur, D., A tabu search algorithm for the vehicle routing problem, Computers & Operations Research, 26, 255-270 (1999) · Zbl 0941.90017
[29] Tarantilis, C. D.; Kiranoudis, C. T.; Vassiliadis, V. S., A backtracking adaptive threshold accepting metaheuristic method for the Vehicle Routing Problem, System Analysis Modelling Simulation (SAMS), 42, 5, 631-644 (2002) · Zbl 1070.90528
[30] Tarantilis, C. D.; Kiranoudis, C. T.; Vassiliadis, V. S., A list based threshold accepting algorithm for the capacitated vehicle routing problem, International Journal of Computer Mathematics, 79, 5, 537-553 (2002) · Zbl 1024.90018
[31] Bullnheimer, B.; Hartl, P. F.; Strauss, C., An improved ant system algorithm for the vehicle routing problem, Annals Operations Research, 89, 319-328 (1999) · Zbl 0937.90125
[32] Reimann M, Stummer M, Doerner K. A savings based ant system for the vehicle routing problem. In: Proceedings of the Genetic and Evolutionary Computation Conference, New York; 2002. p. 1317-26.; Reimann M, Stummer M, Doerner K. A savings based ant system for the vehicle routing problem. In: Proceedings of the Genetic and Evolutionary Computation Conference, New York; 2002. p. 1317-26.
[33] Reimann, M.; Doerner, K.; Hartl, R. F., D-Ants: savings based ants divide and conquer the vehicle routing problem, Computers & Operations Research, 31, 4, 563-591 (2004) · Zbl 1061.90024
[34] Baker, B. M.; Ayechew, M. A., A genetic algorithm for the vehicle routing problem, Computers & Operations Research, 30, 5, 787-800 (2003) · Zbl 1026.90013
[35] Prins C. A simple and effective evolutionary algorithm for the vehicle routing problem. Research Report, University of Technology of Troyes, France, 2001. Computers & Operations Research 2004;31;1985-2002.; Prins C. A simple and effective evolutionary algorithm for the vehicle routing problem. Research Report, University of Technology of Troyes, France, 2001. Computers & Operations Research 2004;31;1985-2002. · Zbl 1100.90504
[36] Berger J, Mohamed B. A hybrid genetic algorithm for the capacitated vehicle routing problem. In: Proceedings of the Genetic and Evolutionary Computation Conference, Chicago; 2003, p. 646-56.; Berger J, Mohamed B. A hybrid genetic algorithm for the capacitated vehicle routing problem. In: Proceedings of the Genetic and Evolutionary Computation Conference, Chicago; 2003, p. 646-56. · Zbl 1028.68678
[37] Coy, S. P.; Golden, B. L.; Runger, G. C.; Wasil, E. A., Using experimental design to find effective parameter settings for heuristics, Journal of Heuristics, 7, 1, 77-97 (2001) · Zbl 0967.90018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.