Algorithm Deep Dive: TSP Heuristics (Nearest Neighbor, 2-Opt & 3-Opt)

A Bit of History

The Traveling Salesman Problem (TSP) introduced in Part 14 is NP-hard. In 1958, Georges A. Croes introduced the 2-Opt local search heuristic to untangle self-crossing routes in Euclidean TSP instances. In 1965, S. Lin expanded this idea to 3-Opt, which later led to the world-famous Lin-Kernighan (LK / LKH) heuristic in 1973 (developed by Shen Lin and Brian Kernighan). Today, LKH is widely considered the most effective heuristic for solving symmetric TSP instances up to hundreds of thousands of cities within 1% of the proven optimal tour.

Nearest Neighbor Constructive Heuristic

The Nearest Neighbor (NN) algorithm is a simple greedy constructive heuristic:

Start at an arbitrary initial city $v_0$. Mark it visited.
While unvisited cities remain: find the unvisited city $u$ closest to the current city, add edge $(\text{current}, u)$ to the tour, mark $u$ visited, and set $\text{current} = u$.
Return to the starting city $v_0$ to complete the tour.

Although NN runs in $O(N^2)$ time, it suffers from "greedy myopia": early choices are cheap, but the final remaining unvisited cities may force extremely long, crossing "disaster edges" back to the start.

2-Opt Local Search

2-Opt is a local search improvement heuristic designed to eliminate edge crossings. It repeatedly takes two non-adjacent edges $(A, B)$ and $(C, D)$ in a tour and replaces them with $(A, C)$ and $(B, D)$ if that replacement reduces total tour length:

2-Opt Swap Rule

Given a tour represented as an ordered array of cities, replacing edges between indices $i$ and $i+1$ and $j$ and $j+1$ ($i < j$) is equivalent to reversing the sub-segment of the tour array from index $i+1$ to $j$!

The change in distance ($\Delta \text{length}$) is calculated in $O(1)$ time:

$$\Delta = d(A, C) + d(B, D) - \left( d(A, B) + d(C, D) \right)$$

If $\Delta < 0$, the swap is performed. The algorithm repeats until no 2-edge swap improves the tour (a 2-optimal state).

3-Opt Local Search

3-Opt removes three edges $(A,B)$, $(C,D)$, and $(E,F)$ from the tour, breaking it into 3 paths. Re-connecting these 3 paths without creating subtours offers 8 possible configurations (including the original). By checking all 7 valid non-original reconnections, 3-Opt escapes local minima that 2-Opt gets stuck in.

Worked Example

Consider a tour on 4 2D points $(0,0), (0,1), (1,0), (1,1)$ where the current tour crosses itself: $A(0,0) \to D(1,1) \to B(0,1) \to C(1,0) \to A(0,0)$ with total length $1.414 + 1.0 + 1.414 + 1.0 = 4.828$.

Select edges $(A, D)$ and $(B, C)$.
Try swapping them with $(A, B)$ and $(D, C)$.
New tour: $A(0,0) \to B(0,1) \to D(1,1) \to C(1,0) \to A(0,0)$.
New length: $1.0 + 1.0 + 1.0 + 1.0 = 4.0$. Delta $\Delta = -0.828 < 0$. The crossing is untangled!

Complexity & Performance

Algorithm	Type	Time Complexity per Pass	Tour Quality vs. Optimal
Nearest Neighbor	Constructive Greedy	$O(N^2)$	15% – 25% above OPT
2-Opt Local Search	Iterative Local Search	$O(N^2)$ per pass	3% – 7% above OPT
3-Opt Local Search	Iterative Local Search	$O(N^3)$ per pass	1% – 3% above OPT
Lin-Kernighan (LKH)	Variable $k$-Opt	$O(N^{2.2})$ empirical	< 0.1% above OPT

Implementation

import math

def euclidean_dist(p1, p2):
    return math.hypot(p1[0] - p2[0], p1[1] - p2[1])

def nearest_neighbor_tsp(points):
    n = len(points)
    unvisited = set(range(1, n))
    tour = [0]
    current = 0

    while unvisited:
        next_city = min(unvisited, key=lambda city: euclidean_dist(points[current], points[city]))
        unvisited.remove(next_city)
        tour.append(next_city)
        current = next_city

    return tour

def tour_length(tour, points):
    n = len(tour)
    return sum(euclidean_dist(points[tour[i]], points[tour[(i + 1) % n]]) for i in range(n))

def two_opt(tour, points):
    n = len(tour)
    improved = True

    while improved:
        improved = False
        for i in range(1, n - 1):
            for j in range(i + 1, n):
                if j - i == 1:
                    continue  # adjacent edges share a vertex
                
                A, B = points[tour[i - 1]], points[tour[i]]
                C, D = points[tour[j]], points[tour[(j + 1) % n]]

                d_old = euclidean_dist(A, B) + euclidean_dist(C, D)
                d_new = euclidean_dist(A, C) + euclidean_dist(B, D)

                if d_new < d_old:
                    # Reverse segment [i..j]
                    tour[i:j+1] = reversed(tour[i:j+1])
                    improved = True
                    break
            if improved:
                break

    return tour

# Example
coords = [(0,0), (0,4), (3,0), (3,4), (1,1)]
init_tour = nearest_neighbor_tsp(coords)
print("Nearest Neighbor Tour:", init_tour, "Length:", tour_length(init_tour, coords))

opt_tour = two_opt(init_tour, coords)
print("2-Opt Optimized Tour:", opt_tour, "Length:", tour_length(opt_tour, coords))

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

struct Point { double x, y; };

double dist(Point p1, Point p2) {
    return hypot(p1.x - p2.x, p1.y - p2.y);
}

double getTourLength(const vector<int>& tour, const vector<Point>& pts) {
    double len = 0;
    int n = tour.size();
    for (int i = 0; i < n; ++i) {
        len += dist(pts[tour[i]], pts[tour[(i + 1) % n]]);
    }
    return len;
}

vector<int> nearestNeighbor(const vector<Point>& pts) {
    int n = pts.size();
    vector<bool> visited(n, false);
    vector<int> tour = {0};
    visited[0] = true;

    for (int step = 1; step < n; ++step) {
        int curr = tour.back();
        int best_next = -1;
        double min_d = 1e18;
        for (int i = 0; i < n; ++i) {
            if (!visited[i] && dist(pts[curr], pts[i]) < min_d) {
                min_d = dist(pts[curr], pts[i]);
                best_next = i;
            }
        }
        visited[best_next] = true;
        tour.push_back(best_next);
    }
    return tour;
}

void twoOpt(vector<int>& tour, const vector<Point>& pts) {
    int n = tour.size();
    bool improved = true;

    while (improved) {
        improved = false;
        for (int i = 1; i < n - 1; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (j - i == 1) continue;

                Point A = pts[tour[i - 1]], B = pts[tour[i]];
                Point C = pts[tour[j]],     D = pts[tour[(j + 1) % n]];

                double d_old = dist(A, B) + dist(C, D);
                double d_new = dist(A, C) + dist(B, D);

                if (d_new < d_old) {
                    reverse(tour.begin() + i, tour.begin() + j + 1);
                    improved = true;
                    break;
                }
            }
            if (improved) break;
        }
    }
}

int main() {
    vector<Point> pts = {{0,0}, {0,4}, {3,0}, {3,4}, {1,1}};
    vector<int> tour = nearestNeighbor(pts);
    cout << "NN Length: " << getTourLength(tour, pts) << endl;

    twoOpt(tour, pts);
    cout << "2-Opt Length: " << getTourLength(tour, pts) << endl;
    return 0;
}

import java.util.*;

public class TSPHeuristics {
    static class Point {
        double x, y;
        Point(double x, double y) { this.x = x; this.y = y; }
    }

    static double dist(Point p1, Point p2) {
        return Math.hypot(p1.x - p2.x, p1.y - p2.y);
    }

    static double getTourLength(int[] tour, Point[] pts) {
        double len = 0;
        int n = tour.length;
        for (int i = 0; i < n; i++) {
            len += dist(pts[tour[i]], pts[tour[(i + 1) % n]]);
        }
        return len;
    }

    static int[] nearestNeighbor(Point[] pts) {
        int n = pts.length;
        boolean[] visited = new boolean[n];
        int[] tour = new int[n];
        tour[0] = 0; visited[0] = true;

        for (int step = 1; step < n; step++) {
            int curr = tour[step - 1];
            int bestNext = -1;
            double minD = Double.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                if (!visited[i] && dist(pts[curr], pts[i]) < minD) {
                    minD = dist(pts[curr], pts[i]);
                    bestNext = i;
                }
            }
            visited[bestNext] = true;
            tour[step] = bestNext;
        }
        return tour;
    }

    static void twoOpt(int[] tour, Point[] pts) {
        int n = tour.length;
        boolean improved = true;

        while (improved) {
            improved = false;
            for (int i = 1; i < n - 1; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (j - i == 1) continue;

                    Point A = pts[tour[i - 1]], B = pts[tour[i]];
                    Point C = pts[tour[j]],     D = pts[tour[(j + 1) % n]];

                    double dOld = dist(A, B) + dist(C, D);
                    double dNew = dist(A, C) + dist(B, D);

                    if (dNew < dOld) {
                        reverse(tour, i, j);
                        improved = true;
                        break;
                    }
                }
                if (improved) break;
            }
        }
    }

    private static void reverse(int[] arr, int i, int j) {
        while (i < j) {
            int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
            i++; j--;
        }
    }

    public static void main(String[] args) {
        Point[] pts = {
            new Point(0,0), new Point(0,4), new Point(3,0), new Point(3,4), new Point(1,1)
        };
        int[] tour = nearestNeighbor(pts);
        System.out.println("NN Length: " + getTourLength(tour, pts));

        twoOpt(tour, pts);
        System.out.println("2-Opt Length: " + getTourLength(tour, pts));
    }
}

Real-World Applications

Case Study

Logistics Fleet Dispatch & PCB Drilling

Delivery services (UPS, FedEx) and rideshare routing servers run 2-Opt and 3-Opt local search on top of initial greedy tours to optimize driver routes in real time. In industrial manufacturing, printed circuit board (PCB) drill heads use 2-Opt / Lin-Kernighan heuristics to minimize drill motion between millions of hole coordinates per day.

Fleet RoutingIndustrial Robotics

Exercises

Construct a 4-point counterexample where Nearest Neighbor generates a tour that is strictly worse than the optimal tour.
Show that 2-Opt swap always removes at least one edge crossing when executed on a 2D Euclidean TSP instance.
Write out the 8 possible path reconnection choices for 3-Opt, and identify which ones correspond to simple 2-Opt swaps.
Challenge: Implement Simulated Annealing on top of 2-Opt swaps to allow probabilistic acceptance of bad moves ($\Delta > 0$) and escape local minima.

Limitations

Local Minima & Worst-Case Guarantees

2-Opt and 3-Opt are local search heuristics: they guarantee convergence to a locally optimal tour with respect to 2-swaps or 3-swaps, but do not offer worst-case approximation ratios on non-metric graphs. For guaranteed 3/2-approximation on metric TSP, use Christofides Algorithm.

Cookie Consent

TSP Heuristics (Nearest Neighbor, 2-Opt & 3-Opt)

Contents

A Bit of History

Nearest Neighbor Constructive Heuristic

2-Opt Local Search

2-Opt Swap Rule

3-Opt Local Search

Worked Example

Complexity & Performance

Implementation

Real-World Applications

Logistics Fleet Dispatch & PCB Drilling

Exercises

Limitations

Local Minima & Worst-Case Guarantees

Algorithm	Type	Time Complexity per Pass	Tour Quality vs. Optimal
Nearest Neighbor	Constructive Greedy	\(O(N^2)\)	15% – 25% above OPT
2-Opt Local Search	Iterative Local Search	\(O(N^2)\) per pass	3% – 7% above OPT
3-Opt Local Search	Iterative Local Search	\(O(N^3)\) per pass	1% – 3% above OPT
Lin-Kernighan (LKH)	Variable $k$-Opt	\(O(N^{2.2})\) empirical	< 0.1% above OPT

Cookie Consent

TSP Heuristics (Nearest Neighbor, 2-Opt & 3-Opt)

Contents

A Bit of History

Nearest Neighbor Constructive Heuristic

2-Opt Local Search

2-Opt Swap Rule

3-Opt Local Search

Worked Example

Complexity & Performance

Implementation

Real-World Applications

Logistics Fleet Dispatch & PCB Drilling

Exercises

Limitations

Local Minima & Worst-Case Guarantees

Related Deep Dives

Graph Theory Series

Part 14: The Traveling Salesman Problem

Christofides Algorithm