Solving the Traveling Salesperson Problem (TSP) remains a persistent challenge, despite its fundamental role in numerous generalized applications in modern contexts. Heuristic solvers address the demand for finding high-quality solutions efficiently. Among these solvers, the Lin-Kernighan-Helsgaun (LKH) heuristic stands out, as it complements the performance of genetic algorithms across a diverse range of problem instances. However, frequent timeouts on challenging instances hinder the practical applicability of the solver. Within this work, we investigate a previously overlooked factor contributing to many timeouts: The use of a fixed candidate set based on a tree structure. Our investigations reveal that candidate sets based on Hamiltonian circuits contain more optimal edges. We thus propose to integrate this promising initialization strategy, in the form of POPMUSIC, within an efficient restart version of LKH. As confirmed by our experimental studies, this refined TSP heuristic is much more efficient – causing fewer timeouts and improving the performance (in terms of penalized average runtime) by an order of magnitude – and thereby challenges the state of the art in TSP solving.
%0 Conference Paper
%1 390f1dc791c64639beedced999d08aa6
%A Heins, Jonathan
%A Schäpermeier, Lennart
%A Kerschke, Pascal
%A Whitley, Darrell
%B Parallel Problem Solving from Nature – PPSN XVIII
%D 2024
%E Affenzeller, Michael
%E Winkler, Stephan M.
%E Kononova, Anna V.
%E Bäck, Thomas
%E Trautmann, Heike
%E Tusar, Tea
%E Machado, Penousal
%I Springer, Berlin u. a.
%K topic_engineering Algorithm Benchmarking, Configuration, FIS_scads Hardness, Heuristic Problem Salesperson Search, Traveling
%P 100--115
%R 10.1007/978-3-031-70055-2_7
%T Dancing to the State of the Art?: How Candidate Lists Influence LKH for Solving the Traveling Salesperson Problem
%X Solving the Traveling Salesperson Problem (TSP) remains a persistent challenge, despite its fundamental role in numerous generalized applications in modern contexts. Heuristic solvers address the demand for finding high-quality solutions efficiently. Among these solvers, the Lin-Kernighan-Helsgaun (LKH) heuristic stands out, as it complements the performance of genetic algorithms across a diverse range of problem instances. However, frequent timeouts on challenging instances hinder the practical applicability of the solver. Within this work, we investigate a previously overlooked factor contributing to many timeouts: The use of a fixed candidate set based on a tree structure. Our investigations reveal that candidate sets based on Hamiltonian circuits contain more optimal edges. We thus propose to integrate this promising initialization strategy, in the form of POPMUSIC, within an efficient restart version of LKH. As confirmed by our experimental studies, this refined TSP heuristic is much more efficient – causing fewer timeouts and improving the performance (in terms of penalized average runtime) by an order of magnitude – and thereby challenges the state of the art in TSP solving.
%@ 978-3-031-70054-5
@inproceedings{390f1dc791c64639beedced999d08aa6,
abstract = {Solving the Traveling Salesperson Problem (TSP) remains a persistent challenge, despite its fundamental role in numerous generalized applications in modern contexts. Heuristic solvers address the demand for finding high-quality solutions efficiently. Among these solvers, the Lin-Kernighan-Helsgaun (LKH) heuristic stands out, as it complements the performance of genetic algorithms across a diverse range of problem instances. However, frequent timeouts on challenging instances hinder the practical applicability of the solver. Within this work, we investigate a previously overlooked factor contributing to many timeouts: The use of a fixed candidate set based on a tree structure. Our investigations reveal that candidate sets based on Hamiltonian circuits contain more optimal edges. We thus propose to integrate this promising initialization strategy, in the form of POPMUSIC, within an efficient restart version of LKH. As confirmed by our experimental studies, this refined TSP heuristic is much more efficient – causing fewer timeouts and improving the performance (in terms of penalized average runtime) by an order of magnitude – and thereby challenges the state of the art in TSP solving.},
added-at = {2024-11-28T16:27:18.000+0100},
author = {Heins, Jonathan and Sch{\"a}permeier, Lennart and Kerschke, Pascal and Whitley, Darrell},
biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/260eaec0d419a8bcac9bc9846fd3ae425/scadsfct},
booktitle = {Parallel Problem Solving from Nature – PPSN XVIII},
day = 7,
doi = {10.1007/978-3-031-70055-2_7},
editor = {Affenzeller, Michael and Winkler, {Stephan M.} and Kononova, {Anna V.} and B{\"a}ck, Thomas and Trautmann, Heike and Tu{\v s}ar, Tea and Machado, Penousal},
interhash = {65ea902fd115c421cc331a5015bc5e56},
intrahash = {60eaec0d419a8bcac9bc9846fd3ae425},
isbn = {978-3-031-70054-5},
keywords = {topic_engineering Algorithm Benchmarking, Configuration, FIS_scads Hardness, Heuristic Problem Salesperson Search, Traveling},
language = {English},
month = sep,
note = {Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.},
pages = {100--115},
publisher = {Springer, Berlin [u. a.]},
series = {Lecture Notes in Computer Science},
timestamp = {2024-11-28T17:41:02.000+0100},
title = {Dancing to the State of the Art?: How Candidate Lists Influence LKH for Solving the Traveling Salesperson Problem},
year = 2024
}
