Solve the traveling salesman problem (TSP) in Python

The traveling salesman problem — find the shortest route that visits every city exactly once and returns to the start — is the most famous NP-hard problem there is. The default Python answers are itertools.permutations over every tour or a from-scratch nearest-neighbor heuristic. With quicopt you model it once and get the provably shortest tour.

The brute-force trap

Trying every tour is the direct translation:

from itertools import permutations

D = [[0,3,4,2,7],[3,0,4,6,3],[4,4,0,5,8],[2,6,5,0,6],[7,3,8,6,0]]
n = len(D)
best = min(
    sum(D[t[i]][t[i+1]] for i in range(n-1)) + D[t[-1]][t[0]]
    for t in ((0,) + p for p in permutations(range(1, n)))
)
print(best)  # -> 19

Fine for five cities. But the number of tours is (n-1)!/2, which passes a trillion around 15 cities. Enumeration is a dead end.

Model it as a MILP

The compact Miller–Tucker–Zemlin (MTZ) formulation: a binary x[i,j] marks using the arc from city i to city j. Each city is entered once and left once, and the u position variables forbid disconnected subtours:

from ortools.math_opt.python import mathopt
from quicopt import Client
D = [[0,3,4,2,7],[3,0,4,6,3],[4,4,0,5,8],[2,6,5,0,6],[7,3,8,6,0]]
n = len(D)
model = mathopt.Model(name="tsp")
x = {(i,j): model.add_binary_variable(name=f"x_{i}_{j}") for i in range(n) for j in range(n) if i != j}
u = [model.add_variable(lb=0.0, ub=n - 1, name=f"u{i}") for i in range(n)]
for i in range(n):
    model.add_linear_constraint(sum(x[i,j] for j in range(n) if j != i) == 1)
    model.add_linear_constraint(sum(x[j,i] for j in range(n) if j != i) == 1)
for i in range(1, n):
    for j in range(1, n):
        if i != j:
            model.add_linear_constraint(u[i] - u[j] + n * x[i,j] <= n - 1)  # MTZ subtour elimination
model.minimize(sum(D[i][j] * x[i,j] for i in range(n) for j in range(n) if i != j))
print(Client("https://try.quicoptapi.pgi.fz-juelich.de").solve(model).display)

├── status:     optimal
├── feasible:   true
├── objective:  19.0
├── x:          u0=0, u1=1, u2=0, u3=4, u4=2, x_0_1=0, …  (25 variables)
└── solve_time: 0.0153 s

What you get

status: optimal means the tour is proven shortest — length 19, matching the brute-force answer, found in about fifteen milliseconds. The x[i,j] arcs that are 1 spell out the route; the u variables carry the visiting order that rules out subtours.

Unlike enumeration, the MILP prunes the tour space with bounds instead of listing it, so it solves instances well past where itertools.permutations gives up. This compact MTZ formulation is best for small-to-medium instances; very large TSPs call for specialized routines (stronger cutting planes or dedicated heuristics).

Next

• The problem class behind this: Mixed-integer linear (MILP)
• A runnable model for every supported class: Examples
• Set up the client and solve your first model: Getting started

Reference: C. E. Miller, A. W. Tucker, R. A. Zemlin, Integer Programming Formulation of Traveling Salesman Problems, Journal of the ACM, 1960.