精读笔记

Problem Setting

论文标题：Traveling Salesman Tardiness（arXiv preprint / 2026-07-08）。

这篇论文关心的不是经典 TSP 的求解，也不是 stochastic/robust TSP 中“给定不确定集合后求 worst-case route”。它实际在解决一个更运营化的问题：给定历史客户位置样本和一个 route-time deadline，系统对空间需求分布偏移有多脆弱。

真正困难点在于，TSP 路长对空间分布的响应不是简单的一阶均值函数。BHH 近似给出的是 beta sqrt(n) int sqrt(f)，其中 sqrt(f) 使得局部密度尖峰会对路长产生非线性影响；而 Wasserstein 距离又鼓励局部搬运质量。因此 deadline violation 的最坏斜率由“局部密度集中”和“空间搬运成本”之间的 trade-off 决定。

以前方法主要卡在两个地方：经典连续近似给 nominal scaling，但不处理 target violation；Wasserstein DRO TSP 能算 worst-case length，但通常固定半径，缺少对 deadline fragility 的解析刻画。本文把问题从“某个半径内最坏多长”改成“单位空间分布偏移会造成多少超时”，这是关键建模转向。

Motivation

已有路线不够的地方在于，它们通常把不确定性作为优化约束或保守目标，而不是把运营 target 本身作为研究对象。对配送系统来说，manager 更关心的是：8 小时窗口到底有多 fragile，区域面积、需求量、历史样本密度、车队规模分别怎样影响这个 fragility。

作者的核心观察是：route-time target 的可靠性不能只看 nominal TSP length。即使 nominal 路长满足 target，空间分布发生小幅 Wasserstein 偏移后，BHH 积分项可能显著增大。这个风险不等价于传统的 route-length scaling，因为被度量的是 exceedance per perturbation，而不是 route length 本身。

关键缺口是缺少一个同时满足三点的对象：有明确 target interpretation、可计算、可推出 scaling law。robust satisficing 提供了 target-oriented risk 的框架，BHH 提供了 TSP 对密度的连续近似，半离散 OT 提供了处理 empirical support 的工具；本文的动机就是把这三者接起来。

Core Idea

核心思想是定义 TSP tardiness index：在所有可能真实空间密度 f 中，取超出 deadline 的路长部分相对于 f 到历史经验分布 Wasserstein 距离的最大比值。这个 index 不是概率意义上的 violation probability，而是一个 Lipschitz-like fragility constant：它衡量 target violation 对空间分布 misspecification 的最坏敏感度。

这个建模引入的 inductive bias 很明确：风险来自空间分布偏移，而不是来自需求量随机性或 travel-time noise；route length 由 BHH 的 sqrt-density functional 主导；历史样本只通过 empirical support 和 Wasserstein geometry 进入。相比固定半径 DRO，它重新组织了信息流：半径 t 不再是外生参数，而是在 sup_t [(beta sqrt(n) E_D(t)-tau)^+]/t 中被内生选择。也正因为如此，论文能解释为什么 fragility scaling 是 n sqrt(|D|m)/tau，而不是经典 TSP 的 sqrt(n)。

Method

第一，BHH 连续近似把 TSP 路长写成 beta sqrt(n) int_D sqrt(f)。它解决的是离散 TSP 难以直接做分布扰动分析的问题。代价是牺牲有限样本和边界效应，但换来了可微/可变分的密度泛函。

第二，robust satisficing 把 target violation 写成 rho_tau = sup_f (L(f)-tau)^+ / W1(f, empirical)。它解决的是 deadline risk 缺少统一尺度的问题。核心变化是从 worst-case performance 转向 target fragility：同样的 worst-case 路长，如果离 empirical distribution 很远，其风险解释会弱很多。

第三，固定 k 的 value function V_D(k)=sup_f {beta sqrt(n) int sqrt(f)-k W1(f, empirical)} 被转成有限维问题。半离散 OT duality 把 W1 的连续-离散耦合变成 lambda 变量，进一步可得到最坏密度 f*_k(x) proportional to 1/(k a_lambda(x)+nu)^2。这一步说明 worst-case density 的形态不是任意的，而是由到经验支持点的 transport potential 决定。

第四，SOCP reformulation 是计算层面的关键。它把积分网格化并用 rotated cone 表示 1/t 型约束。这里的贡献更偏 engineering/optimization formulation：它确实提升可解性，但论文真正的理论贡献不在 SOCP 本身，而在后面的 envelope scaling。

第五，envelope E_D(t)=sup_{W1<=t} int sqrt(f) 是分析核心。上界用 distance-to-support 函数控制 int sqrt(f)，下界通过在足够分散的经验点附近构造局部尖峰密度。这个机制直接导出 E_D(t) ~ |D|^{1/4} m^{1/4} sqrt(t)，再经过一维优化得到 rho_tau ~ beta^2 n sqrt(|D|m)/tau。

Key Insight / Why It Works

最重要的 insight 是：tardiness fragility 的 scaling 不继承 TSP nominal length 的 sqrt(n)，而是经过 target-ratio 优化后变成线性 n。原因很具体：route length 项是 beta sqrt(n) E_D(t)，而 E_D(t) 在 Wasserstein 半径 t 下按 sqrt(t) 增长；最大化 (A sqrt(t)-tau)/t 的 interior optimum 给出 A^2/tau，其中 A^2 正比 n sqrt(|D|m)。所以 n 的线性增长不是实验现象，而是 sqrt-density envelope 和 ratio objective 共同造成的。

第二个核心 insight 是 m^{1/2} 项的来源。它不是“样本越多越不确定”这种统计悖论，而是几何敏感度：经验支持点越密，distance-to-support 积分 I_X 越大，单位 Wasserstein budget 可以在更多局部邻域制造尖峰密度，从而增加 int sqrt(f)。这是一种空间几何下的 adversarial local concentration effect。

第三，方法有效主要来自 better inductive bias，而不是 data scaling。它把风险限制在 locational distributional shift 这一个轴上，并用 W1 的局部搬运几何刻画它；这比直接用 overtime historical frequency 更可迁移，因为后者混入服务时间、道路拥堵、调度习惯等因素。

但也要直接说：SOCP 的速度提升更多是 formulation/engineering contribution；partition rule 的有效性主要来自 scaling law 的低维化，而不是复杂优化。实验里真实数据相关性增强依赖 service-time control，说明原始 overtime 风险里有很大一部分不是空间分布解释的。若不控制这些 confounder，tardiness index 的信号并不强。

Relation To Prior Work

最接近的路线是 Carlsson/Delage 的 robust partitioning 和 Carlsson-Behroozi-Mihic 的 Wasserstein DRO TSP。本文沿用了 spatial distributional uncertainty + Wasserstein ambiguity 的谱系，也沿用了连续近似下的 TSP density functional。不同点在于 prior 多数是半径固定的 worst-case optimization，而本文研究的是 target violation 对半径的最坏比例，即 robust satisficing fragility。

和经典 BHH/TSP scaling 的本质差异是研究对象变了。BHH 解释 route length 的 first-order growth；本文解释 deadline fragility 的 sensitivity growth。因此出现 n 而不是 sqrt(n) 并不是推翻 BHH，而是 ratio objective 对 BHH functional 的二次放大。

和 robust satisficing literature 相比，本文不是把 satisficing measure 嵌入某个应用模型后做数值优化，而是对这个 measure 在 TSP 空间几何下做结构分析。实质创新在于把 robust satisficing 的抽象 fragility measure 具体化为一个可推导 scaling law 的 TSP risk object。

看似新的部分中，SOCP reformulation 更像已有半离散 OT/DRO 思想的重组；真正新增的信息是 envelope bound 和由此得到的 n sqrt(|D|m)/tau 规律，以及多车情形下的 1/K^2 fragility reduction。

Dataset / Evaluation

evaluation 覆盖 synthetic spatial distributions 和 Amazon last-mile data。synthetic 部分主要用于验证 index 与 out-of-sample overtime 指标的关联，以及 partition rules 在不同分布下的表现；真实数据部分用于说明空间 fragility signal 在实际配送记录中仍有解释力。

实验基本支持两个弱 claim：tardiness index 是 overtime risk 的有用 proxy；SOCP 比 cutting-plane 更 scalable。但它没有完全验证最强 claim，即 scaling law 在真实大规模运营环境中稳定成立。真实数据只选了覆盖较好的 Amazon stations，且需要控制 service time 后相关性才明显增强，这说明 spatial uncertainty 只是 overtime 的一个分量。

partition rule 的实验是有价值的，但仍是模拟式 out-of-sample evaluation：区域形状、道路网络、司机行为、容量约束、route sequencing 细节都被高度抽象。它验证的是 scaling-derived rule 在理想化 TSP setting 下合理，不等于证明真实 zone redesign 会带来同等收益。

Limitation

第一，BHH 近似是理论地基，也是主要上限。有限 n、非欧氏路网、复杂边界、depot 位置、道路通行约束都会改变 route length functional。文中承认 calibration 可吸收部分误差，但未充分说明 calibration error 对 rho_tau 的影响。

第二，locational uncertainty 被单独抽出。真实 tardiness 通常由服务时间、交通、车辆容量、driver behavior、stop density、楼宇类型共同决定。Amazon 实验中 service-time control 后结果明显变强，反过来说明不控制时 index 的解释力有限。

第三，lower bound 依赖 interior support dispersion。严重聚类、边界集中、线状道路网络、非均匀城市结构都可能破坏局部球构造。这个条件不是技术小问题，而是 scaling law 能否迁移到真实城市空间的关键前提。

第四，m 的解释存在潜在误读。理论里的 m 是经验支持点数量，进入的是几何支持密度；实际中 m 同时代表数据量、需求覆盖、采样偏差和历史窗口长度。文中未充分说明如何区分“更多样本导致支持更密”与“更多样本降低分布估计误差”这两个方向相反的效应。

第五，多车 1/K^2 结论依赖 balanced makespan approximation。真实 VRP 中车辆增加可能受到 depot loading、区域切分离散性、容量、司机班次和 traffic synchronization 限制，实际收益很可能低于理论 scaling。

Takeaway

• 最值得记住的不是 SOCP，也不是实验相关性，而是把 route deadline fragility 写成 Wasserstein perturbation 下的 target-violation slope。
• 这个对象比 nominal route length 更接近运营风险，也比固定半径 DRO 更适合做系统设计比较。
• 这篇真正推动的是 TSP continuous approximation 从“估计路长”走向“刻画目标脆弱性”。
• 它说明在 target-oriented risk 下，经典 sqrt(n) economies of scale 不会自动转化为 reliability；需求量增加会线性放大 deadline fragility。

一句话总结

这篇论文把 Wasserstein DRO TSP 和 robust satisficing 结合成一个 deadline fragility 理论，真正贡献是证明 TSP 迟到风险的主导 scaling 为 n sqrt(|D|m)/tau，并把经典路长近似推进到 target-oriented system design。