IEICE TRANSACTIONS on Fundamentals
Hybrid Consultant-Guided Search for the Traveling Salesperson Problem
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.8 pp.1728-1738
- Publication Date
- 2014/08/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E97.A.1728
- Type of Manuscript
- PAPER
- Category
- Algorithms and Data Structures
Authors
Hiroyuki EBARA
Kansai University
Yudai HIRANUMA
Kansai University
Koki NAKAYAMA
Kansai University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hiroyuki EBARA, Yudai HIRANUMA, Koki NAKAYAMA, "Hybrid Consultant-Guided Search for the Traveling Salesperson Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E97-A, no. 8, pp. 1728-1738, August 2014, doi: 10.1587/transfun.E97.A.1728.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.1728/_p
Copy
@ARTICLE{e97-a_8_1728,
author={Hiroyuki EBARA, Yudai HIRANUMA, Koki NAKAYAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Hybrid Consultant-Guided Search for the Traveling Salesperson Problem},
year={2014},
volume={E97-A},
number={8},
pages={1728-1738},
abstract={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.},
keywords={},
doi={10.1587/transfun.E97.A.1728},
ISSN={1745-1337},
month={August},}
Copy
TY - JOUR
TI - Hybrid Consultant-Guided Search for the Traveling Salesperson Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1728
EP - 1738
AU - Hiroyuki EBARA
AU - Yudai HIRANUMA
AU - Koki NAKAYAMA
PY - 2014
DO - 10.1587/transfun.E97.A.1728
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 8
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - August 2014
AB - 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.
ER -
English
