Improving the Efficiency of Helsgaun’s Lin-Kernighan Heuristic for the Symmetric TSP
2007 (English)In: Proceedings of the 4th conference on Combinatorial and Algorithmic Aspects of Networking (CAAN 2007) / [ed] J. Janssen and P. Pralat, Berlin-Heidelberg: Springer Berlin/Heidelberg, 2007, 99-111 p.Conference paper (Refereed)
Helsgaun has introduced and implemented the lower tolerances (-values) for an approximation of Held-Karp’s 1-tree with the purpose to improve the Lin-Kernighan Heuristic (LKH) for the Symmetric TSP (STSP). The LKH appears to exceed the performance of all STSP heuristic algorithms proposed to date. In this paper we improve Helsgaun’s LKH based on an approximation of Zhang and Looks’ backbones and an extension of double bridges further combined with implementation details by all of which we guide the search process instead of Helsgaun’s -values. Our computational results are competitive and lead to improved solutions for some of the VLSI instances announced at the TSP homepage.
Place, publisher, year, edition, pages
Berlin-Heidelberg: Springer Berlin/Heidelberg, 2007. 99-111 p.
, Lecture Notes in Computer Science, Volume 4852
IdentifiersURN: urn:nbn:se:umu:diva-84437ISBN: 3-540-77293-6ISBN: 978-3-540-77293-4OAI: oai:DiVA.org:umu-84437DiVA: diva2:684039
4th conference on Combinatorial and Algorithmic Aspects of Networking (CAAN 2007)