关于「段移位与单行道:Or-opt 邻域与非对称行程」,《买手扫货路线与时间窗》给出的定量结论是什么?

结论:段移位把一到三家连续的专柜整段挪到别处,补上了二元交换做不到的那一类改进。示意大阪日上,二元交换停在 23.41 公里、超出 0.070,段移位四步走到 21.93 公里,只比精确最优的 21.89 公里长 0.002。300 张十站日上,两者交替使用平均只超出 0.0009,最坏一天 0.042。行程不对称时,对称增益公式会把近一半的交换做错,朴素二元交换在 3859 次交换中有 1893 次让路线更慢;只做正向段移位就能避开这个陷阱。那么,在十站、十二站的规模上,能不能干脆不用这些近似办法,直接求出精确最短闭环?

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

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.002, 0.070, 21.89, 21.93, 23.41

nearest neighbour    26.43 km  SAEBDJHCFIGS
then 2-opt (4)       23.41 km  SIBDGEAJHCFS
  Or-opt: move G between J and H, gain 0.37
  Or-opt: move D between J and G, gain 0.09
  Or-opt: move B between J and D, gain 0.71
  Or-opt: move EI between J and B, gain 0.31
then Or-opt (4)      21.93 km  SAJEIBDGHCFS
then 2-opt again (0) 21.93 km
Held-Karp optimum    21.89 km
excess: 2-opt 0.070, 2-opt + Or-opt 0.002
查看完整验算程序
# Chapter 3. p31: an Osaka day where 2-opt stalls and Or-opt moves on.
# Model: ten counters A to J and hotel S, illustrative coordinates (km,
# not real addresses). 2-opt reverses one segment; Or-opt lifts a run
# of one, two or three consecutive counters and reinserts it elsewhere,
# forwards or backwards. Both stop at a local optimum; Held-Karp gives
# the exact optimum for comparison.
import math

NAMES = ["S"] + list("ABCDEFGHIJ")
# 大阪示意街区(公里,示意,非真实地址)
PTS = [(0.0, 0.0), (0.6, -0.4), (0.6, -1.8), (2.5, 1.9), (1.2, -2.0),
       (0.2, -1.0), (-2.0, 2.7), (4.0, -2.7), (2.9, 0.6), (-0.9, -1.3),
       (1.4, -0.3)]
D = [[math.hypot(a[0] - b[0], a[1] - b[1]) for b in PTS] for a in PTS]


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


def nearest_neighbour():
    t, left = [0], list(range(1, len(PTS)))
    while left:
        j = min(left, key=lambda k: (D[t[-1]][k], k))
        t.append(j)
        left.remove(j)
    return t


def two_opt(t):
    t, n, moves = t[:], len(t), 0
    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][b] + D[c][e] - D[a][c] - D[b][e] > 1e-12:
                    t[i + 1:k + 1] = reversed(t[i + 1:k + 1])
                    moves += 1
                    improved = True
    return t, moves


def or_opt(t, log=None):
    # 段移位:取连续 L 个点(L = 1, 2, 3),插到别的边中间,可正可反
    t, n, moves = t[:], len(t), 0
    improved = True
    while improved:
        improved = False
        for seg in (1, 2, 3):
            for i in range(n):
                s = [t[(i + q) % n] for q in range(seg)]
                p, nx = t[(i - 1) % n], t[(i + seg) % n]
                rest = [x for x in t if x not in s]
                gain0 = D[p][s[0]] + D[s[-1]][nx] - D[p][nx]
                for j in range(len(rest)):
                    a, b = rest[j], rest[(j + 1) % len(rest)]
                    if (a, b) == (p, nx):
                        continue
                    for blk in (s, s[::-1]):
                        add = D[a][blk[0]] + D[blk[-1]][b] - D[a][b]
                        if gain0 - add > 1e-12:
                            if log is not None:
                                log.append((blk, a, b, gain0 - add))
                            t = rest[:j + 1] + blk + rest[j + 1:]
                            moves += 1
                            improved = True
                            break
                    if improved:
                        break
                if improved:
                    break
            if improved:
                break
    return t, moves


def held_karp():
    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):
        for j in range(n):
            v = dp[m][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 label(t):
    k = t.index(0)
    return "".join(NAMES[i] for i in t[k:] + t[:k] + [0])


nn = nearest_neighbour()
t2, m2 = two_opt(nn)
log = []
t3, m3 = or_opt(t2, log)
t4, m4 = two_opt(t3)
opt = held_karp()
print("nearest neighbour   %6.2f km  %s" % (tour_len(nn), label(nn)))
print("then 2-opt (%d)      %6.2f km  %s" % (m2, tour_len(t2), label(t2)))
for blk, a, b, g in log:
    print("  Or-opt: move %s between %s and %s, gain %.2f" % (
        "".join(NAMES[x] for x in blk), NAMES[a], NAMES[b], g))
print("then Or-opt (%d)     %6.2f km  %s" % (m3, tour_len(t3), label(t3)))
print("then 2-opt again (%d) %5.2f km" % (m4, tour_len(t4)))
print("Held-Karp optimum   %6.2f km" % opt)
print("excess: 2-opt %.3f, 2-opt + Or-opt %.3f" % (
    tour_len(t2) / opt - 1, tour_len(t4) / opt - 1))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《旅行商二元交换与时间窗车辆路径、东京大阪首尔扫货路线最短闭环与专柜开门时间窗母典》第 3 章「段移位与单行道:Or-opt 邻域与非对称行程」(版本 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}
}

本书其他章节结论