
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Hybrid ConsultantGuided Search for the Traveling Salesperson Problem
Hiroyuki EBARA Yudai HIRANUMA Koki NAKAYAMA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E97A
No.8
pp.17281738 Publication Date: 2014/08/01 Online ISSN: 17451337
DOI: 10.1587/transfun.E97.A.1728 Type of Manuscript: PAPER Category: Algorithms and Data Structures Keyword: ConsultantGuided Search, Traveling Salesperson Problem, Combinatorial Optimization Problem, Parallel Algorithm, Ant Colony Optimization,
Full Text: PDF(3MB)>>
Summary:
Metaheuristic methods have been studied for combinational optimization problems for some time. Recently, a ConsultantGuided Search (CGS) has been proposed as a metaheuristic method for the Traveling Salesperson Problem (TSP). This approach is an algorithm in which a virtual person called a client creates a solution based on consultation with a virtual person called a consultant. In this research, we propose a parallel algorithm which uses the Ant Colony System (ACS) to create a solution with a consultant in a ConsultantGuided Search, and calculate an approximation solution for the TSP. Finally, we execute a computer experiment using the benchmark problems (TSPLIB). Our algorithm provides a solution with less than 2% error rate for problem instances using less than 2000 cities.

