An Improved NSGA-II Algorithm for Multi-objective Traveling Salesman Problem

Yabo Luo (Hunan Institute of Engineering)
Min Liu (Hunan University of Science and Technology)
Zhongxiao Hao (Hebei University of Engineering)
Dongbo Liu (Hunan Institute of Engineering)

Indonesian Journal of Electrical Engineering and Computer Science
Vol 12, No 6: June 2014

Multi-objective traveling salesman problem (MOTSP) is an extended instance of traveling salesman problem (TSP), which is a well-known NP hard problem. In this paper, an improved NSGA-II algorithm (denoted by INSGA-II-MOTSP) is proposed to solve the MOTSP. Specifically, a layer strategy according to need is proposed to avoid generating unnecessary non-dominated fronts. The arena’s principle is also adopted to construct non-dominated set, so as to reduce the count of dominance comparison. In addition, an order crossover like operator and an inversion mutation operator are adopted for MOTSP. The experiment results show that the proposed INSGA-II-MOTSP algorithm is able to find better spread of solutions compared to other three algorithms. DOI : http://dx.doi.org/10.11591/telkomnika.v12i6.5476