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

Journal of Advances in Computer Research

شناسنامه علمی شماره، دوره 7، شماره 3 - شماره پیاپی 25، آبان 2016، صفحه 131-142   

نویسندگان

Touraj Mohammadpour^{* 1}؛ Mehdi Yadollahi¹؛ Amir Massoud Bidgoli²؛ Habib Esmaeelzadeh Rostam³

¹Department of Computer Engineering, Ayatollah Amoli Branch, Islamic Azad University, Amol, Iran

²Assistant Professor, B.Sc., M.Sc., Ph.D. (Manchester University), MIEEE, Tehran North Branch, Islamic Azad University, Tehran, Iran

³Department of Computer Engineering, Ghaemshahr Branch, Islamic Azad University, Ghaemshahr, Iran

چکیده

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.

کلیدواژه‌ها

MTSP؛ Optimization؛ genetic algorithm؛ GELS Algorithm