Comparison of crossover operators in genetic algorithm for vehicle routing problems

Wibisono, Eric and Martin, Iris and Prayogo, Dina Natalia (2021) Comparison of crossover operators in genetic algorithm for vehicle routing problems. In: Second Asia Pacific International Conference on Industrial Engineering and Operations Management, September 14-16, 2021, Surakarta.

[thumbnail of Eric_Wibisono-2nd_APIEOM_Indonesia-2021.pdf] PDF
Eric_Wibisono-2nd_APIEOM_Indonesia-2021.pdf

Download (277kB)
[thumbnail of Eric_Wibisono-2nd_APIEOM_Indonesia_Abstract_2021.pdf] PDF
Eric_Wibisono-2nd_APIEOM_Indonesia_Abstract_2021.pdf
Restricted to Registered users only

Download (79kB) | Request a copy

Abstract

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.

Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: Genetic algorithm, Vehicle routing problem, Crossover operator
Subjects: H Social Sciences > HD Industries. Land use. Labor > HD28 Management. Industrial Management
Divisions: Faculty of Engineering > Department of Industrial Engineering
Depositing User: Eko Setiawan 194014
Date Deposited: 10 Sep 2021 09:37
Last Modified: 10 Sep 2021 09:37
URI: http://repository.ubaya.ac.id/id/eprint/40276

Actions (login required)

View Item View Item