Hybrid evolutionary algorithms for the Multiobjective Traveling Salesman Problem

In the Multiobjective Traveling Salesman Problem (moTSP) simultaneous optimization of more than one objective functions is required. In this paper, three hybrid evolutionary algorithms with common characteristics are proposed and analyzed for the solution of the Multiobjective Traveling Salesman Problem. The two hybrid evolutionary algorithms are based on Differential Evolution algorithm and the third one is a hybridized version of the NSGA II. One of the challenges of the proposed algorithms is the efficient application of an algorithm, the Differential Evolution algorithm, which is suitable for continuous optimization problems, in a combinatorial optimization problem. Thus, we test two different versions of the algorithm, the one with the use of an external archive (denoted as MODE) and the other using the crowding distance (denoted as NSDE). Also, another novelty of the proposed algorithms is the use of three different mutation operators in each of the two versions of the Differential Evolution algorithm leading to six different algorithms (MODE1, MODE2 and MODE3 for the first version and NSDE1, NSDE2 and NSDE3 for the second version). We use in each algorithm a Variable Neighborhood Search (VNS) procedure in each solution separately in order to increase the exploitation abilities of the algorithms. In order to give the quality of the algorithms, experiments are conducted using classic Euclidean Traveling Salesman Problem benchmark instances taken from the TSP library. Also, we use a number of different evaluation measures in order to conclude which of the three algorithms is the most suitable for the solution of the selected problem. In general, the proposed algorithms can easily be applied in all multiobjective routing problems by changing the objective function and the constraints of the problem and they have the ability to use more than two objective functions (in the paper we test the algorithm with up to five different objective functions). The hybridized use of the global search algorithm, the Differential Evolution, with the Variable Neighborhood Search increases the exploration and the exploitation abilities of the algorithms giving very effective evolutionary multiobjective optimization algorithms. (C) 2015 Elsevier Ltd. All rights reserved.