Modification of the Ant Colony Optimization for Solving the Multiple Traveling Salesman Problem

作者：Yousefikhoshbakht Majid^*; Didehvar Farzad; Rahmati Farhad

来源：Romanian Journal of Information Science and Technology, 2013, 16(1): 65-80.

• Multiple Traveling Salesman Problem
• Ant Colony Optimization
• Updating Pheromone
• Combinatorial Optimization Problems

This article presents a new modified version of the ant colony optimization (ACO) mixed with insert, swap and 2-opt algorithm called NMACO for solving the multiple traveling salesman problem (MTSP) which utilizes an effective criterion for escaping from the local optimum points. The MTSP is one of the most important combinatorial optimization problems in which the objective is to minimize the distance traveled by several salesmen for servicing a set of nodes. Since this problem belongs to NP-hard Problems, some meta-heuristic approaches have been used to solve it in recent years. In contrast to the classical ACO, the proposed algorithm uses only a global updating for the current best solution and the best found solution until now. Furthermore, a new state transition rule and an efficient candidate list are used in order to assess the efficiency of the proposed algorithm. The proposed algorithm is tested on some standard instances available from the literature and their results were compared with other well-known meta-heuristic algorithms. The results indicate that the NMACO has been able to improve the efficiency of the ACO in all instances and is quite competitive with other meta-heuristic algorithms.

• 出版日期2013