What does Buyer Shopping Routes and Time Windows conclude, in numbers, about “Two Buyers and Random Queues: Vehicle Routing with Time Windows and Planning Slack”?

Answer: Chapter 6 deals with two buyers sharing the work and with slack for random queues: planning on average times completes the list on 0.740 of days, and a fifth of slack raises that to 0.915.

Scope of the numbers: Chapter 7 examines Shen Kuo's account of Ding Wei's "one move, three jobs" (an illustrative account saves 0.826) and Euler's seven bridges. Marked boxes separate published evidence, runnable Python calculations (19 programs), classical sources and the author's hypotheses.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 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
Show the full program
# 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]))

Single source and citation

Fan, Y. (2026). Two-Opt Travelling-Salesman Search and Vehicle Routing with Time Windows: Shortest Shopping Loops in Tokyo, Osaka and Seoul under Counter Opening Hours (Version 1.0.0), Chapter 6: Two Buyers and Random Queues: Vehicle Routing with Time Windows and Planning Slack. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 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}
}

Other chapter answers in this book