What is the TSP?

Read first

• Primer A: graphs. You need four words from it. A vertex is a point. An edge joins two vertices and carries a weight. A path is a sequence of edges that does not repeat a vertex. A cycle is a path that comes back to where it started. You also need the complete graph, where every pair of vertices has an edge, and the distance matrix that stores those edge weights.

The question this post answers: what exactly is the Traveling Salesman Problem, and what is a solution to it?

Intuition

Every delivery route, however many constraints it carries, comes down to one van leaving a depot, making stops in some order, and coming back. The TSP is that problem with everything else removed.

Here are eight stops. A is the depot. The coordinates are in kilometres on a flat plane, not latitude and longitude, so distance is a straight line.

I compute distances the way TSPLIB does for this kind of instance: the Euclidean distance, rounded to the nearest whole number. To keep some precision I measure in units of 100 m. A to B is √(4² + 1²) = √17 ≈ 4.123 km, which is 41.23 units and rounds to 41. Doing that for every pair gives the distance matrix, in units of 100 m.

A tour is any order that visits every stop exactly once and then returns to the first one. The cost of a tour is the sum of the distances along it, including the last leg home.

Let me price the most obvious tour, alphabetical order. A tour uses exactly one cell in each row of the matrix (where it leaves each stop) and one in each column (where it arrives). The outlined cells below are the eight legs, and the strip underneath adds them up in driving order.

The first six legs are short. The damage is in the last two: G sits in the middle, H is in the far corner, and A is in the opposite corner. Moving H earlier, between D and E, fixes that:

That tour costs 315, a hundred less than alphabetical order. It is also the best possible tour for these eight stops. I know that because I checked every tour by computer, which is the subject of the next post.

Step through the diagram below to see both tours and the change that turns one into the other. The diagrams in this series show each leg’s straight-line length in kilometres, unrounded, so their totals can differ by a few tenths from the rounded matrix: the optimal tour is 31.5 km in matrix units and 31.7 km unrounded. That gap is the same rounding effect that matters for berlin52, below.

Two things to take from this already. Every tour visits the same eight stops, so the only thing you choose is the order. And the cost depends on the order in ways that are hard to see from the list: one stop in the wrong place cost 100.

The formal idea

The problem. We have n cities, numbered 1 to n. For every ordered pair of cities i and j, d(i, j) ≥ 0 is the cost of going from i to j. These costs form an n × n distance matrix D. In graph terms, the cities are the vertices of a complete graph and d(i, j) is the weight of the edge between them.

A tour is a permutation. Write a tour as π = (π₁, π₂, …, πₙ), where π₁ is the first city visited, π₂ the second, and so on. Each city appears exactly once, so π is a permutation of {1, …, n}. The tour is a cycle: after πₙ the salesman goes back to π₁.

Tour cost.

c(π) = d(π₁, π₂) + d(π₂, π₃) + … + d(πₙ₋₁, πₙ) + d(πₙ, π₁)

The last term is the return leg. Forgetting it is the most common bug I see in hand-rolled TSP code.

The TSP. Find a permutation π that makes c(π) as small as possible. TSPLIB, the standard library of test instances, states it as finding “a roundtrip of minimal total length visiting each node exactly once.”

The diagram below draws the optimal permutation (A, B, C, D, H, E, F, G) as a cycle; follow the arrows and add the labels to get 315, including the return leg from G to A.

flowchart TD
  A -->|41| B
  B -->|36| C
  C -->|41| D
  D -->|28| H
  H -->|50| E
  E -->|41| F
  F -->|42| G
  G -->|"36, return leg"| A

Many permutations, one tour. A cycle has no natural first city. (A, B, C, D, H, E, F, G) and (B, C, D, H, E, F, G, A) are the same tour written from a different starting point. So fix city 1 as π₁. That leaves (n − 1)! orderings of the other cities.

Symmetric vs. asymmetric. The TSP is symmetric when d(i, j) = d(j, i) for every pair, so the matrix equals its own transpose. Then a tour and the same tour driven backwards cost the same, and there are (n − 1)!/2 distinct tours. With 8 stops that is 7!/2 = 2,520.

The TSP is asymmetric (ATSP) when some d(i, j) ≠ d(j, i). Road networks do this all the time: one-way streets, turn restrictions, a flyover in one direction only. Direction becomes part of the answer, and all (n − 1)! orderings are different tours: 5,040 for 8 stops.

To see it on our example, suppose H→D is a one-way detour costing 50 instead of 28, while D→H stays 28. The diagram below shows the two directions of that one pair as separate edges with separate costs.

flowchart LR
  D -->|28| H
  H -->|"50, one-way detour"| D

The optimal tour driven forwards (…D→H…) still costs 315. Driven backwards (…H→D…), it costs 337. Same stops, same order, different cost.

A path is not a tour. Dijkstra’s algorithm (1959) finds a shortest path from one vertex to another. Run it from A to H on our matrix and you get the direct edge, 106 (A→D→H also totals 106 after rounding). That path visits two or three stops and never comes back. It is allowed to skip vertices; a tour is not. A minimum spanning tree is a different mistake in the same family: it connects every stop, but it has no cycle, and some stops are leaves with one edge. A tour uses exactly two edges at every stop.

Step through the diagram below to compare the three structures on the same eight stops.

The running example. berlin52 is a TSPLIB instance: 52 locations in Berlin, attributed in the file to Grötschel (spelled “Groetschel”), symmetric, with EDGE_WEIGHT_TYPE: EUC_2D. That last field means exactly what I did above: Euclidean distance on plane coordinates, rounded to the nearest integer with nint. Its proven optimal tour has length 7,542, and TSPLIB publishes that tour. If you sum the same tour without rounding each edge, you get about 7,544.37. That is not a better or worse answer. It is a different instance. TSPLIB’s FAQ says that every claim so far to have beaten a published optimum came from computing distances the wrong way, and the first error it lists is evaluating them as floating-point numbers.

Common misconceptions

“The TSP is a shortest path problem, so Dijkstra solves it.” Dijkstra returns a path between two vertices. It may skip any vertex that is not on the way, and it does not return. The TSP asks for a minimum-cost cycle through all vertices. On our example Dijkstra’s answer from A to H is 106 and visits at most three of the eight stops.

“Once I have the distance between every pair of stops, I have solved it.” On a road network you often run a shortest-path algorithm between every pair of stops to build the matrix. That matrix is the input to the TSP. The answer is an ordering, and you still have to choose it.

“The minimum spanning tree is the cheapest way to connect the stops, so it is the tour.” A tree has no cycle and has leaves. In our example, F, G and H are leaves of the tree, with one edge each, and D has three. The tree costs 259 and the tour costs 315. The tree is useful later as a lower bound (Held and Karp, 1970), but it is not a tour.

“Direction doesn’t matter.” Only when the matrix is symmetric. With the one-way H→D detour, the same order costs 315 one way and 337 the other.

Try it in Python

Everything in this post is plain arithmetic, so you don’t need a solver to check it. This script loads berlin52 from TSPLIB, prices its published optimal tour with the same rounded EUC_2D distances I used above, and then prices the same tour without rounding. You need two files from the TSPLIB site: berlin52.tsp (the coordinates) and berlin52.opt.tour (the optimal tour).

import math

def read_coords(path):  # TSPLIB .tsp file: one "id x y" line per city
    body = open(path).read().split("NODE_COORD_SECTION")[1].split("EOF")[0]
    return {int(i): (float(x), float(y)) for i, x, y in (ln.split() for ln in body.strip().splitlines())}

def read_tour(path):    # TSPLIB .opt.tour file: city ids, ended by -1
    body = open(path).read().split("TOUR_SECTION")[1]
    return [int(t) for t in body.split() if t.lstrip("-").isdigit() and int(t) > 0]

def euc_2d(p, q):       # TSPLIB EUC_2D: Euclidean distance, rounded to the nearest integer
    return int(math.hypot(p[0] - q[0], p[1] - q[1]) + 0.5)

def tour_cost(tour, dist):
    return sum(dist(tour[i], tour[(i + 1) % len(tour)]) for i in range(len(tour)))  # includes the return leg

xy = read_coords("berlin52.tsp")
tour = read_tour("berlin52.opt.tour")
assert sorted(tour) == sorted(xy), "a tour must visit every city exactly once"

print("cities:", len(tour))
print("rounded (EUC_2D):", tour_cost(tour, lambda a, b: euc_2d(xy[a], xy[b])))
print("unrounded:       ", round(tour_cost(tour, lambda a, b: math.dist(xy[a], xy[b])), 2))

It prints:

The assert line is the definition of a tour from this post, as code: every city appears exactly once. The two totals are the same tour priced under two different distance functions, which is why comparing a result against the published 7,542 only makes sense with rounded distances.

Exercise

Take the eight-stop matrix above. Make it asymmetric by setting d(H, D) = 50 and leaving d(D, H) = 28. Price the optimal tour A-B-C-D-H-E-F-G-A forwards and backwards, and confirm you get 315 and 337. Then answer: how many distinct tours does this asymmetric instance have, and how many did the symmetric one have?

Hint: fix A as the first city in both cases. In the asymmetric case, does a tour and its reverse still count as one?

What this method can’t do yet

So far I can define a tour, price it, and recognise the optimum when someone hands it to me. I cannot yet find it. For eight stops I let a computer price all 2,520 tours. For berlin52 the same count is 51!/2, about 7.76 × 10⁶⁵ tours. That raises the obvious question: how hard can it be? Post 2, “Why is the TSP hard?”, answers it.

References

• 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.
• Dijkstra, E. W. (1959). “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1: 269–271.
• Held, M., and Karp, R. M. (1970). “The Traveling-Salesman Problem and Minimum Spanning Trees.” Operations Research 18(6): 1138–1162.
• Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., and Shmoys, D. B., eds. (1985). The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley.
• Reinelt, G. (1991). “TSPLIB—A Traveling Salesman Problem Library.” ORSA Journal on Computing 3(4): 376–384.
• Reinelt, G. TSPLIB 95 documentation (tsp95.pdf), FAQ, berlin52.tsp, berlin52.opt.tour, and the list of optimal solutions. University of Heidelberg. https://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
• Applegate, D. L., Bixby, R. E., Chvátal, V., and Cook, W. J. (2006). The Traveling Salesman Problem: A Computational Study. Princeton University Press.

See the whole series · ← All writing