Karapetyan, Daniel and Gutin, Gregory (2011) Lin–Kernighan heuristic adaptations for the generalized traveling salesman problem. European Journal of Operational Research, 208 (3). pp. 221-232. DOI https://doi.org/10.1016/j.ejor.2010.08.011
Karapetyan, Daniel and Gutin, Gregory (2011) Lin–Kernighan heuristic adaptations for the generalized traveling salesman problem. European Journal of Operational Research, 208 (3). pp. 221-232. DOI https://doi.org/10.1016/j.ejor.2010.08.011
Karapetyan, Daniel and Gutin, Gregory (2011) Lin–Kernighan heuristic adaptations for the generalized traveling salesman problem. European Journal of Operational Research, 208 (3). pp. 221-232. DOI https://doi.org/10.1016/j.ejor.2010.08.011
Abstract
The Lin-Kernighan heuristic is known to be one of the most successful heuristics for the Traveling Salesman Problem (TSP). It has also proven its efficiency in application to some other problems. In this paper, we discuss possible adaptations of TSP heuristics for the generalized traveling salesman problem (GTSP) and focus on the case of the Lin-Kernighan algorithm. At first, we provide an easy-to-understand description of the original Lin-Kernighan heuristic. Then we propose several adaptations, both trivial and complicated. Finally, we conduct a fair competition between all the variations of the Lin-Kernighan adaptation and some other GTSP heuristics. It appears that our adaptation of the Lin-Kernighan algorithm for the GTSP reproduces the success of the original heuristic. Different variations of our adaptation outperform all other heuristics in a wide range of trade-offs between solution quality and running time, making Lin-Kernighan the state-of-the-art GTSP local search
Item Type: | Article |
---|---|
Additional Information: | 25 pages |
Uncontrolled Keywords: | Heuristics; Lin–Kernighan; Generalized traveling salesman problem; Combinatorial optimization |
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 24 May 2018 12:19 |
Last Modified: | 07 Aug 2024 20:09 |
URI: | http://repository.essex.ac.uk/id/eprint/22074 |
Available files
Filename: 1003.5330v2.pdf