一种统一的知识嵌入强化学习框架，用于广义容量车辆路径问题

# 一种基于知识嵌入强化学习的统一框架用于广义带容量车辆路径问题  
来源：https://arxiv.org/html/2605.14416  

向晨 Wu¹ 梁 Wang¹ 豪 Hu¹ 贤平 Tao¹  
¹南京大学 \{wangwen, ixc\}@smail\.nju\.edu\.cn, \{wl, myou, txp\}@nju\.edu\.cn  

###### 摘要  

带容量车辆路径问题 \(CVRP\) 是一个基础的 NP\-难问题，在物流和运输领域有广泛的应用。现实中的 CVRP 通常涉及多样化的目标和复杂的约束，例如时间窗或回程需求，这促使了统一解决方案框架的发展。近年来，强化学习 \(RL\) 方法在组合优化中显示出潜力，但它们依赖端到端学习，缺乏显式的求解知识，限制了求解质量。在本文中，我们提出了一种受“先定路线后分簇”启发式启发的知识嵌入框架。它从两个层面融入知识：\(1\) 将 CVRP 分解为“先定路线”和“后分簇”两个子问题，以及 \(2\) 利用动态规划求解第二个子问题，其结果指导基于 RL 的构造式求解器解决第一个问题。为了缓解由问题分解引起的部分可观测性问题，我们引入了一个统一的历史增强上下文处理模块。大量实验表明，该框架相较于最先进的基于学习的方法取得了更优的求解质量，并与经典启发式方法的差距更小，在多种 CVRP 变体上展现出强大的泛化能力。  

## 1 引言  

带容量车辆路径问题 \(CVRP\) 是组合优化中的一个基础研究课题，也是众多现实世界应用中的典型模型，包括城市物流 [Jeong and Song (2025) (https://arxiv.org/html/2605.14416#bib.bib8)]、最后一公里配送 [Tiwari and Sharma (2023) (https://arxiv.org/html/2605.14416#bib.bib9)]、邮政分发 [Sbai et al. (2022) (https://arxiv.org/html/2605.14416#bib.bib10)] 和交通规划 [Leng and Li (2021) (https://arxiv.org/html/2605.14416#bib.bib11)]，在这些场景中，货物需从中央仓库配送至一组地理分散的客户。在实际应用中，CVRP 实例常包含额外约束，以反映真实世界的运营需求。例如，时间窗约束 [Vidal et al. (2014) (https://arxiv.org/html/2605.14416#bib.bib12)] 要求客户必须在指定时间段内被服务；而开放路线约束 [Li et al. (2007) (https://arxiv.org/html/2605.14416#bib.bib40)] 允许车辆完成服务后无需返回仓库。鉴于该问题的 NP\-难性质 [Lenstra and Kan (1981) (https://arxiv.org/html/2605.14416#bib.bib13)] 以及这些变体带来的更高复杂度，开发一个统一且高效的近似求解器已成为一个重要的长期研究目标。  

随着基于学习方法在组合优化领域的发展，近期提出了一系列针对 VRP 的基础模型 [Berto et al. (2024) (https://arxiv.org/html/2605.14416#bib.bib41); Drakulic et al. (2025) (https://arxiv.org/html/2605.14416#bib.bib42); Zhou et al. (2024) (https://arxiv.org/html/2605.14416#bib.bib43)]。这些方法借鉴了大语言模型 \(LLMs\) 中的先进架构设计，引入多头混合注意力块、Transformer 编码器和混合专家 \(MoE\) 结构等组件，构建能够处理多种 VRP 变体的统一网络架构。从学习范式来看，这些模型通常采用 POMO 风格 [Kwon et al. (2020) (https://arxiv.org/html/2605.14416#bib.bib44)] 的强化学习或模仿学习范式来训练神经网络，以端到端方式直接生成高质量路径解。在此求解框架中，领域知识的融入体现在两个方面：\(1\) 由问题特定洞察指导的网络架构设计；\(2\) 由经典求解器生成的解样本。尽管已取得令人鼓舞的结果，但仅依赖模型或数据驱动的领域知识忽略了算法设计在解决经典问题中的重要性，从而限制了求解质量的进一步提升。  

为了直接在 CVRP 求解中利用领域知识，我们利用了问题的可分解性质。问题分解在 CVRP 研究中历史悠久，尤其是在进化计算领域 [Zhang et al. (2022) (https://arxiv.org/html/2605.14416#bib.bib14)]。在这些方法中，“先定路线后分簇” \(RFCS\) 启发式 [Prins et al. (2014) (https://arxiv.org/html/2605.14416#bib.bib46)] 是最具影响力的策略之一，并由此衍生出众多变体。具体来说，RFCS 启发式首先使用 TSP 求解器等启发式方法构建一条覆盖所有客户节点（不含仓库）的全局路径；然后采用多项式时间最优算法将全局路径分割成可行的车辆路线，从而生成原始 CVRP 变体的有效解。人工设计的算法可以自然地融入各种操作约束。更重要的是，一旦生成全局路径，后续过程通常以多项式时间运行，保证了高计算效率。例如，Vidal (2015) (https://arxiv.org/html/2605.14416#bib.bib45) 针对最小和 CVRP 给出了一个 \(O(n)\) 算法，Wang et al. (2025) (https://arxiv.org/html/2605.14416#bib.bib15) 为最小最大 VRP 提出了一个基于二分搜索的分割算法。然而，这类方法通常依赖基于 TSP 的启发式来构造全局路径，而最优 TSP 路线在经过“后分簇”操作后并不一定能得到原始 CVRP 变体的最优解。  

在本文中，我们引入强化学习来自动学习“先定路线”部分，从而避免了手工设计的 TSP 启发式的局限。然而，问题分解机制引入了一个部分可观测性挑战：在生成整条路线并完成后续分割阶段之前，无法完全评估部分路线的上下文。为了解决该问题，我们引入了一个历史增强模块作为上下文处理器的核心。该模块采用 LSTM [Hochreiter and Schmidhuber (1997) (https://arxiv.org/html/2605.14416#bib.bib3)] 架构来维护一个时间隐藏状态，在路线构建过程中持续聚合历史信息，从而使模型即使在最终评估信号被延迟时，也能推断问题的潜在信息。  

除了缓解部分可观测性外，历史增强的上下文表示还为不同的 VRP 变体提供了统一的神经架构。通过将不断演变的决策上下文编码为学习到的隐藏状态，该框架消除了对人工设计的问题特定上下文的需求。因此，相同的网络架构可以无缝地泛化到多种问题类型，例如开放路线、回程请求和时间窗 CVRP，而无需额外调整。  

主要贡献可总结如下：  

- • 我们提出了一个统一的**知识嵌入 RFCS 框架**，将强化学习与“先定路线后分簇” \(RFCS\) 启发式相结合，以处理广泛的 CVRP 变体。该框架结合了通用的基于学习方法与算法设计原则，能够灵活适应各种问题特定约束。  
- • 我们引入了一个**历史增强上下文处理模块**，在通用 CVRP 变体上保持统一的神经网络架构。该模块利用“先定路线”部分提供的共同表示来简化上下文特征的设计，从而有效处理复杂约束。  
- • 我们进行了大量实验，评估了该框架在不同 CVRP 设置下的求解质量和迁移能力。结果表明，所提出的知识嵌入 RFCS 框架始终优于现有的基于学习方法，并在未见过的问题变体上表现出强大的零样本泛化能力。  

## 2 相关工作  

自从 Pointer Network [Vinyals et al. (2015) (https://arxiv.org/html/2605.14416#bib.bib16)] 将神经网络引入组合优化以来，随后涌现出一系列基于学习的组合优化求解器，统称为神经组合优化 \(NCO\)。从求解范式来看，基于学习的方法大致可分为三类 [Wu et al. (2024) (https://arxiv.org/html/2605.14416#bib.bib17)]：\(1\) 学习构造 \(L2C\)，专注于直接生成解；\(2\) 学习改进 \(L2I\)，旨在精炼或增强现有解；以及 \(3\) 学习预测 \(L2P\)，利用神经网络支持和增强传统运筹学方法。  

在 L2C 范式中，Attention Model \(AM\) [Kool et al. (2018) (https://arxiv.org/html/2605.14416#bib.bib18)] 提出了基于 Transformer 的编码器-解码器架构来直接生成解。随后，POMO [Kwon et al. (2020) (https://arxiv.org/html/2605.14416#bib.bib44)] 和 Sym\-NCO [Kim et al. (2022a) (https://arxiv.org/html/2605.14416#bib.bib19)] 分别在解生成过程中引入了多起点和基于对称性的 [Shi et al. (2025) (https://arxiv.org/html/2605.14416#bib.bib1); Yu et al. (2024) (https://arxiv.org/html/2605.14416#bib.bib2)] 训练策略，进一步提升了求解质量。最近的研究主要集中在提升泛化能力 [Gao et al. (2024) (https://arxiv.org/html/2605.14416#bib.bib24)]、处理多样化的目标和约束 [Son et al. (2024) (https://arxiv.org/html/2605.14416#bib.bib20); Zheng et al. (2024) (https://arxiv.org/html/2605.14416#bib.bib21); Bi et al. (2024) (https://arxiv.org/html/2605.14416#bib.bib22)]，以及扩展到更大规模的实例 [Luo et al. (2023) (https://arxiv.org/html/2605.14416#bib.bib23); Kim et al. (2022b) (https://arxiv.org/html/2605.14416#bib.bib25)]。该范式在求解质量和推理效率之间取得了良好的平衡，本文也采用了这一范式。  

L2I 范式起源于学习局部重写操作 [Chen and Tian (2019) (https://arxiv.org/html/2605.14416#bib.bib26)]，后来扩展到学习 2-OPT 和交叉交换等启发式算子 [O Costa et al. (2020) (https://arxiv.org/html/2605.14416#bib.bib27); Hottung and Tierney (2020) (https://arxiv.org/html/2605.14416#bib.bib28); Sui et al. (2021) (https://arxiv.org/html/2605.14416#bib.bib29); Wu et al. (2021) (https://arxiv.org/html/2605.14416#bib.bib30)]。近年来，该方向的研究越来越关注大规模问题求解 [Cheng et al. (2023) (https://arxiv.org/html/2605.14416#bib.bib31); Li et al. (2025) (https://arxiv.org/html/2605.14416#bib.bib32)]。尽管该范式更适合处理大规模问题，但使用统一框架来处理多种类型的约束相对困难。  

L2P 范式将传统算法方法与基于学习的方法相结合，例如将学习与 LKH 算法结合 [Xin et al. (2021) (https://arxiv.org/html/2605.14416#bib.bib33); Zheng et al. (2021) (https://arxiv.org/html/2605.14416#bib.bib34)]，将学习与动态规划结合 [Kool et al. (2022) (https://arxiv.org/html/2605.14416#bib.bib35); Xu et al. (2020) (https://arxiv.org/html/2605.14416#bib.bib36)]，以及利用大语言模型 \(LLMs\) 和元学习进行自动算法设计 [Liu et al. (2024b) (https://arxiv.org/html/2605.14416#bib.bib37); Dernedde et al. (2025) (https://arxiv.org/html/2605.14416#bib.bib38)]。这类方法通过融入算法设计原则，有潜力提升求解质量。在本文中，我们在 L2C 框架内采用了类似的方法，将知识作为奖励信号引入，这有助于处理一般形式的约束。  

## 3 预备知识  

在本节中，我们首先介绍一般形式的 CVRP。然后，我们总结 CVRP 的强化学习公式，描述如何将解建模为序列化动作并在强化学习范式下进行优化。  

### 3.1 一般形式的 CVRP  

CVRP 可以定义在一个完全图 \(G=(V,E)\) 上，其中 \(V=\{v_0,v_1,\cdots,v_n\}\) 是节点集合，\(v_0\) 表示仓库，\(\{v_1,\cdots,v_n\}\) 表示客户节点。每条边 \((i,j)\in E\) 关联一个非负成本 \(c_{ij}\)。通常，每个节点被赋予二维坐标，以欧几里得距离作为成本。具有相同容量 \(Q\) 的车辆停在仓库。每个客户节点 \(i\in\{1,\cdots,n\}\) 具有一个非零需求 \(q_i\leq Q\)，必须由恰好一辆车来满足。每辆车从仓库出发，服务客户后返回仓库。所服务节点的总需求不得超过容量。  

我们效仿 [Berto et al. (2024) (https://arxiv.org/html/2605.14416#bib.bib41)]，考虑一个包含多个额外约束的广义 CVRP 公式：\(1\) 开放路线——车辆无需返回仓库；\(2\) 回程需求——客户请求可能同时涉及配送和取货操作；\(3\) 距离限制——每条路线的行驶距离不得超过预定义阈值；以及 \(4\) 时间窗——每个客户必须在指定时间区间内被服务。每个额外约束可独立激活或停用，从而产生十六种问题变体，分别记为 CVRP、OVRP、VRPB、VRPL、VRPTW 等。我们的目标是最小化所有车辆路线的总旅行成本。  

令 \(\{R_k\}_{k=1}^K\) 表示一个可行的路线方案，其中 \(R_k\) 是第 \(k\) 辆车服务的节点序列。路线 \(R_k\) 的成本为  

\[ C_k = \sum_{(i,j)\in R_k} c_{i,j}, \]  

其中 \(c_{i,j}\) 表示节点 \(i\) 和 \(j\) 之间的旅行成本。最小和目标则表述为  

\[ \min_{\{R_k\}_{k=1}^K} \; \sum_{k=1}^K C_k, \]  

并满足以下可行条件：1) 每个客户恰好被访问一次；2) 每条路线上的总需求不超过车辆容量；3) 所有额外约束均被满足。这里，\(K\) 表示解中使用的车辆数量。  

### 3.2 CVRP 的强化学习  

在 CVRP 的强化学习框架中，构造式求解器通过每次选择一个客户节点来逐步构建解。形式上，在步骤 \(t\)，求解器根据上下文 \(c_t\) 选择一个动作 \(a_t \in V_t\)，即接下来访问一个客户节点，依据随机策略  

\[ a_t \sim \pi_\theta(a_t \mid c_t), \]  

该策略由神经网络参数 \(\theta\) 参数化。在访问节点 \(a_t\) 后，状态更新为 \(c_{t+1}\)，可用动作集合也会变化。