Evolutionary algorithm hybridized with local search and intelligent seeding for solving multi-objective Euclidian TSP

摘要

Multi-objective Euclidian TSP (ETSP) has several practical applications such as mobile computing and maritime surveillance. This problem has complexity not only in terms of combinatorial constraints but also in terms of multiple objectives. The local heuristic-based algorithms are extremely efficient in solving the single-objective ETSPs. However, their efficacy is limited in solving the multi-objective ETSPs due to the presence of multiple objectives. To bridge this gap, a two-stage evolutionary algorithm (TSEA) is developed to solve multi-objective ETSPs. In this algorithm, the first stage involves the use of a hybrid local search evolutionary algorithm (HLS-EA) which incorporates the local heuristic of nearest neighbor and 2-opt in the framework of real-coded NSGA-II to solve the individual objectives of multi-objective ETSP. These individual single-objective solutions which represent the corner solutions of the Pareto optimal front are used in the second stage as seed solutions in seeded HLS-EA (SHLS-EA) for solving the corresponding multi-objective ETSP. The developed algorithm is tested on 17 two-objective, 6 three-objective, and 2 four-objective ETSPs to show the superior performance over multiobjective variants of the Lin-Kernighan algorithm. Also, the developed algorithm is compared with several variants of DE and GA to illustrate the superior performance over the variants of evolutionary algorithms. Further, the algorithm is extended to the multi-objective ETSPs up to 10,000 cities.