Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 228, Issue 1, Pages 72-82Publisher
ELSEVIER
DOI: 10.1016/j.ejor.2013.01.043
Keywords
Two-part chromosome; Crossover operator; MTSP; Genetic algorithms
Funding
- ARC Linkage Grant [LP0, 882, 745]
- Patrick Stevedores Holdings (PTS)
- University of Technology, Sydney, Australia (UTS)
Ask authors/readers for more resources
This paper proposes a new crossover operator called two-part chromosome crossover (TCX) for solving the multiple travelling salesmen problem (MTSP) using a genetic algorithm (GA) for near-optimal solutions. We adopt the two-part chromosome representation technique which has been proven to minimise the size of the problem search space. Nevertheless, the existing crossover method for the two-part chromosome representation has two limitations. Firstly, it has extremely limited diversity in the second part of the chromosome, which greatly restricts the search ability of the GA. Secondly, the existing crossover approach tends to break useful building blocks in the first part of the chromosome, which reduces the GA's effectiveness and solution quality. Therefore, in order to improve the GA search performance with the two-part chromosome representation, we propose TCX to overcome these two limitations and improve solution quality. Moreover, we evaluate and compare the proposed TCX with three different crossover methods for two MTSP objective functions, namely, minimising total travel distance and minimising longest tour. The experimental results show that TCX can improve the solution quality of the GA compared to three existing crossover approaches. Crown Copyright (C) 2013 Published by Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available