Lecture 5.1 Recap

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.

2-opt by hand

Added by the instructor Lecture 5.1, Sec. 3, Ex. 3(a) and 3(b)

Lecture The example

“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.”

\[ D = \begin{bmatrix} 0 & 8 & 6 & 9 & 1 & 5 \\ 3 & 0 & 1 & 5 & 4 & 2 \\ 9 & 2 & 0 & 3 & 1 & 1 \\ 8 & 2 & 1 & 0 & 10 & 6 \\ 6 & 7 & 10 & 1 & 0 & 10 \\ 6 & 2 & 5 & 2 & 1 & 0 \end{bmatrix} \tag{7} \]

“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?

Another view The costs the panels below use

New costs are whole numbers from 1 to 10, drawn at random, for a fresh problem that follows the same logic as Ex. 3.

Lecture A change: two arcs out, the segment between them reversed

“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.”

Another view Fig. 8, one change at a time

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.

Tour
Arcs outSequenceCost

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.

Lecture Code block 12: the same nine changes, in order

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]
\[ \overbrace{\sum_{j = 3}^{n - 1} ( 1 )}^{\text{first arc } a} + \overbrace{\sum_{i = 2}^{n - 2} \sum_{j = i + 2}^{n} ( 1 )}^{\text{arcs } b \text{ to } n - 2} = \frac{n ( n - 3 )}{2} = 9 \text{ for } n = 6 \tag{6} \]

Lecture When a change is kept

“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.”

Another view Work Table 2 from the table of all 120 tours

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:

  1. The yellow row is the tour the scan is on, drawn with its arcs lettered a to f. Its 9 changes are taken in the order of Code block 12: arcs a and c out first, then a and d, a and e, b and d, and so on to d and f.
  2. Work out the sequence the next change gives, find it among the rows listed, and click it. The row clicked goes into the table below, with the number of the change that gives it.
  3. If its cost is lower than the yellow row’s, it becomes the yellow row and the scan starts again at its first change, a and c. If not, the scan goes on to the next change of the same yellow row.
  4. When none of the yellow row’s 9 changes is lower, 2-opt stops: that row is the local optimum.
Start
Rows listed
#RowSequenceCostChange
Table 2 so far: each row picked, with its number in the table of 120 tours.
The lecture’s own walk through Table 2

“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.”

Multi-start: a random tour, then 2-opt, again and again

Added by the instructor Lecture 5.1, Secs. 1 and 3, Ex. 3(c) and 3(d)

The review asksWhy is any random permutation of the stops a feasible tour for the TSP?

Lecture Any permutation is a tour, so start anywhere

“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.”

Another view Multi-start on the same costs

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.

StartRandom rowLocal optimumCostBest so far

Lecture Ex. 3(c) and 3(d)

“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.”

A claim to check One worked conclusion, with a defect

“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 defect

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.

How the lecture checks Ex. 3: Triangulate, Landmark, Assumptions

“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.

FamilyCheckAsks
ScreensUnitsDo the units work out?
BoundsDoes it break a hard limit?
AssumptionsAre the preconditions satisfied here?
ExpectationsPriorDoes it land inside the estimate committed before the run?
NudgeDoes the answer move the right way?
LandmarkDoes it hit a case already known?
ConfirmationsTriangulateDoes an independent route agree?
BalanceDo the parts add up to the whole?
SourceDoes the document say what is claimed?
Lecture 1.2, Table 2: The nine validation checks, each with the memorable case worked out in the prose below. The rule: screen every result, expect what is used, confirm what is signed.

Estimating a tour’s length

Added by the instructor Lecture 5.1, Sec. 4, Ex. 4

Lecture Eq. 13, and the tour of North Carolina

\[ \boxed{\; \hat{d}_m^{TSP} = \varphi\sqrt{ma} \approx 0.908\sqrt{ma} \;} \tag{13} \]

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.”

Map of North Carolina with the best of the 100 multi-start tours through the 100 county points.
Lecture 5.1, Figure 14: The best tour of the 100 NC counties that 2-opt finds from 100 random starts.

Six questions

Added by the instructor Lecture 5.1, Secs. 1, 3 and 4

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?

  1. Landmark, since the tour of Ex. 3(a) is a case whose answer was already known
  2. Balance, since the tour’s arc costs add up to its total cost of 12
  3. Triangulate, since a person and a program reach one tour by two independent routes
  4. Prior, since the hand trace was written down before the code was run
  5. Nudge, since each change the procedure kept moved the cost down, the right way
Answer

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?

  1. the nodes \(\pi_{i+1}\) and \(\pi_j\) swapped, with the nodes between them left in place
  2. the arcs out of \(\pi_i\) and out of \(\pi_j\) removed, and the segment from \(\pi_{i+1}\) to \(\pi_j\) reversed
  3. node \(\pi_{i+1}\) moved to position \(j\), with the nodes between them shifted forward
  4. the nodes at positions \(i\) and \(j\) exchanged, as the exchange procedure of the UFL does
Answer

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?

  1. both restrict the tours the solver may return, and are listed apart only to keep the model readable
  2. the solver enforces the assumption too, since TSP(c) refuses a cost matrix that is not symmetric
  3. the first restricts the solutions, while the second is something that has to be true about the world
  4. a false assumption only gives a somewhat worse tour, while a broken constraint gives no tour at all
Answer

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?

  1. it is kept, and a new scan starts from that tour at its first change
  2. it is noted, and the scan goes on to keep the lowest-cost change among all of them
  3. it is kept, and the scan goes on from the next change of the same scan
  4. it is kept, and the procedure stops, since a lower cost has been reached
Answer

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?

  1. that it is optimal, since any tour can be reached from any other by 2-opt changes
  2. that it is a local optimum, the best of the tours one change away, and not proved optimal
  3. that it is within a percent of the optimum, since a 2-opt tour always is
  4. that it is optimal, since a tour none of whose changes helps has no crossing arcs left
Answer

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?

  1. their locations, so that the distances between them can be measured
  2. the distance from the DC to each of them, since the estimate sums those
  3. the road distances between them, since the estimate is in road miles
  4. only how many there are and the area of the region they are spread over
Answer

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.”

Other questions worth asking

Added by the instructor Lecture 5.1, Secs. 1 and 3

The review offers these as examples of what a student may ask about the lecture. Each answer is the lecture’s.

Why is a problem with so many possible tours still called easy in practice?

“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).”

Why does a tour’s cost include the trip back to the depot once the vehicle is empty?

“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.”

Why would a heuristic start from a random tour rather than a carefully built one?

“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.”

What is a spacefilling curve still good for, now that its use in routing is obsolete?

“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.”