Introduction

A delivery driver has twenty stops and one truck. A circuit board needs a drill to hit a thousand holes. A tourist wants to see ten sights in a day and get back to the hotel. All of them face the same question: what's the shortest route that visits every place once and returns to the start?

That's the Traveling Salesman Problem (TSP) — maybe the most famous hard problem of all. It sounds almost trivial: just try the possible orders and pick the shortest. But the orders multiply factorially. Ten cities have over 180,000 routes; twenty cities have more routes than there are grains of sand on Earth; sixty cities outrun the atoms in the universe.

So you can't just check them all. TSP is NP-hard, and along with its cousins on this site it's a poster child for combinatorial explosion. The twist that keeps the world moving: even though the perfect tour is out of reach for big maps, clever methods get astonishingly close — within a few percent of optimal — fast.

Plan the Route

Try it. The dots are cities. Click them in the order you'd visit — the demo draws your tour back to the start and measures its total length. Try to make it as short as you can.

<p class="hint">The dots are cities; <b>A</b> is home. Click cities in the order you'd visit — the tour closes back to A and the <b>length</b> updates. Make it as short as you can, then compare with greedy and the optimum.</p>
<svg id="svg" viewBox="0 0 320 250" class="svg"></svg>
<div class="meter">Tour length: <b id="len" class="len">—</b><span id="status" class="status"></span></div>
<div class="btns">
  <button id="nn" type="button">Nearest neighbor</button>
  <button id="opt" type="button">Optimal</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.svg { width: 100%; max-width: 420px; background: #f4f7f9; border: 1px solid #e2e6eb; border-radius: 10px; display: block; }
.tour { fill: none; stroke: #457b9d; stroke-width: 2.5; stroke-linejoin: round; }
.city { fill: #8aa0b3; cursor: pointer; transition: fill .1s; }
.city:hover { fill: #457b9d; }
.city.visited { fill: #2a9d8f; }
.city.home { fill: #c0392b; }
.clbl { font: 700 11px ui-monospace, monospace; fill: #fff; text-anchor: middle; dominant-baseline: central; pointer-events: none; }
.ord { font: 700 10px system-ui; fill: #1d3557; text-anchor: middle; }
.meter { margin: .8rem 0 .6rem; font-size: 1.05rem; }
.len { color: #1d3557; font-family: ui-monospace, monospace; }
.status { margin-left: .6rem; font: 700 .9rem system-ui; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Traveling Salesman Problem. Visit every city once and return to A, shortest total distance. NP-hard: (n-1)!/2 tours. Nearest-neighbor is greedy (often ~15% over); Optimal brute-forces the best tour for this small map.
const C = [[60, 40], [200, 30], [280, 120], [230, 210], [120, 220], [40, 150], [150, 120]];
const NAMES = ['A', 'B', 'C', 'D', 'E', 'F', 'G'];
const N = C.length;
const d = (a, b) => Math.hypot(C[a][0] - C[b][0], C[a][1] - C[b][1]);
function len(t) { let s = 0; for (let i = 0; i < t.length; i++) s += d(t[i], t[(i + 1) % t.length]); return s; }

let tour = [0]; // start at home (A)
// optimum (brute force, fixed start 0)
let OPT = Infinity;
(function () { const rest = [1, 2, 3, 4, 5, 6]; (function perm(a, acc) { if (!a.length) { OPT = Math.min(OPT, len([0, ...acc])); return; } for (let i = 0; i < a.length; i++) perm(a.slice(0, i).concat(a.slice(i + 1)), [...acc, a[i]]); })(rest, []); })();
OPT = Math.round(OPT);

function render() {
  let s = '';
  if (tour.length > 1) {
    const pts = tour.map(i => C[i][0] + ',' + C[i][1]).join(' ') + ' ' + C[tour[0]][0] + ',' + C[tour[0]][1];
    s += '<polyline class="tour" points="' + pts + '"/>';
  }
  for (let i = 0; i < N; i++) {
    const visited = tour.includes(i), home = i === 0;
    const cls = home ? 'city home' : (visited ? 'city visited' : 'city');
    s += '<circle class="' + cls + '" cx="' + C[i][0] + '" cy="' + C[i][1] + '" r="13" data-i="' + i + '"/>';
    s += '<text class="clbl" x="' + C[i][0] + '" y="' + C[i][1] + '">' + NAMES[i] + '</text>';
    const pos = tour.indexOf(i);
    if (pos >= 0) s += '<text class="ord" x="' + C[i][0] + '" y="' + (C[i][1] - 18) + '">' + (pos + 1) + '</text>';
  }
  document.getElementById('svg').innerHTML = s;
  document.getElementById('svg').querySelectorAll('.city').forEach(el => el.addEventListener('click', () => { const i = +el.dataset.i; if (!tour.includes(i)) { tour.push(i); render(); } }));
  const complete = tour.length === N;
  document.getElementById('len').textContent = tour.length > 1 ? Math.round(len(tour)) : '—';
  const st = document.getElementById('status');
  if (!complete) { st.style.color = '#777'; st.textContent = fmt('visit all %N% cities', { N: N }); }
  else if (Math.round(len(tour)) <= OPT) { st.style.color = '#0a7d33'; st.textContent = fmt('✓ shortest possible! (%OPT%)', { OPT: OPT }); }
  else { st.style.color = '#b9770e'; st.textContent = fmt('%round%% over the optimum (%OPT%)', { round: Math.round((len(tour) / OPT - 1) * 100), OPT: OPT }); }
}

function nearest() {
  const t = [0], used = new Set([0]);
  while (t.length < N) { const last = t[t.length - 1]; let best = -1, bd = Infinity; for (let i = 0; i < N; i++) if (!used.has(i) && d(last, i) < bd) { bd = d(last, i); best = i; } t.push(best); used.add(best); }
  tour = t; render();
}
function optimal() {
  let best = Infinity, bt = null; const rest = [1, 2, 3, 4, 5, 6];
  (function perm(a, acc) { if (!a.length) { const L = len([0, ...acc]); if (L < best) { best = L; bt = [0, ...acc]; } return; } for (let i = 0; i < a.length; i++) perm(a.slice(0, i).concat(a.slice(i + 1)), [...acc, a[i]]); })(rest, []);
  tour = bt; render();
}

document.getElementById('nn').addEventListener('click', nearest);
document.getElementById('opt').addEventListener('click', optimal);
document.getElementById('reset').addEventListener('click', () => { tour = [0]; render(); });
render();
Result
Console

Then compare. Nearest neighbor greedily hops to the closest unvisited city — fast, but it often paints itself into a long detour at the end. Optimal finds the true shortest tour (by brute force on this small map). Watch the greedy route fall short of the best — that small gap, multiplied across thousands of stops, is exactly why TSP matters and why it's hard.

The Hard Part

TSP is the classic hard problem, and a beautiful case study in coping with hardness:

  • Checking a tour is easy. Add up the distances between consecutive stops.
  • Brute force is factorial. Trying all (n−1)!/2 tours is hopeless past ~15 cities.
  • It's NP-hard. Deciding the shortest tour is NP-hard; even approximating general (non-metric) TSP is hard. Its decision version is NP-complete.
  • Exact methods reach surprisingly far. Held–Karp dynamic programming solves it in O(2n⋅n2)O(2^{n} \cdot n^{2}) — fine for ~20 cities — and branch-and-cut solvers (Concorde) have found provably optimal tours through tens of thousands of cities.
  • Heuristics get close, fast. For metric TSP (distances obey the triangle inequality), Christofides' algorithm guarantees a tour at most 1.5× optimal. In practice, nearest neighbor then 2-opt/Or-opt local search, and the celebrated Lin–Kernighan (LKH) heuristic, routinely land within 1–2% of optimal on millions of points.
  • It's a hub. Many problems reduce to or from TSP, and the same techniques power vehicle routing and scheduling.

So TSP is hard in the worst case yet solved well enough every day — the recurring lesson of this site, in its most iconic form.

Where It Matters

The shortest-tour problem is worth billions in the real world:

  • Logistics and delivery: planning routes for trucks, couriers and field technicians — the everyday face of TSP (and its vehicle-routing extensions).
  • Manufacturing: ordering the holes a drill or the points a laser must hit on a circuit board, minimizing machine travel.
  • Genomics: assembling DNA fragments maps onto TSP-like ordering problems.
  • Astronomy: scheduling a telescope's slews between targets to waste the least time.
  • Warehousing: routing pickers through aisles to fill an order fastest.

Because a small percentage saved scales across millions of routes, TSP solvers and heuristics are a quiet, valuable industry.

Conclusion

The Traveling Salesman is the face on the poster of hard problems. The question is childishly simple, the brute-force answer is impossibly large, and no one knows a fast method that's always exact — if they did, they'd have cracked P vs NP and a million dollars with it.

And yet your packages arrive, your circuit boards get drilled, and your maps suggest good routes — because we stopped demanding perfection and learned to get within a whisker of it, quickly. TSP is the clearest reminder this site offers: a problem can be provably hard and practically conquered at the same time, and the space between "optimal" and "good enough" is where most of the world actually runs.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/routes/Content licensed under CC BY-NC 4.0.