Vehicle Routing, End to End · Reference
Glossary and notation
On this page
How to use this page
Each table below lists the terms of one area of the series, alphabetically, with a one-sentence meaning and a link to the post or primer that first defines it in reading order. The meanings are short on purpose: follow the link for the worked example and the full definition. Terms from Parts 6 to 12 will be added as those posts appear.
The groups build on each other in roughly this order:
flowchart TD P["Problems"] --> G["Graphs and complexity"] G --> E["Exact methods"] G --> B["Building tours"] B --> L["Local search"] L --> I["Iterated local search and metaheuristics"] S["Statistics and experiments"] --> I
Problems
| Term | Meaning | First defined in |
|---|---|---|
| Asymmetric TSP (ATSP) | A TSP where some d(i, j) ≠ d(j, i), as with one-way streets, so a tour and its reverse can cost different amounts. | Post 1 |
| berlin52 | A TSPLIB instance of 52 locations in Berlin with a proven optimal tour of 7,542; the series’ measuring instance. | Post 0 |
| Cost of a tour | The sum of the distances along the tour, including the last leg back to the start. | Post 1 |
| Distance matrix | A table whose row i, column j holds the cost of going from i to j. | Primer A |
| Gap | How far a tour’s cost is above the optimum, as a percentage; for a lower bound, how far it is below. | Post 0 |
| Metric TSP | A TSP whose distances are symmetric and obey the triangle inequality. | Post 10 |
| Multiple TSP | Several salesmen leave the same start and together visit every stop once; the bridge to vehicle routing. | Post 3 |
| Orienteering problem | Collect as much prize as possible with a route no longer than a given budget. | Post 3 |
| Prize-collecting TSP | Every stop is optional, but skipping one costs its prize; minimize distance plus skipped prizes. | Post 3 |
| Symmetric TSP | A TSP where d(i, j) = d(j, i) for every pair, so a tour and its reverse cost the same. | Post 1 |
| TSP with time windows (TSPTW) | Each stop must be reached within its window; arriving early means waiting, arriving late is not allowed. | Post 3 |
| TSPLIB | Reinelt’s 1991 library of TSP test instances, which made results comparable across papers. | Post 0 |
| Traveling Salesman Problem (TSP) | Find the cheapest tour through every stop: the routing problem with one vehicle and no other rules. | Post 0 |
| Triangle inequality | d(i, k) ≤ d(i, j) + d(j, k) for every three stops: a direct trip is never longer than a detour. | Post 10 |
| Vehicle routing problem (VRP) | Given a fleet, a set of stops and a list of rules, decide which vehicle visits which stops, in what order. | Post 0 |
Graphs and complexity
| Term | Meaning | First defined in |
|---|---|---|
| Adjacency list | A graph stored as, for each vertex, only its neighbours and their edge weights; suits sparse road networks. | Primer A |
| Arc | An edge with a direction, in a directed graph. | Primer A |
| Array | Values kept in numbered slots, so any position can be read in one step. | Primer B |
| Base case | The case where a recursive function stops calling itself. | Primer B |
| Big-O, O(g(n)) | f(n) = O(g(n)) if, beyond some size, f grows no faster than g up to a constant factor. | Primer B |
| Big-Omega and Big-Theta, Ω and Θ | Ω(g) means growing at least as fast as g; Θ(g) means both O(g) and Ω(g). | Primer B |
| Certificate | Evidence that a “yes” answer is right and can be checked quickly; for TSP-DECISION, a tour. | Post 2 |
| Complete graph | A graph in which every pair of vertices is joined by an edge; n(n − 1)/2 edges. | Primer A |
| Cut property | For any split of the vertices into two groups, the cheapest edge crossing between them belongs to some minimum spanning tree. | Primer A |
| Cycle | A path whose last vertex is joined back to its first. | Primer A |
| Decision version (TSP-DECISION) | The yes/no form of the TSP: given the matrix and a number K, is there a tour of cost at most K? | Post 2 |
| Degree | The number of edges touching a vertex; every stop of a tour has degree 2. | Primer A |
| Depth first | A search order that follows one branch all the way down before backing up to try the next choice. | Primer B |
| Dijkstra’s algorithm | Finds a shortest path between two vertices; a shortest path is not a tour. | Primer A |
| Directed graph | A graph whose edges have a direction, so its matrix need not be symmetric. | Primer A |
| Edge | A connection between two vertices, carrying a weight. | Primer A |
| Euler circuit | A closed walk that uses every edge exactly once; exists in a connected graph whose degrees are all even. | Post 10 |
| Exponential growth | A step count growing like cⁿ for some c > 1, or faster; 2ⁿ and n! both qualify. | Primer B |
| Graph, G = (V, E) | A set of vertices V and a set of edges E, each edge joining two vertices. | Primer A |
| Hamiltonian cycle | A cycle through every vertex exactly once; in routing, a tour. | Primer A |
| Heap | A tree in which every parent is no larger than its children, so the smallest item is always on top; add or remove in about log₂ n steps. | Primer B |
| Kruskal’s rule | Build a minimum spanning tree by taking edges from cheapest up, skipping any that would close a cycle. | Primer A |
| Linear growth | A step count that doubles when the input doubles, O(n). | Primer B |
| Linked list | Each item keeps a pointer to the next, so reaching position k takes k steps. | Primer B |
| Matching | A set of edges no two of which share a vertex. | Primer A |
| Minimum spanning tree (MST) | The spanning tree of least total weight. | Primer A |
| NP | Yes/no problems whose “yes” answers come with a certificate that can be checked in polynomial time; short for nondeterministic polynomial time. | Post 2 |
| NP-complete | In NP, and every problem in NP can be translated into it in polynomial time. | Post 2 |
| NP-hard | At least as hard as every problem in NP, whether or not it is a yes/no problem itself; the TSP is NP-hard. | Post 2 |
| P | Yes/no problems that some algorithm can solve in polynomial time. | Post 2 |
| Path | A sequence of distinct vertices, consecutive ones joined by edges. | Primer A |
| Perfect matching | A matching that covers every vertex of the set being matched. | Primer A |
| Polynomial | A step count of O(nᵏ) for some fixed k, such as n, n log n, n² or n³. | Primer B |
| Prim’s algorithm | Grow a minimum spanning tree from one vertex, always adding the cheapest edge from the tree to a vertex outside it. | Primer A |
| Recursion | A function that solves a problem by calling itself on a smaller version of it. | Primer B |
| Recursive case | The case where a recursive function calls itself on a smaller problem. | Primer B |
| Spanning tree | A tree that contains every vertex of the graph; n − 1 edges. | Primer A |
| Tour | A cycle through every vertex exactly once that returns to the start. | Primer A |
| Tree | A connected graph with no cycle; on n vertices it has n − 1 edges. | Primer A |
| Undirected graph | A graph whose edges are two-way, each with one weight; its matrix is symmetric. | Primer A |
| Vertex (node) | A point of a graph; in routing, a stop. | Primer A |
| Weight | The number on an edge: a distance, a travel time or a cost. | Primer A |
Exact methods
| Term | Meaning | First defined in |
|---|---|---|
| 1-tree | A spanning tree on all cities but one special city, plus two edges at that city; its cost is a lower bound on every tour. | Post 5 |
| Assignment bound | The cheapest way to give every city one successor and one predecessor, ignoring whether that forms one cycle; a lower bound on every tour. | Post 5 |
| Assignment problem | The model in which each stop is left once and entered once, with no rule against subtours. | Post 6 |
| Best predecessor | In Held-Karp, the stop each table entry came from, followed backwards to recover the tour. | Post 4 |
| Best-first search | Branch and bound that always expands the open node with the smallest lower bound. | Post 5 |
| Branch and bound | Split the set of tours into groups (branching) and discard any group whose lower bound is no better than the best tour found (pruning). | Post 5 |
| Branch-and-cut | Branch and bound with a cutting-plane loop at every node; named by Padberg and Rinaldi in 1987. | Post 7 |
| Comb inequality | A constraint every tour satisfies, built from a handle set and an odd number of teeth sets, that catches LP solutions subtour constraints miss. | Post 7 |
| Concorde | The exact TSP solver of Applegate, Bixby, Chvátal and Cook, which solved all 110 TSPLIB instances. | Post 7 |
| Constraint programming (CP) | Model a problem as variables, domains and constraints, and let propagation remove impossible values before searching. | Post 8 |
| Constraints | The rules a solution must satisfy. | Primer C |
| Cut | A constraint added because the current LP solution breaks it, cutting that solution out of the feasible region. | Post 7 |
| Cutting-plane loop | Solve the LP, find one constraint the solution breaks, add only that one, and solve again. | Post 7 |
| Dantzig-Fulkerson-Johnson (DFJ) formulation | The TSP as an integer program with degree constraints and one subtour elimination constraint per subset of stops. | Post 6 |
| Decision variables | The unknowns a model chooses, such as the number of vans or whether a leg is driven. | Primer C |
| Degree constraint | Every stop is left once and entered once (directed model); in the symmetric model of Post 7, every stop has exactly two tour edges. | Post 6 |
| Depth-first search | Branch and bound that dives to a leaf quickly, finding tours, and so upper bounds, early. | Post 5 |
| Dimension | In OR-Tools, a quantity that accumulates along a route, such as time or load, with a variable at every location. | Post 8 |
| Domain | In constraint programming, the values a variable may still take. | Post 8 |
| Dual | The partner LP of every LP: prices on the requirements, maximized subject to no variable being worth more than it costs. | Primer C |
| Dynamic programming | Solve a problem by building answers to subproblems and reusing them; for the TSP, the Held-Karp algorithm. | Post 4 |
| Exact method | A method that proves its answer is optimal, even if its worst case is exponential. | Post 2 |
| Feasible region | The set of plans that satisfy every constraint. | Primer C |
| Forward checking | Removing, right after each choice, the values that the choice makes impossible for the stops still to come. | Post 8 |
| Held-Karp algorithm | Dynamic programming over states (set of stops visited, current stop); O(n² · 2ⁿ) time. | Post 4 |
| Held-Karp bound | The 1-tree bound strengthened with Lagrangian penalties on the cities; 7,542 on berlin52 after rounding up. | Post 5 |
| Integer program (IP) | A linear program in which some or all variables must be whole numbers. | Primer C |
| Integrality gap | The difference between an integer program’s optimum and its LP relaxation’s. | Primer C |
| Lagrangian relaxation | Add a penalty πᵢ to every edge at city i, which changes every tour by the same amount but changes the cheapest 1-tree. | Post 5 |
| Linear program (LP) | Minimize or maximize a linear objective subject to linear constraints. | Primer C |
| Lower bound (LB) | A number guaranteed to be at most the cost of every solution in a group. | Primer C |
| LP relaxation | The integer program with the whole-number requirement dropped; its optimum is a lower bound. | Primer C |
| Miller-Tucker-Zemlin (MTZ) formulation | Forbids subtours with a position variable u(i) per stop and one constraint per pair of stops; compact but with a weak LP bound. | Post 6 |
| Node (of a search tree) | A group of tours described by the edges they must use and the edges they must not. | Post 5 |
| Objective | The quantity a model minimizes or maximizes. | Primer C |
| Propagation | Using a constraint to delete values from domains before searching them. | Post 8 |
| Pruning | Discarding a group of tours whose lower bound is already no better than the upper bound. | Post 5 |
| Reduced cost | A variable’s cost minus what it is worth at the shadow prices; a negative one means bringing it in lowers the cost. | Primer C |
| Relaxation | An easier problem whose feasible set contains every tour, so its optimum is a lower bound. | Post 5 |
| Separation problem | Finding a constraint that the current LP solution breaks. | Post 7 |
| Shadow price | How much the optimal LP cost rises per extra unit of a requirement. | Primer C |
| Simplex method | Walk from corner to corner of the feasible region, always downhill, until no edge leads downhill. | Primer C |
| Strong duality | The best dual prices give exactly the LP optimum. | Primer C |
| Subtour | A closed cycle that does not visit every stop. | Post 6 |
| Subtour elimination constraint | For every set S of stops, at most |S| − 1 legs run inside S (Post 6); equivalently, at least two tour edges leave every proper subset (Post 7). | Post 6 |
| Upper bound (UB) | The cost of the best tour found so far. | Post 5 |
| Weak duality | Any dual-feasible prices give a lower bound on the cost of every plan. | Primer C |
Building tours
| Term | Meaning | First defined in |
|---|---|---|
| Approximation algorithm | A polynomial-time algorithm that proves its tour costs at most ρ times the optimum on every instance. | Post 10 |
| Approximation ratio, ρ | The fixed factor an approximation algorithm guarantees: ALG(I) ≤ ρ · OPT(I). | Post 10 |
| Cheapest insertion | Insert the stop, and position, with the smallest insertion cost overall. | Post 9 |
| Christofides’ algorithm | MST plus a minimum perfect matching on its odd-degree stops, then an Euler circuit and shortcuts; at most 1.5 times optimal on metric instances. | Post 10 |
| Construction heuristic | Build one tour from nothing, one stop at a time, never changing an earlier decision. | Post 9 |
| Double-tree algorithm | Walk around the MST, using every edge twice, then shortcut repeated stops; at most 2 times optimal on metric instances. | Post 10 |
| Farthest insertion | Insert next the stop whose distance to the loop is largest. | Post 9 |
| Heuristic | A method that returns a good solution quickly, with no proof of optimality. | Post 2 |
| Insertion cost | The extra length of putting stop k between i and j: d(i, k) + d(k, j) − d(i, j). | Post 9 |
| Nearest insertion | Insert next the stop closest to any stop already in the loop. | Post 9 |
| Nearest neighbour | From the current stop, always drive to the closest unvisited one. | Post 2 |
| Shortcut | Skip stops a walk has already visited and jump straight to the next new one; never longer under the triangle inequality. | Post 10 |
| Space-filling curve heuristic | Visit the stops in the order a curve through every grid cell reaches them, computing no distances. | Post 9 |
Local search
| Term | Meaning | First defined in |
|---|---|---|
| 2-opt move | Delete two edges of a tour and reconnect the pieces the other way, which reverses the segment between them. | Post 11 |
| 3-opt | Moves that remove three edges and reconnect the three pieces; four of the reconnections are pure. | Post 14 |
| Adjacent swap | Exchange two stops that sit next to each other in the tour; a tour of n stops has n of them. | Post 15 |
| α-nearness | How much longer the minimum 1-tree gets if forced to contain an edge, after Lagrangian penalties; LKH’s candidate rule. | Post 14 |
| Basin | The set of starting tours from which local search ends at a given local optimum. | Post 15 |
| Best improvement | Scan every move and make the one with the most negative Δ. | Post 11 |
| Big valley | On the TSP, better local optima lie close to each other and to the best one. | Post 15 |
| Bond distance | The number of edges of one tour that another tour does not use. | Post 15 |
| Delta evaluation | Pricing a move from only the edges it removes and adds, instead of re-scoring the whole tour. | Post 11 |
| Don’t-look bit | A per-city flag that skips cities whose edges have not changed since a search from them found nothing. | Post 13 |
| Doubly linked list | Each stop points to both its neighbours; reconnecting is cheap, but a reversal leaves every node inside pointing the wrong way. | Post 13 |
| First improvement | Make the first improving move the scan meets, then start scanning again. | Post 11 |
| Fitness distance correlation | The correlation between a solution’s cost and its distance to the nearest global optimum. | Post 15 |
| Gain criterion | Only try a new edge t₂–t₃ shorter than the removed edge t₁–t₂; any improving move is still found from some starting city. | Post 13 |
| Global optimum | A solution no other solution beats. | Post 15 |
| Inversion | Croes’s 1958 name for reversing the stretch of a tour between two edges: the 2-opt move. | Post 11 |
| k-opt move | Remove k edges and reconnect the pieces into a new tour. | Post 14 |
| k-optimal | No move that removes at most k edges and adds k new ones shortens the tour. | Post 14 |
| Lin-Kernighan (LK) | Builds one improving move edge by edge, choosing its depth k as it goes, while the running gain stays positive. | Post 14 |
| LKH | Helsgaun’s implementation of Lin-Kernighan, with 5-opt steps and α-nearness candidates. | Post 14 |
| Local optimum | A tour no tour in its neighborhood beats; always relative to a set of moves. | Post 11 |
| Local search | Start from a complete tour and keep making small improving changes until none helps. | Post 11 |
| Move | One small change to a tour, such as a 2-opt reversal, a swap or a relocation. | Post 11 |
| Neighbor list | For each city, its K closest cities, sorted by distance; new edges are only tried to cities on it. | Post 13 |
| Neighborhood, N(T) | The set of tours reachable from T with one move. | Post 11 |
| Or-opt | Cut out a segment of up to three consecutive stops and insert it, in the same direction, into another gap. | Post 12 |
| Pivoting rule | The rule for which improving move to take: first improvement or best improvement. | Post 12 |
| Pure move | A k-opt reconnection in which no removed edge comes back. | Post 14 |
| Quadrant neighbors | The closest cities in each of the four quadrants around a city, so candidates exist in every direction. | Post 13 |
| Random restart | Run local search again from a fresh random tour, keeping nothing from the last run. | Post 15 |
| Relocate | Take one stop out, close the gap, and insert it between two other neighbours. | Post 12 |
| Reversal bit | A flag on each segment of a two-level list; reversing the whole segment means flipping one bit. | Post 13 |
| Search landscape | The solutions, the neighborhood joining them, and the cost of each. | Post 15 |
| Segment | A stretch of consecutive stops in a tour. | Post 12 |
| Swap | Exchange the positions of two stops. | Post 12 |
| Two-level doubly linked list | A tour cut into about √n segments, each with a reversal bit, so a 2-opt move costs O(√n). | Post 13 |
Iterated local search and metaheuristics
| Term | Meaning | First defined in |
|---|---|---|
| Acceptance criterion | The rule that decides whether the new local optimum replaces the current one. | Post 18 |
| Annealing-style acceptance (LSMC) | Keep a worse tour with probability e^(−Δ/T), so bigger losses are kept less often. | Post 18 |
| Better | Accept the new local optimum only if it is strictly shorter. | Post 16 |
| Diversification | Moving on to new regions of the search, as random walk does. | Post 18 |
| Double bridge | Break four edges, leaving segments A1 A2 A3 A4, and reconnect them as A2 A1 A4 A3, none reversed. | Post 16 |
| Fell back | Local search after a kick ended on exactly the tour it was kicked from. | Post 17 |
| History | The record of earlier iterations that perturbation and acceptance may depend on. | Post 16 |
| Intensification | Staying close to the best tours found, as the Better rule does. | Post 18 |
| Iterated local search (ILS) | Repeat: kick the current local optimum, run local search, decide whether to keep the result. | Post 16 |
| Kick (perturbation) | A deliberate change to the current local optimum that moves the search out of its basin. | Post 16 |
| Large-step Markov chains | Martin, Otto and Felten’s 1991 name for their double-bridge method with annealing-style acceptance. | Post 18 |
| Late acceptance hill climbing (LAHC) | Accept the new tour if it is no longer than the current tour was L iterations ago. | Post 18 |
| Local kick | A double bridge whose edges are picked near one out-of-place city rather than at random. | Post 17 |
| Not worse | Accept the new local optimum if it is shorter or equally long; the rule of Posts 16 and 17. | Post 18 |
| Population | A set of solutions kept together, which decides which new solutions survive. | Post 18 |
| PyVRP | An open-source VRP solver package for Python; an ILS since version 0.13. | Post 16 |
| Random walk acceptance | Always accept the new local optimum. | Post 16 |
| reinterpretcat/vrp | A Rust VRP solver built on ruin and recreate, a hyper-heuristic and a population. | Post 16 |
| Restart criterion | Accept only improvements, and after a set number of iterations without one, jump to a fresh starting tour. | Post 18 |
| Ruin and recreate | Remove part of a solution and rebuild it. | Post 16 |
| Segment swap | A-B-C-D → A-C-B-D: often mistaken for a double bridge, but it changes only three edges. | Post 17 |
| Stopping criteria | Iteration budget, time budget, no improvement for k iterations, or reaching a target cost. | Post 19 |
| Strength (of a perturbation) | The number of solution components a kick changes; for the TSP, edges. | Post 17 |
| Temperature, T | The parameter of annealing-style acceptance, in the same units as the tour cost. | Post 18 |
| Termination condition | The test that reads the history and decides whether ILS stops or continues. | Post 19 |
Statistics and experiments
| Term | Meaning | First defined in |
|---|---|---|
| Distribution | How often each value, or band of values, occurs. | Primer D |
| Expected value, E[X] | The long-run average: Σ xᵢ · pᵢ over the possible values xᵢ and their probabilities pᵢ. | Primer D |
| Median | The middle value of the sorted results; with an even count, the average of the two middle values. | Primer D |
| p-th percentile | The value below which p% of the results fall. | Primer D |
| Probability | A number between 0 and 1 saying how often an event happens in the long run. | Primer D |
| Pseudo-random generator | Produces numbers that look random but are completely determined by a seed. | Primer D |
| Reproducible | Gives the same result on every rerun and machine, as a fixed seed does; not the same as fair. | Primer D |
| Sample | A set of values drawn at random, used to describe a population too large to list. | Primer D |
| Sample mean, x̄ | The average of a sample. | Primer D |
| Sample standard deviation, s | The spread of a sample, computed with N − 1 in the denominator. | Primer D |
| Seed | The starting value of a pseudo-random generator. | Primer D |
| Standard deviation, σ | The square root of the variance, in the same units as the values. | Primer D |
| Standard error | s/√N: how far a sample mean typically lies from the true mean. | Primer D |
| Success within a budget | The chance of at least one success in k independent tries: 1 − (1 − p)ᵏ. | Primer D |
| Uniform random number | A number u drawn from [0, 1) so that every interval of length p contains it with probability p. | Primer D |
| Variance | The average squared distance from the mean, E[(X − μ)²]. | Primer D |
Notation
Most posts share these symbols. Where two posts use different letters for the same idea, or one letter for different ideas, the last column says so.
| Symbol | Meaning | Where |
|---|---|---|
| n | Number of stops (cities, vertices) | Throughout |
| d(i, j) | Distance or cost from stop i to stop j | Post 1 on |
| D | The n × n distance matrix | Post 1, Post 2 |
| w(e) | Weight of edge e in a graph; the same number as d(i, j) | Primer A |
| G = (V, E), m | A graph with vertex set V and edge set E; m = |E| edges | Primer A |
| π = (π₁, …, πₙ) | A tour written as a permutation of the stops | Post 1 |
| πᵢ | Lagrangian penalty on city i (a different use of π) | Post 5 |
| c(π), c(T) | Cost of a tour. Post 10 also writes c(T) for the cost of the minimum spanning tree T | Post 1, Post 5, Post 11 |
| f(s), C(s) | Cost of solution s: f in the landscape language of Post 15, C in the ILS posts | Post 15, Post 16 |
| OPT, ALG(I) | Optimal cost; cost of an algorithm’s answer on instance I | Post 10 |
| K | Threshold of TSP-DECISION in Post 2; neighbor list length in Post 13 | Post 2, Post 13 |
| O(·), Ω(·), Θ(·) | Upper, lower and exact growth rates | Primer B |
| x(i, j) | 0/1 variable: 1 if the tour drives from i to j | Post 6 |
| u(i) | MTZ position of stop i in the tour | Post 6 |
| UB, LB | Upper bound and lower bound in branch and bound | Post 5 |
| ρ | Approximation ratio | Post 10 |
| N(T), N(s) | Neighborhood of a tour: the tours one move away | Post 11, Post 15 |
| Δ | Change in tour length from a move, or between two local optima; negative means shorter | Post 11, Post 18 |
| t₁, t₂, t₃, t₄ | The four cities around a 2-opt move; t₁–t₂ and t₃–t₄ are removed | Post 13 |
| xᵢ, yᵢ, gᵢ, Gᵢ | Lin-Kernighan: removed edge, added edge, step gain |xᵢ| − |yᵢ|, running gain | Post 14 |
| MT(k) | Number of ways to reconnect the pieces after removing k edges | Post 14 |
| ŝ | A local optimum | Post 15 |
| s_opt | A global optimum | Post 15 |
| s* | The current local optimum in the ILS posts | Post 16 |
| s′, s*′ | The kicked solution and the new local optimum after local search | Post 16 |
| T | A tour in Posts 5, 11 and 12; the MST in Post 10; the temperature in Post 18; Tᵢ are comb teeth in Post 7 | Several |
| L | Late-acceptance history length | Post 18 |
| u, p | A uniform random number, and a probability | Primer D |
| E[X], μ, σ, x̄, s | Expected value, mean, standard deviation, sample mean, sample standard deviation | Primer D |
The running examples
Every hand-worked example uses eight stops: A(2,2) B(6,1) C(9,3) D(8,7) E(5,9) F(1,8) G(4,5) H(10,9), coordinates in kilometres. Distances are straight lines rounded to units of 100 m. The heatmap outlines the optimal tour, A-B-C-D-H-E-F-G-A, and the strip adds up its legs.
The eight stops and their optimal tour
| A | B | C | D | E | F | G | H | |
|---|---|---|---|---|---|---|---|---|
| A | · | 41 | 71 | 78 | 76 | 61 | 36 | 106 |
| B | 41 | · | 36 | 63 | 81 | 86 | 45 | 89 |
| C | 71 | 36 | · | 41 | 72 | 94 | 54 | 61 |
| D | 78 | 63 | 41 | · | 36 | 71 | 45 | 28 |
| E | 76 | 81 | 72 | 36 | · | 41 | 41 | 50 |
| F | 61 | 86 | 94 | 71 | 41 | · | 42 | 91 |
| G | 36 | 45 | 54 | 45 | 41 | 42 | · | 72 |
| H | 106 | 89 | 61 | 28 | 50 | 91 | 72 | · |
- A→B41Σ 41
- B→C36Σ 77
- C→D41Σ 118
- D→H28Σ 146
- H→E50Σ 196
- E→F41Σ 237
- F→G42Σ 279
- G→A36Σ 315
Total: 315 × 100 m
Key numbers on the eight stops, each from the post that computes it:
| Fact | Value | Source |
|---|---|---|
| Distinct tours | 2,520 | Post 2 |
| Optimal tour A-B-C-D-H-E-F-G-A | 315 | Post 2 |
| Average length of a random tour | 488 | Primer D |
| Nearest neighbour from A, A-G-E-D-H-C-B-F-A | 385 | Post 9 |
| Minimum spanning tree | 259 | Primer A |
| Degree-only LP (four two-stop loops) | 282 | Post 6 |
| Optimum of the six-stop subset A, B, C, D, G, H | 247 | Post 4 |
| Adjacent-swap local optima | 46 | Post 15 |
| The adjacent-swap trap A-B-C-G-D-H-E-F-A | 356 | Post 15 |
And on berlin52, the measuring instance:
| Fact | Value | Source |
|---|---|---|
| Cities | 52 | Post 0 |
| Distinct tours | about 7.76 × 10⁶⁵ | Post 1 |
| Optimal tour | 7,542 | Post 0 |
| Minimum spanning tree | 6,078 | Primer A |
| 1-tree bound, city 1 special | 6,172 | Post 5 |
| Assignment bound | 6,287 | Post 5 |
| Held-Karp bound, rounded up | 7,542 | Post 5 |
| Nearest neighbour from city 1 | 8,980 (19.1%) | Post 9 |
| Christofides | 8,595 (14.0%) | Post 10 |
| 2-opt from the nearest-neighbour tour | 7,842 (4.0%) | Post 11 |
| 2-opt plus Or-opt | 7,749 (2.7%) | Post 12 |
| 3-opt | 7,741 (2.6%) | Post 14 |
| Simplified Lin-Kernighan, starts reaching 7,542 | 39 of 52 | Post 14 |
| Iterated local search, seeds reaching 7,542 | 100 of 100 | Post 19 |