Hybrid Consultant-Guided Search for the Traveling Salesperson Problem

Hiroyuki EBARA  Yudai HIRANUMA  Koki NAKAYAMA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E97-A   No.8   pp.1728-1738
Publication Date: 2014/08/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E97.A.1728
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
Keyword: 
Consultant-Guided Search,  Traveling Salesperson Problem,  Combinatorial Optimization Problem,  Parallel Algorithm,  Ant Colony Optimization,  

Full Text: PDF(3MB)>>
Buy this Article




Summary: 
Metaheuristic methods have been studied for combinational optimization problems for some time. Recently, a Consultant-Guided 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 Consultant-Guided 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.