《Transportation Research Record》：Pointer Amplifier for Vehicle Routing Problem: Solving Time-Constrained Vehicle Routing Problems with Finite Fleet Using End-to-End Neural Combinatorial Optimization
编辑推荐：
车辆路径问题（vehicle routing problem, VRP）的快速最优解是实现高效货物运输、无缝物流和可持续出行的先决条件。这需要能在极短计算时间内快速生成准确解的算法。传统优化方法难以应对涉及各种约束和不同目标的VRP在现实世界中的复杂性。近期，
车辆路径问题（vehicle routing problem, VRP）的快速最优解是实现高效货物运输、无缝物流和可持续出行的先决条件。这需要能在极短计算时间内快速生成准确解的算法。传统优化方法难以应对涉及各种约束和不同目标的VRP在现实世界中的复杂性。近期，神经组合优化（neural combinatorial optimization, NCO）的进展——利用生成式人工智能求解组合问题——已展现出成熟成果和良好前景。研究人员提出一种针对有限车队、时间约束的容量受限VRP（capacitated VRP, CVRP）的NCO求解方法。该方法动态地整合客户约束，使其灵活适用于各种运输物流场景。本文引入的指针放大器（pointer amplifier, PAMP）机制通过在指针网络中直接重缩放注意力分数，在路线生成过程中优先处理紧急服务。针对容量约束，研究人员采用带掩码的奖励函数惩罚机制来排除不可行动作。该架构采用遵循多最优点策略优化（Policy Optimization with Multiple Optima, POMO）协议的编码器-解码器结构，并通过近端策略优化（Proximal Policy Optimization, PPO）算法进行训练。所提出的框架已在中型和大型实例上成功训练和验证，与最先进的启发式方法相比，提供了具有竞争力的成本效益解，同时展现出鲁棒性和泛化能力。最后，研究人员对NCO生成的解进行了批判性分析，并探讨了这一深度学习算法新分支所面临的挑战与机遇。
车辆路径问题（vehicle routing problem, VRP）是交通运输与优化科学中最经典、最受关注的组合优化问题之一。实际业务中的VRP通常包含大量现实约束，例如需要在即时派送与后续装载整合之间权衡，需要平衡成本最小化和车队利用效率，还需要面对车辆数量有限、客户交付时间窗（time windows, TW）制约等情况。传统优化方法在处理这种多约束、多目标的复杂场景时，往往难以在可接受的计算时间内给出同时满足可行性和最优性的解，因此发展能快速生成考虑上下文并应对不确定性的实时规划算法是运输领域的迫切需求。近年来，结合强化学习（reinforcement learning, RL）与生成式人工智能的神经组合优化（neural combinatorial optimization, NCO）范式为顺序决策优化开创了新方向。本研究面向有限同质车队、带硬时间约束的容量受限车辆路径问题（capacitated VRP, CVRP），其目标是在不违反TW和车队数量的前提下服务客户需求并最小化总行驶里程，同时最大化车辆利用率，属于典型的多目标NP-hard组合优化问题。
针对上述问题，研究人员扩展了面向运筹学的强化学习框架Reinforcement Learning for Operations Research（RLOR），该框架整合了OpenAI Gym环境、多最优点策略优化（Policy Optimization with Multiple Optima, POMO）与近端策略优化（Proximal Policy Optimization, PPO）算法。研究人员设计了带容量惩罚因子的奖励函数，并提出了指针网络放大器（pointer network amplifier, PAMP）机制：在解码器的指针网络中对各候选节点注意力分数进行动态重缩放，使时间紧迫的客户被优先服务。通过敏感性分析，惩罚因子被校准为P=10，以获得总里程与车队利用率之间的最佳折衷。经过训练和验证，该模型在中型和大型实例上表现优于或接近最先进的启发式方法，推理时间大幅缩短，对未见过的数据分布也展现出良好的泛化能力。这项工作的意义在于，NCO方法可在极短推理时间内生成可行且较优的路线，并可直接将TW等动态约束纳入解码阶段，为构建混合优化系统提供了一种灵活、可扩展的实现路径。
**主要技术方法**
