Source-linked AI summary
Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning
Paulo R. de O. da Costa, Jason Rhuggenaath, Yingqian Zhang, Alp Akcay
TL;DR
The paper addresses the limited use of learned improvement heuristics for TSP, where construction methods often need extra search or sampling. It learns a stochastic 2-opt policy with policy gradients and pointer attention, achieving near-optimal solutions from poor initial tours and outperforming prior learned and classical 2-opt methods in reported comparisons.
Problem
Most deep-learning TSP methods learn construction heuristics and require additional search or sampling, while improvement heuristics have received comparatively little attention.
Method
The paper trains a deep reinforcement-learning policy with Policy Gradient to select 2-opt moves, using a neural architecture with graph and sequence embeddings and pointer attention.
Results
0.01%, 0.36% and 1.84% optimality gap for TSP20, TSP50 and TSP100, respectively, after 500 steps, while outperforming traditional construction heuristics and several learned baselines.
Takeaways & Limitations
The learned heuristic can improve poor or random initial solutions, approach near-optimal tours, outperform classical 2-opt, and reuse policies trained on smaller instances for larger TSP instances.
Takeaways & Limitations
Policy Gradient requires a large number of samples to train a good policy, motivating more sample-efficient methods.
Abstract
from arXiv · showhide
Recent works using deep learning to solve the Traveling Salesman Problem (TSP) have focused on learning construction heuristics. Such approaches find TSP solutions of good quality but require additional procedures such as beam search and sampling to improve solutions and achieve state-of-the-art performance. However, few studies have focused on improvement heuristics, where a given solution is improved until reaching a near-optimal one. In this work, we propose to learn a local search heuristic based on 2-opt operators via deep reinforcement learning. We propose a policy gradient algorithm to learn a stochastic policy that selects 2-opt operations given a current solution. Moreover, we introduce a policy neural network that leverages a pointing attention mechanism, which unlike previous works, can be easily extended to more general k-opt moves. Our results show that the learned policies can improve even over random initial solutions and approach near-optimal solutions at a faster rate than previous state-of-the-art deep learning methods.
1. Introduction
The TSP is computationally difficult, and traditional heuristics trade solution quality against runtime and expert design. Deep learning has mainly learned construction heuristics, motivating direct learning of improvement policies.
- The TSP seeks the shortest tour visiting every node exactly once and returning to the departure point, but is NP-hard even in Euclidean space.
- Exact methods guarantee optimality but are often computationally expensive, whereas heuristic methods use faster approximate moves such as k-opt.
- Designed heuristics require specialized knowledge, and their performance can be limited by algorithmic design decisions.
- Most learned TSP methods construct tours sequentially, but often require beam search, classical improvement heuristics, or sampling for stronger solutions.
- The paper learns a Policy Gradient improvement heuristic using 2-opt moves and a pointer-attention architecture for stochastic action selection.
- The learned policies approach near-optimal solutions from poor-quality initial tours and outperform prior deep-learning construction and improvement heuristics.
2. Related Work
Prior deep-learning TSP research largely learned construction heuristics using sequence, graph, attention, and reinforcement-learning models. This paper addresses the comparatively neglected problem of learning improvement policies directly.
- Early neural approaches included Hopfield networks and deformable templates, whose performance did not match classical heuristics.
- Pointer Networks learned sequence models with attention to construct TSP tours from solutions generated by Concorde.
- Graph attention, REINFORCE, and graph convolution methods improved learned construction, often combined with search heuristics.
- Previous methods commonly needed beam search, classical improvement heuristics, or sampling to obtain good solutions.
- Wu et al. learned 2-opt and node-swap improvement operations with fixed output embeddings tied to the squared number of nodes.
3. Background
The paper frames TSP improvement as sequential edge-swap search: 2-opt reverses a tour segment, offering a simpler operator than general k-opt but remaining vulnerable to local optima.
- 3.1. Travelling Salesman Problem: The Euclidean TSP seeks a minimum-length permutation of nodes, with tour cost defined as the sum of distances between consecutive nodes.
- 3.2. k-opt Heuristic for the TSP: Improvement heuristics iteratively replace a feasible solution with a shorter one through k edge swaps, including simpler 2-opt and 3-opt alternatives.
- 3.2. k-opt Heuristic for the TSP: Sequential k-opt operators can be decomposed into simpler l-opt moves; for example, sequential 3-opt can use up to three 2-opt operations.
- 3.2. k-opt Heuristic for the TSP: Local search can get stuck in local optima, and the initial solution usually affects the quality of the final solution.
- 3.2. k-opt Heuristic for the TSP: 2-opt replaces two tour edges and inverts the sequence between their selected endpoints.
- 3.2. k-opt Heuristic for the TSP: The proposed stochastic policy combines machine learning with 2-opt operators to explore improved solutions sequentially.
4. Reinforcement Learning Formulation
The method casts 2-opt TSP improvement as a Markov Decision Process whose policy selects node pairs while tracking both the current tour and the best tour found. Episodes and returns define the learning signal.
- States: Each state contains the current tour S and the lowest-cost tour S′ observed during the search.
- Actions: Actions are node-index pairs A = (a_1, a_2) with a_2 > a_1, specifying a 2-opt move.
- Transitions: A selected pair deterministically breaks two edges, reconnects them differently, and reverses the nodes between the selected positions.
- Rewards: Rewards are assigned to actions that improve the best solution found so far.
- The architecture uses dual encoders for graph and sequence information, with policy and value decoders producing actions and state values.
- Environment: Episodes restart from the previous episode’s last state, exposing the learner to poor solutions early and higher-quality solutions later.
- Returns: The objective maximizes cumulative discounted rewards until the episode horizon T.
5. Policy Gradient Neural Architecture
The architecture encodes the current and best-known tours alongside graph structure, then uses sequential pointing attention to select feasible 2-opt moves. A value decoder estimates state values from tour and graph representations.
- Policy Decoder: The policy decoder samples two node indices sequentially, factorizing each 2-opt action through the chain rule and updating queries with prior selections.
- Graph Convolutional Layers: GCN layers combine each node’s features with neighboring topology, producing richer node representations for the tour and graph.
- Sequence Embedding Layers: Bidirectional LSTMs read tours in both directions, explicitly encoding tour symmetry before combining forward and backward representations.
- Dual Encoding: The encoder processes the current solution S and best solution S′ independently, representing both tour structure and node ordering.
- Policy Decoder: Masking enforces increasing node-index choices, reducing the feasible action space to n(n −1)/2 permutations.
- Value Decoder: The value decoder combines pooled node representations with tour representations from S and S′ to estimate the current state value.
6. Policy Gradient Optimization
The model is optimized with policy gradients over uniformly sampled TSP states, using advantage estimates, entropy regularization, and a separately trained value network. Training progressively lengthens episodes to improve credit assignment over larger horizons.
- The objective maximizes expected rewards over uniformly distributed TSP graphs and uses sampled batches to estimate the policy gradient.
- The policy update uses an advantage function, while an entropy bonus discourages premature convergence to a sub-optimal policy.
- The value network is trained with mean squared error between predicted values and Monte Carlo return estimates.
- The combined objectives are optimized with ADAM, producing a method close to REINFORCE but with terminal-state bootstrapping and periodic episode-length updates.
7. Experiments and Results
Experiments evaluate learned 2-opt policies on Euclidean TSP20, TSP50, and TSP100, including convergence, comparisons with classical and learning methods, transfer to larger instances, and real-world instances. The policies reach near-optimal gaps, improve over several baselines, and can produce shorter tours with less time on TSP100.
- Experimental setup: The experiments use Euclidean TSP20, TSP50, and TSP100, with uniformly random training coordinates, fixed optimal-solution validation instances, and 10,000-instance test sets.The reported comparisons use shared test data where possible, while some prior results use the same generation process but different data.
- Convergence: The learned policies reduce validation optimality gaps over training epochs, with longer episode lengths improving validation performance and larger instances exhibiting larger gaps.Best policies quickly reduce gaps early, then fine-tune the best tour over later sampling steps.
- Classical heuristic comparison: On TSP100, the learned policy finds tours with lower median and less dispersion than classical 2-opt First Improvement and Best Improvement heuristics with restarts.The authors attribute this comparison to considering future rewards in 2-opt move selection and note avoidance of FI and BI's worst-case O(n2) next-solution selection complexity.
- Benchmark comparisons: 0.01%, 0.36% and 1.84% optimality gap are achieved on TSP20, TSP50 and TSP100 with 500 steps, outperforming traditional construction heuristics, greedy learning methods, and OR-Tools.At 500 steps, the method also outperforms prior reinforcement-learning methods using sampling or search, while GCN remains better under its larger beam width.
- Benchmark comparisons: 0.00% (TSP20), 0.12% (TSP50) and 0.87% (TSP100) optimality gaps are obtained after 2,000 sampling steps.The experiments also find optimal solutions for TSP20 and remain within 0.1% and 0.7% gaps for TSP50 and TSP100, respectively.
8. Conclusions and Future Work
The paper presents a deep reinforcement learning approach that approximates a 2-opt improvement heuristic for Euclidean TSPs. It reports lower optimality gaps than classical 2-opt and proposes sample efficiency and broader applications as future directions.
- The proposed method uses deep reinforcement learning to approximate a 2-opt improvement heuristic for the Euclidean TSP.
- The learned heuristics outperform state-of-the-art learned construction and improvement heuristics while requiring fewer samples.
- The authors identify sample efficiency, k-opt extensions, and improvement heuristics for broader combinatorial problems as future directions.
- On 35 TSPlib instances, the reported optimality gaps are 8.61% for the proposed method and 3.70% for OR-Tools.
Supplementary Material
The supplementary material presents a table comparing OR-Tools with the proposed method on TSPlib instances.
- The supplementary material evaluates OR-Tools and the proposed method on 35 TSPlib instances.
- Table 6 reports the performance comparison between OR-Tools and the proposed method on TSPlib instances.