The Traveling Salesperson Problem

Forty-two cities,
one route

A van must visit 42 cities, each exactly once, and return to where it started. Which order makes the trip shortest? That question is the Traveling Salesperson Problem, and there are 1.7 × 1049 possible answers — far too many for any computer to check.

This project finds a route within 1.9% of the proven shortest one, using a genetic algorithm: keep a pool of routes, let the short ones breed, repeat.

Watch it run → Why it is hard Read the code

The algorithm, running

starting

Best route so far — the faint line is the one it replaced
Best route length per generation
Generation
0
Best route
—
Above target
—
Known optimum
—

The problem, in plain terms

A van has 42 stops to make and has to end up back at the depot. Which order should it visit them in to drive the fewest miles?

That question is called the Traveling Salesperson Problem, and it is famously hard — not because any single route is difficult to measure, but because there are so many of them. With 42 stops there are roughly 1.7 × 1049 possible routes. To put that number in perspective: if you could check a billion routes every second, and had started at the Big Bang, you would still have looked at almost none of them.

Nobody knows a method that reliably finds the single best route without effectively trying them all. So the practical goal changes from find the best to find something very good, quickly — which is exactly what real routing, scheduling and logistics software has to do every day.

This project does that with a genetic algorithm: start with a hundred random routes, keep the shortest ones, combine them to make "child" routes, occasionally introduce a random change, and repeat for a few hundred rounds. Good structure survives, bad structure dies out. Nothing in the program knows what a map is.

What I built

  • The algorithm itself, in Python — population, fitness, three ways of choosing parents, three ways of combining routes, three ways of mutating them, and elitism.
  • A controlled comparison of every combination of those operators, run 30 times each across three standard benchmark problems, to find which choices actually matter.
  • This site, including a from-scratch JavaScript port of the algorithm so you can run it yourself and watch the route improve in real time.
  • A verification pass that caught a real error in the project's own input data — one wrong digit that had quietly invalidated its headline result.

At a glance

Built with
Python (NumPy, pandas, matplotlib) · vanilla JavaScript, no framework
Benchmarks
swiss42, bayg29, brazil58 — standard TSPLIB problems with published optimal answers
Best result
Within 1.9% of the proven optimum on swiss42, 0.8% on bayg29, 0.4% on brazil58
Verification
The browser port matches the Python byte-for-byte on 400 randomised operator tests

What it demonstrates

Algorithm design

Implementing evolutionary operators that respect a hard constraint — every route must visit every city exactly once, which rules out the textbook way of combining two solutions.

Scepticism about data

The original results beat a mathematically proven optimum, which is impossible. Tracking that down to a single mistyped digit is the piece of work I am most pleased with.

Measuring the right thing

The operator with the best single result was not the one most likely to produce a good result. Reporting reliability, not just the record, changes which one you would actually ship.

Proving a rewrite is faithful

Rewriting the algorithm in another language is only useful if it behaves identically. I tested it against the original on 400 random inputs rather than assuming.

Read on