A Hybrid Distribution Algorithm Based on Membrane Computing for Solving the Multiobjective Multiple Traveling Salesman Problem

Abstract

The multiobjective multiple traveling salesman problem (MmTSP), in which multiple salesmen and objectives are involved in a route, is known to be NP-hard. The MmTSP is more appropriate for real-life applications than the classical traveling salesman problem (TSP), however it has not received the same amount of attention. Due to the high complexity of the MmTSP, a promising algorithm for solving it must be based on a global search procedure. This paper proposes a hybrid global search algorithm, that belongs to the membrane computing framework. The search behavior of the algorithm is enhanced by a communication mechanism. The multichromosome representation is considered to reduce the excess runtime. The effectiveness of the proposed algorithm is tested on the MmTSP with disparately-scaled objective functions, salesmen and problem sizes. The experimental results are compared with the NSGA-II and several evolutionary strategies with decomposition, including simulated annealing algorithm, hill climbing method, pure evolutionary algorithm, and genetic algorithm.