Please use this identifier to cite or link to this item: https://hdl.handle.net/1959.11/61481
Title: Hybrid Ejection Chain Methods for the Traveling Salesman Problem
Contributor(s): Liu, Weichen (author); Weise, Thomas (author); Wu, Yuezhong (author); Chiong, Raymond  (author)orcid 
Publication Date: 2015
DOI: 10.1007/978-3-662-49014-3_25
Handle Link: https://hdl.handle.net/1959.11/61481
Abstract: 

Local search such as Ejection Chain Methods (ECMs) based on the stem-and-cycle (S&C) reference structure, Lin-Kernighan (LK) heuristics, as well as the recently proposed Multi-Neighborhood Search (MNS), are among the most competitive algorithms for the Traveling Salesman Problem (TSP). In this paper, we carry out a large-scale experiment with all 110 symmetric instances from the TSPLib to investigate the performances of these algorithms. Our study is different from previous work along this line of research in that we consider the entire runtime behavior of the algorithms, not just their end results. This leads to one of the most comprehensive comparisons of these algorithms to date. We introduce a new, improved S&C-ECM that can outperform LK and MNS. We then develop new hybrid versions of our ECM implementations by combining them with Evolutionary Algorithms and Population-based Ant Colony Optimization (PACO). We compare them to similar hybrids of LK and MNS. Our results show that hybrid PACO-S&C, PACO-LK and PACO-MNS are all very efficient. We also find that the full runtime behavior comparison provides deeper and clearer insights, while focusing on end results only would have led to a misleading conclusion.

Publication Type: Conference Publication
Conference Details: BIC-TA 2015: 10th International Bio-Inspired Computing -- Theories and Applications, Hefei, China, 25th - 28th September, 2015
Source of Publication: Bio-Inspired Computing -- Theories and Applications, 10th International Conference, BIC-TA 2015 Hefei, China, September 25-28, 2015, Proceedings, p. 268-282
Publisher: Springer - Verlag
Place of Publication: Germany
ISSN: 1865-0937
1865-0929
Fields of Research (FoR) 2020: 4602 Artificial intelligence
Peer Reviewed: Yes
HERDC Category Description: E1 Refereed Scholarly Conference Publication
Series Name: Communications in Computer and Information Science
Series Number : 562
Appears in Collections:Conference Publication
School of Science and Technology

Files in This Item:
1 files
File SizeFormat 
Show full item record

SCOPUSTM   
Citations

5
checked on Aug 24, 2024
Google Media

Google ScholarTM

Check

Altmetric


Items in Research UNE are protected by copyright, with all rights reserved, unless otherwise indicated.