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 | |
| 8 | 400 0.079 0.069 0.171 | 0.007 0.740 |
| 10 | 300 0.092 0.080 0.190 | 0.014 0.573 |
| 12 | 150 0.107 0.100 0.217 | 0.010 0.600 |
| 95% CI of mean NN excess at 10 counters | 0.084 to 0.100 |
| counters days NN/2opt-1: mean med p90 (no exact optimum) | |
| 40 | 60 0.136 0.129 0.241 |
| 80 | 30 0.148 0.151 0.214 |
| 160 | 10 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
- Chapter 2 · Croes's Pairwise Exchange: Reversing a Stretch, Crossings and Local Optima
- Chapter 3 · Segment Moves and One-Way Streets: the Or-opt Neighbourhood and Asymmetric Travel
- Chapter 4 · Held-Karp Dynamic Programming: Exact Solutions, State Counts and "Above the Bound"
- Chapter 5 · The Counters' Clocks: Time-Window Feasibility and the Day with the Most Items
- Chapter 6 · Two Buyers and Random Queues: Vehicle Routing with Time Windows and Planning Slack
- Chapter 7 · Classical Sources East and West: Ding Wei's "One Move, Three Jobs" and Euler's Seven Bridges
- Chapter 8 · Closing the Loop: the Shopping Route Planner and a Pre-Registered Test Plan