关于「由近及远的代价:最近邻路线比最短闭环长多少」,《买手扫货路线与时间窗》给出的定量结论是什么?
结论:第一章核实并修正立项蓝图:文献里最近邻「约高出四分之一」是大规模实例上相对于 Held-Karp 下界的超出;在十站规模上,最近邻只比精确最优平均长 0.092,到六十站才比下界高 0.2501。
数据口径:书中的坐标、专柜、营业时段、排队时长与限购件数均为示意,不对应任何真实店铺;全部计算由书中程序生成;本书是非个人化经营建议,跨境所购物品须按各地海关规定如实申报并遵守限购规定,书中不讨论任何规避做法。 第五章是全书的转折:示意东京日上,20.99 公里的最短闭环只买到 12 件,件数最多的方案多走 0.32 公里就买齐 15 件;随机日上,把最近邻换成最短闭环每天只多买 0.03 件,按时间窗排序多买 2.93 件。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 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 |
查看完整验算程序
# 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)))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《旅行商二元交换与时间窗车辆路径、东京大阪首尔扫货路线最短闭环与专柜开门时间窗母典》第 1 章「由近及远的代价:最近邻路线比最短闭环长多少」(版本 1.0.0). 5D Library. DOI 待发布
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 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}
}