关于「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 件。

English version

对照数据表

下表数字由本章 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

核心公式

\[g = d_{ab} + d_{ce} - d_{ac} - d_{be}.\]
查看完整验算程序
# 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}
}

本书其他章节结论