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
- 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 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 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