What does Buyer Shopping Routes and Time Windows conclude, in numbers, about “The Counters' Clocks: Time-Window Feasibility and the Day with the Most Items”?
Answer: Chapter 5 is the turning point: on an illustrative Tokyo day the shortest loop of 20.99 km collects only 12 items, while the plan with the most items walks 0.32 km more and collects all 15; over random days, switching from nearest neighbour to the shortest loop gains only 0.03 items a day, while sequencing by time windows gains 2.93.
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.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 |
Show the full program
# 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))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 5: The Counters' Clocks: Time-Window Feasibility and the Day with the Most Items. 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 6 · Two Buyers and Random Queues: Vehicle Routing with Time Windows and Planning Slack
- 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