Lab
Optimization · Traveling Salesman Problem

Route Optimizer

Given a set of stops, find the shortest round-trip that visits each one and returns home. Easy to state, brutally hard to solve exactly — the number of possible tours grows factorially. So instead we use heuristics that find a very good tour fast.

click to add a stop

How it works

  1. Nearest-neighbour build: start somewhere and always hop to the closest unvisited stop. Fast, but it leaves ugly crossings.
  2. 2-opt improvement: pick two edges, reverse the segment between them, and keep the swap whenever it shortens the tour. Crossings untangle themselves.
  3. Repeat until no swap helps — a local optimum. The length label ticks down as the route improves.

This is exactly the problem family from both my theses: routing a probe through the TRAPPIST-1 exoplanets, and steering a boat through drifting ocean debris. Same core, different universe.