《Mathematics》：End-to-End Graph-Embedded Reinforcement Learning for Solving the Shortest Path Problem with Constraints
编辑推荐：
最短路径问题（SPP）带有约束时，是运筹学与物流中一个基础但计算上难以处理的NP-hard挑战。传统优化算法，包括精确方法和近似方法，在大规模实例上往往存在难以承受的计算时间和严重的可扩展性瓶颈。相比之下，新兴的神经组合优化（NCO）方法具有快速推理的潜力，但
最短路径问题（SPP）带有约束时，是运筹学与物流中一个基础但计算上难以处理的NP-hard挑战。传统优化算法，包括精确方法和近似方法，在大规模实例上往往存在难以承受的计算时间和严重的可扩展性瓶颈。相比之下，新兴的神经组合优化（NCO）方法具有快速推理的潜力，但在严格约束下常无法保证结构可行性。为弥合这一差距，本研究提出E2E_GERL，一种用于带时间约束SPP的新型端到端图嵌入强化学习算法。该问题被重构为结构感知与资源感知的顺序决策过程，其中引入神经图嵌入网络structure2vec来捕捉关键图节点的长期结构等价性。在该框架中，研究人员引入基于ReLU的拉格朗日惩罚，将时间约束违反嵌入学习目标，并采用n步Q学习有效克服路径级延迟后果。在合成图、修改后的基准实例以及真实物流网络上的大量实验证明了所提出算法E2E_GERL的优越性。与经典基线和NCO基线相比，它以显著更低的推理时间取得更好结果，这也验证了将NCO集成到约束优化问题算法中的潜力。
该论文发表于《Mathematics》，围绕带时间约束的最短路径问题（Shortest Path Problem, SPP）展开研究。该问题在运输、物流、通信网络和供应链决策中广泛存在，但属于NP-hard问题。传统精确算法和近似算法在大规模实例上存在计算时间过长与可扩展性瓶颈；现有端到端神经组合优化（NCO）方法多针对旅行商问题（TSP）和车辆路径问题（VRP），难以直接处理SPP的图结构与资源约束。为此，研究人员提出E2E_GERL，一种端到端图嵌入强化学习算法，将约束路径构建建模为结构感知与资源感知的马尔可夫决策过程（MDP），并证明其在解质量、可行性和推理效率上均优于多种基线，为NCO方法用于约束优化问题提供了有效路径。
研究人员使用的主要关键技术包括：采用structure2vec图嵌入网络，根据当前节点、目标节点、已访问节点、累计成本与累计时间等动态特征迭代更新节点表示；提出基于ReLU的拉格朗日惩罚，将时间约束违反量[T(P)?T
max]
+嵌入学习目标；采用n步Q学习以γ=1的有限时域回报训练动作价值函数，并结合经验回放与拟合Q迭代；通过可行性动作掩码保证路径连通且无环。实验数据来源包括Erd?s-Rényi（ER）合成图、修改后的Gehring and Homberger基准，以及一家中国物流公司构成的1558节点、3253边真实物流网络。
研究结果如下：
5.1 数据集与实例生成：研究人员使用ER模型生成不同规模合成图，并改造Gehring and Homberger基准，得到涵盖7至800节点的测试集，以弥补现有基准不适用的问题。
5.2 约束生成：通过未约束最小成本路径和最小时间路径构造时间预算，保证可行集非空且排除未约束最优解；实验表明约束紧度δ取0.6时解质量与可行性最佳。
5.3 评估指标：采用可行性率、最优性间隙和相对于CPLEX当前最优可行解的相对百分比偏差（RPD）作为指标；只有满足结构要求与时间约束的路径才被视为可行解。
5.4 超参数调参与泛化分析：研究人员采用预训练策略，先用小图训练模型再迁移到大图；自适应拉格朗日系数λ比固定大常数更稳定且收敛更快；模型可在不同规模图间迁移，但跨尺度过大时需微调。
5.5 E2E_GERL的收敛性：不同规模实例的训练曲线显示算法能够快速稳定收敛，适合处理不同规模的问题。
5.6 基线与约束适配：对比方法包括CPLEX、资源约束双向标签设置算法（RC-BD）、蚁群优化（ACO）、增强学习型改进算法（L2I）、注意力模型（AM）和图注意力网络（GAT）；所有NCO基线均在相同状态、奖励和掩码设置下重新训练。
5.7 性能比较：在合成数据集和修改后的Gehring and Homberger基准上，E2E_GERL在解质量、可行性和计算时间上均优于所有基线，且规模越大优势越明显；部分算法能在3600秒内找到低于CPLEX当前最优可行解成本的解，但不能视为优于未知全局最优。
5.8 消融研究：去掉structure2vec、去掉ReLU-拉格朗日惩罚、或将n步Q学习改为1步Q学习，均导致最优性间隙、相对偏差或可行性率下降，验证了这三个组件对算法性能的共同贡献。
5.9 效率分析：structure2vec前向计算占推理时间的60%至84%，是该算法的主要计算成本；通过缓存边嵌入、批处理Q网络前向以及自适应λ加速，使计算成本近似随图规模线性增长。
5.10 真实世界实例实验：在1558节点物流网络上，E2E_GERL在较短计算时间内取得优于CPLEX、RC-BD和ACO的解质量；多个源-目的（O-D）对实验中，训练O-D对与留出O-D对的表现差异较小，说明模型学到了可迁移的图结构模式。
讨论与结论部分指出，现有框架主要在单资源约束的确定性图上验证；状态依赖图嵌入的重计算是主要瓶颈，但剖析实验表明其在所测试的图规模和稀疏程度下仍可扩展。未来工作将扩展至更复杂约束的SPP、约束定向越野、资源约束路径问题，并探索将E2E_GERL作为大规模精确分解框架中的快速启发式或热启动机制。研究结论为：E2E_GERL通过将structure2vec图嵌入与n步拟合Q迭代相结合，同时利用可行性动作掩码和ReLU-拉格朗日惩罚，能够在小规模实例上匹配精确算法的最优性，并在大规模实例上以更快速度获得更优可行解，显著优于多种经典与NCO基线。
