For Full-Text 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 Consultant-Guided Search for the Traveling Salesperson Problem
Hiroyuki EBARA Yudai HIRANUMA Koki NAKAYAMA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2014/08/01
Online ISSN: 1745-1337
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
Consultant-Guided Search, Traveling Salesperson Problem, Combinatorial Optimization Problem, Parallel Algorithm, Ant Colony Optimization,
Full Text: PDF(3MB)>>
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.