Build a TSP tour
Click cities to append them to the route, or load one of the tours from the chapter. The cost table uses the approximate driving times in the TeX source.
Current route
Driving-time matrix
Traveling salesman problem
Input
- An integer n.
- A nonnegative cost c(i,j) for every ordered pair of cities.
Output
- A permutation π of 1,2,…,n.
Goal
A tour has no real beginning
Although the story starts at a home city, the same cycle can be written starting at any city. The total tour cost is unchanged by rotation.
Try every permutation
For the 7-city instance, fixing Ithaca as the start leaves 6! = 720 orders to check. The enumerator below steps through those orders and keeps the best tour seen so far.
Factorial growth explorer
Nearest neighbor and nearest insertion
A heuristic is fast and always returns a tour, but it is not guaranteed to be optimal.
Nearest neighbor
Repeatedly visit the closest unvisited city from the current city.
Nearest insertion
Start with a small cycle, then insert the city that increases the tour length the least.
A lower bound proves every tour is at least this long
For minimization problems, one way to argue that a solution is good is to show that every feasible solution has objective value at least some lower bound.
For TSP, every tour uses exactly n transitions. If cmin is the smallest transition cost in the table, then every tour has cost at least n cmin.
When the simple bound is tight
For cities equally spaced around a circle, the nearest-neighbor distance is the side length of the polygon. The perimeter tour has length exactly n cmin, so the lower bound proves optimality.
Build visual lower-bound certificates
A tour must enter and leave each disc around a city. If the discs do not overlap, the sum of their diameters is a valid lower bound. Moats around separated groups give additional lower-bound terms because a tour must cross them.
Three-disc lab
Adjust radii. If every pair of discs is non-overlapping, the lower bound is 2(r₁+r₂+r₃).
Two-cluster moat sketch
The left triangle and right triangle have their own disc certificates. The tour must also cross separating moats to connect the groups.
Use TSP by adding a dummy city
The playlist problem is a path problem: the first and last songs are not connected. TSP is a cycle problem. The chapter’s trick is to add a dummy city with zero cost to and from every song.
Start the TSP tour immediately after the dummy city and delete the dummy city. The remaining order is a playlist with the same cost.
