What does Buyer Shopping Routes and Time Windows conclude, in numbers, about “The Price of Nearest First: How Much Longer than the Shortest Loop”?

Answer: Chapter 1 checks and corrects the project blueprint: the literature's "about a quarter above" for nearest neighbour is an excess over the Held-Karp lower bound on large instances; at ten stops nearest neighbour is only 0.092 longer than the exact optimum on average, and only at sixty stops does it reach 0.2501 above the bound.

Scope of the numbers: Chapter 7 examines Shen Kuo's account of Ding Wei's "one move, three jobs" (an illustrative account saves 0.826) and Euler's seven bridges. Marked boxes separate published evidence, runnable Python calculations (19 programs), classical sources and the author's hypotheses.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 0.092

counters days NN/opt-1: mean med p90 | 2opt/opt-1 mean at opt
8400 0.079 0.069 0.171 | 0.007 0.740
10300 0.092 0.080 0.190 | 0.014 0.573
12150 0.107 0.100 0.217 | 0.010 0.600
95% CI of mean NN excess at 10 counters0.084 to 0.100
counters days NN/2opt-1: mean med p90 (no exact optimum)
4060 0.136 0.129 0.241
8030 0.148 0.151 0.214
16010 0.177 0.180 0.240
Show the full program
# Chapter 1. p12: how much longer is nearest neighbour, by day size?
# Model: counters drawn uniformly in an 8 km by 6 km district (fixed
# seed, illustrative), hotel at the centre. For 8, 10 and 12 counters
# every day is solved exactly by Held-Karp; for 40 and 80 counters the
# exact optimum is out of reach in pure Python, so nearest neighbour is
# compared with its own 2-opt local optimum instead.
# Johnson and McGeoch (1997) report nearest-neighbour tours about a
# quarter above the Held-Karp lower bound on large random instances.
import math
import random
import statistics

RNG = random.Random(20261113)


def dmat(p):
    return [[math.hypot(a[0] - b[0], a[1] - b[1]) for b in p] for a in p]


def tour_len(t, d):
    return math.fsum(d[t[i - 1]][t[i]] for i in range(len(t)))


def nearest_neighbour(d, start=0):
    t, left = [start], [k for k in range(len(d)) if k != start]
    while left:
        c = t[-1]
        j = min(left, key=lambda k: (d[c][k], k))
        t.append(j)
        left.remove(j)
    return t


def two_opt(t, d):
    t, n = t[:], len(t)
    improved = True
    while improved:
        improved = False
        for i in range(n - 1):
            for k in range(i + 2, n if i else n - 1):
                a, b, c, e = t[i], t[i + 1], t[k], t[(k + 1) % n]
                if d[a][c] + d[b][e] - d[a][b] - d[c][e] < -1e-12:
                    t[i + 1:k + 1] = reversed(t[i + 1:k + 1])
                    improved = True
    return t


def held_karp_len(d):
    n = len(d) - 1
    full, inf = (1 << n) - 1, float("inf")
    dp = [[inf] * n for _ in range(full + 1)]
    for j in range(n):
        dp[1 << j][j] = d[0][j + 1]
    for m in range(1, full + 1):
        row = dp[m]
        for j in range(n):
            v = row[j]
            if v == inf or not (m >> j) & 1:
                continue
            dj = d[j + 1]
            for k in range(n):
                if not (m >> k) & 1 and v + dj[k + 1] < dp[m | 1 << k][k]:
                    dp[m | 1 << k][k] = v + dj[k + 1]
    return min(dp[full][j] + d[j + 1][0] for j in range(n))


def day(n):
    return [(4.0, 3.0)] + [(RNG.uniform(0, 8), RNG.uniform(0, 6))
                           for _ in range(n)]


def q(xs, p):
    xs = sorted(xs)
    return xs[min(len(xs) - 1, int(p * len(xs)))]


print("counters days  NN/opt-1: mean   med    p90 | 2opt/opt-1 mean"
      "  at opt")
for n, reps in ((8, 400), (10, 300), (12, 150)):
    e_nn, e_2 = [], []
    for _ in range(reps):
        d = dmat(day(n))
        nn = nearest_neighbour(d)
        best = held_karp_len(d)
        e_nn.append(tour_len(nn, d) / best - 1)
        e_2.append(tour_len(two_opt(nn, d), d) / best - 1)
    hit = len([e for e in e_2 if e < 1e-9]) / reps
    m = statistics.fmean(e_nn)
    half = 1.96 * statistics.stdev(e_nn) / math.sqrt(reps)
    print("%8d %5d %14.3f %6.3f %6.3f | %15.3f %7.3f" % (
        n, reps, m, statistics.median(e_nn), q(e_nn, 0.9),
        statistics.fmean(e_2), hit))
    if n == 10:
        ci = (m - half, m + half)
print("95%% CI of mean NN excess at 10 counters: %.3f to %.3f" % ci)
print("counters days  NN/2opt-1: mean   med    p90   (no exact optimum)")
for n, reps in ((40, 60), (80, 30), (160, 10)):
    r = []
    for _ in range(reps):
        d = dmat(day(n))
        nn = nearest_neighbour(d)
        r.append(tour_len(nn, d) / tour_len(two_opt(nn, d), d) - 1)
    print("%8d %5d %15.3f %6.3f %6.3f" % (
        n, reps, statistics.fmean(r), statistics.median(r), q(r, 0.9)))

Single source and citation

Fan, Y. (2026). Two-Opt Travelling-Salesman Search and Vehicle Routing with Time Windows: Shortest Shopping Loops in Tokyo, Osaka and Seoul under Counter Opening Hours (Version 1.0.0), Chapter 1: The Price of Nearest First: How Much Longer than the Shortest Loop. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 5DL-B-298 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026298,
  author    = {Fan, Yafu},
  title     = {Two-Opt Travelling-Salesman Search and Vehicle Routing with Time Windows: Shortest Shopping Loops in Tokyo, Osaka and Seoul under Counter Opening Hours},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book