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

Area of Science:

• Computer Science
• Operations Research
• Algorithmics

Background:

• Scalability of Traveling Salesperson Problem (TSP) algorithms for large instances remains a significant challenge.
• The Santa Claus challenge was established to address this by testing algorithms on a TSP instance exceeding 1 million nodes within a 1-hour time constraint.

Purpose of the Study:

• To analyze the performance of submitted algorithms for large-scale TSP instances under strict time limitations.
• To identify key design choices that contribute to effective TSP algorithm solutions within computational constraints.

Main Methods:

• Evaluation of three valid algorithm submissions for the Santa Claus challenge.
• Analysis focused on local search techniques, specifically k-opt (up to k=5).
• Investigation into the impact of operator localization using neighborhood graphs and divide-and-merge strategies.

Main Results:

• All valid submissions utilized local search methods, with k-opt (up to k=5) being a common feature.
• Localization of operators via neighborhood graphs was identified as the most critical design choice for performance.
• A 2% quality loss was observed with divide-and-merge strategies, but parallelization reduced computation time to under 2 minutes.

Conclusions:

• Neighborhood graph-based operator localization is crucial for efficient large-scale TSP solving.
• Parallelization significantly enhances the speed of TSP algorithms, making them practical for real-world applications.
• Local search algorithms, particularly when optimized with neighborhood graphs and parallelization, offer effective solutions for large-scale Traveling Salesperson Problems.