5.1: Traveling Salesman Problem · ISE 754, Fall 2026 · in class 29 October 2026
A recap answers what students found most difficult in their pre-class review of the lecture, along with anything the instructor adds. Blue Lecture panels quote the lecture; orange Another view panels look at the same idea from another side.
“Determine a tour of the six nodes of Fig. 3 by 2-opt improvement of the tour 1-2-3-4-5-6-1, under the arc costs \(D\) of Eq. 7, by hand, in Julia, and by multi-start from random starting tours, and determine how far the tours it finds are from the optimum.”
“Note that \(D\) is not symmetric: the cost from node 1 to node 2 is 8, and from node 2 to node 1 is 3, as on two one-way streets.”
The review asksStarting from 1-2-3-4-5-6-1 at a cost of 38, how would you find out whether the tour 2-opt ends on is the best tour of these six nodes?
New costs are whole numbers from 1 to 10, drawn at random, for a fresh problem that follows the same logic as Ex. 3.
“In Fig. 8, the letters a to f are the arcs of the tour 1-2-3-4-5-6-1, and the first change gets rid of arcs a and c and adds instead an arc from 1 to 3 and another from 2 to 4, replacing two arcs with two other arcs so that the tour is still feasible: it now goes from 1 to 3, back to 2 and over to 4.”
“A change is made by taking the segment between the two arcs removed and flipping it. Removing a and c flips 2-3 into 3-2; removing a and d gives the route 1-4-3-2-5, the segment 2-3-4 flipped; removing a and e flips everything from 2 to 5. These are the 2-opt changes, and they continue with b and d, b and e, and on through d and f. With \(n = 6\) there are nine of them in all, \(n(n - 3)/2\) (Eq. 6).”
“The tour up to \(\pi_i\), then the segment from \(\pi_{i+1}\) to \(\pi_j\) reversed, then the rest: the arcs out of \(\pi_i\) and out of \(\pi_j\) are removed, and arcs from \(\pi_i\) to \(\pi_j\) and from \(\pi_{i+1}\) to \(\pi_{j+1}\) are added.”
The lecture’s Fig. 8 draws two of the nine changes on one tour, so their arcs overlap. Here each change is drawn alone: Next takes them in the order of Code block 11, or click a row. Any tour can be the one changed, such as a tour Table 2 keeps.
| Arcs out | Sequence | Cost |
|---|
Green letters name the arcs of the tour being changed. Ink: arcs the change keeps. Blue: arcs it adds. Dashed with ×: the two arcs it removes. In the table, the reversed segment is shaded, as Fig. 8 boxes it.
1# Code block 12: the nine 2-opt changes of the tour 1-2-3-4-5-6-1 2π = [1:6; 1] 3println(π) 4for i = 1:length(π)-2 5 for j = i+2:min(length(π)-1, length(π)+i-3) 6 println(vcat(π[1:i], reverse(π[i+1:j]), π[j+1:end])) 7 end 8end
[1, 2, 3, 4, 5, 6, 1] [1, 3, 2, 4, 5, 6, 1] [1, 4, 3, 2, 5, 6, 1] [1, 5, 4, 3, 2, 6, 1] [1, 2, 4, 3, 5, 6, 1] [1, 2, 5, 4, 3, 6, 1] [1, 2, 6, 5, 4, 3, 1] [1, 2, 3, 5, 4, 6, 1] [1, 2, 3, 6, 5, 4, 1] [1, 2, 3, 4, 6, 5, 1]
“It is a first improvement procedure: others look at all the possibilities and take the best, but this one makes any improvement as soon as it sees it, and the new sequence becomes the base point. Whenever there is an improvement, the clock is put back and the scan starts again at the first change; it is not a continuation.”
“Table 2: The sequences 2-opt considers in Ex. 3(a), in order, with their costs. In each, the segment its change reverses is shaded blue, and Change counts the changes looked at since the last tour kept, in the order of the rows of the table in Fig. 8; each kept sequence is the tour the scan starts again from. A scan stops at its first change that lowers the cost, so only the last, from the local optimum, looks at all 9 changes of Eq. 6, verifying that none is lower: 2-opt does its most work at the end.”
The way an exam asks it: a numbered table lists every tour that starts at node 1 with its cost, and from a given start the rows 2-opt looks at are picked out of it in order. From row 1, the first row to find is row 25, 1-3-2-4-5-6-1, as in the lecture’s Table 2. To work it here:
| # | Row | Sequence | Cost | Change |
|---|
“In the run, 39 is not better than 38, but 32 is, so 1-4-3-2-5-6-1 becomes the new target and the scan starts over from it; flipping its first segment gives 1-3-4-2-5-6-1 at 31, the next target. From 31, the first change gets back to the tour of row 3, which has been seen before; if a tour were expensive to evaluate, as with one that needed a simulation, a dictionary keyed by the tour would keep it from being evaluated again. The next change gives 31 again, which is no improvement, and the one after it, 1-5-2-4-3-6-1, lowers the cost to 21, the new target. From 21, the first change gives 21 again, which is not taken, since an improvement has to be strict, and three changes later 1-5-4-2-3-6-1 reaches 12.”
“2-opt from 1-2-3-4-5-6-1, of cost 38, reaches the local optimum 1-5-4-2-3-6-1, of cost 12.”
“The tour found by hand and the one the implementation finds agree, a Triangulate check of Lecture 1.2: solving Ex. 3(a) by hand, as Table 2 does, and running Logjam’s code reach the same tour by two different routes, a person and a program.”
“It is important to get the mechanics right: once it has been done by hand and verified with the procedure, it is known really well, and the steps should be the same as the code’s.”
The review asksWhy is any random permutation of the stops a feasible tour for the TSP?
“The TSP is the basic routing problem, and in vehicle routing problems it is basically just a subroutine. What makes it simple and easy to solve is that it is unconstrained: any permutation is a feasible route. All that is done is to take a permutation of the integers 1 through 6 and make it into a tour, assuming a return to wherever it starts, by repeating its first node, the depot 1, at the end.”
“From this starting tour, 12 is the best 2-opt can do: it is a local minimum, the bottom of one valley in a mountain range, as for the UFL in Lecture 2.4. A different starting permutation could lead, by 2-opt changes, somewhere better, which is why a multi-start picks several different permutations, runs 2-opt from each and keeps the best, a very simplistic but very effective way.”
1algorithm multistart; 2{ input: n nodes, cost c(π) of a tour π, number of starts N } 3{ output: best tour πᵒ found, and its cost TCᵒ } 4begin 5 TCᵒ := ∞; 6 for k := 1 to N do 7 begin 8 π := a random tour of the n nodes; { easy construction } 9 π′, TC′ := twoopt with π; { improvement } 10 if TC′ < TCᵒ then πᵒ := π′, TCᵒ := TC′; 11 end; 12 return πᵒ, TCᵒ; 13end;
“Line 8 is the construction and line 9 the improvement; line 10 keeps the best tour over all of the starts, where 2-opt keeps the first improvement it sees.”
Each start is a random row of the table of 120 tours, a random tour with node 1 first, improved by 2-opt to its local optimum; the best so far is kept, and each start that improves on it is printed the way Code block 18 prints it. Any start can be sent up to the table panel and worked by hand.
Press Run multi-start.
| Start | Random row | Local optimum | Cost | Best so far |
|---|
“The best of 100 random starts is 2-1-5-4-3-6-2, of cost 9.”
“The optimal tour is 1-5-4-3-6-2-1, of cost 9.”
“From 1-2-3-4-5-6-1, 2-opt reaches 1-5-4-2-3-6-1 at a cost of 12 and stops, since none of its nine changes lowers the cost; the best of them is 13. A tour that no change improves is the optimal tour, so 12 is the lowest cost of all 120 tours of the six nodes.”
The last step. A tour that no 2-opt change improves is a local optimum, the best of the tours one change away, and nothing more. The case already known says otherwise, a Landmark: all 120 tours, by brute force, and Model 1 both give 1-5-4-3-6-2-1 at 9, so 12 is 33% above the optimum. Of the 120 rows of the table, 10 lead 2-opt to that optimum, 1 in 12, which is why multi-start runs from many.
“The optimum is a Landmark check of Lecture 1.2 on the 2-opt tours: the best of the 100 starts of Ex. 3(c) is optimal, and the local optimum of Ex. 3(a) is 33% above it. The count of 120 is an Assumptions check as well: Eq. 3 halves the count only when costs are symmetric, and under \(D\) the tour 1-2-3-4-5-6-1 costs 38 while its reverse, 1-6-5-4-3-2-1, costs 13, so all 120 have to be looked at. So is the crossing argument of Sec. 1, which needs Euclidean costs and which Ex. 3(a)’s trace therefore sets aside.”
Eqs. 2 and 3 count the tours of \(n\) nodes: \((n - 1)!\) when the arc costs are asymmetric, and \((n - 1)!/2\) when they are symmetric, which for \(n = 6\) is 120 and 60.
| Family | Check | Asks |
|---|---|---|
| Screens | Units | Do the units work out? |
| Bounds | Does it break a hard limit? | |
| Assumptions | Are the preconditions satisfied here? | |
| Expectations | Prior | Does it land inside the estimate committed before the run? |
| Nudge | Does the answer move the right way? | |
| Landmark | Does it hit a case already known? | |
| Confirmations | Triangulate | Does an independent route agree? |
| Balance | Do the parts add up to the whole? | |
| Source | Does the document say what is claimed? |
where \(\hat{d}_m^{TSP}\) = estimated length of a tour from a central DC through \(m\) customers (mi); \(m\) = number of customers; \(a\) = area of the region (mi²); \(\varphi\) = tour constant, fitted to the two-customer route.
“All the estimate needs to know is the area and the number of stops.”
“The estimated length of a tour of the 100 counties is 2,106.45 mi.”
“The best of 100 random starts is 2,141.21 mi.”
“The optimal tour of the 100 counties is 2,107.56 mi, and the best of the 100 starts is 1.6% above it.”
The review’s six, as written, renumbered and with the tour written \(\pi\) to match the lecture as revised on 29 October. Each answer opens with the lecture’s own words.
1. In Ex. 3(b), the tour found by hand and the tour Logjam’s twoopt returns agree. Which of the nine checks is that, and why?
C. Triangulate, since a person and a program reach one tour by two independent routes.
“The tour found by hand and the one the implementation finds agree, a Triangulate check of Lecture 1.2: solving Ex. 3(a) by hand, as Table 2 does, and running Logjam’s code reach the same tour by two different routes, a person and a program.”
2. Code block 12, line 6: println(vcat(π[1:i], reverse(π[i+1:j]), π[j+1:end])). What change to the tour π does this line print?
B. The arcs out of \(\pi_i\) and out of \(\pi_j\) removed, and the segment from \(\pi_{i+1}\) to \(\pi_j\) reversed.
“The tour up to \(\pi_i\), then the segment from \(\pi_{i+1}\) to \(\pi_j\) reversed, then the rest: the arcs out of \(\pi_i\) and out of \(\pi_j\) are removed, and arcs from \(\pi_i\) to \(\pi_j\) and from \(\pi_{i+1}\) to \(\pi_{j+1}\) are added.”
3. Model 1 lists “each node is left exactly once” under subject to: and “arc costs are given and need not be symmetric” under assumptions:. What does that difference mean?
C. The first restricts the solutions, while the second is something that has to be true about the world.
“assumptions: lists what must be true about the world, and it is the slot to reach for when the temptation is to write another constraint: a constraint restricts the solutions, while an assumption is something that has to be true about the world.”
Lecture 1.2, Sec. 3. Model 1’s implementation, TSP(c), checks only that the cost matrix is square, and Ex. 3 runs it on the asymmetric \(D\).
4. In 2-opt as the lecture runs it, what happens as soon as a scan finds a change that lowers the cost?
A. It is kept, and a new scan starts from that tour at its first change.
“It is a first improvement procedure: others look at all the possibilities and take the best, but this one makes any improvement as soon as it sees it, and the new sequence becomes the base point. Whenever there is an improvement, the clock is put back and the scan starts again at the first change; it is not a continuation.”
5. 2-opt stops at a tour that none of its changes improves. What does that show about the tour?
B. That it is a local optimum, the best of the tours one change away, and not proved optimal.
“From this starting tour, 12 is the best 2-opt can do: it is a local minimum, the bottom of one valley in a mountain range, as for the UFL in Lecture 2.4.”
“A solution from a heuristic procedure can never be guaranteed optimal without doing that; it is just the best known.”
6. A planner wants the expected length of tomorrow’s delivery tours with Eq. 13. What does it need to know about the customers?
D. Only how many there are and the area of the region they are spread over.
“All the estimate needs to know is the area and the number of stops.”
The review offers these as examples of what a student may ask about the lecture. Each answer is the lecture’s.
“The traveling salesman problem (TSP) is a well-solved problem, in practice and in approximation, though not in theory.”
“It is a hard problem in theory, since for \(n = 100\), \((n - 1)! \approx 9.33 \times 10^{155}\), and easy in practice, using multi-start random tour construction and 2-opt improvement, since each final 2-opt verification requires \(n(n - 3)/2 = 4{,}850\) tour cost calculations (Eq. 6).”
“In a peddling situation, the vehicle is loaded at the depot and makes all of its drop-offs, the last of them at node 6 of Fig. 3. The vehicle is then empty, but by convention the TSP includes the cost of getting back to the depot, so a tour is a route plus the return to the depot. The convention could be dropped, and it would be perfectly fine to assume the route ends at node 6, so it is not an assumption that is important to what is being done; it can be made or not.”
“In constrained problems, construction is an achievement; in unconstrained ones, it’s only the beginning, for when feasibility comes easily, the challenge shifts to improvement.”
“Under easy construction (e.g., the quadratic assignment problem and the TSP), the lack of constraints makes any random point or permutation a feasible solution, and it can then be improved, allowing construct-then-improve multiple times, or what is termed multi-start.”
“Its application in logistics is now obsolete. Its application elsewhere is not: when Bartholdi was the external reviewer of NC State’s operations research program, around 2016 or 2017, he reported that the 1988 paper was being cited quite a bit, because of geographic mapping applications and machine learning. A database of two-dimensional geographic information has no single key, since \(x\) and \(y\) have no obvious order, and a spacefilling curve gives each point one, which allows a join of two spatial databases. The curve has been more popular than ever.”