Solving the Large-Scale TSP Problem in 1 h: Santa Claus Challenge 2020

Mariescu-Istodor, Radu and Fränti, Pasi (2021) Solving the Large-Scale TSP Problem in 1 h: Santa Claus Challenge 2020. Frontiers in Robotics and AI, 8. ISSN 2296-9144

[thumbnail of pubmed-zip/versions/1/package-entries/frobt-08-689908/frobt-08-689908.pdf] Text
pubmed-zip/versions/1/package-entries/frobt-08-689908/frobt-08-689908.pdf - Published Version

Download (8MB)

Abstract

The scalability of traveling salesperson problem (TSP) algorithms for handling large-scale problem instances has been an open problem for a long time. We arranged a so-called Santa Claus challenge and invited people to submit their algorithms to solve a TSP problem instance that is larger than 1 M nodes given only 1 h of computing time. In this article, we analyze the results and show which design choices are decisive in providing the best solution to the problem with the given constraints. There were three valid submissions, all based on local search, including k-opt up to k = 5. The most important design choice turned out to be the localization of the operator using a neighborhood graph. The divide-and-merge strategy suffers a 2% loss of quality. However, via parallelization, the result can be obtained within less than 2 min, which can make a key difference in real-life applications.

Item Type: Article
Subjects: Science Global Plos > Mathematical Science
Depositing User: Unnamed user with email support@science.globalplos.com
Date Deposited: 27 Jun 2023 07:05
Last Modified: 31 Oct 2023 04:57
URI: http://ebooks.manu2sent.com/id/eprint/1224

Actions (login required)

View Item
View Item