wikillm

Paper · 2020-04-03 · cs.LG, cs.AI, stat.ML

Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning

Learns a 2-opt improvement heuristic for the Euclidean TSP with policy gradient. A GCN and bidirectional-LSTM encoder feeds a pointer-attention decoder that picks two tour positions to reverse, trained with a learned critic. Author-reported: optimality gaps of 0.00%, 0.12% and 0.87% for TSP20, TSP50 and TSP100 after 2,000 sampled steps.

Neural combinatorial optimizationPolicy gradientAttention mechanismActor-criticcombinatorial-optimizationtraveling-salesmanlocal-searchreinforcement-learning

arXivPDFCodeMarkdown14 min read

AI-compiled by claude-haiku-5-5 on 2026-11-12, not yet reviewed by a human. Every claim cites its source; check it when a detail matters.

In plain words

The travelling salesman problem asks for the shortest loop through a set of cities. A common way to improve a loop is the 2-opt move: pick two edges, cut them, and reconnect the route by reversing the stretch between them. Keep making such moves while they help and the route gets better, but it can stop at a poor local best.

This paper trains a neural network to choose these moves. It starts from a random route, looks at the current route and the best route found so far, and proposes two positions to reverse. It learns by trial and error: a move that shortens the best-known route earns a reward, and the network is adjusted to make such moves more likely. Because it tries several samples and keeps the best route, a trained policy can work from a random start and reach routes close to the optimum.

The authors report that this beats earlier learned methods that build a route one city at a time, and that it does well against classical 2-opt and OR-Tools on the instance sizes they test. The reported figures come from the authors' own runs.

TL;DR

  • Learns the choice of 2-opt moves for the 2-D Euclidean TSP with policy gradient (REINFORCE-style) and a learned value baseline §5 §6.
  • Input: current tour and best tour, each encoded by a GCN with edge features followed by a bidirectional LSTM; output: two pointer choices over tour positions §5.1 §5.2.
  • Author-reported: 2,000 sampled steps give gaps of 0.00%, 0.12% and 0.87% on TSP20, TSP50 and TSP100 against Concorde tab. 1.
  • Epochs took 2m01s, 3m05s and 7m16s for TSP20, TSP50 and TSP100 on one RTX 2080Ti §7.1. Reported results use sampled moves at test time §7.2. The Paper vs code and Pitfalls sections list details where the code differs from the paper.
  • Code is public but has no LICENSE file, so it is cited, not reused.

Problem

Tour construction methods that learn to add one city at a time need extra search (beam search, sampling, classical improvement) to reach their best results §1. Learned improvement methods existed but had output heads tied to the number of possible moves, which made general k-opt moves harder to add §2. The paper targets the 2-D Euclidean TSP with n = 20, 50 and 100 nodes, with coordinates drawn uniformly in the unit square §3.1 §7.

Method

MDP. The state is a pair (S, S'), where S is the current tour and S' is the shortest tour seen so far in the current search §4. An action is a pair of positions (a1, a2) with a2 > a1, and the transition reverses the tour between them, which replaces two edges by two others §4, Transitions. The reward is the drop in the best-so-far length, R_t = L(S't) − L(S'{t+1}) [§4, Rewards]. Episodes have length T, and after each episode the next starts from the last state, so training sees both poor and good tours §4, Environment.

Encoder §5.1. Coordinates are embedded linearly to d = 128 dimensions. Pairwise edge weights are normalised with a symmetric rule and used in three residual graph-convolution layers eq. 1. The tour order is then read by two LSTM passes, one from the first node and one from the last, each started from the last (respectively first) node's state eq. 2 eq. 3. The two directions are combined per node by a tanh of two projections §5.1. The tour vector is the sum of the two final LSTM states §5.1. The current tour S and the best tour S' each have their own encoder.

Policy decoder §5.2. The action is factorised as a product of two pointer distributions, each a softmax eq. 4. A query is updated after each pointer from the previously pointed node's output eq. 5. The pointer score of each node is v^T tanh(K·node + Q·query), and the logits are clipped to [−C, C] with C = 10 eq. 6 §7.1. The first query combines projections of the two tour vectors with the max-pooled node embeddings of S §5.2. The first pointer must not choose the last position, and the second must lie after the first §5.2. Infeasible nodes get probability zero. The code also bars the last position for the first pointer, which the paper does not state (see Paper vs code).

Critic §5.3. The value is a two-layer head on the mean of the node embeddings of S plus projections of the two tour vectors eq. 7.

Training §6 alg. 1. Gradients come from a policy-gradient estimate with the advantage G − V eq. 8, an entropy bonus eq. 9, and a squared-error critic loss on Monte Carlo returns eq. 10. The objectives are combined and optimised with Adam §6. Each batch rolls out T steps, then updates the networks; returns are not bootstrapped beyond the segment §6. Episode length is increased during training §6 §7.1.

Pseudocode
# Apply a 2-opt move: reverse the tour between two positions  [§4]
def apply_two_opt(tour, first, second):
    # The paper keeps first < second; both bounds are inclusive
    low = min(first, second)
    high = max(first, second)
    tour[low:high + 1] = tour[low:high + 1][::-1]
    return tour
Pseudocode
# Node embedding and graph convolution, three layers  [§5.1] [eq. 1]
def graph_encode(coords):
    # coords: (B, n, 2); edges: (B, n, n), see Pitfalls
    edges = normalised_squared_distances(coords)
    nodes = linear_embed(coords)                    # (B, n, d)
    for layer in range(3):
        nodes = nodes + relu(edges @ linear_layer[layer](nodes))
    return nodes
Pseudocode
# Bidirectional LSTM over the tour order  [§5.1] [eq. 2] [eq. 3]
def sequence_encode(nodes_in_tour_order):
    # Forward pass starts from the last node, backward from the first
    fwd_out, fwd_state = lstm_forward(nodes_in_tour_order)
    bwd_out, bwd_state = lstm_backward(reversed(nodes_in_tour_order))
    # Per-node output combines the two directions  [§5.1]
    outputs = tanh(W_f @ fwd_out + W_b @ flip(bwd_out))   # (B, n, d)
    # Tour vector sums the final states of the two passes  [§5.1]
    tour_vector = fwd_state + bwd_state                    # (B, d)
    return outputs, tour_vector
Pseudocode
# Initial query: tour summaries plus max-pooled node features  [§5.2]
def initial_query(tour_vec, best_tour_vec, nodes):
    summary = concat(W_s @ tour_vec, W_s2 @ best_tour_vec)  # (B, d)
    return summary + max_over_nodes(nodes)                  # (B, d)
Pseudocode
# Pointer decoder: two positions, the second after the first  [§5.2]
# [eq. 4] [eq. 5] [eq. 6]
def sample_two_opt_move(query, outputs, fixed_start):
    # fixed_start: fixed random vector used as the first "previous" output
    previous = fixed_start                          # (d,)
    # First pointer cannot be the last position
    # [code: ActorCriticNetwork.py#L271-L277]
    feasible = positions < n - 1                    # (n,) bool
    actions = []
    for step in range(2):
        query = tanh(W_q @ query + W_o @ previous)  # (B, d)
        scores = v @ tanh(K @ outputs + Q @ query)  # (B, n)
        scores = C * tanh(scores)                   # clip, C = 10 [§7.1]
        probs = softmax(where(feasible, scores, -inf))
        index = sample(probs)                       # (B,)
        actions.append(index)
        # Second pointer must lie after the first  [§5.2]
        feasible = positions > index[:, None]       # (B, n)
        previous = gather(outputs, index)           # (B, d)
    return actions
Pseudocode
# Critic: mean-pooled nodes plus both tour summaries  [§5.3] [eq. 7]
def value(nodes, tour_vec, best_tour_vec):
    pooled = mean_over_nodes(nodes)                  # (B, d)
    summary = concat(W_v @ tour_vec, W_v2 @ best_tour_vec)
    hidden = relu(W_z @ (pooled + summary) + b_z)
    return W_r @ hidden + b_r                        # (B, 1)
Pseudocode
# Reward: drop in the best-so-far length, clipped at 1; else 0  [§4] [§7.1]
def reward(best_length, new_length):
    if new_length < best_length:
        return min(best_length - new_length, 1.0)
    return 0.0
Pseudocode
# One training update over a T-step segment  [alg. 1] [eq. 8-10]
def update(log_probs, values, rewards, entropies, epoch):
    # Discounted return from each step to the segment end, gamma = 0.99
    returns = discounted_returns(rewards, gamma=0.99)   # (T, B)
    # Normalise returns over the segment (not in the paper)
    returns = (returns - mean(returns)) / std(returns)
    advantage = returns - values
    # Policy term, averaged over the two pointers  [eq. 8] [alg. 1]
    policy_loss = -mean(mean_pointers(log_probs) * advantage.detach())
    # Critic term, weight beta_V = 0.5  [eq. 10]
    value_loss = 0.5 * mean(advantage ** 2)
    # Entropy bonus summed over steps, decayed by 0.9 each epoch  [eq. 9]
    decay = 0.9 ** (epoch + 1)
    entropy_bonus = beta_H * decay * mean_batch(sum_steps(entropies))
    loss = policy_loss + value_loss - entropy_bonus
    # One Adam step on the combined objective  [§6]
    adam_step(loss, lr=0.001, weight_decay=1e-5)
Pseudocode
# Training schedule  [§7.1] [alg. 1]
for epoch in range(epochs):
    for batch in random_instances(batch_size, n):   # uniform in [0,1]^2
        tours = start_tours(batch)                  # see Pitfalls
        for segment in range(200 // episode_len(epoch)):
            # Roll out T sampled 2-opt moves, then update  [§6]
            ...
    # Learning rate multiplied by 0.98 after each epoch  [§7.1]
    lr = lr * 0.98

Hyperparameters

All values come from the paper unless the column says otherwise. The code columns are the defaults in the repository; the README gives no run commands, so the per-size paper settings are not reproduced by the defaults alone.

NameValueWhereNotes
node dimension d128§7.1code default 128 PGTSP50_100.py
GCN layers3§7.1 eq. 1ActorCriticNetwork.py
LSTM blocks1§7.1n_rnn_layers default 1 PGTSP50_100.py
clip C10 (training and test)§7.1 eq. 6Attention default C=10 ActorCriticNetwork.py
batch size B512 (TSP20, TSP50); 256 (TSP100)§7.1code default 512 for every size PGTSP50_100.py; 256 needs a flag
mini-batches per epoch10 (TSP20, TSP50); 20 (TSP100)§7.1code default train_size 5,120 PGTSP50_100.py
epochs200 (TSP20); 300 (TSP50, TSP100)§7.1defaults match PGTSP20.py PGTSP50_100.py
step limit in training200§7.1PGTSP50_100.py
episode length TTSP20: 8, 10 from epoch 100, 20 from epoch 150. TSP50: 8, 10 from epoch 100, 20 from epoch 200. TSP100: 4, 8 from epoch 100, 10 from epoch 200§7.1code starts TSP100 at 8 by default; see Paper vs code
discount γ0.99§7.1PGTSP50_100.py
learning rate0.001, multiplied by 0.98 each epoch§7.1StepLR, stepped each epoch PGTSP50_100.py PGTSP50_100.py
optimiserAdam, ℓ2 penalty 1e-5§7.1Adam betas 0.9, 0.999 are not stated in the paper; code defaults PGTSP50_100.py
entropy weight β_H0.0045 (TSP20, TSP50); 0.0018 (TSP100); multiplied by 0.9 each epoch§7.1 §6code default 0.005 PGTSP50_100.py
value weight β_V0.5§7.1PGTSP50_100.py
reward clip1§7.1TSPEnvironment.py
mixed precisionused for TSP50 and TSP100§7.1apex AMP O1 PGTSP50_100.py; no apex import in PGTSP20.py
gradient clippingnot stated—a max norm of 0.3 is defined but the clip is commented out PGTSP50_100.py PGTSP50_100.py
initialisationv and o_0 uniform in ±1/√d; others PyTorch defaults§7.1o_0 is fixed, not trained ActorCriticNetwork.py
training instancesuniform random in [0,1]^2§6 §7DataGenerator.py
validationfixed instances with known optima; 256 in the validation plots§7 fig. 3PGTSP50_100.py
test (Table 1)10,000 instances per size, same as Kool et al.§7the card cannot confirm which script produced Table 1
test defaults in repo512 instances, 2,000 steps, seed 1234—TestLearnedAgent.py TestLearnedAgent.py TestLearnedAgent.py

Results

Author-reported. Setup: 10,000 test instances per size, optimal costs from Concorde §7.2 tab. 1. Gap is the average optimality gap. Times are for 10,000 instances; the authors' own rows were timed on an RTX 2080Ti, and the other rows' times are as reported by their sources §7.2.

MethodTypeTSP20 gapTSP50 gapTSP100 gapTSP20 / 50 / 100 timeSource
Concorde (reference)Solver0.00%0.00%0.00%1m / 2m / 3mtab. 1
OR-ToolsS0.37%1.83%2.90%—tab. 1
GAT (greedy)RL0.34%1.76%4.53%0s / 2s / 6stab. 1
GAT, 1280 samplesRL,S0.08%0.52%2.26%5m / 24m / 1htab. 1
GCN, beam + shortest tourSL,BS0.01%0.01%1.39%12m / 18m / 40mtab. 1
GAT-T, 1,000 stepsRL0.03%0.83%3.24%12m / 16m / 25mtab. 1
GAT-T, 5,000 stepsRL0.00%0.20%1.42%1h / 1h / 2htab. 1
This paper, 500 stepsRL0.01%0.36%1.84%5m / 7m / 10mtab. 1
This paper, 1,000 stepsRL0.00%0.21%1.26%10m / 13m / 21mtab. 1
This paper, 2,000 stepsRL0.00%0.12%0.87%15m / 29m / 41mtab. 1

The GAT-T figures are as reported by Wu et al. because no implementation was available at submission; the data there is not the same test set but has the same generation process §7.1.

Policies trained on TSP50 applied to TSP100 tab. 2: 500 steps 2.78%, 1,000 steps 1.86%, 2,000 steps 1.37%. The TSP100-trained policy gives 1.84%, 1.26% and 0.87% at the same step counts.

Ablation, TSP50, 512 instances, 1,000 steps, ten trials tab. 3:

VariantOpt. gap at epoch 10 (%)CostOpt. gap at epoch 200 (%)Cost
Proposed3.00 ± 0.085.870.22 ± 0.015.72
(a) without bi-LSTM203.87 ± 0.6117.33134.42 ± 0.5613.37
(b) without GCN9.74 ± 0.086.260.30 ± 0.015.72
(c) single direction17.94 ± 0.156.732.20 ± 0.055.82
(d) without best solution4.55 ± 0.045.960.22 ± 0.025.72
(e) shared encoder5.15 ± 0.066.000.23 ± 0.015.72

Same sample budget as GAT on the same hardware tab. 4. Times are for this method vs GAT. At 500 samples: 5m vs 3m (TSP20, this method slower), 7m vs 10m (TSP50), 10m vs 27m (TSP100). At 2,000 samples: 15m vs 5m (TSP20), 29m vs 22m (TSP50), 41m vs 1h13m (TSP100).

TSPLib tab. 5 [supp.]: on 10 instances the method beats OR-Tools on 5, with an average gap of 4.56% vs 3.79%. On the 35 instances in the supplement the gaps are 8.61% (this method, 2,000 steps) and 3.70% (OR-Tools).

Figures fig. 3 shows validation gaps during training for TSP20, TSP50 and TSP100 over 200 steps; longer episodes improved validation. fig. 4 shows best-tour gaps over 2,000 sampled steps on 512 test instances. fig. 5 shows that on TSP100 the learned policy, with 1,000 steps, has a lower median and spread than first- and best-improvement 2-opt with restarts.

Paper vs code

Code: https://github.com/paulorocosta/learning-2opt-drl at commit e06045e90aa45f2f5ea90776aa07e41cb9f18532. It is linked from the paper's own footnote, and its owner name matches the first author, Paulo R. de O. da Costa. Searched: the paper's footnote (found it). The repository has no LICENSE file, so it is cited for comparison only and not reused. Citations below are to the code at that commit.

  • Edge input. Paper: Euclidean distances, normalised symmetrically §5.1. Code: squared Euclidean distances, then divided by the square roots of the two row sums, with no square root taken utils.py ActorCriticNetwork.py.
  • Sequence RNNs. Paper writes one RNN function for the start state and the sequence §5.1 eq. 2. Code builds two LSTM modules per direction, one for the start state and one for the sequence ActorCriticNetwork.py ActorCriticNetwork.py.
  • First pointer. Paper says only a2 > a1 §5.2. Code also forbids the last position for the first pointer ActorCriticNetwork.py.
  • Return normalisation. Not in the paper. Code standardises returns over segment and batch before computing the advantage PGTSP50_100.py. Turn off with --no_norm_return.
  • Log-probabilities. The code averages the log-probability over the two pointers PGTSP50_100.py, which matches the 1/k in Algorithm 1 alg. 1 but not the plain policy-gradient equation eq. 8.
  • Gradient clipping. Paper: not stated. Code defines a max norm of 0.3 but never applies it PGTSP50_100.py.
  • Batch size and entropy weight. Paper: B = 256 for TSP100 and β_H = 0.0045 / 0.0018 §7.1. Code defaults: B = 512 and β_H = 0.005 for all sizes PGTSP50_100.py PGTSP50_100.py.
  • TSP100 episode length. Paper: T starts at 4 §7.1. Code starts at the default 8 and changes only at epochs 100 and 200 PGTSP50_100.py.
  • Other schedules match. TSP20 episode lengths and epochs PGTSP20.py; TSP50 episode lengths PGTSP50_100.py; learning-rate decay 0.98 per epoch PGTSP50_100.py; ℓ2 1e-5 PGTSP50_100.py.
  • Query initialisation order. The code concatenates the S' projection first, the paper the S projection first §5.2 ActorCriticNetwork.py. Same network, different weight order; no effect on the function class.
  • Test-time sampling. Paper reports sampled 2-opt moves §7.2. The test loop calls the same sampling policy, so there is no greedy option TestLearnedAgent.py.
  • Unverified. I did not re-run the released checkpoints (best_policy/) or the 10,000-instance evaluation behind Table 1.

Pitfalls

  • Distance encoding. The paper's normalisation formula is ambiguous (its subscripts do not say which sums are over which index). The code uses squared distances; an implementation that uses plain distances will not match the code's behaviour utils.py.
  • Masking and renormalisation. Code writes −∞ into infeasible logits, which the clip turns into −C, then multiplies by the mask and lets the categorical distribution renormalise ActorCriticNetwork.py ActorCriticNetwork.py. The result equals a softmax over the feasible positions only if you renormalise. Skipping that step leaks probability to infeasible positions.
  • Entropy weight scales with episode length. The entropy term is summed over the segment while the policy term is averaged over it PGTSP50_100.py. Changing T therefore changes the effective entropy weight, even with β unchanged.
  • Entropy decay starts at epoch 1. The code multiplies β by 0.9^(epoch+1), so the first epoch already uses 0.9β PGTSP50_100.py. The paper says only "after every epoch".
  • Update count. There is one optimiser step per T-step segment, so with 200 steps and T = 8 each mini-batch gets 25 updates per epoch. The paper's sample-efficiency comparison counts samples, not updates, so compare with care §7.1 PGTSP50_100.py.
  • Starting tour. The start is the identity order of the instance's points, not a shuffle TSPEnvironment.py. Random training points make this effectively random, but on a fixed test file the start tour follows the file's point order.
  • Reward precision. Distances are multiplied by 10⁴ and rounded to integers TSPEnvironment.py, and rewards are rounded to four decimals TSPEnvironment.py. Improvements below 10⁻⁴ in unit-square length are lost.
  • Mixed precision. The 50/100 script uses apex AMP at O1 PGTSP50_100.py. Numerics differ from fp32, and the script needs apex installed.
  • Hidden-state bug, dormant. If a hidden state is passed to the encoder, the cell state is overwritten with the hidden state ActorCriticNetwork.py. Training and validation pass hidden=None, so the bug does not fire there PGTSP50_100.py PGTSP50_100.py. Do not carry hidden state across steps without fixing this.
  • Sampling variance. All reported numbers come from sampled trajectories, with only ablations giving ± values tab. 3. Expect run-to-run variance, and report the step count with every number.
  • Cost of the search. Each step runs an O(n) pointer over all positions for two pointers, and the batched edge matrix is n×n per instance. The authors report time, not memory, for TSP100 tab. 1.
  • Generalisation claim. Policies trained on TSP50 are applied to TSP100 and the paper reports this works tab. 2. Its TSPLib comparison with OR-Tools is less favourable, and the authors say the difference grows on large instances §7.2 tab. 5.

Lineage

  • Builds on the Pointer Network of Vinyals et al. (2015) for the pointing decoder, and on Bello et al. (2017) for the chain-rule factorisation of the pointer probabilities and the logit clipping §2 §5.2.
  • Uses symmetric normalisation of edge weights following Kipf and Welling. The method is close to REINFORCE and to A2C, bootstrapping only from terminal states §5.1 §6.
  • Compared against: the construction methods of Kool et al. (2018), Deudon et al. (2018) and others, the supervised GCN of Joshi et al. (2019), and the improvement policy GAT-T of Wu et al. (2019), which the paper names as the best learned improvement heuristic it compares with §2 §7.2.
  • Classical baselines: OR-Tools and first- and best-improvement 2-opt §7.2.
  • Superseded by: not established from content in this wiki.

Source and license

Adapted from “Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning” by Paulo R. de O. da Costa, Jason Rhuggenaath, Yingqian Zhang, Alp Akcay (arXiv:2004.01608), used under CC BY 4.0. Changes: condensed and restructured for implementation, with tables, equations and algorithms taken from the paper and its code, each cited to its source. Not affiliated with or endorsed by the authors. Code citations refer to https://github.com/paulorocosta/learning-2opt-drl at commit e06045e90aa4 (none (no LICENSE file in repository)). Any quoted code is shown under that license.