A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms

Publisher:
Elsevier B.V.
Publication Type:
Journal Article
Citation:
European Journal Of Operational Research, 2013, 228 (1), pp. 72 - 82
Issue Date:
2013-01
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2012001781OK.pdf685.35 kB
Adobe PDF
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.
Please use this identifier to cite or link to this item: