Construction heuristics

Read first

• Post 1: What is the TSP? A tour visits every stop once and returns to the start; its cost is the sum of its legs, including the last leg home. Our running example has eight stops, A to H, with distances in units of 100 m, rounded. The optimal tour is A-B-C-D-H-E-F-G-A at 315.
• Post 2: Why is the TSP hard? Checking every tour grows like (n − 1)!/2, so exact search stops scaling quickly. Post 2 also introduced nearest neighbour and the gap: how far a tour’s cost is above the optimum, as a percentage.

The question this post answers: when you need a decent tour right now, how do you build one, and how good is it?

Intuition

Exact methods (Posts 4 to 8) prove optimality but get slow. In production I almost never start there. Every planning request first needs some complete tour, quickly, so the rest of the system has something to work with.

A construction heuristic builds one tour from nothing, adding one stop at a time, and never goes back to change an earlier decision. That last part is what makes it fast, and also what makes it imperfect.

Here are the eight stops again. The distance matrix from Post 1 appears further down as a heatmap: light cells are short legs, dark cells are long ones.

Nearest neighbour: always go to the closest stop

Start at A. Repeatedly drive to the closest stop you haven’t visited yet. When none are left, drive home. If two stops are equally close, take the one that comes first alphabetically.

Step through the diagram to watch the tour grow. The filled stop is the one just added. As in earlier posts, the diagram measures lengths in unrounded kilometres, so its running length can differ by a few tenths from the matrix values in the captions.

Here is the bill, leg by leg. The outlined cells are the legs the tour used.

The total is 385, 22% above the optimum of 315. The pattern is typical. The first legs are short because there are plenty of stops nearby to choose from. The greedy choices then leave F stranded, and the last two legs, B→F at 86 and F→A at 61, pay for it.

Insertion: grow a loop instead of a path

Insertion heuristics keep a closed loop at every step instead of an open path. They start with the loop A→A and repeatedly insert one more stop into it. Inserting stop k between neighbours i and j replaces the leg i→j with two legs, i→k and k→j, so it costs

insertion cost = d(i, k) + d(k, j) − d(i, j)

Each step makes two choices: which stop to insert next, and where. The where is always the same: the position with the smallest insertion cost. The which gives three classic rules:

When two choices cost the same, I take the alphabetically first stop and the earliest position in the loop. On these eight stops the tie-breaking order doesn’t change any result.

Step through cheapest insertion below. In each step the dashed red edge is the leg that gets replaced and the green edges are the two legs that replace it.

The table follows each step: which stop went in, where, and what it cost.

Nearest insertion makes exactly the same first four moves. At step 5 it parts ways: H is the stop closest to the loop (28 from D), so nearest insertion puts H in next, between C and D, for 48. Cheapest insertion saw that H would be cheaper to add later, once E was in place. That single choice costs nearest insertion 6 units: it finishes at A-B-C-H-D-E-F-G-A, cost 321.

Farthest insertion sounds backwards, but it also finds 315 here. It starts with H, the stop farthest from A, then C, then F: three stops that sketch the outline of the map. Every later stop fills in a gap in that outline, so no stop ends up stranded the way F did for nearest neighbour.

A space-filling curve: no distances at all

The last method is the strangest. Lay a fine grid over the map and draw one continuous curve that passes through every grid cell, such as the Hilbert curve. Visit the stops in the order the curve reaches them. That is the whole method: it sorts the stops, and it never computes a single distance.

Bartholdi and Platzman (1982) proposed this for exactly the case where distances are expensive to compute or not available at all. With a 16 × 16 Hilbert curve over our eight stops, the visiting order is A, G, F, E, H, D, B, C.

The table puts all five methods side by side on the eight stops.

Two insertion rules hit the optimum on eight stops. That says more about how small eight stops is than about the rules. On berlin52, below, every method lands well above the optimum from a typical start.

The formal idea

Write V for the set of n cities and d(i, j) for the cost from i to j. A construction heuristic keeps a partial tour T, a sequence of distinct cities, and a set U = V ∖ T of cities still to place. Each step moves one city from U into T. After n − 1 steps U is empty and T is a tour.

Nearest neighbour keeps T as an open path ending at city t, and appends the city k ∈ U with the smallest d(t, k).

Insertion keeps T as a closed loop. For a city k ∈ U and consecutive cities i, j in T, the insertion cost is

Δ(i, k, j) = d(i, k) + d(k, j) − d(i, j)

With the triangle inequality, d(i, j) ≤ d(i, k) + d(k, j), so Δ is never negative: every insertion makes the loop at least as long. Let δ(k) = min over i ∈ T of d(i, k), the distance from k to the loop. The three rules choose k as follows, then insert k at the position with the smallest Δ:

• nearest insertion: the k with the smallest δ(k)
• farthest insertion: the k with the largest δ(k)
• cheapest insertion: the pair (k, position) with the smallest Δ, over all k ∈ U

The diagram below is the loop all three rules share. Only the box that picks the next city changes.

flowchart TD
  S["Loop = start city"] --> Q{"Cities left to place?"}
  Q -- no --> R["Return the loop"]
  Q -- yes --> P["Pick next city k (the rule)"]
  P --> W["Find the cheapest position for k"]
  W --> I["Insert k, update distances to the loop"]
  I --> Q

Space-filling curve maps each city’s coordinates to a cell of a 2ᵐ × 2ᵐ grid, computes that cell’s position h along the Hilbert curve, and sorts cities by h.

The table below summarises running time and the best proven worst-case guarantee for each method, assuming the triangle inequality holds. Rosenkrantz, Stearns and Lewis (1977) proved the bounds for nearest neighbour and the insertion rules, and Platzman and Bartholdi (1989) proved the one for the space-filling curve.

Three of these numbers grow with n. For nearest neighbour that is not just a weak proof: Rosenkrantz, Stearns and Lewis also built instances where its tour is longer than optimal by a factor that grows like log n, about a third of log₂ n. For the space-filling curve, Bertsimas and Grigni (1989) built instances that reach its log n bound. Farthest insertion is the open case: nobody has proved a constant bound for it, and the worst instances known only push it to about 6.5 times optimal. A constant like 2 says something about every instance; a log n says the method can drift arbitrarily far on big ones.

Common misconceptions

“Nearest neighbour is the natural greedy choice, so it’s the best simple method.” It is the most intuitive, not the best. On berlin52 from city 1, farthest insertion builds a tour 10.1% above optimal against nearest neighbour’s 19.1%, in comparable time. Greedy-by-distance spends its good choices early and pays at the end, as F showed on our eight stops.

“Farthest insertion is backwards: you should add nearby stops first.” Adding far stops first sketches the overall shape of the tour early. The later, nearby stops then slot into an outline that already makes sense. On random uniform instances with 100,000 cities, Johnson and McGeoch (2002) measured farthest insertion at about 13% above the Held-Karp lower bound, against about 27% for nearest insertion and roughly 23% for nearest neighbour.

“If a heuristic found the optimum, it is a good heuristic.” Farthest insertion found 7,542 on berlin52, but only from one starting city out of 52 (city 9). From the other starts it ranged up to 8,818, 16.9% above. One lucky run says nothing about the next instance.

“A space-filling curve tour is too poor to be useful.” At 38.7% above optimal on berlin52 it is the weakest method here. But it needs only coordinates, never a distance matrix, and it sorts n stops in O(n log n). Bartholdi and colleagues used a space-filling curve (Sierpiński’s, not Hilbert’s) to route Meals on Wheels deliveries to more than 200 stops in Atlanta. The whole system ran on two Rolodex card files, with no computer, and cost less than $50.

Try it in Python

This script runs all five methods on berlin52. Each method except the space-filling curve depends on its starting city, so it builds one tour from every one of the 52 cities and reports the tour from city 1, the best and the worst. You need berlin52.tsp from TSPLIB.

import math

body = open("berlin52.tsp").read().split("NODE_COORD_SECTION")[1].split("EOF")[0]
xy = [tuple(map(float, ln.split()[1:])) for ln in body.strip().splitlines()]
n = len(xy)
d = [[int(math.hypot(p[0] - q[0], p[1] - q[1]) + 0.5) for q in xy] for p in xy]  # EUC_2D
OPTIMAL = 7542

def cost(tour):
    return sum(d[tour[i]][tour[(i + 1) % len(tour)]] for i in range(len(tour)))

def nearest_neighbour(start):
    tour, left = [start], set(range(n)) - {start}
    while left:
        nxt = min(left, key=lambda c: (d[tour[-1]][c], c))  # ties go to the lower city number
        tour.append(nxt)
        left.remove(nxt)
    return tour

def insert_cost(tour, i, k):  # cost of putting city k between tour[i] and the city after it
    a, b = tour[i], tour[(i + 1) % len(tour)]
    return d[a][k] + d[k][b] - d[a][b] if len(tour) > 1 else 2 * d[a][k]

def insertion(start, rule):
    tour, left = [start], set(range(n)) - {start}
    gap_to_tour = {c: d[start][c] for c in left}  # distance from each city to its nearest tour city
    while left:
        if rule == "cheapest":  # best (city, position) pair overall
            _, i, k = min((insert_cost(tour, i, k), i, k) for k in left for i in range(len(tour)))
        else:                   # pick the city first, then its cheapest position
            pick = min if rule == "nearest" else max
            k = pick(sorted(left), key=lambda c: gap_to_tour[c])
            i = min(range(len(tour)), key=lambda i: insert_cost(tour, i, k))
        tour.insert(i + 1, k)
        left.remove(k)
        for c in left:
            gap_to_tour[c] = min(gap_to_tour[c], d[k][c])
    return tour

def hilbert_index(x, y, side):  # position of grid cell (x, y) along a Hilbert curve
    h, s = 0, side // 2
    while s:
        rx, ry = int((x & s) > 0), int((y & s) > 0)
        h += s * s * ((3 * rx) ^ ry)
        if ry == 0:
            if rx == 1:
                x, y = s - 1 - x, s - 1 - y
            x, y = y, x
        s //= 2
    return h

def space_filling_curve(side=1024):
    lo_x, lo_y = min(p[0] for p in xy), min(p[1] for p in xy)
    span = max(max(p[0] for p in xy) - lo_x, max(p[1] for p in xy) - lo_y)
    cell = lambda v, lo: int((v - lo) / span * (side - 1) + 0.5)
    return sorted(range(n), key=lambda c: hilbert_index(cell(xy[c][0], lo_x), cell(xy[c][1], lo_y), side))

gap = lambda c: f"{100 * (c - OPTIMAL) / OPTIMAL:.1f}%"
builders = {
    "nearest neighbour": nearest_neighbour,
    "nearest insertion": lambda s: insertion(s, "nearest"),
    "cheapest insertion": lambda s: insertion(s, "cheapest"),
    "farthest insertion": lambda s: insertion(s, "farthest"),
}
for name, build in builders.items():
    costs = [cost(build(s)) for s in range(n)]  # one tour per starting city
    first, best, worst = costs[0], min(costs), max(costs)
    print(f"{name:<19} city 1: {first} ({gap(first)})  best: {best} ({gap(best)})  worst: {worst} ({gap(worst)})")
sfc = cost(space_filling_curve())
print(f"{'space-filling curve':<19} one ordering: {sfc} ({gap(sfc)})")

It prints:

Three things stand out. Farthest insertion is the best method here from every angle: from city 1, at its best and at its worst. Nearest neighbour has both a strong best case and the worst worst case, so its result depends heavily on where you start. And the insertion rules are much more consistent than nearest neighbour: their best and worst starts are closer together.

The whole script runs in well under a second. That is the point of construction heuristics: a complete, reasonable tour almost instantly.

Exercise

Run farthest insertion by hand on the eight stops, starting from A. Use the heatmap above for distances. Which stop goes in first, and why? Then find the step where a stop is inserted for a cost of 0, and explain how that can happen.

Hint: the first stop is the one farthest from A. For the zero-cost step, compare d(H, E) + d(E, F) with d(H, F), and remember that every distance in the matrix is rounded.

What this method can’t do yet

Every method in this post gives you a tour, but none of them tells you how bad that tour might be. On berlin52, nearest neighbour landed anywhere from 8.5% to 36.5% above optimal depending only on the starting city, and nothing in the output says which case you got. The guarantees in the table are worse still: for nearest neighbour, farthest insertion and the space-filling curve they grow with n, so on a big enough instance there is no limit to how far off they can be. That is the gap this method leaves: no promise on how bad a tour can be. Post 10, “Approximation algorithms”, builds tours that come with a fixed guarantee, such as Christofides’ algorithm, which is never more than 50% above optimal.

References

• Rosenkrantz, D. J., Stearns, R. E., and Lewis, P. M. (1977). “An Analysis of Several Heuristics for the Traveling Salesman Problem.” SIAM Journal on Computing 6(3): 563–581.
• Bartholdi, J. J., and Platzman, L. K. (1982). “An O(N log N) Planar Travelling Salesman Heuristic Based on Spacefilling Curves.” Operations Research Letters 1(4): 121–125.
• Platzman, L. K., and Bartholdi, J. J. (1989). “Spacefilling Curves and the Planar Travelling Salesman Problem.” Journal of the ACM 36(4): 719–737.
• Bertsimas, D., and Grigni, M. (1989). “Worst-Case Examples for the Spacefilling Curve Heuristic for the Euclidean Traveling Salesman Problem.” Operations Research Letters 8(5): 241–244.
• Bartholdi, J. J., Platzman, L. K., Collins, R. L., and Warden, W. H. (1983). “A Minimal Technology Routing System for Meals on Wheels.” Interfaces 13(3): 1–8.
• Johnson, D. S., and McGeoch, L. A. (2002). “Experimental Analysis of Heuristics for the STSP.” In G. Gutin and A. P. Punnen (eds.), The Traveling Salesman Problem and Its Variations, Kluwer, 369–443.
• Reinelt, G. (1991). “TSPLIB—A Traveling Salesman Problem Library.” ORSA Journal on Computing 3(4): 376–384; berlin52 files and list of optimal solutions.

See the whole series · ← All writing