DocumentCode :
2554131
Title :
ABC-GSX: A hybrid method for solving the Traveling Salesman Problem
Author :
Banharnsakun, Anan ; Achalakul, Tiranee ; Sirinaovakul, Booncharoen
Author_Institution :
Dept. of Comput. Eng., King Mongkut´´s Univ. of Technol. Thonburi, Bangkok, Thailand
fYear :
2010
fDate :
15-17 Dec. 2010
Firstpage :
7
Lastpage :
12
Abstract :
An optimization problem is a problem of finding the best solution from all possible solutions. In most computer science and mathematical applications, the decision to select the best solution is not polynomially bounded. Heuristics approaches are thus often considered to solve such NP-hard problems. In our work, we focus on developing a heuristic method to solve a combinatorial optimization problem known as the Traveling Salesman Problem or TSP. Our technique implements the Artificial Bee Colony algorithm, which is inspired by the decision making process of the honey bees in finding optimal food sources. We extend the ABC algorithm with Greedy Subtour Crossover to improve the precision. In this hybrid procedure, the exploitation process in the ABC algorithm is improved upon by the Greedy Subtour Crossover method. The new proposed method is called ABC-GSX. We then empirically assess performance of our proposed work using functions from a standard TSP library. Experimental results show improvements in both precision and computational time compared to techniques presented in recent literatures.
Keywords :
travelling salesman problems; ABC-GSX; TSP; artificial bee colony algorithm; combinatorial optimization problem; greedy subtour crossover; heuristic method; traveling salesman problem; Workstations; Artificial Bee Colony; Greedy Subtour Crossover; Optimization; Swarm Intelligence; Traveling Salesman Problem;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Nature and Biologically Inspired Computing (NaBIC), 2010 Second World Congress on
Conference_Location :
Fukuoka
Print_ISBN :
978-1-4244-7377-9
Type :
conf
DOI :
10.1109/NABIC.2010.5716308
Filename :
5716308
Link To Document :
بازگشت