What does Optimal Transport for Luxury Stock Transfers conclude, in numbers, about “Whole Units, Fees per Shipment and Moving Rates: From a Linear Optimum to an Executable Transfer Sheet”?

Answer: Chapter 6 deals with whole units, fixed fees per shipment and moving rates: at a fee of 200 yuan the linear optimum exceeds the exact optimum by 0.2117, shortage-first then ties with the optimum, and pruning recovers it.

Scope of the numbers: Chapter 5 applies optimal transport to client migration: in an illustrative matrix, gross movement is 13.43 times what the net change requires, so goods follow net flows and people follow gross flows. Chapter 7 examines equitable transport in the Treatise on the Balanced Standard of the Shiji (lateral transfers save 0.721 of freight in an illustrative model) and Monge's cuttings and fillings.

中文版

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.2117, 200

integer plans enumerated3874
fee best routes LP+fee routes greedy+fee routes prune LP excess
01015 6 1015 6 1028 4 1015 0.0000
501228 4 1315 6 1228 4 1228 0.0708
1001428 4 1615 6 1428 4 1428 0.1310
2001828 4 2215 6 1828 4 1828 0.2117
4002628 4 3415 6 2628 4 2628 0.2995
fee 200 plan: SH>BJ 2, HZ>CD 2, NJ>WH 4, GZ>SZ 2
LP plan: SH>BJ 1, HZ>WH 3, NJ>WH 1, NJ>BJ 1, NJ>CD 2, GZ>SZ 2
Show the full program
# Chapter 6. p62: a fixed fee per shipment (pickup, sealing, two-person
# handover) on top of the per-unit cost. Four stores hold 12 spare units
# against 10 units of shortage, so 2 units may stay where they are.
# Every integer plan is enumerated column by column, so the fixed-charge
# optimum is exact. Compared: the linear optimum (MODI with a KEEP
# column at cost 0), shortage-first greedy, and "prune": forbid one used
# route at a time, re-solve by MODI, keep the best saving, repeat.
import math
import itertools

# 十一城经纬度(取整到 0.1 度);单位搬运费 = 30 + 0.1 * 公里,取整(示意:
# 含保价快递与门店交接,非任何承运商报价)
CITY = {"BJ": (116.4, 39.9), "TJ": (117.2, 39.1), "SH": (121.5, 31.2),
        "HZ": (120.2, 30.3), "NJ": (118.8, 32.1), "GZ": (113.3, 23.1),
        "SZ": (114.1, 22.5), "CD": (104.1, 30.7), "CQ": (106.5, 29.6),
        "WH": (114.3, 30.6), "XA": (108.9, 34.3)}


def km(a, b):
    (x1, y1), (x2, y2) = CITY[a], CITY[b]
    dx = (x1 - x2) * 111.0 * math.cos(math.radians((y1 + y2) / 2.0))
    return math.hypot(dx, (y1 - y2) * 111.0)


def unit_cost(a, b):
    return 30 + round(0.1 * km(a, b))
def northwest(s, d):
    # 西北角初解:阶梯形走 m + n - 1 步,保证基是一棵生成树
    s, d = list(s), list(d)
    m, n = len(s), len(d)
    x = [[0] * n for _ in range(m)]
    basis = []
    i = j = 0
    while True:
        q = min(s[i], d[j])
        x[i][j] = q
        basis.append((i, j))
        s[i] -= q
        d[j] -= q
        if i == m - 1 and j == n - 1:
            break
        if s[i] == 0 and i < m - 1:
            i += 1
        else:
            j += 1
    return x, basis


def potentials(c, basis, m, n):
    # 位势:基格上 u_i + v_j = c_ij,取 u_0 = 0
    u = [None] * m
    v = [None] * n
    u[0] = 0
    while None in u or None in v:
        for i, j in basis:
            if u[i] is not None and v[j] is None:
                v[j] = c[i][j] - u[i]
            elif v[j] is not None and u[i] is None:
                u[i] = c[i][j] - v[j]
    return u, v


def tree_path(basis, i, j):
    # 基树中从列 j 走回行 i 的格子序列(闭回路去掉入基格)
    adj = {}
    for a, b in basis:
        adj.setdefault(("r", a), []).append(("c", b))
        adj.setdefault(("c", b), []).append(("r", a))
    prev = {("r", i): None}
    todo = [("r", i)]
    while todo:
        node = todo.pop()
        for nb in adj.get(node, []):
            if nb not in prev:
                prev[nb] = node
                todo.append(nb)
    path, node = [], ("c", j)
    while prev[node] is not None:
        p = prev[node]
        cell = (p[1], node[1]) if p[0] == "r" else (node[1], p[1])
        path.append(cell)
        node = p
    return path


def modi(c, s, d, x=None, basis=None, trace=None):
    # 位势法(MODI):检验数 r_ij = c_ij - u_i - v_j 全部非负即最优
    m, n = len(s), len(d)
    if x is None:
        x, basis = northwest(s, d)
    x = [row[:] for row in x]
    basis = list(basis)
    steps = 0
    while True:
        u, v = potentials(c, basis, m, n)
        best, cell = 0, None
        for i in range(m):
            for j in range(n):
                r = c[i][j] - u[i] - v[j]
                if r < best:
                    best, cell = r, (i, j)
        if cell is None:
            return x, basis, u, v, steps
        i, j = cell
        path = tree_path(basis, i, j)
        minus, plus = path[0::2], path[1::2]
        theta = min(x[a][b] for a, b in minus)
        out = [e for e in minus if x[e[0]][e[1]] == theta][0]
        x[i][j] += theta
        for a, b in minus:
            x[a][b] -= theta
        for a, b in plus:
            x[a][b] += theta
        basis.remove(out)
        basis.append(cell)
        steps += 1
        if trace is not None:
            trace.append((cell, best, theta, out))


def total(c, x):
    return math.fsum(c[i][j] * x[i][j]
                     for i in range(len(x)) for j in range(len(x[0])))

SUP, S = ["SH", "HZ", "NJ", "GZ"], [3, 3, 4, 2]
DEM, D = ["WH", "BJ", "SZ", "CD"], [4, 2, 2, 2]
C = [[unit_cost(a, b) for b in DEM] for a in SUP]


def splits(q, k):
    for xs in itertools.product(range(q + 1), repeat=k):
        if int(math.fsum(xs)) == q:
            yield xs


plans = []
for cols in itertools.product(*[list(splits(q, 4)) for q in D]):
    x = [[cols[j][i] for j in range(4)] for i in range(4)]
    if all(int(math.fsum(x[i])) <= S[i] for i in range(4)):
        plans.append(x)
ck = [row + [0] for row in C]
xk = modi(ck, S, D + [int(math.fsum(S) - math.fsum(D))])[0]
lp = [row[:4] for row in xk]


def shortage_first():
    s, d = list(S), list(D)
    x = [[0] * 4 for _ in range(4)]
    for j in sorted(range(4), key=lambda k: (-d[k], k)):
        while d[j] > 0:
            i = min((k for k in range(4) if s[k] > 0),
                    key=lambda k: (C[k][j], k))
            q = min(s[i], d[j])
            x[i][j] += q
            s[i] -= q
            d[j] -= q
    return x


def with_fee(x, fee):
    n = len([w for row in x for w in row if w > 0])
    return total(C, x) + fee * n, n


def solve_lp(forbid):
    ck = [[C[i][j] if (i, j) not in forbid else 10 ** 6
           for j in range(4)] + [0] for i in range(4)]
    xk = modi(ck, S, D + [int(math.fsum(S) - math.fsum(D))])[0]
    return [row[:4] for row in xk]


def prune(fee):
    # 剪枝:逐条禁用在用路线并重解,取节省最多的一步,直到不再节省
    forbid = set()
    x = solve_lp(forbid)
    while True:
        best = (with_fee(x, fee)[0], None, x)
        for i in range(4):
            for j in range(4):
                if x[i][j] > 0:
                    y = solve_lp(forbid | {(i, j)})
                    if with_fee(y, fee)[0] < best[0] - 1e-9:
                        best = (with_fee(y, fee)[0], (i, j), y)
        if best[1] is None:
            return x
        forbid.add(best[1])
        x = best[2]


gr = shortage_first()
print("integer plans enumerated: %d" % len(plans))
print("fee  best routes  LP+fee routes  greedy+fee routes  prune  LP excess")
for fee in (0, 50, 100, 200, 400):
    best = min(plans, key=lambda x: (with_fee(x, fee)[0], str(x)))
    b, nb = with_fee(best, fee)
    l, nl = with_fee(lp, fee)
    g, ng = with_fee(gr, fee)
    pr = with_fee(prune(fee), fee)[0]
    print("%3d %5d %6d %6d %6d %11d %6d %6d %10.4f"
          % (fee, int(b), nb, int(l), nl, int(g), ng, int(pr), l / b - 1.0))
    if fee == 200:
        keep = best
print("fee 200 plan: " + ", ".join(
    "%s>%s %d" % (SUP[i], DEM[j], keep[i][j])
    for i in range(4) for j in range(4) if keep[i][j]))
print("LP plan:      " + ", ".join(
    "%s>%s %d" % (SUP[i], DEM[j], lp[i][j])
    for i in range(4) for j in range(4) if lp[i][j]))

Single source and citation

Fan, Y. (2026). Optimal Transport and Kantorovich Duality: Minimum-Cost Rebalancing of Luxury Stock across Regions and Client-Migration Matrices (Version 1.0.0), Chapter 6: Whole Units, Fees per Shipment and Moving Rates: From a Linear Optimum to an Executable Transfer Sheet. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 5DL-B-233 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026233,
  author    = {Fan, Yafu},
  title     = {Optimal Transport and Kantorovich Duality: Minimum-Cost Rebalancing of Luxury Stock across Regions and Client-Migration Matrices},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book