Sam Austinon November 5, 202614 min read

Solve the Traveling Salesman Problem with Reinforcement Learning

Solve the Traveling Salesman Problem with Reinforcement Learning
Contents

Figure 1: Solve the Traveling Salesman Problem with Reinforcement Learning — twenty cities is small enough to train on a laptop and honest enough to expose a weak baseline

A salesperson needs to visit 20 cities and come home. The number of possible tours is 19!/2, roughly 60 quadrillion. Your laptop cannot check them all, but a small neural network can learn to build a decent tour in milliseconds.

I have not run this at industrial scale, so treat it as a learning project. I did run every line below on a laptop and measure it against two baselines, and the numbers are less flattering than the tutorials suggest. TSP is still the best sandbox for RL on optimisation, precisely because the baselines are strong enough to keep you honest.

What Is the TSP?

The traveling salesman problem asks for the shortest closed tour that visits every city exactly once. This post uses the Euclidean version: random points in a unit square, cost equal to straight-line distance.

TSP is NP-hard, so exact solvers slow down as cities multiply. Specialised solvers like Concorde and LKH-3 still handle huge instances well, which sets a high bar for any neural method [2][3].

How RL Frames the TSP

The tour is built one city at a time, which turns it into a sequential decision problem:

  1. State: city coordinates, the partial tour, the set of unvisited cities.
  2. Action: pick the next unvisited city.
  3. Reward: negative total tour length, paid at the end.
  4. Masking: block cities already visited.

This is the constructive approach popularised by pointer networks and the attention model of Kool and colleagues [1]. Training uses REINFORCE with a baseline, which keeps the code short enough to read in one sitting.

Setting Up

pip install torch numpy matplotlib ortools

The run behind this post used PyTorch 2.15.0+cpu, NumPy 2.5.3 and OR-Tools 9.15.6755 on Python 3.12. Library versions change, so check the docs if an import fails [4].

Building the Model

The model has two parts: an encoder that turns each city into an embedding, and a decoder that picks the next city by attending over those embeddings. This is a simplified design, not the full Kool architecture.

import math
import torch
import torch.nn as nn

class TSPPolicy(nn.Module):
    def __init__(self, dim=64, heads=8, layers=2):
        super().__init__()
        self.embed = nn.Linear(2, dim)
        enc = nn.TransformerEncoderLayer(
            dim, heads, dim_feedforward=256, batch_first=True)
        self.encoder = nn.TransformerEncoder(enc, layers)
        self.ctx = nn.Linear(3 * dim, dim)   # graph, first, last
        self.q = nn.Linear(dim, dim, bias=False)
        self.k = nn.Linear(dim, dim, bias=False)
        self.dim = dim

    def forward(self, coords, greedy=False):
        B, N, _ = coords.shape
        h = self.encoder(self.embed(coords))
        graph = h.mean(1)
        keys = self.k(h)
        visited = torch.zeros(B, N, dtype=torch.bool, device=coords.device)
        idx = torch.arange(B, device=coords.device)
        first = last = None
        tour, logps = [], []

        for t in range(N):
            if t == 0:
                f = l = torch.zeros_like(graph)
            else:
                f, l = h[idx, first], h[idx, last]
            query = self.q(self.ctx(torch.cat([graph, f, l], -1)))
            scores = (keys @ query.unsqueeze(-1)).squeeze(-1) / math.sqrt(self.dim)
            scores = 10 * torch.tanh(scores)             # clip logits
            scores = scores.masked_fill(visited.clone(), float("-inf"))
            dist = torch.distributions.Categorical(logits=scores)
            nxt = scores.argmax(-1) if greedy else dist.sample()
            logps.append(dist.log_prob(nxt))
            tour.append(nxt)
            visited[idx, nxt] = True
            if t == 0:
                first = nxt
            last = nxt

        return torch.stack(tour, 1), torch.stack(logps, 1).sum(1)

That visited.clone() is not cosmetic. Without it, PyTorch raises "one of the variables needed for gradient computation has been modified by an inplace operation" on the second training step, because masked_fill saved the mask for backward and the next iteration flipped bits in the same tensor. It is the first bug you will hit, and it has nothing to do with your model.

Why Masking Matters

The masked_fill line sets visited cities to negative infinity, so the agent can never revisit one. Penalties teach that slowly and unreliably; masking guarantees a valid tour every time.

Computing Tour Length

def tour_length(coords, tour):
    idx = torch.arange(coords.size(0), device=coords.device).unsqueeze(1)
    ordered = coords[idx, tour]
    rolled = torch.roll(ordered, -1, dims=1)
    return (ordered - rolled).norm(dim=-1).sum(1)

The roll closes the loop by connecting the last city back to the first.

Training with REINFORCE

REINFORCE alone gives noisy gradients, so subtract a baseline: the mean tour length of the batch. Kool's paper uses a rollout baseline, which performs better [1].

device = "cpu"
N, BATCH, STEPS = 20, 128, 800

model = TSPPolicy().to(device)
opt = torch.optim.Adam(model.parameters(), lr=1e-4)

for step in range(STEPS):
    coords = torch.rand(BATCH, N, 2, device=device)
    tour, logp = model(coords)
    length = tour_length(coords, tour)
    advantage = (length - length.mean()).detach()
    loss = (advantage * logp).mean()   # minimise length

    opt.zero_grad()
    loss.backward()
    nn.utils.clip_grad_norm_(model.parameters(), 1.0)
    opt.step()

    if step % 200 == 0:
        print(f"step {step} | mean length {length.mean().item():.3f}")

Random cities appear in every batch, so the policy cannot memorise one instance. In this run the training mean fell from 9.940 at step 0 to 5.001, 4.634 and 4.500 at steps 200, 400 and 600, and the whole 800 steps took 1.7 minutes on CPU.

If your number never drops, check the advantage sign first. Minimising advantage * logp pushes down the probability of above-average tours, which is the behaviour you want.

Baselines You Must Run

A neural result means nothing in isolation.

Nearest Neighbour

import numpy as np

def nearest_neighbor(pts):
    n = len(pts)
    unvisited = set(range(1, n))
    tour = [0]
    while unvisited:
        last = pts[tour[-1]]
        nxt = min(unvisited, key=lambda j: np.linalg.norm(pts[j] - last))
        tour.append(nxt)
        unvisited.remove(nxt)
    return tour

def np_length(pts, tour):
    p = pts[tour]
    return np.linalg.norm(p - np.roll(p, -1, axis=0), axis=1).sum()

OR-Tools

OR-Tools needs integer distances, so scale the coordinates.

from ortools.constraint_solver import pywrapcp, routing_enums_pb2

def solve_ortools(pts, seconds=1, scale=10000):
    n = len(pts)
    D = (np.linalg.norm(pts[:, None] - pts[None], axis=-1) * scale).astype(int)
    manager = pywrapcp.RoutingIndexManager(n, 1, 0)
    routing = pywrapcp.RoutingModel(manager)

    def cb(i, j):
        return int(D[manager.IndexToNode(i)][manager.IndexToNode(j)])

    routing.SetArcCostEvaluatorOfAllVehicles(routing.RegisterTransitCallback(cb))
    params = pywrapcp.DefaultRoutingSearchParameters()
    params.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    params.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
    params.time_limit.FromSeconds(seconds)
    sol = routing.SolveWithParameters(params)
    idx, tour = routing.Start(0), []
    while not routing.IsEnd(idx):
        tour.append(manager.IndexToNode(idx))
        idx = sol.Value(routing.NextVar(idx))
    return tour

Use params.time_limit.FromSeconds(seconds), not .seconds = seconds. Both work in current builds, but the method is the documented API and survives version changes [4].

Evaluating Fairly

Test on fresh instances the model never saw, and print the per-instance comparison rather than only the mean:

model.eval()
rng = np.random.default_rng(123)
rows = []
for _ in range(50):
    pts = rng.random((N, 2)).astype(np.float32)
    with torch.no_grad():
        t, _ = model(torch.tensor(pts).unsqueeze(0), greedy=True)
    rl = np_length(pts, t[0].numpy())
    nn_ = np_length(pts, nearest_neighbor(pts))
    ort = np_length(pts, solve_ortools(pts))
    rows.append((rl, nn_, ort))

rl, nn_, ort = np.mean(rows, axis=0)
print(f"RL {rl:.3f} | NN {nn_:.3f} | OR-Tools {ort:.3f}")
print(f"RL gap vs OR-Tools: {(rl - ort) / ort * 100:.1f}%")

What the Numbers Actually Showed

Fifty fresh 20-city instances and twenty fresh 50-city instances, same seeds for every method:

Method 20 cities Gap vs OR-Tools 50 cities Gap vs OR-Tools
RL, greedy decode 4.207 +8.4% 6.889 +20.8%
RL, best of 50 samples 4.001 +3.1% 6.940 +21.7%
Nearest neighbour 4.551 +17.2% 6.924 +21.4%
OR-Tools, 1 s 3.882 best 5.702 best

Three things are worth more than the mean. First, the policy beat nearest neighbour on 37 of 50 instances at its trained size, and never beat OR-Tools on any. Second, sampling 50 tours and keeping the shortest closed the gap from 8.4% to 3.1% — the cheapest improvement available, and it costs 50 forward passes. Third, at 50 cities the same policy scored 6.889 against nearest neighbour's 6.924 and the solver's 5.702, so the out-of-distribution collapse is real and it lands right at the baseline you were trying to beat.

Greedy inference took 9.7 ms per instance at 20 cities and 21.7 ms at 50 on CPU. That is the entire selling point: 400× faster than a one-second solver run, at 8.4% worse quality — and on a GPU, batched, the throughput argument gets much stronger.

How to Improve Your Policy

Try these in order:

  1. Sample many tours at inference and keep the best. This moved 8.4% to 3.1% here.
  2. Use a rollout baseline: compare each sample against a greedy rollout of the same model, as Kool did [1].
  3. Add POMO-style multiple starts, rolling out from every city and sharing the reward [5].
  4. Add 2-opt post-processing. A cheap local search usually closes most of the remaining gap.
  5. Train longer and with a bigger encoder before adding architectural complexity.
  6. Scale gradually: 20 to 50 cities only after the small version works.

Common Pitfalls

  1. Training on one instance. The policy memorises it and fails everywhere else.
  2. Skipping the mask. The agent revisits cities and produces invalid tours.
  3. Comparing against nothing. Always race nearest neighbour and OR-Tools.
  4. Testing on training data. Use fresh random instances, and report the spread.
  5. Ignoring generalisation. A 20-city policy scored at nearest-neighbour level at 50 cities in this run.
  6. Hitting the in-place mask error and assuming the model is wrong. It is a tensor-versioning bug, not an architecture problem.

Most failures in this pipeline come from setup and evaluation, not from the neural network.

Best Book to Read

CoverBookDescriptionGet it
Cover of “In Pursuit of the Traveling Salesman” In Pursuit of the Traveling Salesmanby William J. Cook the story of the problem and the solvers that actually crack it, from cutting planes to Concorde, and the clearest explanation of why the bar for a learned heuristic is so high. View on Amazon

As an Amazon Associate I earn from qualifying purchases. Links on this page are affiliate links, and I may earn a commission at no extra cost to you.

Read it after you have run the code once. It makes the difference between "my policy beats random" and "my policy beats the state of the art" impossible to confuse.

Wrapping Up

You built a constructive RL pipeline: an attention policy, a masked decoder, REINFORCE training and two baselines. It beat nearest neighbour at the size it trained on and lost to a one-second solver run everywhere, which is the honest result for a laptop-scale TSP policy.

So run the script this week, then change one thing: the baseline, the city count, or the decoding strategy. If your policy beats nearest neighbour, that is a real result. If OR-Tools still crushes it, welcome to the club — and see the routing comparison for where neural policies do earn their keep.

Frequently Asked Questions

Can a reinforcement learning model solve the TSP better than OR-Tools?

Not on quality at 20 or 50 cities. In the benchmark for this post, OR-Tools reached a mean tour of 3.882 at 20 cities while the trained policy reached 4.207, an 8.4% gap that sampling narrowed to 3.1%. The policy wins on nothing except raw inference speed and batch throughput.

Why does the training loop crash with an in-place modification error?

Because the visited mask is mutated while autograd still needs its old value. masked_fill saves the mask for backward, and the next iteration flips bits in the same tensor. Pass visited.clone() to masked_fill, or rebuild the mask each step.

What baseline should I use for a TSP policy?

Nearest neighbour and a solver, both on the same instances. Nearest neighbour is the floor a trained policy must clear, and OR-Tools with guided local search is the practical ceiling. A mean tour length printed without either is not a result.

How many training steps does a small TSP policy need?

Enough to get from a random tour near 10 to something near 4.5 at 20 cities. In this run, 800 steps of batch 128 with a 64-dimensional two-layer encoder took 1.7 minutes on CPU and reached 4.5 on training batches, which evaluated to 4.207 on fresh instances.

Does the policy generalise to more cities?

Not without retraining. Trained on 20 cities, it scored 6.889 at 50 cities against a 5.702 solver result, roughly tied with nearest neighbour at 6.924. Constructive policies encode the instance size in their behaviour, so test across sizes before claiming generalisation.

Sources

  • [1] Kool, van Hoof and Welling, Attention, Learn to Solve Routing Problems! — the attention encoder-decoder and rollout baseline this simplified policy follows: arxiv.org/abs/1803.08475
  • [2] Concorde TSP Solver — the exact solver and its cutting-plane approach, plus the TSP challenge instances: math.uwaterloo.ca/tsp/concorde.html
  • [3] TSP and TSPLIB data — the Waterloo TSP pages, including benchmark instances and best-known tours for comparing your policy against published results: math.uwaterloo.ca/tsp/data
  • [4] Google OR-Tools, Routing and vehicle routing — the routing model, search parameters and time_limit API used in the baseline: developers.google.com/optimization/routing
  • [5] ai4co, RL4CO — a library of neural combinatorial optimisation models and training schemes, including POMO, if you want to go past this toy: github.com/ai4co/rl4co

What are You Looking For?

esc