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.
J. Heins and L. Schäpermeier—Equal contributions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Applegate, D.L., Bixby, R.E., Chvátal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study, vol. 17. Princeton University Press, Princeton (2011)
Bossek, J., Kerschke, P., Neumann, A., Wagner, M., Neumann, F., Trautmann, H.: Evolving diverse TSP instances by means of novel and creative mutation operators. In: Friedrich, T., Doerr, C., Arnold, D.V. (eds.) Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA), pp. 58–71. ACM (2019). https://doi.org/10.1145/3299904.3340307
Croes, G.A.: A method for solving traveling-salesman problems. Oper. Res. 6(6), 791–812 (1958). https://www.jstor.org/stable/167074
Dubois-Lacoste, J., Hoos, H.H., Stützle, T.: On the empirical scaling behaviour of state-of-the-art local search algorithms for the euclidean TSP. In: Silva, S., Esparcia-Alcázar, A.I. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pp. 377–384. ACM (2015). https://doi.org/10.1145/2739480.2754747
Heins, J., Bossek, J., Pohl, J., Seiler, M., Trautmann, H., Kerschke, P.: On the potential of normalized TSP features for automated algorithm selection. In: Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA), pp. 1–15. ACM (2021). https://doi.org/10.1145/3450218.3477308
Heins, J., Bossek, J., Pohl, J., Seiler, M., Trautmann, H., Kerschke, P.: A study on the effects of normalized TSP features for automated algorithm selection. Theoret. Comput. Sci. 940, 123–145 (2023). https://doi.org/10.1016/j.tcs.2022.10.019
Held, M., Karp, R.M.: The traveling-salesman problem and minimum spanning trees. Oper. Res. 18(6), 1138–1162 (1970). https://doi.org/10.1287/opre.18.6.1138
Held, M., Karp, R.M.: The traveling-salesman problem and minimum spanning trees: part II. Math. Program. 1(1), 6–25 (1971). https://doi.org/10.1007/BF01584070
Helsgaun, K.: An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126(1), 106–130 (2000). https://doi.org/10.1016/S0377-2217(99)00284-2
Helsgaun, K.: General k-opt submoves for the Lin-Kernighan TSP heuristic. Math. Program. Comput. 1, 119–163 (2009). https://doi.org/10.1007/s12532-009-0004-6
Kerschke, P., Bossek, J., Trautmann, H.: Parameterization of state-of-the-art performance indicators: a robustness study based on inexact TSP solvers. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) Companion, pp. 1737–1744. ACM (2018). https://doi.org/10.1145/3205651.3208233
Kerschke, P., Kotthoff, L., Bossek, J., Hoos, H.H., Trautmann, H.: Leveraging TSP solver complementarity through machine learning. Evol. Comput. 26(4), 597–620 (2018). https://doi.org/10.1162/evco_a_00215
Kotthoff, L., Kerschke, P., Hoos, H., Trautmann, H.: Improving the state of the art in inexact TSP solving using per-instance algorithm selection. In: Dhaenens, C., Jourdan, L., Marmion, M.-E. (eds.) LION 2015. LNCS, vol. 8994, pp. 202–217. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-19084-6_18
Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling-salesman problem. Oper. Re. 21(2), 498–516 (1973). https://doi.org/10.1287/opre.21.2.498
Nagata, Y., Kobayashi, S.: Edge assembly crossover: a high-power genetic algorithm for the traveling salesman problem. In: Proceedings of the 7th International Conference on Genetic Algorithms (ICGA), pp. 450–457 (1997)
Nagata, Y., Kobayashi, S.: A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem. INFORMS J. Comput. 25(2), 346–363 (2013). https://doi.org/10.1287/IJOC.1120.0506
Ribeiro, C.C., Hansen, P., Taillard, E.D., Voss, S.: POPMUSIC - partial optimization metaheuristic under special intensification conditions. In: Ribeiro, C.C., Hansen, P. (eds.) Essays and Surveys in Metaheuristics, pp. 613–629. Springer, New York (2002). https://doi.org/10.1007/978-1-4615-1507-4
Seiler, M.V., Rook, J., Heins, J., Preuß, O.L., Bossek, J., Trautmann, H.: Using reinforcement learning for per-instance algorithm configuration on the TSP. In: IEEE Symposium Series on Computational Intelligence (SSCI), pp. 361–368. IEEE (2023). https://doi.org/10.1109/SSCI52147.2023.10372008
Taillard, É.: Parallel iterative search methods for vehicle routing problems. Networks 23(8), 661–673 (1993). https://doi.org/10.1002/net.3230230804
Taillard, É.D., Helsgaun, K.: POPMUSIC for the travelling salesman problem. Eur. J. Oper. Res. 272(2), 420–429 (2019). https://doi.org/10.1016/J.EJOR.2018.06.039
Varadarajan, S., Whitley, L.D.: The massively parallel mixing genetic algorithm for the traveling salesman problem. In: Auger, A., Stützle, T. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pp. 872–879. ACM (2019). https://doi.org/10.1145/3321707.3321772
Xie, X.F., Liu, J.: Multiagent optimization system for solving the traveling salesman problem (TSP). IEEE Trans. Syst. Man Cybern. Part B (Cybern.) 39(2), 489–502 (2008). https://doi.org/10.1109/TSMCB.2008.2006910
Acknowledgments
The authors gratefully acknowledge the computing time made available to them on the high-performance computer at the NHR Center of TU Dresden. This center is jointly supported by the Federal Ministry of Education and Research and the state governments participating in the NHR (www.nhr-verein.de/unsere-partner). This research received financial support from the German Academic Exchange Service (DAAD) under the Program for Project-Related Personal Exchange (PPP). Lennart Schäpermeier and Pascal Kerschke acknowledge support by the Center for Scalable Data Analytics and Artificial Intelligence (ScaDS.AI) Dresden/Leipzig.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Heins, J., Schäpermeier, L., Kerschke, P., Whitley, D. (2024). Dancing to the State of the Art?. In: Affenzeller, M., et al. Parallel Problem Solving from Nature – PPSN XVIII. PPSN 2024. Lecture Notes in Computer Science, vol 15148. Springer, Cham. https://doi.org/10.1007/978-3-031-70055-2_7
Download citation
DOI: https://doi.org/10.1007/978-3-031-70055-2_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-70054-5
Online ISBN: 978-3-031-70055-2
eBook Packages: Computer ScienceComputer Science (R0)