History and series map

Who this series is for

This series is for someone who wants to understand vehicle routing end to end and is starting from zero. You need to be comfortable reading a little Python. Everything else, from graphs to linear programming, is covered in five short primers.

Vehicle routing asks a plain question: given a fleet, a set of stops and a list of rules, which vehicle visits which stops, in what order? The simplest version, one vehicle and no rules, is the Traveling Salesman Problem (TSP). Almost every idea in routing was first tried on the TSP, so the series starts there and adds vehicles, capacities and time windows only once the methods are in place.

The series is concepts first. Code illustrates each idea, but it is not a solver tutorial: by the end you should be able to read a routing paper, judge a solver’s output and know which method fits which problem.

A short history of routing

Routing has a long research history, and almost every method in this series has a name and a date attached. The tables below give the milestones the series builds on, in four eras. The last column says where the series covers each one.

Before computers. The TSP was a puzzle about tours long before it was a computing problem.

The first exact methods, 1954–1972. Linear programming arrived, and with it the first proofs that a tour was optimal.

Heuristics with structure, 1973–1992. Since exact methods could not scale, researchers built fast methods and studied how good they were.

Records and open solvers, 2000–today. Implementations matured, and so did the records.

Updated October 2026: two later events matter for the series. In January 2026, PyVRP 0.13 replaced its hybrid genetic search with iterated local search, which is why Part 5 uses it. And in October 2025, Yuichi Nagata’s genetic algorithm, seeded with Helsgaun’s 2021 tour, shortened the World TSP record by 44 metres.

Two patterns run through the tables. Exact and heuristic methods grew up together: the Korea proof started from a tour that LKH found, and Concorde proved nothing shorter exists. And the VRP inherited the TSP’s toolkit, move by move: the 2-opt, Or-opt and double-bridge ideas of Parts 4 and 5 reappear, adapted to many routes, in Part 7.

The series map

The series has 13 parts. Parts 1 to 7 form a chain: each post ends on something the method cannot do yet, and the next post fixes it. Parts 8 to 12 are reference parts you can read in any order once the chain is done.

flowchart TD
  P0["Part 0: Start here"] --> P1["Part 1: The TSP"]
  P1 --> P2["Part 2: Exact methods"]
  P2 --> P3["Part 3: Fast first answers"]
  P3 --> P4["Part 4: Local search"]
  P4 --> P5["Part 5: Iterated local search"]
  P5 --> P6["Part 6: The metaheuristic family"]
  P6 --> P7["Part 7: From TSP to VRP"]
  P7 --> R{"Reference parts, any order"}
  R --> P8["Part 8: VRP variant atlas"]
  R --> P9["Part 9: Objectives, uncertainty, scale"]
  R --> P10["Part 10: Routing in the real world"]
  R --> P11["Part 11: Evaluation and solvers"]
  R --> P12["Part 12: The frontier"]

Each part answers one question:

The running examples

Two instances appear in almost every post, so you can see each method’s effect on the same problem.

Eight stops for working by hand. Every hand-worked example uses these eight stops. Coordinates are in kilometres on a flat plane, and distances are straight lines, rounded to units of 100 m. The optimal tour is A-B-C-D-H-E-F-G-A, which costs 315: 31.5 km. Step through the diagram to see the stops and then that tour.

Here are the distances between them. The outlined cells are the legs of the optimal tour, and the strip below adds them up.

berlin52 for measuring. berlin52 is a set of 52 locations in Berlin from TSPLIB, Reinelt’s 1991 library of test instances. Its optimal tour length, 7,542, is known and proven, so every method can report its gap: how far above the optimum it lands. The results so far, as the series has reached them:

Each row is the method of one post, run with that post’s script. The table will grow as the series moves on to vehicle routing, where the instances change but the habit stays: every result is reported against a known optimum or a stated bound.

Reading paths

You can read the series straight through. If you already know some of it, one of these paths may suit you better.

Wherever you start, each post’s “Read first” list names exactly what it builds on, with a one-line refresher of each.

How each post works

Every post in Parts 1 to 7 has the same sections, so you always know where to look:

1. Read first: the earlier posts and primers it relies on, each with a one-line refresher, and the question the post answers.
2. Intuition: the idea worked by hand on the eight stops, usually as a diagram you can step through.
3. The formal idea: just enough math to make it precise, with every symbol defined.
4. Common misconceptions: claims that sound right and are not.
5. Code: up to Part 4, one short script in plain Python with no libraries, run on berlin52, and its output as a table. From Part 5 on, the same section shows how PyVRP and reinterpretcat/vrp implement the idea.
6. Exercise: one small problem with a hint.
7. What this method can’t do yet: the concrete limitation the next post fixes. In Part 6 this becomes a comparison with iterated local search instead.

Numbers are shown, not listed. Distances appear as heatmaps with the tour’s legs outlined, as in the matrix above. Moves appear as step-through diagrams in which removed edges are dashed and new ones are drawn thick. Every number in a post comes from running its code, and every historical claim is checked against a primary source.

References

• Menger, K. (1932). “Das Botenproblem.” In K. Menger (ed.), Ergebnisse eines Mathematischen Kolloquiums 2, Teubner, Leipzig, 11–12. Posed at a colloquium in Vienna on 5 February 1930.
• Dantzig, G., Fulkerson, R., and Johnson, S. (1954). “Solution of a Large-Scale Traveling-Salesman Problem.” Journal of the Operations Research Society of America 2(4): 393–410.
• Flood, M. M. (1956). “The Traveling-Salesman Problem.” Operations Research 4(1): 61–75.
• Croes, G. A. (1958). “A Method for Solving Traveling-Salesman Problems.” Operations Research 6(6): 791–812.
• Dantzig, G. B., and Ramser, J. H. (1959). “The Truck Dispatching Problem.” Management Science 6(1): 80–91.
• Bellman, R. (1962). “Dynamic Programming Treatment of the Travelling Salesman Problem.” Journal of the ACM 9(1): 61–63.
• Held, M., and Karp, R. M. (1962). “A Dynamic Programming Approach to Sequencing Problems.” Journal of the Society for Industrial and Applied Mathematics 10(1): 196–210.
• Clarke, G., and Wright, J. W. (1964). “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points.” Operations Research 12(4): 568–581.
• Lin, S. (1965). “Computer Solutions of the Traveling Salesman Problem.” Bell System Technical Journal 44(10): 2245–2269.
• Held, M., and Karp, R. M. (1970). “The Traveling-Salesman Problem and Minimum Spanning Trees.” Operations Research 18(6): 1138–1162.
• Held, M., and Karp, R. M. (1971). “The Traveling-Salesman Problem and Minimum Spanning Trees: Part II.” Mathematical Programming 1(1): 6–25.
• Karp, R. M. (1972). “Reducibility Among Combinatorial Problems.” In R. E. Miller and J. W. Thatcher (eds.), Complexity of Computer Computations, Plenum, 85–103.
• Lin, S., and Kernighan, B. W. (1973). “An Effective Heuristic Algorithm for the Traveling-Salesman Problem.” Operations Research 21(2): 498–516.
• Christofides, N. (1976). “Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem.” Management Sciences Research Report 388, Carnegie-Mellon University.
• Serdyukov, A. I. (1978). “On some extremal walks in graphs.” Upravlyaemye Sistemy 17: 76–79 (in Russian; submitted 1976).
• Rosenkrantz, D. J., Stearns, R. E., and Lewis, P. M. (1977). “An Analysis of Several Heuristics for the Traveling Salesman Problem.” SIAM Journal on Computing 6(3): 563–581.
• Reinelt, G. (1991). “TSPLIB—A Traveling Salesman Problem Library.” ORSA Journal on Computing 3(4): 376–384.
• Martin, O., Otto, S. W., and Felten, E. W. (1991). “Large-Step Markov Chains for the Traveling Salesman Problem.” Complex Systems 5(3): 299–326.
• Bentley, J. L. (1992). “Fast Algorithms for Geometric Traveling Salesman Problems.” ORSA Journal on Computing 4(4): 387–411.
• Helsgaun, K. (2000). “An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic.” European Journal of Operational Research 126(1): 106–130.
• Applegate, D. L., Bixby, R. E., Chvátal, V., and Cook, W. J. (2006). The Traveling Salesman Problem: A Computational Study. Princeton University Press.
• Vidal, T., Crainic, T. G., Gendreau, M., Lahrichi, N., and Rei, W. (2012). “A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems.” Operations Research 60(3): 611–624.
• Helsgaun, K. (2017). “An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems.” Technical report, Roskilde University.
• Vidal, T. (2022). “Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood.” Computers & Operations Research 140: 105643.
• Wouda, N. A., Lan, L., and Kool, W. (2024). “PyVRP: A High-Performance VRP Solver Package.” INFORMS Journal on Computing 36(4): 943–955. Release notes for version 0.13.0 (January 2026): https://github.com/PyVRP/PyVRP
• Cook, W., Espinoza, D., Goycoolea, M., and Helsgaun, K. (2025). “Korea TSPs.” University of Waterloo. https://www.math.uwaterloo.ca/tsp/korea/
• Cook, W., et al. “World TSP.” University of Waterloo. https://www.math.uwaterloo.ca/tsp/world/
• Cook, W. “History of the TSP.” University of Waterloo. https://www.math.uwaterloo.ca/tsp/history/

See the whole series · ← All writing