What does Buyer Shopping Routes and Time Windows conclude, in numbers, about “Held-Karp Dynamic Programming: Exact Solutions, State Counts and "Above the Bound"”?

Answer: Held-Karp dynamic programming remembers only "where I have been and where I stand", reducing the factorial of brute force to the order of \(n2 2n\). For the nine-stop loop of the illustrative Seoul day, the dynamic programme uses 9216 extensions and brute force 181440 loops, and both arrive at 23.2337 km. At twelve stops it has only 24576 states, at twenty 10485760, and at twenty-five it needs 3355.4 megabytes; for a day of up to fifteen stops the exact solution is at hand. The literature's "about a quarter above" measures the large-scale excess over the Held-Karp bound, and the program reproduces 0.2501 at sixty stops; at twelve stops bound and optimum nearly coincide and nearest neighbour is only 0.1027 above the optimum. With the exact shortest loop in hand, the next question follows: can that shortest loop be walked within the hours when the counters are open?

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: 181440, 23.2337, 9216

counters9 (Seoul, illustrative km)
Held-Karp2304 states, 9216 transitions
brute force181440 loops checked
Held-Karp best23.2337 km SGHABCDEFI
brute force best 23.2337 km SGHABCDEFI
lengths agree: True; work ratio brute/HK19.7
dp[full][j] + return leg, by last counter j:
A 24.64, B 24.07, C 24.65, D 25.08, E 23.92
F 23.41, G 23.23, H 24.35, I 23.23

Key formula

\[f(S, j) = \min_{i \in S \setminus \{j\}} \big( f(S \setminus \{j\}, i) + d_{ij} \big),\]
Show the full program
# Chapter 4. p41: Held-Karp dynamic programming against brute force.
# Model: a Seoul day of nine counters A to I and hotel S, illustrative
# coordinates (km, not real addresses). Held-Karp (1962) and Bellman
# (1962): f(S, j) = min over i in S - {j} of f(S - {j}, i) + d(i, j),
# the shortest path from the hotel through set S ending at j. Brute
# force lists every loop with the first counter index below the last.
import itertools
import math

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)]
D = [[math.hypot(a[0] - b[0], a[1] - b[1]) for b in PTS] for a in PTS]
N = len(PTS) - 1

full, inf = (1 << N) - 1, float("inf")
dp = [[inf] * N for _ in range(full + 1)]
par = [[-1] * N for _ in range(full + 1)]
states = transitions = 0
for j in range(N):
    dp[1 << j][j] = D[0][j + 1]
for m in range(1, full + 1):
    for j in range(N):
        v = dp[m][j]
        if v == inf or not (m >> j) & 1:
            continue
        states += 1
        for k in range(N):
            if (m >> k) & 1:
                continue
            transitions += 1
            if v + D[j + 1][k + 1] < dp[m | 1 << k][k]:
                dp[m | 1 << k][k] = v + D[j + 1][k + 1]
                par[m | 1 << k][k] = j
best, j = min((dp[full][j] + D[j + 1][0], j) for j in range(N))
t, m = [], full
while j != -1:
    t.append(j + 1)
    m, j = m ^ (1 << j), par[m][j]
hk = [0] + t[::-1]

checked, bf_best, bf_tour = 0, inf, None
for perm in itertools.permutations(range(1, N + 1)):
    if perm[0] > perm[-1]:
        continue
    checked += 1
    loop = (0,) + perm
    v = math.fsum(D[loop[i - 1]][loop[i]] for i in range(len(loop)))
    if v < bf_best - 1e-12:
        bf_best, bf_tour = v, loop
print("counters: %d (Seoul, illustrative km)" % N)
print("Held-Karp: %d states, %d transitions" % (states, transitions))
print("brute force: %d loops checked" % checked)
print("Held-Karp best  %.4f km  %s" % (best, "".join(NAMES[i] for i in hk)))
print("brute force best %.4f km  %s" % (bf_best, "".join(
    NAMES[i] for i in bf_tour)))
same = abs(best - bf_best) < 1e-9
print("lengths agree: %s; work ratio brute/HK = %.1f" % (
    same, checked / transitions))
print("dp[full][j] + return leg, by last counter j:")
row = ["%s %.2f" % (NAMES[j + 1], dp[full][j] + D[j + 1][0])
       for j in range(N)]
print("  " + ", ".join(row[:5]))
print("  " + ", ".join(row[5:]))

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 4: Held-Karp Dynamic Programming: Exact Solutions, State Counts and "Above the Bound". 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