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
| 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 |
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
- Chapter 1 · The Price of Nearest First: How Much Longer than the Shortest Loop
- Chapter 2 · Croes's Pairwise Exchange: Reversing a Stretch, Crossings and Local Optima
- Chapter 3 · Segment Moves and One-Way Streets: the Or-opt Neighbourhood and Asymmetric Travel
- Chapter 4 · Held-Karp Dynamic Programming: Exact Solutions, State Counts and "Above the Bound"
- Chapter 5 · The Counters' Clocks: Time-Window Feasibility and the Day with the Most Items
- Chapter 7 · Classical Sources East and West: Ding Wei's "One Move, Three Jobs" and Euler's Seven Bridges
- Chapter 8 · Closing the Loop: the Shopping Route Planner and a Pre-Registered Test Plan