Ant Colony Optimization Based Memetic Algorithm to Solve Bi-Objective Multiple Traveling Salesmen Problem for Multi-Robot Systems

Abstract

This paper considers the problem of having a team of mobile robots to visit a set of target locations. This problem is known as multi-robot patrolling problems. In this paper, the problem is formulated as a multiple traveling salesman problem (MTSP) with single depot or multiple depot, which is an nondeterministic polynomial-hard problem. Unlike most previous research works, in real-world applications, the requirement of optimizing the maximum traveled distance and the total traveled distance simultaneously widely exists. In this paper, a bi-objective ant colony optimization (ACO) based memetic algorithm is proposed to solve the problem. In the algorithm, a simple multi-ACO is integrated with a sequential variable neighborhood descent. A powerful local optimization method for bi-objective MTSP is proposed to improve the candidate solutions. In addition, we adopt the technique for order preference by similarity to an ideal solution method to select a reasonable solution from the optimal Pareto. Through computational experiments, we demonstrated the benefits of our algorithm as compared with four other existing algorithms. Computational results show that proposed algorithm is promising and effective for the bi-objective MTSPs.

Keywords

• Ant colony optimization
• memetic algorithm
• Pareto optimization
• multiple traveling salesmen problem