Travelling Santa Problem: Optimization of a Million-Households Tour Within One Hour

Area of Science:

• Computational Science
• Operations Research
• Computer Science

Background:

• The Traveling Salesman Problem (TSP) is a classic optimization challenge.
• Solving large TSP instances is computationally intensive, limiting optimal solutions.
• Current research focuses on efficient sub-optimal solutions for time-constrained scenarios.

Purpose of the Study:

• To develop a novel, efficient algorithm for large-scale, two-dimensional symmetric TSP.
• To generate high-quality initial tours for problems exceeding a million coordinates within minutes.
• To improve upon existing state-of-the-art methods for TSP with non-uniform distributions.

Main Methods:

• A hierarchical clustering strategy is employed for tour construction.
• The approach supports parallel processing for enhanced efficiency.
• A path correction method is introduced to refine unfavorable routes.

Main Results:

• The proposed method generates good initial tours for large TSP instances in minutes.
• It demonstrates superior performance compared to state-of-the-art methods on non-uniformly distributed TSP instances.
• The approach effectively handles problems with over a million coordinates.

Conclusions:

• The novel hierarchical clustering approach offers an efficient solution for large-scale TSP.
• This method provides a practical way to find high-quality sub-optimal tours rapidly.
• It is particularly advantageous for TSP instances with complex, non-uniform coordinate distributions.