What does Buyer Shopping Routes and Time Windows conclude, in numbers, about “Segment Moves and One-Way Streets: the Or-opt Neighbourhood and Asymmetric Travel”?

Answer: Segment moves lift one to three consecutive counters as a block and put them elsewhere, supplying the kind of improvement pairwise exchange cannot make. On the illustrative Osaka day, pairwise exchange stops at 23.41 km, 0.070 above the optimum; four segment moves reach 21.93 km, only 0.002 above the exact optimum of 21.89 km. On 300 days of ten counters, alternating the two moves gives a mean excess of only 0.0009 and a worst day of 0.042. When travel is asymmetric, the symmetric gain formula gets nearly half its exchanges wrong: naive pairwise exchange made 3859 exchanges of which 1893 slowed the route, and forward segment moves avoid that trap. At ten or twelve stops, then, can we skip these approximations altogether and compute the exact shortest loop directly?

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.002, 0.070, 21.89, 21.93, 23.41

nearest neighbour    26.43 km  SAEBDJHCFIGS
then 2-opt (4)       23.41 km  SIBDGEAJHCFS
  Or-opt: move G between J and H, gain 0.37
  Or-opt: move D between J and G, gain 0.09
  Or-opt: move B between J and D, gain 0.71
  Or-opt: move EI between J and B, gain 0.31
then Or-opt (4)      21.93 km  SAJEIBDGHCFS
then 2-opt again (0) 21.93 km
Held-Karp optimum    21.89 km
excess: 2-opt 0.070, 2-opt + Or-opt 0.002
Show the full program
# Chapter 3. p31: an Osaka day where 2-opt stalls and Or-opt moves on.
# Model: ten counters A to J and hotel S, illustrative coordinates (km,
# not real addresses). 2-opt reverses one segment; Or-opt lifts a run
# of one, two or three consecutive counters and reinserts it elsewhere,
# forwards or backwards. Both stop at a local optimum; Held-Karp gives
# the exact optimum for comparison.
import math

NAMES = ["S"] + list("ABCDEFGHIJ")
# 大阪示意街区(公里,示意,非真实地址)
PTS = [(0.0, 0.0), (0.6, -0.4), (0.6, -1.8), (2.5, 1.9), (1.2, -2.0),
       (0.2, -1.0), (-2.0, 2.7), (4.0, -2.7), (2.9, 0.6), (-0.9, -1.3),
       (1.4, -0.3)]
D = [[math.hypot(a[0] - b[0], a[1] - b[1]) for b in PTS] for a in PTS]


def tour_len(t):
    return math.fsum(D[t[i - 1]][t[i]] for i in range(len(t)))


def nearest_neighbour():
    t, left = [0], list(range(1, len(PTS)))
    while left:
        j = min(left, key=lambda k: (D[t[-1]][k], k))
        t.append(j)
        left.remove(j)
    return t


def two_opt(t):
    t, n, moves = t[:], len(t), 0
    improved = True
    while improved:
        improved = False
        for i in range(n - 1):
            for k in range(i + 2, n if i else n - 1):
                a, b, c, e = t[i], t[i + 1], t[k], t[(k + 1) % n]
                if D[a][b] + D[c][e] - D[a][c] - D[b][e] > 1e-12:
                    t[i + 1:k + 1] = reversed(t[i + 1:k + 1])
                    moves += 1
                    improved = True
    return t, moves


def or_opt(t, log=None):
    # 段移位:取连续 L 个点(L = 1, 2, 3),插到别的边中间,可正可反
    t, n, moves = t[:], len(t), 0
    improved = True
    while improved:
        improved = False
        for seg in (1, 2, 3):
            for i in range(n):
                s = [t[(i + q) % n] for q in range(seg)]
                p, nx = t[(i - 1) % n], t[(i + seg) % n]
                rest = [x for x in t if x not in s]
                gain0 = D[p][s[0]] + D[s[-1]][nx] - D[p][nx]
                for j in range(len(rest)):
                    a, b = rest[j], rest[(j + 1) % len(rest)]
                    if (a, b) == (p, nx):
                        continue
                    for blk in (s, s[::-1]):
                        add = D[a][blk[0]] + D[blk[-1]][b] - D[a][b]
                        if gain0 - add > 1e-12:
                            if log is not None:
                                log.append((blk, a, b, gain0 - add))
                            t = rest[:j + 1] + blk + rest[j + 1:]
                            moves += 1
                            improved = True
                            break
                    if improved:
                        break
                if improved:
                    break
            if improved:
                break
    return t, moves


def held_karp():
    n = len(D) - 1
    full, inf = (1 << n) - 1, float("inf")
    dp = [[inf] * n for _ in range(full + 1)]
    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
            dj = D[j + 1]
            for k in range(n):
                if not (m >> k) & 1 and v + dj[k + 1] < dp[m | 1 << k][k]:
                    dp[m | 1 << k][k] = v + dj[k + 1]
    return min(dp[full][j] + D[j + 1][0] for j in range(n))


def label(t):
    k = t.index(0)
    return "".join(NAMES[i] for i in t[k:] + t[:k] + [0])


nn = nearest_neighbour()
t2, m2 = two_opt(nn)
log = []
t3, m3 = or_opt(t2, log)
t4, m4 = two_opt(t3)
opt = held_karp()
print("nearest neighbour   %6.2f km  %s" % (tour_len(nn), label(nn)))
print("then 2-opt (%d)      %6.2f km  %s" % (m2, tour_len(t2), label(t2)))
for blk, a, b, g in log:
    print("  Or-opt: move %s between %s and %s, gain %.2f" % (
        "".join(NAMES[x] for x in blk), NAMES[a], NAMES[b], g))
print("then Or-opt (%d)     %6.2f km  %s" % (m3, tour_len(t3), label(t3)))
print("then 2-opt again (%d) %5.2f km" % (m4, tour_len(t4)))
print("Held-Karp optimum   %6.2f km" % opt)
print("excess: 2-opt %.3f, 2-opt + Or-opt %.3f" % (
    tour_len(t2) / opt - 1, tour_len(t4) / opt - 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 3: Segment Moves and One-Way Streets: the Or-opt Neighbourhood and Asymmetric Travel. 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