带时间窗与容量约束的取货配送路径问题深度强化学习解决方案

arXiv cs.LG 论文
deep-reinforcement-learning vehicle-routing pickup-and-delivery time-window capacity-constraints combinatorial-optimization

摘要

本文提出了一种改进的JAMPR深度强化学习模型，用于求解带容量与时间窗约束的取货配送问题（CPDPTW）。该模型可为中小规模实例提供快速最优解，并为大规模实例提供次优解。

arXiv:2608.14156v1 公告类型：新论文 摘要：在全球城市人口增长背景下，构建车辆最优取货配送路径是最具前景的任务之一。虽然小规模问题可通过多种经典方法求解，但在真实约束（如容量和时间窗限制）下，为中大规模问题设计快速（或实时）路径优化器仍极具挑战性。本文首次成功将深度强化学习方法（改进的JAMPR模型）应用于求解带容量与时间窗约束的取货配送问题（CPDPTW），构建的模型能为中小规模问题提供快速最优解，并为大规模（>200）问题提供快速次优解。
查看原文
查看缓存全文

缓存时间: 2026/08/17 10:21 

# 面向带时间窗和容量约束的取货配送路径问题的深度强化学习解决方案
来源：https://arxiv.org/html/2608.14156
Andrew SorokaAffiliation: 莫斯科国立大学，莫斯科，俄罗斯联邦E\-mail[andrew\.soroka@student\.msu\.ru](mailto:[email protected]) Alex Meshcheryakov Sergey GerasimovAffiliation: 莫斯科国立大学，莫斯科，俄罗斯联邦E\-mail[gerasimov@cs\.msu\.ru](mailto:[email protected])

###### 摘要

在全球城市人口增长的背景下，构建车辆货物取货配送的最优路径是极具前景的研究任务之一。尽管小规模问题可通过多种经典方法求解，但在真实世界约束下（如容量和时间窗限制）为中大型问题提供快速（或实时）路径优化器，仍是一项高度挑战性的工作。本研究首次成功应用深度强化学习方法（改进的JAMPR模型）解决了带容量与时间窗约束的取货配送问题（CPDPTW）。我们获得了鲁棒的模型，能为中小型规模问题快速给出最优解，为更大规模（\>200）问题快速提供次优解。

###### 关键词：

车辆路径问题 深度学习 强化学习

## 1引言

车辆路径问题（VRP）是组合优化与整数规划问题\[21\]。它解答了“为一组出行车辆设计配送给定客户的最优路径集合”这一问题。VRP概括了著名的旅行商问题（TSP）\[13\]，两者均为NP难问题。

现实中，满足实际业务需求产生了许多额外限制。例如，客户并非总是只接收货物，有时希望将货物交还仓库或配送给其他客户——这就出现了取货配送（PDP）约束。客户货物体积实际上非零，且存在车辆最大容量限制需要处理。客户在特定时段的可用性则增加了另一类需关注的现实约束——时间窗。所有这些约束综合形成了带容量与时间窗约束的取货配送问题（CPDPTW）。

CPDPTW问题具有广泛的实践应用：快递配送、出租车运营、仓库与销售点间的货物物流。已有工具可为无约束、有限规模的经典问题提供次优解（例如Google OR-Tools\[14\]、启发式算法\[1,3\]、深度神经网络\[11\]）。但至今仍未有方案能同时处理大规模路径问题与所有重要的现实约束。

现有方法的一个著名难题是难以处理新的现实约束。例如，HGS启发式算法\[19,18\]仅支持求解经典CVRP问题。另一方面，另一种流行启发式算法OR-Tools\[14\]虽支持多种现实约束，但即使对小规模问题也常无法给出可行解（参见\[6\]中的表1）。尽管强大的启发式求解器（如LKH-3\[8\]或HGS\[19,18\]）最终能为超大规模（\>\>1000）问题找到良好解，但其成功启发式的构建需大量人工操作，且冗长的迭代计算导致巨大计算负载——结果表现为模型灵活性不足。例如，LKH-3求解2000节点的CVRP实例耗时超一小时，不适用于大型快递或市政服务等应用\[7\]。

本研究的动机在于创建一个快速神经求解器，能够处理具有现实内在限制（时间窗、有限车辆容量、多仓库）的高维问题。为解决此问题，我们考虑强化学习算法，因为VRP优化问题的求解策略可通过神经网络精确参数化。本文旨在探索基于JAMPR模型的强化学习算法在求解CPDPTW问题中的适用性，并与OR-Tools启发式算法提供的基线解进行比较。

## 2相关工作

### 2\.1经典方法

路径问题有两种经典求解方法：混合整数规划（MIP）和启发式算法。MIP是一类数学规划问题，其问题域通过实数和/或整数变量的不等式指定。一个重要的特例是混合整数线性规划，它将问题进一步限制为线性不等式和线性目标函数\[21\]。MIP中用于求解路径问题的两种主要算法是割平面法\[4\]和分支定界算法\[9\]。尽管MIP解具有精确性，但即使对小规模问题，整数规划生成解也需耗时过长。

启发式算法最常用于此类问题，大致可分为构造启发式和元启发式。构造启发式是能构建VRP问题可行解的过程，通常以输入数据规模的多项式时间运行，但不保证解质量。最知名的设计启发式是最近邻算法，它从仓库出发逐步构建车辆路径，每步选择最近的可用位置\[3\]。虽然设计启发式通常能保证快速满足约束的解，但不保证最优性。因此最先进的启发式会采用搜索过程。

元启发式是重复使用简单规则或更简单启发式构建最优路径的过程。元启发式最简单且最普遍的例子是局部搜索——一类搜索过程具有以下共同特征：

1. 以单个可行解（通常由某种构造启发式生成）开始搜索
2. 每次迭代为现有解创建邻域——一组有效解，通常呈多项式规模且由与当前解“相似”的解组成
3. 根据某规则（可以是确定性规则——若更优则接受；或随机性规则——若更优则接受，否则以某概率接受）从当前解的邻域中选择一个解并接受（提升至当前解）\[1\]。

这还包括局部搜索、遗传算法和蚁群方法。例如，移动、交换和2-opt是旅行商问题和车辆路径问题中著名的启发式算法。最常见的LKH-3 VRP求解器以Lin-Kernighan启发式（通过替换子路径对创建新路径）为基础，而HGS CVRP求解器则使用混合遗传算法和局部搜索过程，对规模达1000的问题取得有竞争力的结果。另一种常用于实际应用的额外方法是Google OR-Tools的开源解决方案\[14\]。该算法的概念是从一个初始可行解开始，使用较简单的启发式（如最便宜弧PCA启发式）生成。随后通过应用一组变更语句对当前解进行迭代改进\[1\]。对于路径和车辆调度问题，最合适的改进算子类别是所谓的边交换算法。OR-Tools中用于VRP和PDP最常见的改进算子包括Two-opt\[8\]、OR-opt\[12\]、Relocate、Exchange和Cross\[15\]。我们使用Google OR-Tools作为研究的基线，因其是实际任务中使用的主要工具。

### 2\.2深度学习和强化学习算法

Nazari等人\[11\]提出了首个用于序贯VRP求解的深度学习模型，他们将Vinyals等人的指针网络（PtrNet）\[20\]适配于处理CVRP。Nazari等人\[11\]完全舍弃了RNN编码器模型的原始部分，替换为具有共享参数的线性嵌入层。Kool等人的更新Attention Model（AM）算法\[6\]用采用自注意力机制\[17\]的适配Transformer模型替换了该架构。Falkner等人提出的JAMPR方法\[5\]是对该模型的直接改进，作者为当前路径和卡车位置添加了额外的线性嵌入网络。该附加组件使算法成功解决了CVRP-TW问题。Chen和Tian\[2\]提出基于强化学习的改进方法，迭代选择图上的区域，然后选择并应用既定的局部启发式。Lu等人引入的破坏算子\[10\]进一步改进了该方法。Li等人\[7\]提出了利用深度学习将点集划分为子问题，并用黑盒求解器求解的最新尝试。作者提出两种监督学习方法：对最终成本可能改进的回归预测，以及对最佳子任务的分类。通过降维并使用经典元启发式处理每个子问题，作者在高维（超过1000个点）问题上取得了良好结果。据我们所知，目前尚无针对高维CPDPTW问题的深度学习方法研究，因此本工作可能作为解决现实路径问题的基线而具有价值。

## 3模型

我们使用JAMPR\[5\]模型作为主要算法。原始JAMPR模型是Kool等人的Attention Model（AM）\[6\]的改进，采用基于自注意力机制\[17\]的编码器-解码器架构。两种模型都将路径优化问题视为序贯决策问题，建模为马尔可夫决策过程并使用强化学习求解。问题解通过逐节点构建路径逐片段生成。当前决策、路径和未访问节点被解释为状态，而可添加到当前路径的所有未访问节点索引被解释为动作。

首先，编码器接收每个节点i的节点特征x\_i（坐标、需求、时间窗等），并将其编码为维度为d\_emb的隐藏嵌入向量\tilde{x}\_i\in R^{d\_{emb}}。然后解码器模型在解码步t时，针对特定上下文C^{(t)}计算每个\tilde{x}\_i的注意力查询，以获得所有可添加至当前路径的节点估计值。此处上下文包括问题图的隐式嵌入及问题的额外信息，如仓库节点索引、添加到当前路径的最后一个节点、剩余容量等。所得分数随后用于贪婪选择过程（即总是选择得分最高的节点），或通过softmax转换为分布用于采样。总体上，编码器-解码器模型是具有可训练参数\theta的策略\pi(i^{(t+1)}|C^{(t)},x;\theta)。可在图1中查看原论文\[5\]作者的架构可视化。

图1：JAMPR架构原始图像。来源：\[5\]中的图1
JAMPR\[5\]扩展了主要为TSP和CVRP设计的标准AM\[6\]，为路径和车辆添加了额外编码器以丰富VRPTW求解的上下文。为此，JAMPR为每条构建的路径r\in R创建隐藏嵌入，通过将节点嵌入\tilde{x}\_i, i\in r和车辆特征\phi\_r（剩余容量、当前节点、当前时间等）引入额外的全连接神经网络，聚合输出并与上下文结合。由于这种方式创建的扩展上下文是状态的更完整表示，它允许多条路径并行构建，这对于成功解决VRPTW等高约束问题已被证明是必要的。这种同时规划的路径数量由常数\kappa固定。这导致了新的扩展动作空间：当前活跃路径R\_\kappa^{(t)}和可用节点A=\{(r,i)\in feasible(R\_\kappa^{(t)}\times N)\}，其中N为客户数量，feasible()是仅选择那些可添加到路径而不违反任何约束的节点的函数。

我们修改了feasible()函数以支持PDP约束。我们添加了额外掩码，根据指定的配送顺序限制每辆卡车可用的客户，类似于时间窗和已访问客户的掩码。在现实场景中，访问所有客户可能不可行，但放弃解决方案（即使是部分方案）并不实际。我们决定不考虑问题的HARD设定（当至少一个客户被遗漏时即无解）。为支持SOFT设定，路径的最终成本被修改：在训练和推理过程中，最终结果均为行驶距离与遗漏客户数量的线性组合，系数分别为13和10。这些值通过经验选择确定。

## 4数据

针对CPDPTW，我们基于R201统计量（Solomon的著名...

相似文章