关于「由近及远的代价:最近邻路线比最短闭环长多少」,《买手扫货路线与时间窗》给出的定量结论是什么?

结论:第一章核实并修正立项蓝图:文献里最近邻「约高出四分之一」是大规模实例上相对于 Held-Karp 下界的超出;在十站规模上,最近邻只比精确最优平均长 0.092,到六十站才比下界高 0.2501。

数据口径:书中的坐标、专柜、营业时段、排队时长与限购件数均为示意,不对应任何真实店铺;全部计算由书中程序生成;本书是非个人化经营建议,跨境所购物品须按各地海关规定如实申报并遵守限购规定,书中不讨论任何规避做法。 第五章是全书的转折:示意东京日上,20.99 公里的最短闭环只买到 12 件,件数最多的方案多走 0.32 公里就买齐 15 件;随机日上,把最近邻换成最短闭环每天只多买 0.03 件,按时间窗排序多买 2.93 件。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 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
查看完整验算程序
# 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}
}

本书其他章节结论