关于「两位买手与随机排队:带时间窗的车辆路径与计划余量」,《买手扫货路线与时间窗》给出的定量结论是什么?

结论:第六章处理两位买手分工与随机排队的余量:按平均时长排,0.740 的日子全部买到,留两成余量升到 0.915。

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

English version

对照数据表

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

kplanroutemean gotP(all)P(lose 2+)
1.014ABHGFEDCI13.630.7400.086
1.114ABHGFIEDC13.630.7630.111
1.213ABCDEFIH12.820.9150.085
1.312ABDEFIH11.920.9630.037
1.511CBAHFEI10.990.9960.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}
}

本书其他章节结论