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:5822.48 kmS-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:41window 10:00-15:00+1
J arrive 10:41window 10:00-11:30+2
B arrive 11:42window 10:00-18:30+1
F arrive 12:37window 10:30-18:50+1
D arrive 13:25window 11:00-19:10+2
I arrive 14:33window 10:00-19:30+1
C arrive 15:17window 10:00-19:20+2
A arrive 16:11window 11:00-19:00+2
H arrive 17:11window 12:00-19:00+2
E arrive 18:30window 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