《Algorithms》：ETHC-VRC: Explicit Time-State Representation and Hybrid Constraint Handling for Time-Windowed Vehicle Routing Construction
编辑推荐：
摘要专业翻译
面向带时间窗的容量约束车辆路径问题（CVRPTW），基于学习的路径构建方法必须允许策略在训练阶段访问不可行状态，同时所部署的路线在既定假设下须可证明地满足每个时间窗。然而，在现有深度强化学习（DRL）方法中，时间信息仅服务于单一的约束处理模式，且
摘要专业翻译
面向带时间窗的容量约束车辆路径问题（CVRPTW），基于学习的路径构建方法必须允许策略在训练阶段访问不可行状态，同时所部署的路线在既定假设下须可证明地满足每个时间窗。然而，在现有深度强化学习（DRL）方法中，时间信息仅服务于单一的约束处理模式，且该模式在训练和推理阶段被固定不变。研究人员提出ETHC-VRC，一种DRL构建方法，其显式时间状态由解码器上下文与硬时间窗掩码共享，使得在软惩罚下训练的策略无需重新训练即可在该掩码下解码；其混合约束策略在两种模式下分别解码每个实例，并保留成本更低的解。在20至100节点的实例上，贪心解码在GPU上数秒内求解10,000个实例，其混合成本低于贪心解码的DRL基线（在100节点上与MVMoE相比无显著差异）。每种模式采样1280个解可进一步将成本降低3.8–4.9%，每实例耗时0.07–0.32秒，达到OR-Tools运行10–120秒每实例所得结果的2.1–4.3%以内，并在相同时间预算下低于OR-Tools。在跨五种规模的零样本泛化中，贪心解码在所有15种训练–测试组合上均优于TPA-Reward，并在8种组合上优于参数量为其5.3倍的MVMoE。单一模型由此提供了显式的质量–延迟权衡，预期可同时适配对延迟敏感和对质量敏感的物流应用场景。
论文解读
一、研究背景与问题
随着中国电子商务和快递行业的持续扩张，2024年快递包裹量已达1745亿件，城乡配送网络的广泛覆盖为智慧物流的大规模部署提供了运营基础。在此背景下，物流行业迫切需要能够同时处理车辆容量限制和客户时间窗要求等复杂约束，并能在实时响应能力下逼近最优解质量的路径规划方案。传统精确算法在处理此类多约束大规模实例时计算成本过高，而启发式算法虽然快速却难以保证解质量，这一矛盾推动了基于学习的神经构建方法的发展。
在现有的深度强化学习（DRL）方法中，时间信息仅服务于单一的约束处理模式，该模式在训练和推理阶段被固定。纯软约束方法虽保持训练灵活性但无法认证可行性；硬掩码方法虽在每一步强制可行性却将不可行动作从训练探索中移除；惩罚与掩码结合的方法则在两个阶段应用相同组合。这些缺陷导致现有方法难以同时实现高解质量、快速推理速度和强泛化能力，限制了其在真实物流场景中的部署。针对上述不足，本文研究如何开发面向CVRPTW的DRL解决方案，以解决两个核心挑战：设计显式时间状态架构以原生整合时间信息，以及建立将训练阶段灵活性与推理阶段可行性保证分离的混合约束处理策略。
二、研究内容与结论
本文旨在构建时间窗感知架构与动态约束处理机制，以联合建模CVRPTW中的容量和时间窗约束，并建立平衡解可行性与质量的惩罚引导训练框架。为此，研究人员开发了改进的Transformer方法，纳入时间约束建模的架构设计，提出平衡训练与部署需求的约束处理机制，并在多种问题规模上开展系统实验验证。主要贡献包括：提出显式时间状态表示，其变量和更新规则由解码器上下文、混合成本和硬时间窗掩码共享，使软约束训练的策略无需重新训练即可在部署时以硬掩码解码；提出混合约束策略，以惩罚软约束训练，推理时混合软约束与硬掩码解码并为每个实例保留成本更低的解；在五种问题规模上评估零样本泛化，贪心解码在所有15种训练–测试组合上优于TPA-Reward，在8种组合上优于参数量5.3倍的MVMoE，采样进一步降低混合成本。
三、关键技术方法
研究人员采用以下主要技术方法开展研究。其一，基于Transformer编码器–解码器架构构建策略网络：编码器通过多层自注意力提取节点嵌入，解码器引入显式时间状态变量（到达时间、车速、剩余容量等）构造上下文向量，并通过掩码注意力计算节点选择概率。其二，提出显式时间状态更新机制（算法1），在每步决策后更新到达时间、容量等状态，处理早到等待与晚到惩罚。其三，设计混合约束处理策略：训练阶段仅使用带惩罚系数的软约束（REINFORCE算法配合滚动基线，算法2），推理阶段分别以软模式和硬掩码模式解码，保留混合成本更低的解。其四，实现贪心与采样两种解码策略，采样模式在每种约束模式下抽取1280个候选解。实验使用合成实例生成器，规模为20、50、100个客户节点，训练集每轮生成1,280,000个实例，验证集和测试集各10,000个实例。基线方法包括MVMoE、TPA-Reward两种DRL方法以及禁忌搜索（TS）、蜂群算法（BA）、OR-Tools三种元启发式方法。
四、实验结果
4.1 与基线方法的性能比较
在10,000个测试实例上，ETHC-VRC(G)在20、50、100节点上分别取得7.24、13.07、20.37的混合成本，显著低于TPA-Reward(G)的10.29、26.28、52.69，并在20和50节点上显著低于MVMoE(G)的7.29、13.12、20.38（100节点上无显著差异）。ETHC-VRC(S)将成本进一步降至6.97、12.43、19.42。在计算效率方面，ETHC-VRC(G)求解整个测试集分别耗时0.63秒、1.44秒、2.97秒，与DRL基线同数量级；采样模式每实例延迟为0.066秒、0.15秒、0.32秒。OR-Tools在10–120秒每实例的时间限制下取得最低混合成本，ETHC-VRC(S)高出其2.05%、3.61%、4.33%；在等时间比较中，ETHC-VRC(S)在20和50节点上分别低于OR-Tools 0.84%和3.95%。
4.2 惩罚缩放因子的敏感性分析
在惩罚缩放因子λp∈{1,2,4,8}范围内，ETHC-VRC的路径长度变化不超过1.05%，可行性率至少为99.99%，表明其解质量对惩罚系数依赖很小。OR-Tools几乎不敏感，MVMoE因硬掩码训练而不依赖λp，TPA-Reward(G)在100节点上变化最大（4.47%）。混合约束策略在推理阶段限制了部署解的迟到情况：硬掩码解无违规，逐实例选择在25个迟到实例中的23个上部署了硬掩码解。
4.3 泛化分析
在跨规模零样本泛化实验中，贪心解码在全部15种训练–测试组合上优于TPA-Reward(G)，在8种组合上优于MVMoE(G)；采样进一步降低混合成本。ETHC-VRC(S)在全部组合上优于TPA-Reward(S)，在5种组合上优于MVMoE(S)。例如，20节点模型测试100节点实例时，采样将成本从24.46降至23.18（降低5.2%），表明采样能补偿模型面对分布外规模时的不确定性。
4.4 消融与解分布分析
消融实验检验显式时间状态对解码器上下文输入的作用，以及硬掩码解码对最终解质量的贡献。结果显示，软约束单次贪心解码（7.28、13.15、20.43）已接近MVMoE(G)，第二次硬掩码解码进一步扩大领先优势。混合策略在推理阶段对每个实例保留两种模式下成本更低的解，保证部署成本不高于任一单独模式。
五、结论
ETHC-VRC通过显式时间状态表示将时间信息同时注入解码器上下文、混合成本和硬掩码，实现训练与推理阶段约束处理的解耦：单一策略在软约束下训练，可在硬掩码下直接解码而无需重新训练。混合约束策略在推理时结合两种解码模式并保留更优解，在安全关键场景中可单独部署硬掩码解以保证严格可行性。实验表明，该方法的贪心解码在20至100节点上以与DRL基线同数量级的延迟取得更低混合成本，采样模式在0.07–0.32秒每实例的延迟下达到OR-Tools运行10–120秒解质量的2.1–4.3%以内，并在等时间预算下优于OR-Tools。单一训练模型由此提供显式的质量–延迟权衡，适合对延迟敏感和对质量敏感的物流应用场景。
