- Title
- An investigation of hybrid Tabu search for the traveling salesman problem
- Creator
- Xu, Dan; Weise, Thomas; Wu, Yuezhong; Lässig, Jörg; Chiong, Raymond
- Publisher Link
- http://dx.doi.org/10th International Conferenceon Bio-inspired Computing (BIC-TA 2015). Proceedings of the 10th International Conferenceon Bio-inspired Computing [presented in Bio-Inspired Computing - Theories and Applications] (Hefei, China 25-28 June, 2015) p. 523-537
- Publisher Link
- http://dx.doi.org/10.1007/978-3-662-49014-3_47
- Publisher
- Springer
- Resource Type
- conference paper
- Date
- 2015
- Description
- The Traveling Salesman Problem (TSP) is one of the most well-known problems in combinatorial optimization. Due to its NP-hardness, research has focused on approximate methods like metaheuristics. Tabu Search (TS) is a very efficient metaheuristic for combinatorial problems. We investigate four different versions of TS with different tabu objects and compare them to the Lin-Kernighan (LK) heuristic as well as the recently developed Multi-Neighborhood Search (MNS). LK is currently considered to be the best approach for solving the TSP, while MNS has shown to be highly competitive. We then propose new hybrid algorithms by hybridizing TS with Evolutionary Algorithms and Ant Colony Optimization. These hybrids are compared to similar hybrids based on LK and MNS. This paper presents the first statistically sound and comprehensive comparison taking the entire optimization processes of (hybrid) TS, LK, and MNS into consideration based on a large-scale experimental study. We show that our new hybrid TS algorithms are highly efficient and comparable to the state-of-the-art algorithms along this line of research.
- Subject
- traveling salesman problem; Tabu search; evolutionary algorithms; ant colony optimization; memetic algorithms
- Identifier
- http://hdl.handle.net/1959.13/1317156
- Identifier
- uon:23348
- Identifier
- ISBN:9783662490136
- Language
- eng
- Reviewed
- Hits: 1043
- Visitors: 1389
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|