Online Allocation with Unknown Shared Supply¶
会议: NeurIPS 2026
arXiv: 2605.07080
OpenReview: https://openreview.net/forum?id=apuN36lY0N
代码: https://github.com/cxjdavin/online-allocation-with-unknown-shared-supply
领域: 其他
关键词: 在线资源分配, 共享供给, 缺货损失系统, 竞争分析, 学习增强算法
一句话总结¶
针对未知共享供给与固定运费约束下的多站点在线前置配给难题，提出确定性阈值比例算法 GPA 与学习增强变体，在理论上证明了紧确的 4/3 竞争比下界与 Pareto 最优预测权衡。
研究背景与动机¶
在人道主义应急救援、疫苗分发物流以及关键备件运维等实际系统中，中央枢纽必须在各站点的真实需求完全显现之前，将极为有限的物资前置调配至各个基层网点。这类场景通常具有严苛的缺货损失（lost-sales）性质：一旦基层网点库存见底，未满足的需求便会造成不可逆的服务损失（如疫苗接种机会丧失或灾民断粮），既无法转入延期交货（backlogging），事后补发也只能用于防范未来的潜在需求。更为棘手的是，上游供给往往存在深度不确定性——由于捐赠波动、突发断资或产能中断，中央枢纽自身并不知晓可调配的共享总库存何时见底，在线决策者仅能在某次申请补给遭到截断时，才获知全局供给已被彻底耗尽。
传统的库存理论与在线算法体系无法直接套用在该问题上。经典的多级库存模型（如单仓库多零售商问题 OWMR 及联合补货问题 JRP）大多建立在无限上游供给或已知平稳需求分布的假设上，允许通过延期交货或持有成本在全局规划周期内平滑发货；而在在线资源分配领域（如 Adwords 预算分配或在线二分图匹配），资源多为即时消耗品或无状态消耗，很少同时面临具有时序持久累积效应的本地库存动态以及非凸阶梯型的整车固定运费（fixed-charge transportation cost）。当运费包含无论满载与否均需支付的批次成本、需求端存在不可逆惩罚、且总供给未知且不可再生时，决策者陷入了严峻的鲁棒配售权衡：若激进补给某一站点，极易在早期耗尽全局稀缺资源，导致其他站点在后续突发高需求时陷入瘫痪；若过于保守惜售，又会在前期任由缺货罚金飞涨，且每次未满载的发货都会严重浪费固定运输成本。
面对这一跨时空的耦合难题，既有方法往往非此即彼，要么完全依赖离线预估，要么在对抗性输入下表现脆弱。本文切入这一挑战的核心构思在于：虽然全局总供给不可知，但在离线最优决策中，物资在各站点间的理想分配比例呈现出严格单调的前缀覆盖结构。通过将本地安全库存补充与基于历史累计需求的保守比例阈值进行正规化绑定，并强力推行满载发货，系统能够在信息完全遮蔽的对抗环境下锁定最坏情况性能边界。核心 idea：提出确定性阈值比例分配策略 GPA，将补货触发条件约束在各站点累计观测需求的一个受控比例阈值内并执行满载发货，通过非耗尽与耗尽双区制的对偶极值分析取得理论最优的 4/3 竞争比，并结合置信截断机制拓展至包含不可靠预测的学习增强框架。
方法详解¶
整体框架¶
在线共享供给分配（Online Shared Supply Allocation, OSSA）问题考虑一个中央枢纽拥有未知固定总供给 \(s\)，向 \(n\) 个面临离散时间步 \(t \ge 1\) 序列需求的站点进行物资配给。每个站点 \(i \in [n]\) 具有单步最大需求上限 \(b_i\)、单次运输固定容量 \(c_i\)、固定运费 \(w_i\)，以及单位缺货罚金 \(p\)（满足无损假设 \(w_i \le p c_i\)）。在每个时间步中，各站点首先面临需求 \(d_i^t\) 并由在手库存 \(k_i^t\) 满足，未满足部分产生惩罚 \(p(d_i^t - k_i^t)_+\)；随后算法观察到需求后决定申请补料 \(\tilde{\ell}_i^t\)，中央枢纽根据剩余供给返回实际补给 \(\ell_i^t = \min\{s, \tilde{\ell}_i^t\}\)，次日库存更新为 \(k_i^{t+1} = (k_i^t - d_i^t)_+ + \ell_i^t\)。算法的目标是最小化运输费用与缺货罚金的总和： $$ \mathrm{cost}(\bar{\ell}) = \sum_{i=1}^n \sum_{t \ge 1} \left( w_i \left\lceil \frac{\ell_i^t}{c_i} \right\rceil + p (d_i^t - k_i^t)_+ \right) $$
GPA（\(\bar{\gamma}\)-Proportional Allocation）通过为每个站点配置一个阈值参数 \(\gamma_i \in [0, 1]\)，将复杂的跨站点全局博弈分解为基于本地观测需求的受控阈值响应。整个决策框架涵盖需求响应、安全库存校验、双区制平衡配置以及基于外部建议的预测截断。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["输入：多站点时序需求与未知总供给<br/>中心枢纽 s 与站点参数 (w_i, c_i, b_i)"] --> B["阈值比例安全库存补货<br/>当本地余量低于 b_i 且累计补量不超过 gamma_i D_i^t 时触发"]
B --> C["双区制参数平衡机制<br/>设定 tau=1/3 联立非耗尽上界与耗尽下界取得 4/3 近似比"]
C --> D["预测引导与置信区间裁剪<br/>融合预测供需计算参考比例并在理论安全区间截断"]
D --> E["输出：在线批次补货决策<br/>达到最优 4/3 竞争比并保持 Pareto 最优预测折中"]关键设计¶
1. 阈值比例安全库存补货：解耦未知供给风险并消除单次运力浪费
针对传统补货策略要么过早耗尽总库存、要么单次补货批量过小导致固定运费激增的痛点，GPA 设计了两重联合校验门槛。首先，为避免无谓发货，只有当站点的剩余库存低于单步最大需求 \(r_i^t = (k_i^t - d_i^t)_+ < b_i\) 时，该站点才具备补货资格；其次，为了防止对突发大需求的过度响应而挤占全局共享供给，算法强制要求截至前一时步的累计补货量不能突破当前累计需求的设定比例，即必须满足 \(L_i^{t-1} \le \gamma_i D_i^t\)。一旦两个条件同时满足，算法绝不按实际缺口随意补货，而是严格按照运输容量 \(c_i\) 向上取整申请整车批次： $$ q_i^t = \left\lceil \frac{b_i - r_i^t}{c_i} \right\rceil $$ 该设计确保了每一次支付固定运费 \(w_i\) 时，都能最大化提取其运输容量效用，将末期可能滞留的无效库存严格限制在 \(s_i^{\mathrm{end}} \le b_i + c_i\) 的常数范围内，从而使算法在不预知总供给 \(s\) 的情况下，将不可控的非凸阶梯运费与缺货惩罚牢牢锚定在与离线基准可比的线性包络内。
2. 双区制参数平衡机制：联立极值状态实现紧确的 4/3 竞争比
在未知总供给 \(s\) 的对抗环境下，算法面临着两种极端且对立的博弈态势：其一是总供给极其充裕（\(s^{\mathrm{end}} > 0\)），枢纽从未耗尽；其二是总供给高度匮乏（\(s^{\mathrm{end}} = 0\)），枢纽在中途被强制耗尽。若 \(\gamma_i\) 偏小，算法在非耗尽情形下会因过于保守而蒙受大量不必要的缺货惩罚；若 \(\gamma_i\) 偏大，算法在耗尽情形下则会过早盲目发货而造成过剩运输成本。
通过严密的势能与归纳分析，论文揭示了两个区制下的成本上界结构：在非耗尽区制中，只要 \(\gamma_i \ge \min\{1, \frac{\tau p c_i}{w_i}\}\)，算法成本满足 \(\mathrm{cost}(\bar{\ell}) \le (1 + \frac{(1-\tau)^2}{4\tau}) \mathrm{cost}(\textsc{Opt}) + \beta\)；在耗尽区制中，只要 \(\gamma_i \le \min\{1, \frac{\tau p c_i}{w_i}\}\)，算法成本满足 \(\mathrm{cost}(\bar{\ell}) \le (1 + \tau) \mathrm{cost}(\textsc{Opt}) + \beta\)。由于真实运行环境属于哪种区制完全未知，算法必须选择两曲线的交点以最小化最坏情况竞争比。令两区制系数相等： $$ 1 + \frac{(1-\tau)^2}{4\tau} = 1 + \tau \implies (1-\tau)^2 = 4\tau^2 \implies \tau = \frac{1}{3} $$ 带入即得最优比例阈值 \(\gamma_i = \min\{1, \frac{p c_i}{3 w_i}\}\)，此时算法达到完美的 \(1 + \tau = 4/3\) 竞争比。更关键的是，论文利用姚氏极小极大原理构造了反例分布，证明了无论是 4/3 的乘性近似比，还是与总供给 \(s\) 无关的加性误差项 \(\sum_i 3p(b_i + c_i)\)，在理论上皆是紧确且不可改进的，即便是预先知晓总供给 \(s\) 的随机化算法也无法打破这一理论壁垒。
3. 预测引导与置信区间裁剪：兼顾一致性与最坏情况鲁棒性的学习增强设计
在实际供应链中，决策者往往能够获取由机器学习模型或气象/人口统计学给出的不完美预测。为了安全利用总供给预测 \(\hat{s}\) 与各站点总需求预测 \(\{\hat{D}_i\}_{i \in [n]}\)，算法提出了 LA-GPA(\(\lambda\)) 机制。该机制引入了一个直观的不信任超参数 \(\lambda \in (0, 1/3]\)：一方面，基于预测净需求 \(\hat{N}_i = (\hat{D}_i - k_i^1)_+\) 贪心模拟离线最优解，推导估算的枢纽耗尽关键站点 \(\hat{i}^\star\) 及分割比例 \(\hat{\zeta}\)；另一方面，设定基于鲁棒性要求的安全裁剪区间： $$ \texttt{lower}_i = \min\left{1, \frac{\lambda p c_i}{w_i}\right}, \quad \texttt{upper}_i = \min\left{1, \frac{\tau p c_i}{w_i}\right} \quad \text{其中 } \tau = (\sqrt{1+\lambda} - \sqrt{\lambda})^2 $$ 算法将预测得到的推荐比例强制投影到该区间内：对关键站点前缀取 \(\texttt{upper}_i\)，对后缀取 \(\texttt{lower}_i\)，对关键站点取裁剪后的中间值。这一设计在数学上实现了优雅的 Pareto 最优折中：当预测完全精确且 \(\lambda \to 0\) 时，算法达成 1-一致性（即与离线最优仅相差可忽略的加性项）；而当预测遭受恶意对抗攻击或误差 \(\eta\) 极大时，最坏情况竞争比仍被稳稳死守在 \(1 + \frac{(1-\lambda)^2}{4\lambda}\) 内，杜绝了盲目信任黑盒预测可能导致的灾难性后果。
损失函数 / 训练策略¶
本算法为非参数化的在线凸/组合优化策略，无需传统神经网络的梯度反向传播训练。对于学习增强版本 LA-GPA(\(\lambda\))，参数调整策略聚焦于超参数 \(\lambda\) 的选择：当外部预测源历史可信度极高（如平稳期的日常物流）时，将 \(\lambda\) 调小至接近 0（例如 0.05）；当外部环境动荡或缺乏验证数据时，将 \(\lambda\) 设置为 1/3，无缝退化为完全对抗鲁棒的无建议 GPA 算法。
实验关键数据¶
主实验¶
实验在合成数据集（50 个站点，\(T=10000\) 步，不同 Beta 分布运费）与纽约市出租车（NYC TLC）真实衍生数据集（9 个区域网点，90 天日度接客量作为需求，按空间几何距离设定运费）上进行了详尽评测。评测指标为相对离线最优解的实际成本比值 \(\mathrm{cost}(\mathrm{Alg}) / \mathrm{cost}(\mathrm{Opt})\)，核心对比了不同供给充裕度 \(\rho = s / \sum_i (D_i - b_i)\) 下的表现。
| 数据集 | 供给充裕度 \(\rho\) | GPA (本文) | AlwaysFill | \(\rho\)-Greedy (已知\(\rho\)) | Backlog | 提升幅度 (相对最强未知基线) |
|---|---|---|---|---|---|---|
| Synthetic (\(\beta(1,1)\)) | \(\rho = 0.2\) (极度匮乏) | 1.21 | 2.15 | 1.35 | 1.88 | 降低 35.6% 成本比 |
| Synthetic (\(\beta(1,1)\)) | \(\rho = 0.5\) (中度匮乏) | 1.14 | 1.62 | 1.20 | 1.45 | 降低 21.4% 成本比 |
| Synthetic (\(\beta(1,1)\)) | \(\rho = 0.8\) (相对充足) | 1.18 | 1.24 | 1.11 | 1.21 | 降低 2.5% 成本比 |
| NYC TLC Taxi | \(\rho = 0.2\) (极度匮乏) | 1.19 | 2.08 | 1.41 | 1.76 | 降低 32.4% 成本比 |
| NYC TLC Taxi | \(\rho = 0.5\) (中度匮乏) | 1.12 | 1.54 | 1.18 | 1.39 | 降低 19.4% 成本比 |
| NYC TLC Taxi | \(\rho = 0.8\) (相对充足) | 1.15 | 1.19 | 1.08 | 1.16 | 降低 0.9% 成本比 |
消融实验¶
在学习增强算法 LA-GPA(\(\lambda\)) 中，评估了不同不信任超参数 \(\lambda \in \{0.05, 0.15, 0.33\}\) 在完美预测（\(\eta = 0\)）与严重噪声预测（\(\eta \approx 10s\)）下的成本表现，以验证一致性与鲁棒性权衡。
| 配置 | 预测误差 \(\eta\) | 成本比值 (\(\rho=0.2\)) | 成本比值 (\(\rho=0.5\)) | 说明 |
|---|---|---|---|---|
| LA-GPA (\(\lambda=0.05\)) | 0 (完美预测) | 1.04 | 1.02 | 接近 1-一致性，几近贴合离线最优 |
| LA-GPA (\(\lambda=0.15\)) | 0 (完美预测) | 1.09 | 1.06 | 适度信任预测，表现显著优于无预测 |
| LA-GPA (\(\lambda=0.33\)) | 0 (完美预测) | 1.21 | 1.14 | 完全退化为标准 GPA，忽略预测增益 |
| LA-GPA (\(\lambda=0.05\)) | \(10s\) (严重对抗噪声) | 1.48 | 1.36 | 高度信任导致被错误预测误导，性能劣化 |
| LA-GPA (\(\lambda=0.15\)) | \(10s\) (严重对抗噪声) | 1.29 | 1.22 | 裁剪机制起效，有效阻断极端错误干扰 |
| LA-GPA (\(\lambda=0.33\)) | \(10s\) (严重对抗噪声) | 1.21 | 1.14 | 具备绝对鲁棒性，完全免疫恶劣虚假建议 |
关键发现¶
- 供给匮乏区间收益最为显著：当共享供给极度稀缺（\(\rho \le 0.4\)）时，GPA 的优势呈现爆发式增长。激进的 AlwaysFill 策略由于迅速在前几个时步将物资挥霍殆尽，后续爆发巨额缺货惩罚，导致成本比高达 2.0 以上；而 GPA 凭借严格的比例节流将成本比稳固在 1.20 附近。
- 优于知晓全局信息的启发式基线：即便 \(\rho\)-Greedy 策略违规提前获知了全局供给比例 \(\rho\)，GPA 在紧平衡状态下依旧通过更细粒度的单位运费优先级配给实现了更低的整体损失。
- 理论下界的经验验证：在全量实验中，无论需求序列如何波动，GPA 的经验比值始终被牢牢压制在理论界 \(4/3 \approx 1.333\) 以内，且平稳过渡，验证了理论推导的坚实性。
亮点与洞察¶
- 双区制极小极大对偶性：将未预知中断的在线决策分解为非耗尽与耗尽两个对立凸包，通过解析联立二者上界直接导出全局最优参数 \(\tau = 1/3\)，数学技巧极为漂亮且自洽。
- 整车取整与安全库存边界吸收：巧妙证明了即使每次补货向上取整导致微量库存滞留，该滞留量在每个站点均恒有上界 \(b_i + c_i\)，成功将非凸发货成本的离散扰动转化为与总供给无关的加性残差。
- 学习增强安全护栏机制：提出的动态区间截断技术为黑盒机器学习预测在关键物流、医疗资源调配中的落地提供了零风险安全护栏，极具工业迁移价值。
局限与展望¶
- 单枢纽与单品类假设：当前理论模型限定于单中央仓库与同质物资，现实中的人道主义供应链往往呈现树状多级中转及多种物资争抢有限车厢容积的复杂网状结构。
- 缺乏紧急补采购期权：模型假设供给完全耗尽即永久中断，未考虑在支付高额溢价的前提下从公开市场启动紧急临时调配的二次反应机制。
- 自适应置信度动态追踪：目前 \(\lambda\) 仍为静态预设参数，未来探索在线观测预测残差并动态自适应收缩/放宽 \(\lambda\) 的 Test-and-Act 机制是极富前景的研究方向。
相关工作与启发¶
- vs OWMR / JRP (单仓库多零售商 / 联合补货问题)：传统模型侧重于在无限可再生供给下平衡持有成本与延期交货成本；本文聚焦于有限、未知且不可再生的共享供给，且在缺货损失立即结算的严苛环境下给出了首个紧确竞争比。
- vs Adwords / 在线二分图匹配：经典预算分配通常处理无状态的即时消耗流，本文必须显式跟踪各站点持久积累的物理库存动态，解决了状态演化与终端资源耗尽的双重耦合难题。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次形式化定义并完整解决了未知共享供给下的状态化在线配给问题。
- 实验充分度: ⭐⭐⭐⭐☆ 理论推导极为完备，合成数据与真实场景重构实验覆盖深入，若有真实战区或疫苗分发实测数据将更为圆满。
- 写作质量: ⭐⭐⭐⭐⭐ 论文结构严谨，数学定义清晰，从算法构建、理论证明到下界验证一气呵成。
- 价值: ⭐⭐⭐⭐⭐ 为应急物流、疫苗供应与计算经济学提供了具备强理论保证的实用算法工具。