A Hybrid Estimation of Distribution Algorithm with Decomposition for Solving the Multiobjective Multiple Traveling Salesman Problem

Evolutionary multiobjective optimization with decomposition, in which the algorithm is not required to differentiate between the dominated and nondominated solutions, is one of the promising approaches in dealing with multiple conflicting objectives. In this paper, the estimation of distribution algorithm (EDA) is integrated into the decomposition framework. The search behavior of the algorithm is further enhanced by hybridizing local search metaheuristic approaches with the decomposition EDA. Three local search techniques, including hill climbing, simulated annealing, and evolutionary gradient search, are considered. A novel multiobjective formulation of the multiple traveling salesman problem is proposed. The hybrid algorithms are used to solve the formulated problem with different number of objective functions, salesmen, and problem sizes. The effectiveness and efficiency of the algorithms are tested and benchmarked against several state-of-the-art multiobjective evolutionary paradigms. © 1998-2012 IEEE.