关于「专柜的时钟:时间窗可行性与件数最多的一天」,《买手扫货路线与时间窗》给出的定量结论是什么?
结论:第五章是全书的转折:示意东京日上,20.99 公里的最短闭环只买到 12 件,件数最多的方案多走 0.32 公里就买齐 15 件;随机日上,把最近邻换成最短闭环每天只多买 0.03 件,按时间窗排序多买 2.93 件。
数据口径:书中的坐标、专柜、营业时段、排队时长与限购件数均为示意,不对应任何真实店铺;全部计算由书中程序生成;本书是非个人化经营建议,跨境所购物品须按各地海关规定如实申报并遵守限购规定,书中不讨论任何规避做法。 第五章是全书的转折:示意东京日上,20.99 公里的最短闭环只买到 12 件,件数最多的方案多走 0.32 公里就买齐 15 件;随机日上,把最近邻换成最短闭环每天只多买 0.03 件,按时间窗排序多买 2.93 件。
对照数据表
下表数字由本章 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:58 | 22.48 km | S-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:41 | window 10:00-15:00 | +1 |
| J arrive 10:41 | window 10:00-11:30 | +2 |
| B arrive 11:42 | window 10:00-18:30 | +1 |
| F arrive 12:37 | window 10:30-18:50 | +1 |
| D arrive 13:25 | window 11:00-19:10 | +2 |
| I arrive 14:33 | window 10:00-19:30 | +1 |
| C arrive 15:17 | window 10:00-19:20 | +2 |
| A arrive 16:11 | window 11:00-19:00 | +2 |
| H arrive 17:11 | window 12:00-19:00 | +2 |
| E arrive 18:30 | window 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}
}