关于「Croes 的二元交换:反转一段路、交叉与局部最优」,《买手扫货路线与时间窗》给出的定量结论是什么?
结论:二元交换拆掉两段腿、换上两段、把中间一段倒过来走,只要总长下降就接受。东京示意日上,五步交换把 25.51 公里缩到 20.99 公里,增益依次是 1.52、0.06、0.99、0.10 和 1.85 公里。平面上交叉的路线一定可以改短,但没有交叉的路线可以很差,最近邻就是一个零交叉却长两成的例子。在 200 张随机的十站日上,最近邻起点的二元交换平均只比最优长 0.0093,20 个随机起点取最好者有 0.990 的日子落在最优上。如果从 \(a\) 到 \(b\) 与从 \(b\) 到 \(a\) 不一样长,或者需要把一家专柜整体挪个位置,二元交换还够用吗?
数据口径:书中的坐标、专柜、营业时段、排队时长与限购件数均为示意,不对应任何真实店铺;全部计算由书中程序生成;本书是非个人化经营建议,跨境所购物品须按各地海关规定如实申报并遵守限购规定,书中不讨论任何规避做法。 第五章是全书的转折:示意东京日上,20.99 公里的最短闭环只买到 12 件,件数最多的方案多走 0.32 公里就买齐 15 件;随机日上,把最近邻换成最短闭环每天只多买 0.03 件,按时间窗排序多买 2.93 件。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.06, 0.10, 0.99, 1.52, 1.85, 20.99
start NN 25.51 km crossings 0 SGJFDECIAHBS
move 1 out SG+HB in SH+GB gain 1.52
23.99 km crossings 0 SHAICEDFJGBS
move 2 out AI+CE in AC+IE gain 0.06
23.93 km crossings 0 SHACIEDFJGBS
move 3 out JG+BS in JB+GS gain 0.99
22.94 km crossings 0 SHACIEDFJBGS
move 4 out SH+IE in SI+HE gain 0.10
22.84 km crossings 1 SICAHEDFJBGS
move 5 out SI+ED in SE+ID gain 1.85
20.99 km crossings 0 SEHACIDFJBGS
no improving pair left among 44 candidate pairs核心公式
查看完整验算程序
# Chapter 2. p21: the five 2-opt moves of the Tokyo day, one by one.
# Model: Croes (1958) inversion. Remove edges (a,b) and (c,e), add
# (a,c) and (b,e), reverse the path b..c. Gain = old pair - new pair.
# Same illustrative coordinates as p11 (km, not real addresses).
# The program also counts pairs of crossing legs: in the plane a loop
# with two crossing legs can always be shortened by one 2-opt move.
import math
NAMES = ["S"] + list("ABCDEFGHIJ")
PTS = [(0.0, 0.0), (3.6, 2.7), (-3.5, -2.5), (2.7, 1.4), (1.4, -1.2),
(0.8, 0.6), (0.6, -2.0), (-0.6, -0.6), (1.8, 3.0), (3.6, 0.3),
(-0.4, -1.4)]
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 cross(p, q, r, s):
# 两条线段 pq 与 rs 是否真正相交(不含共享端点)
def orient(a, b, c):
v = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
return (v > 1e-12) - (v < -1e-12)
return (orient(p, q, r) * orient(p, q, s) < 0
and orient(r, s, p) * orient(r, s, q) < 0)
def crossings(t):
n, c = len(t), 0
for i in range(n):
for k in range(i + 2, n):
if i == 0 and k == n - 1:
continue
a, b = PTS[t[i]], PTS[t[i + 1]]
e, f = PTS[t[k]], PTS[t[(k + 1) % n]]
if cross(a, b, e, f):
c += 1
return c
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 label(t):
return "".join(NAMES[i] for i in t + [0])
t = nearest_neighbour()
print("start NN %6.2f km crossings %d %s" % (tour_len(t), crossings(t),
label(t)))
step, n = 0, 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]
gain = D[a][b] + D[c][e] - D[a][c] - D[b][e]
if gain > 1e-12:
t[i + 1:k + 1] = reversed(t[i + 1:k + 1])
step += 1
print("move %d out %s%s+%s%s in %s%s+%s%s gain %.2f" % (
step, NAMES[a], NAMES[b], NAMES[c], NAMES[e],
NAMES[a], NAMES[c], NAMES[b], NAMES[e], gain))
print(" %6.2f km crossings %d %s" % (
tour_len(t), crossings(t), label(t)))
improved = True
print("no improving pair left among %d candidate pairs" % (
n * (n - 3) // 2))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《旅行商二元交换与时间窗车辆路径、东京大阪首尔扫货路线最短闭环与专柜开门时间窗母典》第 2 章「Croes 的二元交换:反转一段路、交叉与局部最优」(版本 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}
}