关于「专柜的时钟:时间窗可行性与件数最多的一天」,《买手扫货路线与时间窗》给出的定量结论是什么?

结论:第五章是全书的转折:示意东京日上,20.99 公里的最短闭环只买到 12 件,件数最多的方案多走 0.32 公里就买齐 15 件;随机日上,把最近邻换成最短闭环每天只多买 0.03 件,按时间窗排序多买 2.93 件。

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

English version

对照数据表

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

labels kept: 7405; of them home by 21:00: 7405
max items 15 (shortest loop of p11 gave 12)
earliest return back 18:5822.48 kmS-B-J-G-F-D-I-C-A-H-E-S
shortest walk back 19:07 21.31 km S-G-J-B-F-D-I-C-A-H-E-S
extra km over the 20.99 km shortest loop: 0.32 (0.015)
G arrive 09:41window 10:00-15:00+1
J arrive 10:41window 10:00-11:30+2
B arrive 11:42window 10:00-18:30+1
F arrive 12:37window 10:30-18:50+1
D arrive 13:25window 11:00-19:10+2
I arrive 14:33window 10:00-19:30+1
C arrive 15:17window 10:00-19:20+2
A arrive 16:11window 11:00-19:00+2
H arrive 17:11window 12:00-19:00+2
E arrive 18:30window 10:00-19:30+1
查看完整验算程序
# Chapter 5. p52: exact best day under time windows (Held-Karp labels).
# Model: data of p51 (illustrative). Labels are kept per (set visited,
# last counter) as Pareto pairs (finish time, km walked): a label is
# dropped only if another is no later and no longer. Waiting is
# allowed, so an earlier finish never hurts later windows. The best
# day maximises items; among those, the program reports the earliest
# return and the shortest walk.
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)]
WIN = [None, (660, 1140, 45, 2), (600, 1110, 30, 1), (600, 1160, 40, 2),
       (660, 1150, 50, 2), (600, 1170, 25, 1), (630, 1130, 35, 1),
       (600, 900, 30, 1), (720, 1140, 60, 2), (600, 1170, 30, 1),
       (600, 690, 40, 2)]
DAY_START, DAY_END = 570, 1260
KM = [[math.hypot(a[0] - b[0], a[1] - b[1]) for b in PTS] for a in PTS]
TT = [[0.0 if i == j else 8 + 4 * KM[i][j] for j in range(len(PTS))]
      for i in range(len(PTS))]
N = len(PTS) - 1


def hm(x):
    x = int(round(x))
    return "%02d:%02d" % (x // 60, x % 60)


def items_of(m):
    n = 0
    for k in range(1, N + 1):
        if (m >> k) & 1:
            n += WIN[k][3]  # step
    return n


def insert(bucket, lab):
    t, km = lab[0], lab[1]
    for o in bucket:
        if o[0] <= t + 1e-9 and o[1] <= km + 1e-9:
            return
    bucket[:] = [o for o in bucket if not (t <= o[0] and km <= o[1])]
    bucket.append(lab)


labels = {}
for j in range(1, N + 1):
    e, last, s, q = WIN[j]
    start = max(DAY_START + TT[0][j], e)
    if start <= last:
        labels.setdefault((1 << j, j), [])
        insert(labels[(1 << j, j)], (start + s, KM[0][j], (j,)))
for m in range(2, 1 << (N + 1), 2):
    for j in range(1, N + 1):
        for t, km, path in list(labels.get((m, j), [])):
            for k in range(1, N + 1):
                if (m >> k) & 1:
                    continue
                e, last, s, q = WIN[k]
                start = max(t + TT[j][k], e)
                if start > last:
                    continue
                key = (m | 1 << k, k)
                labels.setdefault(key, [])
                insert(labels[key], (start + s, km + KM[j][k], path + (k,)))

best = []
for (m, j), bucket in labels.items():
    items = items_of(m)
    for t, km, path in bucket:
        back = t + TT[j][0]
        if back <= DAY_END:
            best.append((items, back, km + KM[j][0], path))
top = max(b[0] for b in best)
early = min((b for b in best if b[0] == top), key=lambda b: (b[1], b[2]))
short = min((b for b in best if b[0] == top), key=lambda b: (b[2], b[1]))
print("labels kept: %d; of them home by 21:00: %d" % (
    len([1 for b in labels.values() for _ in b]), len(best)))
print("max items %d (shortest loop of p11 gave 12)" % top)
for tag, b in (("earliest return", early), ("shortest walk", short)):
    print("%-15s back %s  %.2f km  S-%s-S" % (
        tag, hm(b[1]), b[2], "-".join(NAMES[k] for k in b[3])))
print("extra km over the 20.99 km shortest loop: %.2f (%.3f)" % (
    short[2] - 20.99, short[2] / 20.99 - 1))
t, cur = DAY_START, 0
for k in short[3]:
    e, last, s, q = WIN[k]
    arr = t + TT[cur][k]
    t, cur = max(arr, e) + s, k
    print("  %s arrive %s  window %s-%s  +%d" % (
        NAMES[k], hm(arr), hm(e), hm(last), q))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《旅行商二元交换与时间窗车辆路径、东京大阪首尔扫货路线最短闭环与专柜开门时间窗母典》第 5 章「专柜的时钟:时间窗可行性与件数最多的一天」(版本 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}
}

本书其他章节结论