A hierarchic approach based on swarm intelligence to solve the traveling salesman problem

Authors: MESUT GÜNDÜZ, MUSTAFA SERVET KIRAN, EREN ÖZCEYLAN

Abstract: The purpose of this paper is to present a new hierarchic method based on swarm intelligence algorithms for solving the well-known traveling salesman problem. The swarm intelligence algorithms implemented in this study are divided into 2 types: path construction-based and path improvement-based methods. The path construction-based method (ant colony optimization (ACO)) produces good solutions but takes more time to achieve a good solution, while the path improvement-based technique (artificial bee colony (ABC)) quickly produces results but does not achieve a good solution in a reasonable time. Therefore, a new hierarchic method, which consists of both ACO and ABC, is proposed to achieve a good solution in a reasonable time. ACO is used to provide a better initial solution for the ABC, which uses the path improvement technique in order to achieve an optimal or near optimal solution. Computational experiments are conducted on 10 instances of well-known data sets available in the literature. The results show that ACO-ABC produces better quality solutions than individual approaches of ACO and ABC with better central processing unit time.

Keywords: Ant colony optimization, artificial bee colony, path construction, path improvement, hierarchic approach, traveling salesman problem

Full Text: PDF