具有方向感知的深度策略学习方法，用于高效的有容量限制的弧线路由

《Engineering Applications of Artificial Intelligence》：Direction-aware deep policy learning for efficient capacitated arc routing

　　冯雪|郭润泽|明安龙|Nicu Sebe
北京邮电大学，中国北京

摘要
多车辆在城市规模路线上的线路覆盖问题可以表述为容量限制弧路由问题（CARP）。早期的解决方案包括基于构建的启发式算法、元启发式算法和精确算法，但它们难以实现高效的运行时间。最近，基于神经网络（NN）的方法作为高效解决CARP的有希望的替代方案出现；然而，它们的解决质量明显低于非NN方法。这一显著差距主要由非欧几里得图、遍历方向和容量约束的不当建模和学习引起。在本文中，我们引入了一种针对这些复杂性的基于NN的求解器，它在显著缩小与先进元启发式算法的差距的同时，实现了更短的运行时间。首先，我们提出了方向感知注意力模型（DaAM），将方向性纳入嵌入过程，从而促进更有效的一阶段决策。其次，我们设计了一种监督强化学习方案，该方案包括监督预训练，以建立用于后续强化 fine-tuning 的稳健初始策略。这对于解决比节点路由问题（NRPs）更复杂的CARP特别有价值。最后，引入了一种路径优化方法来调整DaAM生成的路径中的仓库返回位置。实验表明，DaAM超越了基于构建的启发式算法，并首次实现了与最先进元启发式算法相当的分类决策质量，同时保持了更高的效率。代码和数据集将在链接中提供，并将在GitHub上发布。

引言
随着智慧城市基础设施的发展以及感知（Fan等人，2022年；Chang等人，2022年；冯雪等人，2024年；Xue等人，2025年）和控制技术（Lin等人，2025年；Debarshi等人，2022年；Berahman等人，2025年）在自动驾驶汽车中的突破，由移动机器人和自动驾驶车辆组成的车辆群（Huo等人，2025年；冯晓等人，2024年；傅等人，2025年）的部署已成为一个可预见的趋势。这些协作车辆负责大规模操作，如路面检查、环境感知、垃圾收集和应急物流。它们在有限的能量和负载约束下导航密集的城市道路网络。因此，它们的路线规划的质量和效率直接影响服务和运营成本。

理论上，城市道路网络可以建模为一个连通的无向图G=(V,E,ER)，其中V是节点集，E是街道（边）集，ER?E包括可用的街道（必需的边）。当几辆车辆从一个共同的仓库depart时（仓库∈V），并且每辆车都受到负载或电池容量的限制（表示为Q），该任务就是容量限制弧路由问题（CARP）。CARP要求访问所有必需边ER的序列，同时最小化所有车辆的总旅行成本，并满足每辆车的容量约束。与原始的弧路由问题（ARP）不同，CARP将边的排序与边的分配相结合给车辆，导致组合爆炸问题（Golden和Wong，1981年）。这种耦合是更复杂变体（如定向、多仓库和时窗CARP等）的关键瓶颈。因此，CARP成为基于学习的路由研究的门户问题，并具有重要的科学和实践价值。

根据Golden和Wong（1981年）的说法，CARP是NP难问题的。多年来，已经开发了多种元启发式算法，包括禁忌搜索（Hertz等人，2000年）、基于量子的算法（Shang等人，2018年）、遗传算法（Krasnogor和Smith，2005年；Tang等人，2009年；Li等人，2021年）（MA）等，以获得接近最优解。具有扩展邻域搜索的遗传算法（MAENS）（Tang等人，2009年）（一种为CARP量身定制的MA）被认为是最先进的，并且仍然是评估新方法的基准（Li和Li，2019年）。然而，由于问题规模增加导致搜索空间的指数级增长，这些方法面临较高的时间成本。另一种可行的选择是基于构建的启发式算法，例如经典的路径扫描家族（Golden和Wong，1981年；Santos等人，2009年）及其现代变体（Arakaki和Usberti，2019年）。通过依赖贪婪规则，它们可以将计算时间保持在几秒内，适用于实际场景，但它们的解决方案始终不如先进的元启发式算法。与传统方法相比，基于NN的求解器（Li和Li，2019年；Hong和Liu，2022年；Ramamoorthy和Syrotiuk，2024年），如图1(b)和(c)所示，在GPU的帮助下更快，因此在近年来受到了越来越多的关注。然而，与在欧几里得图中定义的组合问题（如车辆路由问题（VRP）和旅行商问题（TSP），或郵递員問題（RPP）和中文郵递員問題（CPP）中的良好性能不同，基于NN的方法在解决CARP时通常远远落后于传统方法，即使性能差距为10%–30%（Hong和Liu，2022年；Li和Li，2019年）。这种差异归因于现有方法无法有效降低解决CARP的高复杂性：
- **低效的多阶段决策**。在CARP中，边方向、转移成本和容量紧密耦合。然而，现有的基于NN的方法（Li和Li，2019年；Hong和Liu，2022年；Ramamoorthy和Syrotiuk，2024年）将决策过程分为两步：首先选择无向边，然后选择方向，这存在三个问题。① 第一步无法精确测量转移成本，导致决策质量差；② 在第二步中，过多的方向候选项会减慢计算速度；③ 错误的方向可能会违反容量约束，使强化学习（RL）的反馈较弱。
- **学习难度**：在强化学习过程中，由于容量约束，许多候选动作不可用，导致奖励信号极其稀疏。这会产生高方差的策略梯度估计，进一步使得收敛缓慢且不稳定。

在本文中，我们旨在解决上述两个问题，并提出一种基于NN的CARP方法，其运行时间显著低于最先进的MA（Tang等人，2009年），如图1(a)所示。首先，我们提出了方向感知注意力模型（DaAM）。该模型将方向选择、边选择、剩余容量等编码为一个简单高效的单阶段决策过程，这与CARP的固有属性相一致。通过这种设计，DaAM具有更少的决策步骤，并使用完整的状态信息进行决策，从而使CARP解决更加高效。其次，我们开发了一种监督强化学习方法来克服CARP的学习难度。它首先模仿元启发式专家策略来建立基线，然后使用近端策略优化在大规模CARP实例上进行微调。这种两阶段训练实现了快速学习CARP。最后，我们观察到当前的基于NN的CARP求解器通常难以确定具有最佳成本的返回位置。为了进一步优化返回位置，我们采用了一种与大多数CARP求解器兼容的后处理路径优化器（PO），进一步提高了路径质量。在实验中，我们的方法与最先进的MA的平均差距为5%，比最新的基于构建的启发式算法好4%，并且效率更高。我们的贡献如下：
1. 据我们所知，提出的DaAM是第一个将CARP框架为单阶段决策任务的神经模型，解决了多阶段决策框架中普遍存在的低效性和学习难度问题。
2. 我们使用带有明确方向选择的弧令牌对CARP进行建模，并为解码器配备了动态可行性约束（容量和反向弧互斥掩码），使DaAM能够高效可靠地生成具有方向感知的巨型弧游历。
3. 广泛的实验表明，DaAM在解决方案质量上接近元启发式算法，同时其推理速度比先进的基于构建的启发式算法更快，为许多扩展的CARP问题建立了强有力的基线。

**部分摘录**
**图嵌入学习**
图嵌入旨在将图中的节点或边映射到低维向量空间。这一过程通常通过图神经网络（GNNs）（Wu等人，2020年）实现。Kipf和Welling（2017年）引入了图卷积操作，从相邻节点聚合信息以更新节点表示。与GCN不同，图注意力网络（GAT）（Veli?kovi?等人，2018年）允许在信息传播过程中通过注意力机制进行动态节点关注。其他GNN变体...

**背景**
注意力模型（AM）（Kool等人，2019年）在解决经典欧几里得COPs时表现出更好的有效性，因为它使用注意力机制提取输入之间的相关性。因此，我们使用AM作为骨干，并简要回顾了其在TSP中的应用。给定一个欧几里得图G=(V,E)，AM定义了一个随机策略，表示为π(x|S)，其中x=(x0,…,x|V|?1)表示V中节点索引的排列，S是表示G的问题实例。

**方向感知注意力模型**
鉴于第1节中CARP的表述，我们提出了方向感知注意力模型（DaAM），用于高效的单阶段CARP决策。在第4.1节中，我们描述了DaAM的结构。在第4.2节中，我们给出了DaAM的训练方案。最后，在第4.3节中，引入了路径优化这一可选的后处理单元，以进一步提高CARP的解决方案质量。

**北京-CARP基准**
据我们所知，缺乏具有独立训练和测试分割的公共CARP数据集，这阻碍了对深度学习方法的评估。因此，我们构建了一个北京-CARP基准，用于深度学习方法。我们从OpenStreetMap（Haklay和Weber，2008年）获取的中国北京的路线图中提取子图，以生成用于训练和测试的CARP实例。所有实例被划分为七个数据集，每个数据集代表不同的问题规模。

**结论和局限性**
在本文中，我们提出了一种基于学习的CARP求解器，其性能可与最先进的元启发式算法相媲美。首先，我们将边的潜在服务方向编码为嵌入，确保在决策中考虑了边的方向性。其次，我们提出了一种监督强化学习方法，有效地学习了解决CARP的策略。凭借这些贡献，DaAM优于我们测试的基于PS的构建启发式算法（PS及其几种广泛使用的变体）。

**CRediT作者署名声明**
冯雪：撰写——原始草稿、软件、形式分析、数据 curation、概念化。
郭润泽：撰写——原始草稿、验证、软件、资源、数据 curation。
明安龙：撰写——审阅与编辑、监督、项目管理、资金获取、概念化。
Nicu Sebe：监督、概念化。

**利益冲突声明**
作者声明他们没有已知的竞争性财务利益或个人关系可能影响本文报告的工作。

**致谢**
本工作得到了中国创意研究组基金（项目编号61921003）的支持。