|
Vol: 58(72) No: 2 / June 2013 New Results in the Suitability Analysis of Using Blind Crossover Operators in Genetic Algorithms for Solving Routing Problems E. Osaba Department of Mobility, University of Deusto, Av Universidades, 24, Bilbao, 48007, Spain, e-mail: e.osaba@deusto.es R. Carballedo Department of Mobility, University of Deusto, Av Universidades, 24, Bilbao, 48007, Spain, e-mail: roberto.carballedo@deusto.es F. Diaz Department of Mobility, University of Deusto, Av Universidades, 24, Bilbao, 48007, Spain, e-mail: fernando.diaz@deusto.es E. Onieva Department of Mobility, University of Deusto, Av Universidades, 24, Bilbao, 48007, Spain, e-mail: enrique.onieva@deusto.es A. Perallos Department of Mobility, University of Deusto, Av Universidades, 24, Bilbao, 48007, Spain, e-mail: perallos@deusto.es Keywords: Genetic Algorithm, Crossover Operator, Combinatorial Optimization, Vehicle Routing Problems Abstract This paper aims to be an extension of the previously published work “Analysis of the suitability of using blind crossover operators in genetic algorithms for solving routing problems”. In that paper is shown that, when they are applied to routing problem, evolutionary algorithms (without using any crossover operator) can obtain similar results than genetic algorithms in much less time. In this next step of the research, that hypothesis is reinforced. For this purpose, a new analysis of the results has been conducted, and a new experimentation has been made with two different vehicle routing problems, the Capacitated Vehicle Routing Problem and the Vehicle Routing Problem with Backhauls. References [1] J. H. Holland, Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT Press, 1975. [2] K. De Jong, “Analysis of the behavior of a class of genetic adaptive systems,” Ph.D. dissertation, University of Michigan, Michigan, USA, 1975. [3] D. Goldberg, Genetic algorithms in search, optimization, and machine learning. Addison-Wesley Professional, 1989. [4] I. Harvey, “The microbial genetic algorithm,” Advances in Artificial Life. Darwin Meets von Neumann, vol. 5778, pp. 126–133, 2011. [5] M. Affenzeller, S. Wagner, and S. Winkler, Genetic algorithms and genetic programming: modern concepts and practical applications. Chapman & Hall/CRC, 2009, vol. 6. [6] J. Gao, M. Gen, L. Sun, and X. Zhao, “A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems,” Computers & Industrial Engineering, vol. 53, no. 1, pp. 149–162, 2007. [7] I. Moon, J.-H. Lee, and J. Seong, “Vehicle routing problem with time windows considering overtime and outsourcing vehicles,” Expert Systems with Applications,vol. 39, no. 18, pp. 13 202–13 213, 2012. [8] M. Martínez-Torres, “A genetic search of patterns of behaviour in oss communities,” Expert Systems with Applications, vol. 39, no. 18, pp. 13 182–13 192, 2012. [9] E. Osaba, R. Carballedo, F. Diaz, and A. Perallos, “Analysis of the suitability of using blind crossover operators in genetic algorithms for solving routing problems,” in Proceedings of IEEE 8th International Symposium on Applied Computational Intelligence and Informatics, Timisoara, Romania, 2013, pp. 17–23. [10] E. Lawler, J. Lenstra, A. Kan, and D. Shmoys, The traveling salesman problem: a guided tour of combinatorial optimization. Wiley New York, 1985, vol. 3. [11] G. Laporte, “The vehicle routing problem: An overview of exact and approximate algorithms,” European Journal of Operational Research, vol. 59, no. 3, pp. 345–358, 1992. [12] B. Golden, E. Baker, J. Alfaro, and J. Schaffer, “The vehicle routing problem with backhauling: two approaches,” in Proceedings of 21st Annual Meeting of SE TIMS, South Carolina, USA, 1985, pp. 90–92. [13] L. Davis, “Applying adaptive algorithms to epistatic domains,” in Proceedings of International Joint Conference on Artificial Intelligence, 1985, vol. 1, pp. 161–163. [14] C. Wang, J. Zhang, J. Yang, C. Hu, and J. Liu, “A modified particle swarm optimization algorithm and its application for solving traveling salesman problem,” in Proceedings of IEEE International Conference on Neural Networks and Brain, 2005, vol. 2. pp. 689–694. [15] M. Albayrak and N. Allahverdi, “Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms,” Expert Systems with Applications, vol. 38, no. 3, pp. 1313–1320, 2011. [16] S. Lin, “Computer solutions of the traveling salesman problem,” Bell System Technical Journal, vol. 44, no. 10, pp. 2245–2269, 1965. [17] C. Tarantilis and C. Kiranoudis, “A flexible adaptive memory-based algorithm for real-life transportation operations: Two case studies from dairy and construction sector,” European Journal of Operational Research, vol. 179, no. 3, pp. 806–822, 2007. [18] N. Bianchessi and G. Righini, “Heuristic algorithms for the vehicle routing problem with simultaneous pickup and delivery,” Computers & Operations Research, vol. 34, no. 2, pp. 578–594, 2007. [19] E. Osaba, E. Onieva, R. Carballedo, F. Diaz, and A. Perallos, “An adaptive multi-crossover population algorithm for solving routing problems,” in Nature Inspired Cooperative Strategies for Optimization (NICSO 2013). Springer, 2014, pp. 113–124. [20] G. Mattos Ribeiro and G. Laporte, “An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem,” Computers & Operations Research, vol. 39, no. 3, pp. 728–735, 2012. [21] S. Ngueveu, C. Prins, and R. Wolfler Calvo, “An effective memetic algorithm for the cumulative capacitated vehicle routing problem,” computers & Operations Research, vol. 37, no. 11, pp. 1877–1885, 2010. [22] Y. Gajpal and P. Abad, “Multi-ant colony system (macs) for a vehicle routing problem with backhauls,” European Journal of Operational Research, vol. 196, no. 1, pp. 102–117, 2009. [23] S. Anbuudayasankar, K. Ganesh, S. Lenny Koh, and Y. Ducq, “Modified savings heuristics and genetic algorithm for bi-objective vehicle routing problem with forced backhauls,” Expert Systems with Applications, vol. 39, no. 3, pp. 2296–2305, 2012. [24] P. J. Van Laarhoven and E. H. Aarts, Simulated annealing. Springer, 1987. [25] F. Glover, M. Laguna, Tabu search. Springer, 1997, vol. 22. |