TL;DR
This paper introduces a novel "select-and-optimize" iterative framework for solving large-scale Traveling Salesperson Problem (TSP) instances. By intelligently breaking down the problem into smaller, manageable sub-problems and using a specialized neural network to optimize them sequentially, the authors achieve significant speedups (over 2x) compared to existing learning-based methods, while maintaining competitive solution quality.
What Problem Does This Paper Address?
The Traveling Salesperson Problem (TSP) is a classic NP-hard problem in combinatorial optimization with wide-ranging applications. While traditional solvers like Concorde and heuristics like LKH3 are effective, they often require expert knowledge and can be slow for very large instances. More recently, deep learning approaches have shown promise, but they struggle to scale to extremely large TSP instances (tens of thousands of cities) due to challenges in training data acquisition and generalization. Existing learning-based methods often fail to produce high-quality solutions within a reasonable time for these large-scale problems.
Methods
The core of this work is a novel iterative framework called "select-and-optimize." Here's a breakdown of its key components:
- Iterative Sub-problem Optimization: Instead of trying to solve the entire large-scale TSP at once, the framework iteratively selects and optimizes small sub-paths (segments of the tour). This "divide and conquer" approach significantly reduces the computational burden at each step.
- Neural Selector-and-Optimizer Network: A custom Transformer-style Encoder-Decoder network is designed to:
- Select: Identify the most promising sub-problem (segment) that offers the greatest potential for improvement.
-
Optimize: Locally optimize the selected sub-problem to generate a better sub-solution. The network is trained using a policy gradient approach, leveraging the symmetry of the TSP to improve robustness.
-
Destroy-and-Repair Module: To prevent the iterative process from getting stuck in local optima, a "destroy-and-repair" mechanism is introduced. This module randomly perturbs the current solution by "destroying" long connections and then "repairing" them using a heuristic (like Lin-Kernighan) to escape local minima and find better global solutions.
- Initialization: The framework starts with an initial solution generated by an enhanced version of the POPMUSIC initialization algorithm, which aims to provide a good starting point for the iterative optimization.
Datasets
- Training Data: Generated TSP instances of sizes N=200, 500, and 1000. For the neural network models (SO50 and SO100), millions of samples were generated with data augmentation.
- Testing Data:
- Medium-scale: Generated instances with N=200, 500, 1000 (from Fu et al., 2021).
- Large-scale: Generated instances with N=2000, 5000, and 10000.
- Extremely large-scale: Generated instances with N=20000.
- Real-world: TSPLIB benchmark instances, categorized into 1000-2000 and 2000-6000 city groups.
Key Insights and Ideas
- Decomposition is Key for Scale: The paper strongly suggests that breaking down massive TSP instances into smaller, optimizable sub-problems is a highly effective strategy for achieving scalability in learning-based methods.
- Neural Network for Intelligent Selection: The neural selector-and-optimizer is crucial. It's not just about optimizing sub-problems, but about intelligently choosing which sub-problem to optimize next for maximum impact.
- Destroy-and-Repair for Escaping Local Minima: The destroy-and-repair module is vital for overcoming the inherent tendency of iterative optimization methods to get trapped in suboptimal solutions, especially when dealing with complex, large-scale problems.
- Symmetry is a Powerful Tool: Exploiting the inherent symmetry of TSP in the neural network architecture significantly improves performance and robustness.
Key Results
- Speedup: The proposed "select-and-optimize" framework achieves over 2x speedup compared to state-of-the-art learning-based algorithms on large-scale TSP instances.
- Solution Quality: The method maintains competitive solution quality, often approaching that of powerful heuristics like LKH3.
- Scalability: The framework successfully tackles TSP instances up to 20,000 cities, a scale that poses significant challenges for many existing learning-based approaches.
- Robustness: The method demonstrates more stable performance across different data distributions compared to some learning-based baselines, which can suffer from unstable results on atypical instances.
- Ablation Studies: Experiments confirm the importance of individual components: integrating tail embedding in the neural network and exploiting symmetry are crucial for performance. The destroy-and-repair module also shows a clear benefit for large-scale problems.
Limitations and Future Work
- Limitations:
- The paper acknowledges that while the method is vulnerable to local minima, the destroy-and-repair module helps mitigate this.
- For extremely large instances (TSP10000), GPU memory exceptions prevented the exploitation of sub-problem symmetry.
- Future Work:
- Broader Applications: Extend the framework to other large-scale combinatorial optimization problems (e.g., CVRP, Bin Packing).
- More Complex Constraints: Explore applications in real-world scenarios with more practical constraints and diverse data distributions.
- Hybrid Approaches: Investigate combining the select-and-optimize framework with other metaheuristics (like simulated annealing) or evolutionary algorithms to further enhance robustness against local optima.
Summary updated