What does Optimal Transport for Luxury Stock Transfers conclude, in numbers, about “The Price of Serving the Emptiest Shelf First: Greedy Transfers against the Transportation Optimum”?

Answer: Chapter 1 measures the excess of shortage-first over three thousand random snapshots: the median is only 0.0338, but the 99th percentile reaches 0.320.

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.0338, 0.320, 99

3000 random snapshots; excess cost over the MODI optimum
rule exact median p90 p99 mean95%CI
shortage-first0.217 0.0338 0.153 0.320 0.0578 0.0552-0.0604
least-cost0.388 0.0063 0.066 0.154 0.0218 0.0206-0.0230
shortage-first share above 10%0.205 above 25%: 0.026
least-cost share above 10%0.044 above 25%: 0.000
Show the full program
# Chapter 1. p12: how often, and by how much, shortage-first loses.
# Model: 3,000 random weekly snapshots on the eleven-city map of p11.
# Each draws 3 or 4 surplus stores (1 to 6 units each) and 3 to 5 short
# stores whose shortages split the same total at random cut points.
# Compared: shortage-first greedy, the least-cost-cell rule and the
# exact MODI optimum. Fixed seed; all parameters illustrative.
import math
import random

# 十一城经纬度(取整到 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])))

def greedy_shortage_first(c, s, d):
    m, n = len(s), len(d)
    s, d = list(s), list(d)
    x = [[0] * n for _ in range(m)]
    for j in sorted(range(n), key=lambda k: (-d[k], k)):
        while d[j] > 0:
            i = min((k for k in range(m) 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 least_cost_cell(c, s, d):
    # 最小元素法:全表最便宜的格子先装满
    m, n = len(s), len(d)
    s, d = list(s), list(d)
    x = [[0] * n for _ in range(m)]
    for _, i, j in sorted((c[i][j], i, j)
                          for i in range(m) for j in range(n)):
        q = min(s[i], d[j])
        x[i][j] += q
        s[i] -= q
        d[j] -= q
    return x


rng = random.Random(20261113)
names = sorted(CITY)
gaps = {"shortage-first": [], "least-cost": []}
N = 3000
for _ in range(N):
    sup = rng.sample(names, rng.randint(3, 4))
    rest = [k for k in names if k not in sup]
    dem = rng.sample(rest, rng.randint(3, 5))
    s = [rng.randint(1, 6) for _ in sup]
    tot = int(math.fsum(s))
    while tot < len(dem):
        s[0] += 1
        tot += 1
    cuts = sorted(rng.sample(range(1, tot), len(dem) - 1))
    d = [b - a for a, b in zip([0] + cuts, cuts + [tot])]
    c = [[unit_cost(a, b) for b in dem] for a in sup]
    opt = total(c, modi(c, s, d)[0])
    gaps["shortage-first"].append(
        total(c, greedy_shortage_first(c, s, d)) / opt - 1.0)
    gaps["least-cost"].append(total(c, least_cost_cell(c, s, d)) / opt - 1.0)

print("%d random snapshots; excess cost over the MODI optimum" % N)
print("rule             exact  median    p90    p99   mean  95%CI")
for key in ("shortage-first", "least-cost"):
    g = sorted(gaps[key])
    exact = len([v for v in g if v < 1e-12]) / N
    mean = math.fsum(g) / N
    sd = math.sqrt(math.fsum((v - mean) ** 2 for v in g) / (N - 1))
    half = 1.96 * sd / math.sqrt(N)
    print("%-15s %6.3f %7.4f %6.3f %6.3f %6.4f  %.4f-%.4f"
          % (key, exact, g[N // 2], g[int(0.9 * N)], g[int(0.99 * N)],
             mean, mean - half, mean + half))
for key in ("shortage-first", "least-cost"):
    g = gaps[key]
    print("%-15s share above 10%%: %.3f   above 25%%: %.3f"
          % (key, len([v for v in g if v > 0.10]) / N,
             len([v for v in g if v > 0.25]) / N))

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 1: The Price of Serving the Emptiest Shelf First: Greedy Transfers against the Transportation Optimum. 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