What does Buyer Shopping Routes and Time Windows conclude, in numbers, about “Croes's Pairwise Exchange: Reversing a Stretch, Crossings and Local Optima”?

Answer: Pairwise exchange removes two legs, adds two, walks the stretch between them in reverse, and accepts the change whenever the total falls. On the illustrative Tokyo day, five exchanges cut 25.51 km down to 20.99 km, with gains of 1.52, 0.06, 0.99, 0.10 and 1.85 km in turn. A route with crossings in the plane can always be shortened, but a route without crossings can still be bad; nearest neighbour is an example with zero crossings and a fifth too long. On 200 random days of ten counters, pairwise exchange from the nearest-neighbour start exceeds the optimum by only 0.0093 on average, and the best of 20 random starts lands on the optimum on a share of 0.990 of days. If the walk from \(a\) to \(b\) is not as long as the walk from \(b\) to \(a\), or a counter has to be moved as a whole, is pairwise exchange still enough?

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.06, 0.10, 0.99, 1.52, 1.85, 20.99

start NN   25.51 km  crossings 0  SGJFDECIAHBS
move 1  out SG+HB in SH+GB gain 1.52
         23.99 km  crossings 0  SHAICEDFJGBS
move 2  out AI+CE in AC+IE gain 0.06
         23.93 km  crossings 0  SHACIEDFJGBS
move 3  out JG+BS in JB+GS gain 0.99
         22.94 km  crossings 0  SHACIEDFJBGS
move 4  out SH+IE in SI+HE gain 0.10
         22.84 km  crossings 1  SICAHEDFJBGS
move 5  out SI+ED in SE+ID gain 1.85
         20.99 km  crossings 0  SEHACIDFJBGS
no improving pair left among 44 candidate pairs

Key formula

\[g = d_{ab} + d_{ce} - d_{ac} - d_{be}.\]
Show the full program
# Chapter 2. p21: the five 2-opt moves of the Tokyo day, one by one.
# Model: Croes (1958) inversion. Remove edges (a,b) and (c,e), add
# (a,c) and (b,e), reverse the path b..c. Gain = old pair - new pair.
# Same illustrative coordinates as p11 (km, not real addresses).
# The program also counts pairs of crossing legs: in the plane a loop
# with two crossing legs can always be shortened by one 2-opt move.
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)]
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 cross(p, q, r, s):
    # 两条线段 pq 与 rs 是否真正相交(不含共享端点)
    def orient(a, b, c):
        v = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
        return (v > 1e-12) - (v < -1e-12)
    return (orient(p, q, r) * orient(p, q, s) < 0
            and orient(r, s, p) * orient(r, s, q) < 0)


def crossings(t):
    n, c = len(t), 0
    for i in range(n):
        for k in range(i + 2, n):
            if i == 0 and k == n - 1:
                continue
            a, b = PTS[t[i]], PTS[t[i + 1]]
            e, f = PTS[t[k]], PTS[t[(k + 1) % n]]
            if cross(a, b, e, f):
                c += 1
    return c


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 label(t):
    return "".join(NAMES[i] for i in t + [0])


t = nearest_neighbour()
print("start NN  %6.2f km  crossings %d  %s" % (tour_len(t), crossings(t),
                                                label(t)))
step, n = 0, len(t)
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]
            gain = D[a][b] + D[c][e] - D[a][c] - D[b][e]
            if gain > 1e-12:
                t[i + 1:k + 1] = reversed(t[i + 1:k + 1])
                step += 1
                print("move %d  out %s%s+%s%s in %s%s+%s%s gain %.2f" % (
                    step, NAMES[a], NAMES[b], NAMES[c], NAMES[e],
                    NAMES[a], NAMES[c], NAMES[b], NAMES[e], gain))
                print("        %6.2f km  crossings %d  %s" % (
                    tour_len(t), crossings(t), label(t)))
                improved = True
print("no improving pair left among %d candidate pairs" % (
    n * (n - 3) // 2))

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 2: Croes's Pairwise Exchange: Reversing a Stretch, Crossings and Local Optima. 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