为货运承运商设计实时投标决策系统，可快速计算最优性证明。
Certified-Gap Dual-Price Policies for Real-Time Truckload Bid Acceptance with Relocating, Clock-Constrained Resources
- 基于拉格朗日松弛构建双重价格策略，实时决策并提供优化保证。
- 在三个场景中表现优于强化学习模型，提升2.0至3.5个百分点，决策仅需0.09毫秒。
- 适用于高时效、带时钟约束的物流调度，适合需要可信优化结果的工业应用。
货运承运商必须在数秒内决定接受或拒绝每单运输请求，决策依赖于车队状态、小时服务（HOS）时钟和预约窗口。本文将此建模为弱耦合动态规划问题，资源可移动并携带时钟：完成任务后卡车移至新市场且时钟减少，能否服务取决于当前状态。传统基于占用率的可复用资源模型不适用此场景。我们从同一拉格朗日松弛中构建实时双重价格策略，该策略与问题上界来自同一对象，每次运行均能报告认证的最优性差距。证明了三点：第一，证书对任意对偶变量、任意离散化及任意代理质量均有效；第二，策略的同时间空间梯度规则恰好对应流体互补松弛，且在亚临界流体状态下渐近最优，拟合价格可在不同样本路径间迁移，得益于线性规划基的稳定性；第三，证书存在局限：每资源拉格朗日松弛量可能在所有车队规模下保持远离零。我们展示了一个三卡车核心实例的精确有理证书及复制引理。在包含三十组配对种子的公开闭环基准测试中，该策略（无需滚动标签，仅需一次离线对偶求解）在三个场景中有两个胜过滚动训练的代理模型（紧约束：+2.0个百分点，95%置信区间[+0.5, +3.6]，威尔科克斯森检验p=0.023；温和约束：+3.5个百分点，置信区间[+2.4, +4.5]），第三个持平。决策耗时0.04–0.09毫秒，比蒙特卡洛滚动教师快三个数量级。其证书在每场景十个有界实例中稳定，达到最优值的57%-64%，与1000倍慢的教师所证差距仅3-6点。
原文摘要 · Abstract (English)
A truckload carrier must accept or reject each load tender within seconds. The decision depends on fleet state, hours-of-service (HOS) clocks, and appointment windows. We model this as a weakly coupled dynamic program in which the resources relocate and carry clocks: serving a request moves the truck to a new market and depletes its clocks, and whether a truck can serve a request depends on its state. Occupancy-based reusable-resource models do not cover this setting. We build a real-time dual-price policy from the same Lagrangian relaxation that gives the problem's upper bound. Policy and bound come from one object, so every run reports a certified optimality gap. We prove three things. First, the certificate is valid for any duals, any discretization, and any surrogate quality. Second, the policy's same-time spatial-gradient rule is exactly fluid complementary slackness, and the policy is asymptotically optimal in the subcritical fluid regime; the fitted prices are also portable across sample paths, by linear-programming basis stability. Third, certificates have limits: per-resource Lagrangian slack can stay bounded away from zero at every fleet size. We exhibit a three-truck kernel with an exact rational certificate and a replication lemma. On a public closed-loop benchmark with thirty paired seeds, the policy -- which needs no rollout labels, only one offline dual solve -- beats a rollout-trained surrogate on two of three scenarios (tight: +2.0 pp, 95% CI [+0.5, +3.6], Wilcoxon p = 0.023; mild: +3.5 pp, CI [+2.4, +4.5]) and ties the third. It decides in 0.04-0.09 ms, three orders of magnitude faster than the Monte Carlo rollout teacher. Its certificates are stable across ten bounded instances per scenario, at 57-64% of optimal, within 3-6 points of what the 1000x-slower teacher certifies.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。