Solving Multiple Traveling Salesman Problem using the Gravitational Emulation Local Search Algorithm

Multiple Travelling Salesman Problem (mTSP) is one of the most popular and widely used combinatorial optimization problems in the operational research. Many complex problems can be modeled and solved by the mTSP. To solve the mTSP, deterministic algorithms cannot be used as the mTSP is an NP-hard optimization problem. Hence, heuristics approaches are usually applied. In this paper, the Gravitational Emulation Local Search (GELS) algorithm is modified to solve the symmetric mTS P. The GELS algorithm is based on the local search concept and uses two main parameters in physics, velocity and gravity. Performance of the modified GELS has been compared with well-known optimization algorithms such as the genetic algorithm (GA) and ant colony optimization (ACO). Simulation results show superiority of the modified GELS over the other common optimization algori thms.