ISE 754 (Fall 2026) 5.1 Traveling Salesman Problem
Watch on YouTube →
Overview
Michael G. Kay introduces the traveling salesman problem (TSP) as a linear assignment problem constrained to produce one tour, then explains how to add subtour-elimination constraints iteratively because enumerating every node subset requires exponentially many constraints. He demonstrates first-improvement 2-opt with multistart random tours, derives an expected-length estimate of 0.908√(mA), and compares the heuristic with an exact mixed-integer solution for 100 North Carolina county population centroids, where the heuristic is about 1.6% longer.
Key takeaways
- The linear assignment model is not sufficient for TSP because it can select several disconnected subtours; a valid solution must contain one cycle through every node.
- Subtour elimination is practical through iterative constraint generation: detect a subtour in the current solution and add a constraint for that subtour instead of enumerating exponentially many node subsets.
- Because every node permutation is a feasible TSP tour, multistart 2-opt can begin with random tours and spend its effort improving them rather than repairing feasibility.
- For six nodes, the 2-opt procedure checks nine arc exchanges; a tour is locally optimal only after every exchange has been tested without finding an improvement.
- The expected tour length approximation is 0.908√(mA), based on circle geometry and calibrated to the two-node case.
- For 100 North Carolina county centroids, multistart 2-opt was about 1.6% above the exact mixed-integer optimum, and the simple estimate was within one mile of a route longer than 2,000 miles.
Chapters
- Routing differs from point-to-point transportation because a vehicle visits multiple pickup or delivery locations on one route.
- A TSP tour starts at a depot, visits every node, and returns to the depot; the visit order is a permutation of the other n−1 nodes.
- The linear assignment formulation can produce multiple disconnected subtours, so a valid TSP solution requires an added constraint enforcing one tour.
- Subtour-elimination constraints apply to subsets of nodes, but explicitly listing every subset requires exponentially many constraints.
- An iterative mixed-integer approach solves the assignment model, detects subtours, and adds a constraint for a subtour found in that solution before solving again.
- Any permutation of the nodes forms a feasible TSP tour, allowing the search to focus on improvement rather than constructing a feasible solution.
- The 2-opt heuristic exchanges two nonadjacent arcs by reversing the intervening node sequence; the six-node example has nine possible exchanges.
- A multistart heuristic applies first-improvement 2-opt to random tours, keeps each improving solution, and repeats until all nine exchanges fail to improve it.
- Pairwise savings compare two separate depot round trips with one combined route from the depot to customer i, then customer j, and back.
- The expected-length approximation uses the average radial distance of two-thirds of a circle's radius and an average angle of 90 degrees.
- Calibrating the general estimate to the two-node case gives a coefficient of 0.908, yielding expected tour length approximately 0.908√(mA), where m is the number of nodes and A is their occupied area.
- The estimate predicts total distance without identifying the actual tour, making it useful for tactical logistics planning.
- The example routes through the population centroids of all 100 North Carolina counties and returns to the starting point.
- A multistart 2-opt search turns a random permutation into a tour close to the optimum.
- The completed mixed-integer linear program provides the global optimum, while the multistart 2-opt result is about 1.6% longer.
- For a tour exceeding 2,000 miles, the expected-length formula estimates the optimal distance to within one mile.
Transcript excerpt
0:01 This is the first routing lecture. We'll be covering the topic of the traveling salesman problem. Routing problems are distinguished from earlier when we talked about transportation. We were solving the pointto-point transportation where we had a single pickup and delivery. With routing problems, we have multiple pickups and deliveries. One thing to note is that if we have situations where the vehicle is actually empty and not carrying a load, then that is considered multiple routes. So we're basically dealing with the case of a single route for a vehicle. And in the case of where there's an empty portion, it's basically just starting another routing problem. For the traveling salesman problem,
0:58 we'll be dealing with what we'll term a tour. And the tour starts at the first node, conventionally called the depot, visits the series of nodes, all of the nodes, and then returns back to the starting location. And that represents a tour. The tour can be represented as the sequence of nodes visited. And those that sequence corresponds to a permutation of n minus one nodes. And then since we're returning back to one, the one gets repeated at the end. The model of the traveling salesman
1:51 problem is a special case of the linear assignment problem covered in lecture 4.2. And for that problem, the only additional thing we're adding to it is an extra constraint. And the constraint is that the solution has to correspond to a single tour. This figure figure five shows the diff shows what happens in terms of solving a problem like this and in terms of the constraint of having a single tour when solving it as a linear assignment problem. You can have cases where you have multiple tours like in this uh top corner right here. There are
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Michael G. Kay.