关于「段移位与单行道: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 件。
对照数据表
下表数字由本章 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}
}