Data Pattern Pro

Mathematical programming / Routing and scheduling

Traveling Salesman Problem (TSP)

Find the shortest route that visits every location exactly once and returns to the start — the base case every routing problem builds on.

Note Advanced

Short note. A compact reference, correct as far as it goes. It will be expanded into a full guide with a worked example and an interactive demonstration.

Problem

Given a set of locations and travel costs between each pair, find the cheapest closed tour that visits every location exactly once.

When to use it

Rarely in its pure form in industry — real routing problems have vehicle capacities, time windows, and multiple vehicles (see Vehicle Routing Problem). But TSP is the formulation every routing engineer should know cold, because the subtour-elimination trick reappears everywhere.

Formulation

Binary x_ij = 1 if the tour travels directly from i to j. The subtle part isn’t the degree constraints — it’s stopping the solver from returning disconnected mini-loops instead of one full tour.

minimize   sum(c_ij * x_ij)
subject to:
  sum_j(x_ij) = 1   for all i     # leave each node exactly once
  sum_i(x_ij) = 1   for all j     # enter each node exactly once
  subtour elimination constraints (see below)

Subtour elimination (MTZ formulation) — introduce continuous “visit order” variables u_i for n cities:

u_i - u_j + n * x_ij <= n - 1     for all i != j, i,j != depot
1 <= u_i <= n - 1

Code sketch

# For anything beyond ~15-20 nodes, don't hand-roll subtour elimination —
# use a purpose-built solver.
from ortools.constraint_solver import pywrapcp, routing_enums_pb2

manager = pywrapcp.RoutingIndexManager(len(distance_matrix), 1, depot=0)
routing = pywrapcp.RoutingModel(manager)

def distance_callback(from_index, to_index):
    return distance_matrix[manager.IndexToNode(from_index)][manager.IndexToNode(to_index)]

transit_idx = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_idx)

search_params = pywrapcp.DefaultRoutingSearchParameters()
search_params.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
)
solution = routing.SolveWithParameters(search_params)

Pitfalls

  • The naive degree-constraint formulation without subtour elimination will happily return two disconnected 5-city loops instead of one 10-city tour — always check for this if a solve looks “too fast.”
  • MTZ subtour elimination is easy to implement but scales poorly. For real problem sizes, use lazy constraint generation (add violated subtour cuts as they’re found) or a routing-specific library like OR-Tools.
  • Exact MILP solves become impractical past a few hundred nodes — that’s the point where you switch to metaheuristics (2-opt, Lin-Kernighan) or OR-Tools’ built-in local search.