Comparison of crossover operators in genetic algorithm for vehicle routing problems

Genetic algorithm (GA) is a popular metaheuristic with wide-ranging applications, e.g. in routing problems such as traveling salesman problem (TSP) or vehicle routing problem (VRP). Seeking the best combination of parameters in GA application is the key objective in the line of research involving GA. One possible factor to be tested is the operator used for crossover. For VRP, a number of research reporting good performance use the order crossover (OX) operator. For TSP, one paper proposed the modified cycle crossover (CX2) operator and reported that it is better than OX and the partially mapped crossover (PMX). The interest and objective of this paper is to test these three operators in a VRP setting. Excluding the crossover operator, other good principles of GA for VRP obtained from the literature are maintained. The experiment results suggest these findings. Firstly, CX2 is expensive in run time and has difficulty escaping from local optimum but leads to the best fitness value compared to the other operators. Secondly, PMX ranks second both in the fitness performance and run time. Thirdly, while OX has slightly inferior performance, it is able to explore wider search space and therefore still has lots of potential for future research.