Notes from the routing desk

Random numbers, seeds, expectation, spread and percentiles: the statistics you need to read randomized routing results and compare methods fairly.

12 min read

How local search improves a tour one small change at a time: the 2-opt move, neighborhoods, delta evaluation, and how far 2-opt gets on berlin52.

15 min read

How the double-tree and Christofides algorithms guarantee a tour within 2× and 1.5× of optimal, why that needs the triangle inequality, and its limits.

18 min read

Build a tour in milliseconds with nearest neighbour, three insertion rules and a space-filling curve, and measure each against the berlin52 optimum.

17 min read

How constraint programming models a route as variables, domains and rules, lets propagation cut the search, and how OR-Tools builds on it.

15 min read

How branch-and-cut adds subtour and comb constraints only when the LP breaks them, and how Concorde uses that idea to solve huge TSPs exactly.

17 min read

How to write the TSP as an integer program: one variable per leg, degree constraints, and the two classic ways to forbid subtours, DFJ and MTZ.

16 min read

Variables, constraints and objectives; corners and the simplex method; LP relaxations, shadow prices and reduced costs, on a tiny fleet problem.

14 min read

How branch and bound proves a tour optimal: branch on edges, bound with assignment, 1-tree and Lagrangian relaxations, prune, and pick a search order.

15 min read

How the Held-Karp algorithm solves the TSP exactly by building answers over subsets of cities, worked by hand on six stops, and why its memory explodes.

14 min read

Five relatives of the TSP, the asymmetric, multiple, time-window, prize-collecting and orienteering versions, each solved on the same eight stops.

14 min read

Count the tours, brute-force eight stops by hand and in code, and get an honest intuition for NP-hardness and for 'optimal' versus 'good enough'.

12 min read

Big-O notation, recursion, arrays, linked lists and heaps, and why exponential growth decides which routing methods are usable at all.

13 min read

What a tour is, how to price one, why it is a permutation, symmetric vs. asymmetric, and why Dijkstra's shortest path does not solve it.

12 min read

The graph words the whole series uses: vertices, edges, weights, paths, cycles, tours, spanning trees and matchings, worked by hand on eight stops.

14 min read

Routing research from 1930 to today in one timeline, the 13 parts of this series and how they connect, the running examples, and where to start.

14 min read

Every term and symbol the routing series uses, in one place, each with a short meaning and a link to the post that defines it.

26 min read

Eight years of logistics engineering, and the 70-post series on vehicle routing I'm starting here.

2 min read