HGELS: A New Hybrid Algorithm Based on Gravitational Force for Solving Multiple Traveling Salesman Problems

Subject Areas : B. Computer Systems Organization

Touraj Mohammadpour ¹ , Mehdi Yadollahi ² , Amir Massoud Bidgoli ³ , Habib Esmaeelzadeh Rostam ⁴

1 - Department of Computer Engineering, Ayatollah Amoli Branch, Islamic Azad University, Amol, Iran
2 - Department of Computer Engineering, Ayatollah Amoli Branch, Islamic Azad University, Amol, Iran
3 - Assistant Professor, B.Sc., M.Sc., Ph.D. (Manchester University), MIEEE, Tehran North Branch, Islamic Azad University, Tehran, Iran
4 - Department of Computer Engineering, Ghaemshahr Branch, Islamic Azad University, Ghaemshahr, Iran

Received: 2016-08-28 Accepted : 2016-08-28 Published : 2016-08-01

Keywords: Optimization, genetic algorithm, MTSP, GELS Algorithm,

Abstract :

Multiple Traveling Salesman Problem (MTSP) is one of the most popular operation research problem and is known as combinatorial optimization problems. MTSP is an extension version of the famous and widely used problem named Traveling Salesman Problem (TSP). Because of its benefices in various domains, many researchers have tried to solve that, and many methods have proposed so far. MTSP is a NP-complete problem so deterministic algorithms aren’t able to solve it in a reasonable time and in most cases heuristic methods are used. We propose a combination algorithm named at HGELS to solve MTSP in this paper. Our aim is to minimize the distance traveled by salesman and also the cost of path traveling. In fact, the proposed algorithm aims to balance the cost of path and distance. Experimental results indicate that the proposed algorithm needs more time to run than other algorithms, but in most cases has obtained better results.