关于「两位买手与随机排队:带时间窗的车辆路径与计划余量」,《买手扫货路线与时间窗》给出的定量结论是什么?
结论:第六章处理两位买手分工与随机排队的余量:按平均时长排,0.740 的日子全部买到,留两成余量升到 0.915。
数据口径:书中的坐标、专柜、营业时段、排队时长与限购件数均为示意,不对应任何真实店铺;全部计算由书中程序生成;本书是非个人化经营建议,跨境所购物品须按各地海关规定如实申报并遵守限购规定,书中不讨论任何规避做法。 第五章是全书的转折:示意东京日上,20.99 公里的最短闭环只买到 12 件,件数最多的方案多走 0.32 公里就买齐 15 件;随机日上,把最近邻换成最短闭环每天只多买 0.03 件,按时间窗排序多买 2.93 件。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.740, 0.915
| k | plan | route | mean got | P(all) | P(lose 2+) |
| 1.0 | 14 | ABHGFEDCI | 13.63 | 0.740 | 0.086 |
| 1.1 | 14 | ABHGFIEDC | 13.63 | 0.763 | 0.111 |
| 1.2 | 13 | ABCDEFIH | 12.82 | 0.915 | 0.085 |
| 1.3 | 12 | ABDEFIH | 11.92 | 0.963 | 0.037 |
| 1.5 | 11 | CBAHFEI | 10.99 | 0.996 | 0.003 |
| k = 1.2 against 1.0: 0.81 fewer items on average, P(all) +0.175 |
查看完整验算程序
# Chapter 6. p62: queues are random; how much slack should a plan keep?
# Model: the Seoul district of p41 (nine counters, illustrative km) with
# illustrative windows, services and caps. A plan is the exact best day
# computed with every service time multiplied by a planning factor k.
# The day is then lived 4000 times with service = planned mean times a
# lognormal factor (mean 1, sigma 0.4, fixed seed); a counter that can
# no longer start is skipped. Nothing here is any store's real hours.
import math
import random
import statistics
NAMES = ["S"] + list("ABCDEFGHI")
PTS = [(0.0, 0.0), (-2.8, 1.9), (-1.2, 3.1), (0.9, 2.4), (2.6, 3.3),
(3.4, 0.8), (2.1, -1.6), (-0.3, -2.7), (-2.5, -1.4), (0.8, 0.3)]
# 首尔示意时间窗(开始服务最早、最晚分钟)、平均服务分钟、限购件数
WIN = [None, (600, 1140, 50, 2), (630, 720, 60, 2), (600, 1170, 35, 1),
(660, 1110, 70, 2), (600, 1170, 30, 1), (690, 1080, 55, 2),
(600, 960, 40, 1), (660, 1140, 45, 2), (630, 1170, 30, 1)]
DAY_START, DAY_END, N = 570, 1260, 9
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(N + 1)]
for i in range(N + 1)]
SIGMA = 0.4
RNG = random.Random(20261121)
def plan(k):
inf = float("inf")
f = [[inf] * (N + 1) for _ in range(1 << (N + 1))]
par = [[0] * (N + 1) for _ in range(1 << (N + 1))]
for j in range(1, N + 1):
e, last, s, q = WIN[j]
st = max(DAY_START + TT[0][j], e)
if st <= last:
f[1 << j][j] = st + k * s
best = (0, 0.0, 0, 0)
for m in range(2, 1 << (N + 1), 2):
for j in range(1, N + 1):
t = f[m][j]
if t == inf:
continue
if t + TT[j][0] <= DAY_END:
items = 0
for c in range(1, N + 1):
if (m >> c) & 1:
items += WIN[c][3] # step
cand = (items, -(t + TT[j][0]), m, j)
if cand > best:
best = cand
for c in range(1, N + 1):
if (m >> c) & 1:
continue
e, last, s, q = WIN[c]
st = max(t + TT[j][c], e)
if st <= last and st + k * s < f[m | 1 << c][c]:
f[m | 1 << c][c] = st + k * s
par[m | 1 << c][c] = j
items, _, m, j = best
route = []
while j:
route.append(j)
m, j = m ^ (1 << j), par[m][j]
return items, route[::-1]
def live(route):
t, cur, items = DAY_START, 0, 0
for c in route:
e, last, s, q = WIN[c]
st = max(t + TT[cur][c], e)
real = s * RNG.lognormvariate(-SIGMA * SIGMA / 2, SIGMA)
if st > last or st + real + TT[c][0] > DAY_END:
continue
t, cur = st + real, c
items += q # step
return items
print("k plan route mean got P(all) P(lose 2+)")
rows = {}
for k in (1.0, 1.1, 1.2, 1.3, 1.5):
planned, route = plan(k)
got = [live(route) for _ in range(4000)]
rows[k] = (statistics.fmean(got),
len([g for g in got if g == planned]) / len(got))
print("%.1f %6d %-13s %9.2f %7.3f %10.3f" % (
k, planned, "".join(NAMES[c] for c in route),
statistics.fmean(got),
len([g for g in got if g == planned]) / len(got),
len([g for g in got if g <= planned - 2]) / len(got)))
print("k = 1.2 against 1.0: %.2f fewer items on average, P(all) %+.3f" % (
rows[1.0][0] - rows[1.2][0], rows[1.2][1] - rows[1.0][1]))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《旅行商二元交换与时间窗车辆路径、东京大阪首尔扫货路线最短闭环与专柜开门时间窗母典》第 6 章「两位买手与随机排队:带时间窗的车辆路径与计划余量」(版本 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}
}