Crossover and Diversity: A Study about GVR



Genetic Vehicle Representation (GVR) is a
two level representational scheme, designed
to deal in an e®ective way with all the in-
formation needed by candidate solutions, for
the Vehicle Routing Problem (VRP). In this
paper, we present an analysis on the in°u-
ence of two crossover operators in the algo-
rithm performance. A ¯rst study on diver-
sity is also presented, regarding the issues
of diversity measurement and possible rela-
tions to the algorithm performance. Results
show that for GVR one type of crossover is
more suited for solving VRP instances, and
both operators may not avoid the loss of di-
versity. Nevertheless, solutions discovered by
GVR are competitive and are the best ones
found by an evolutionary algorithm.


Representations, Diversity, Crossover, Vehicle Routing Problem


Evolutionary Optimization


a bird-of-a-feather workshop at the 2003 Genetic and Evolutionary Computation Conference (GECCO-2003), July 2003

Cited by

Year 2015 : 1 citations

 Genetic Algorithm Approach for a Class of Multi-Criteria, Multi-Vehicle Planner of UAVs
E Freitas, JRH Carvalho - Evolutionary Multi-Criterion Optimization, 2015 - Springer

Year 2012 : 1 citations

 K Pulji?. An evolutionary algorithm based on repeated mutations for solving the capacitated vehicle routing problem. Journal of Computing and Information Technology, 2012.

Year 2010 : 3 citations

 M. Chavez, O. Parra, Evolutionary algorithm for the vehicles routing problem with time windows, in Computation Y Sistemas, Vol. 13, nº 3, pp. 257-272, 2010.

 Neil Urquhart, Emma Hart and Cathy Scott (2010). Building low CO2 solutions to the Vehicle Routing Problem with Time Windows using an Evolutionary Algorithm. WCCI 2010 IEEE World Congress on Computational Intelligence - IEEE CEC, pp. 3161-3168, July, 18-23, 2010 - CCIB, Barcelona, Spain, IEEE, 2010.

 Naoto Mukai and Kosuke Kawamura, "Simulation evaluation for on-demand bus system with electrical vehicles", Intelligent Decision Technologies, Vol.4, N. 4, pp.307-314, 2010, DOI - 10.3233/IDT-2010-0092

Year 2009 : 4 citations

 Ferdinand de Bakker, \textbf{Phoenix " Non-cooperative bargaining agents}, Master of Media and Knowledge Engineering, Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, The Netherlands, August 2009.

 JY Potvin. State-of-the Art Review—Evolutionary Algorithms for Vehicle Routing. INFORMS Journal on Computing, 2009.

 JE Mendoza, AL Medaglia, N Velasco. An evolutionary-based decision support system for vehicle routing: The case of a public utility. Decision Support Systems, 2009 - Elsevier.

 Z Ursani, D Essam, D Cornforth, R Stocker. Introducing the localized genetic algorithm for small scale capacitated vehicle routing problems. INFOR: Information Systems and Operational Research, 2009.

Year 2008 : 4 citations

 Tadahiko Murata, and Ryota Itai, \textbf{Enhancing Solution Similarity in Multi-Objective Vehicle Routing Problems with Different Demand Periods}, In Vehicle Routing Problem, Tonci Caric and Hrvoje Gold (Editors), Chapter 7, In-Teh Publishers, September 2008, ISBN 978-953-7619-09-1

 H. Sallam, C. S. Regazzoni, I. Talkhan, and A. Atiya, Measuring the Genotype Diversity of Evolvable Neural Networks, In Proceedings of the Sixth International Conference INFOS2008, Egypt, 27-28 March, 2008.

 H. Sallam, C. S. Regazzoni, I. Talkhan and A. Atiya (2008). The Effect of Genetic Operations on the Diversity of Evolvable Neural Networks. IADIS International Conference Intelligent Systems and Agents 2008, pp. 143-150.

 Abel Garcia Najera, \textbf{A First Multi-ob jective Genetic Algorithm Approach To Solving
The Vehicle Routing Problem With Time Windows}, Technical Report, School of Computer Science, University of Birmingham, February 2008.

Year 2007 : 5 citations

 Jean-Yves Potvin, Evolutionary Algorithms for Vehicle Routing, Technical Report CIRRELT-2007-48, Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), November, 2007.

 Jorge E. Mendoza, Andres L. Medaglia, and Nubia M. Velasco, "An evolutionary based decision support system for vehicle routing: the case of a public utility", Departamento de Ingenier?a Industrial, Universidad de los Andes, COPA 2007-1, September 2007.

 Abel Garcia Najera, Population-based techniques for multi-ob jective optimization, Technical Report, School of Computer Science, University of Birmingham, August 2007.

 Abel Garcia Najera, A Genetic Algorithm for the Capacitated Vehicle Routing Problem, Technical Report, School of Computer Science, University of Birmingham, February, 2007.

 Tadahiko Murata and Ryota Itai (2007). Local Search in Two-Fold EMO Algorithm to Enhance Solution Similarity for Multi-objective Vehicle Routing Problems. In Evolutionary Multi-Criterion Optimization, pp. 201-215, LNCS Volume 4403, Springer Berlin/Heidelberg, 2007.

Year 2006 : 2 citations

 Guillermo González Vargas, and Felipe González Aristizábal, "Metaheuristics applied to vehicle routing. A case study. Parte 1: formulating the problem", Revista Ingeniería e Investigación, vol.26 no.3, Bogotá, December 2006.

 Oliver Kunze, Tourenplanung für den eCommerce-Lebensmittel-Heimlieferservice, PhD Thesis, Fakultät für Maschinenbau, Universität Karlsruhe, Germany, March, 2006.

Year 2005 : 4 citations

 Cheng-Hung Tseng, Theory and Implementation of an Intelligent Vehicle Dispatching System, Master's Thesis, Graduate Institute of Information Engineering, Feng Chia University, Taiwan, 2005.

 Tadahiko Murata1 and Ryota Itai1, Multi-objective Vehicle Routing Problems Using Two-Fold EMO Algorithms to Enhance Solution Similarity on Non-dominated Solutions, Evolutionary Multi-Criterion Optimization: Third International Conference, EMO 2005, Guanajuato, Mexico, March 9-11, 2005.

 M. Russel, and G. Lamont A Genetic Algorithm for Unmanned Aerial Vehicle Routing, In Proceedings of the Genetic and Evolutionary Computation Conference, Washinghton D.C., USA, 25-29 June, 2005.

 M. Russel, A Genetic Algorithm for UAV Routing Integrated with a parallel Swarm Simulation, Master Thesis, Department of the Air Force Air University, Air Force Institute of Technology, Wright-Patterson Air Force Base, May, 2005.

Year 2003 : 1 citations

 Wei-Che Chuang, An Inheritable Heuristic Algorithm for Bi-criteria Vehicle Routing Optimization Problems with Time Windows, Master's Thesis, Graduate Institute of Information Engineering, Feng Chia University, Taiwan, 2003.