# DualOpt: A Dual Divide-and-Optimize Algorithm for the Large-scale Traveling Salesman Problem

arXiv: https://arxiv.org/abs/2501.08565 · HTML: https://mlsanity.com/paper/2501.08565/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jan 2025.

## Built on by (most cited first, 8 of 8)

- [Learning to Segment for Vehicle Routing Problems](https://mlsanity.com/paper/2507.01037/) (2025)
- [GELD: A Unified Neural Model for Efficiently Solving Traveling Salesman Problems Across Different Scales](https://mlsanity.com/paper/2506.06634/) (2025)
- [Lifelong Learning with Behavior Consolidation for Vehicle Routing](https://mlsanity.com/paper/2509.21765/) (2025)
- [RsGCN: Subgraph-Based Rescaling Enhances Generalization of GCNs for Solving Traveling Salesman Problems](https://mlsanity.com/paper/2506.00533/) (2025)
- [TSP with Predictions: Heatmap to Tour with Provable Guarantees](https://mlsanity.com/paper/2607.03791/) (2026)
- [Graph Neural Network-based Algorithm Selection for the Traveling Salesman Problem: A Systematic Study of Cost and Rank Losses under Distinct Budget Regimes](https://mlsanity.com/paper/2607.18632/) (2026)
- [COMPASS: Ordered Clustered Routing at 100K Scale](https://mlsanity.com/paper/2609.20352/) (2026)
- [Compute Time Scaling with Recursive Models for Combinatorial Optimization](https://mlsanity.com/paper/2609.34585/) (2026)

## Abstract (arXiv)

This paper proposes a dual divide-and-optimize algorithm (DualOpt) for solving the large-scale traveling salesman problem (TSP). DualOpt combines two complementary strategies to improve both solution quality and computational efficiency. The first strategy is a grid-based divide-and-conquer procedure that partitions the TSP into smaller sub-problems, solving them in parallel and iteratively refining the solution by merging nodes and partial routes. The process continues until only one grid remains, yielding a high-quality initial solution. The second strategy involves a path-based divide-and-optimize procedure that further optimizes the solution by dividing it into sub-paths, optimizing each using a neural solver, and merging them back to progressively improve the overall solution. Extensive experiments conducted on two groups of TSP benchmark instances, including randomly generated instances with up to 100,000 nodes and real-world datasets from TSPLIB, demonstrate the effectiveness of DualOpt. The proposed DualOpt achieves highly competitive results compared to 10 state-of-the-art algorithms in the literature. In particular, DualOpt achieves an improvement gap up to 1.40% for the largest instance TSP100K with a remarkable 104x speed-up over the leading heuristic solver LKH3. Additionally, DualOpt demonstrates strong generalization on TSPLIB benchmarks, confirming its capability to tackle diverse real-world TSP applications.