A memetic Algorithm for the Capacitated Vehicle Routing Problem
Keywords:
Evolutionary algorithm, explicit collective memory, combinatorial optimizationAbstract
In this paper we present a new memetic algorithm for the CVRP (Capacitated Vehicle Routing Problem). The new algorithm was developed from our earlier multi-objective algorithm for the vehicle routing problem – selecting and further developing one part of the earlier algorithm. The new algorithm is a steady-state evolutionary algorithm. It uses tournament selection; the descendents are derived from the parents by mutation based on the EVL (Extended Virtual Loser) where the EVL is an explicit collective memory technique. The algorithm is a memetic algorithm and uses five different stochastic 2-opt local searches to improve the descendents. We used some test problems of the Vehicle Routing Data Sets and of Christofides. Comparing the results with other method’s results we concluded: in the case of n < 200 costumers we got similar results that was published earlier.
References
Baker, B. M., Ayechew, M. A. (2003): A Genetic Algorithm for the Vehicle Routing Problem. Computers & Operations Research, 30(5), 787–800. https://doi.org/10.1016/S0305-0548(02)00051-5
Bin, Y., Zhongzhen, Y., Baozhen, Y. (2008): An Improved Ant Colony Optimization for Vehicle Routing Problem. European Journal of Operational Research (In print).
Borgulya, I. (2006): An Evolutionary Algorithm for the biobjective QAP. In: Reusch, B. (ed). Computational Intelligence, Theory and Applications. Advances in Soft Computing, Springer series. 577–586. https://doi.org/10.1007/3-540-34783-6_55
Borgulya, I. (2008): An Algorithm for the Capacitated Vehicle Routing Problem with Route Balancing. Central European Journal of Operation Research, 16. 331–343. https://doi.org/10.1007/s10100-008-0062-2
Chen, A., Yang, G., Wu, Z. (2006): Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem. J Zhejiang Univ. Science A 7(4), 607–614. https://doi.org/10.1631/jzus.2006.A0607
Ganesh, K., Narendran, T. T. (2007): CLOVES: A cluster-and-search heuristic to solve the vehicle routing problem with delivery and pick-up. European Journal of Operational Research, 178(3), 699–717. https://doi.org/10.1016/j.ejor.2006.01.037
Hadjiconstantinou. E., Christofides, N. (1995): A new exact algorithm for the vehicle muting problem based on q-paths and k-shortest paths relaxations. Annals of Operations Research, 61, 21–43. https://doi.org/10.1007/BF02098280
Laporte, G. (1992): The vehicle routing problem: an overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345–358. https://doi.org/10.1016/0377-2217(92)90192-C
Lin, S-W., Lee, Z-J., Ying, K-C., Lee, C-Y. (2008): Applying hybrid meta-heuristics for capacitated vehicle routing problem. Expert Systems with Applications. https://doi.org/10.1016/j.eswa.2007.11.060
Mazzeo, S., Loiseau, I. (2004): An Ant Colony Algorithm for the Capacitated Vehicle Routing. Electronic Notes in Discrete Mathematics, 18. 181–186. https://doi.org/10.1016/j.endm.2004.06.029
Osman, I. H. (1993): Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem. Ann Oper Res, 41. 421–451. https://doi.org/10.1007/BF02023004
Prins, C. (2004): A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 31. 1985–2002. https://doi.org/10.1016/S0305-0548(03)00158-8
Russel, M., Lamont, G. B. (2005): A Genetic Algorithm for Unmanned Aerial Vehicle Rouiting. GECCO’05 Washington, DC, USA, ACM. 1523–1530. https://doi.org/10.1145/1068009.1068249
Sun, H., Xie, J., Xue, Y. (2005): A Sweep-Based TCNN Algorithm for Capacity Vehicle Routing Problem. Springer-Verlag Berlin Heidelberg, LNCS 3496, 756–761. https://doi.org/10.1007/11427391_121
Tavares, J., Pereira, F. B., Machado, P., Costa, E. (2003): On the Influence of GVR in Vehicle Routing. Proc. of the 2003 ACM Symposium On Applied Computing, Melbourne, Florida USA, 753–758. https://doi.org/10.1145/952532.952679
Toth, P., Vigo, D. (2003): The granular tabu search and its application to the vehicle- routing problem. INFORMS Journal on Computing, 15, 333–346. https://doi.org/10.1287/ijoc.15.4.333.24890
Van Breedam, A. (2001): Comparing descent heuristics and metaheuristics for the vehicle routing problem. Computers & Operations Research 28, 289–315. https://doi.org/10.1016/S0305-0548(99)00101-X
Downloads
Published
Issue
Section
License
Copyright (c) 2008 Borgulya István
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
