An Opposition-Based Self-adaptive Differential Evolution with Decomposition for Solving the Multiobjective Multiple Salesman Problem

The multiple Traveling Salesman Problem (mTSP) is a complex combinatorial optimization problem, which is a generalization of the well-known Traveling Salesman Problem (TSP), where one or more salesmen can be used in the solution. In this paper, we propose a novel differential evolution algorithm called D-OSADE to solve the Multi-objective Multiple Salesman Problem. For the algorithm, an opposition-based self-adaptive differential evolution variant is incorporated into the decomposition-based framework, and then hybridized with the multipoint evolutionary gradient search (EGS) as a form of local search to enhance the search behaviour. The proposed algorithm is used to solve a multi-objective mTSP with different number of objectives, salesmen and problem sizes. Through the experimental results that are presented by employing the Inverted Generational Distance (IGD) performance indicator, the effectiveness and efficiency of the proposed algorithm can be observed and is seen to be able to achieve competitive performance when benchmarked against several state-of-the-art multi-objective evolutionary algorithms in this study.