Smart Routes：用于开发和比较解决现实约束下车辆路径问题算法的系统

# Smart Routes：一种开发与比较求解带现实约束车辆路径问题算法的系统
来源：https://arxiv.org/html/2608.14140
2024

###### 摘要

在全球城市人口增长的背景下，带现实约束的路径优化问题变得极其重要。虽然我们知晓理论上能提供精确最优解的求解方法，但随着问题规模增大，其应用因指数级复杂度而变得困难。本文研究带时间窗的容量约束车辆路径问题（CVRPTW），并比较通过精确求解器SCIP[1 (https://arxiv.org/html/2608.14140#bib.bib1)]与启发式算法（如LKH、2-OPT、3-OPT[2 (https://arxiv.org/html/2608.14140#bib.bib2)]、OR-Tools框架[3 (https://arxiv.org/html/2608.14140#bib.bib3)]以及深度学习模型JAMPR[4 (https://arxiv.org/html/2608.14140#bib.bib4)]）获得的解。我们证明，对于规模为50的问题，深度学习与经典启发式解法已接近SCIP精确解，但所需时间更少。此外，对于规模为100的问题，SCIP精确方法比神经与经典启发式方法慢约~13倍（在相同路径成本下），且在相同时间内求得的首个可行解质量差约~50%。为进行实验，我们开发了Smart Routes平台，用于解决路径优化问题，该平台集成了精确、启发式及深度学习模型，并便于自定义算法与数据集的便捷集成。

关键词：CVRPTW、车辆路径平台、启发式算法、精确解、强化学习

††作者：A. Soroka ([email protected])、G. Mikhelson ([email protected])（莫斯科国立大学，计算数学与控制论学院，莫斯科）、A. Mescheryakov ([email protected])（莫斯科国立大学，计算数学与控制论学院，莫斯科；俄罗斯科学院空间研究所，莫斯科）、S. Gerasimov ([email protected])（莫斯科国立大学，计算数学与控制论学院，莫斯科）

## 1引言

车辆路径问题（VRP）是一类运输物流问题，旨在为一组客户降低运输资源成本、路径开销与货物交付时间。在实际场景中，考虑各种约束优化路径是大多数公司面临的问题。随着城市与客户数量增加，有必要开发一种既能最优利用分配资源又能保持服务质量的解决方案。更短的路径能为客户实现更快交付，并腾出更多时间向其他客户配送货物。

在物流问题中，VRP常需考虑各种约束，其中最受关注的是客户时间窗与服务时间（TW）以及车辆容量（C）。目前，开发能够求解规模递增问题、并在施加约束数量下平衡解质量与搜索时间的算法面临重大挑战。此外，尚无统一平台允许用户不仅使用内置算法求解问题并进行实验，还能在不改变系统架构的情况下添加自有算法、数据读取与处理方法等。

本文贡献如下：

\{itemlist\}

一个用于路径问题优化的平台；
对常见路径优化方法有效性的比较。

我们的主要关注点在于开发名为Smart Routes的创新系统，以及对不同方法在约束问题背景下的深入比较分析。我们研究了启发式、深度强化网络与精确方法（SCIP），并考虑了在不同规模问题中讨论的限制。本研究最终得出关于这些解决方案效率与质量的宝贵信息，其主要通过两个核心指标评估：解的优化时间与由目标函数确定的最终路径成本。

本文揭示了我们为优化路径问题设计的Smart Routes系统的架构。该系统无缝集成了精确与启发式方法，以及深度强化网络方法论，旨在解决车辆路径问题（VRP）及其各种形式与变体。因此，它既适用于经验丰富的运输物流专家，也为该领域经验较少者提供了测试新想法的一站式平台。由此可见，本研究不仅深入探索了解决带时间窗车辆路径问题（CVRPTW）——VRP中具有流行且实用限制的子类——的最有效算法方法，还引入了一种能够全面高效解决该问题的创新工具。

文章结构如下：第2节综述了包含经典与深度强化路径优化方法的近期文献。第3节与第4节分别讨论所考虑的模型与开发的Smart Routes系统。第5节描述实验所用数据。第6节展示所得结果，第7节包含从研究中得出的结论。

failure\_rate=未解任务数任务总数×100%failure\\_rate=\\frac{未解任务数}{任务总数}\\times 100\\%

## 2相关工作

本节探讨三类能够解决该问题的算法。需注意的是，尽管该问题历史悠久，但比较解决路径优化问题不同方法的研究众多。大多数论文往往缺乏精确方法的比较，或仅考虑有限规模的问题，有时缺少约束。我们力求涵盖所有要求，以呈现经典方法适用性的完整图景。

### 2.1启发式算法

第一类算法被称为启发式算法，常用于此类问题。在此组内，可区分为两类：构造性启发式与元启发式。

构造性启发式是通过逐一添加组件迭代构建可行解的算法，例如最近邻启发式、插入启发式与扫描启发式。虽然它们不保证最优解，但能快速生成高质量解。

元启发式算法是更通用的优化方法，通过随机化与启发式探索解空间，例如模拟退火、遗传算法与蚁群优化。它们可能找到比构造性启发式更好的解，但通常需要更多计算资源。

这些算法的选择取决于具体任务及其应用。构造性启发式因其快速高效获取高质量解的特点在实践中常用。另一方面，元启发式方法更灵活，可应用于更广泛的优化问题，但计算成本更高。构造性启发式实现更快，可为特定问题提供有效解。

### 2.2精确算法

下一组包括精确算法，如线性规划算法。这些算法处理目标与约束函数为线性的问题。线性规划问题已被广泛研究，其解的性质广为人知。

线性规划问题（LP）是一个标准形式表示的优化问题如下：

maxcTx∣Ax≤b,x≥0\\max\\{c^{\\mathrm{T}}x\\mid Ax\\leq b,x\\geq 0\\}(1)
其中，A∈Rm,nA\\in R^{m,n}代表技术矩阵，b∈Rmb\\in R^{m}是资源向量，c∈Rnc\\in R^{n}是价格向量，x∈Rnx\\in R^{n}是未知向量。若向量x中部分或全部变量为整数，则问题称为混合整数线性规划（MILP）。

有多种算法可解决MILP问题：

1. 分支定界[5 (https://arxiv.org/html/2608.14140#bib.bib5)]是解决MILP问题的常用算法。它将问题分解为称为节点的子任务，并使用线性规划求解每个节点。该算法通过添加约束将节点分支为子节点，直至找到整数解或证明不可行。
2. 割平面法[6 (https://arxiv.org/html/2608.14140#bib.bib6)]通过迭代添加有效的线性不等式（称为割）来排除问题表述中的非整数解。割通过求解问题的线性规划松弛生成。算法持续进行直至找到整数解或证明不可行。
3. 分支切割法[7 (https://arxiv.org/html/2608.14140#bib.bib7)]是分支定界与割平面算法的结合。它生成割以消除非整数解，并将节点分支以创建子节点。该算法通常比单独使用分支定界或割平面更高效。

通常，算法选择取决于具体问题及对解质量与搜索时间的要求。一些MILP求解器，如CPLEX[8 (https://arxiv.org/html/2608.14140#bib.bib8)]、SCIP[1 (https://arxiv.org/html/2608.14140#bib.bib1)]与Gurobi[9 (https://arxiv.org/html/2608.14140#bib.bib9)]，实现了多种算法，并自动为给定问题实例选择最合适的一种。

线性规划问题的主要挑战在于其高维性，常涉及数千变量与约束。随着整数变量的增加，内存使用与求解时间可能呈指数增长。因此，开发了启发式方法以在更短时间内找到近似最优解。对于复杂问题，启发式方法常能在解质量与计算时间间提供最佳权衡。

### 2.3深度学习与强化学习算法

首个用于解决VRP的深度学习模型由Nazari等人[10 (https://arxiv.org/html/2608.14140#bib.bib10)]提出，他们改编了Vinyals等人[11 (https://arxiv.org/html/2608.14140#bib.bib11)]的指针网络（PtrNet）以处理CVRP。Nazari等人[10 (https://arxiv.org/html/2608.14140#bib.bib10)]完全摒弃了模型的原始RNN编码器部分，并用具有共享参数的线性层替代。Kool等人[12 (https://arxiv.org/html/2608.14140#bib.bib12)]提出的更近期算法AM（注意力模型）用改编的Transformer模型结合注意力机制[13 (https://arxiv.org/html/2608.14140#bib.bib13)]替换了此架构。Falkner等人[4 (https://arxiv.org/html/2608.14140#bib.bib4)]提出的JAMPR方法是对此模型的直接改进，作者为当前路径与卡车位置添加了额外的全连接网络。此添加使算法能成功解决CVRPTW问题。Chen与Tian[14 (https://arxiv.org/html/2608.14140#bib.bib14)]提出一种基于RL的方法，迭代选择图上区域，然后选择并应用已建立的局部启发式。此方法通过Lu等人[15 (https://arxiv.org/html/2608.14140#bib.bib15)]引入的破坏算子得到进一步增强。Li等人[16 (https://arxiv.org/html/2608.14140#bib.bib16)]提出了利用深度学习将点集划分为子问题并用黑盒求解器求解的最新尝试。作者提出两种方法：基于回归预测最终成本潜在改进的回归方法，以及用于选择最佳子问题的分类方法。通过降低维度并在每个子问题中使用经典元启发式方法，作者在高维问题（超过1000个点）上取得了良好结果。我们在最新文章[17 (https://arxiv.org/html/2608.14140#bib.bib17)]中提出并详细探讨了我们深度强化方法在解决带现实约束路径优化问题中的适用性，展示了如何利用学习到的神经启发式快速获得次优解。

## 3算法与模型

### 3.1经典方法

考虑经典启发式方法时，决定聚焦于称为局部搜索的一类算法。这些算法在现实问题中能平衡解质量与搜索效率，并作为元启发式与遗传算法的基本组件[18 (https://arxiv.org/html/2608.14140#bib.bib18)]。

被选为主启发式算法的经典启发式方法之一是林-克里根启发式[2 (https://arxiv.org/html/2608.14140#bib.bib2)]。该算法属于局部优化算法类别。它通过执行交换或移动（称为opt）将一条路径转换为另一条路径。从初始可行路径开始，算法递归执行可减少当前路径长度的交换，直至达到无法通过进一步交换改进的路径。此过程可从初始生成路径以随机方式多次重复。该算法假设存在初始路径划分，然后迭代改进现有近似。改进方法涉及在每个子路径内单独交换顶点。

SCIP[1 (https://arxiv.org/html/2608.14140#bib.bib1)]是一款开源软件，是专门设计用于解决混合整数规划问题的强大优化工具[19 (https://arxiv.org/html/2608.14140#bib.bib19),20 (https://arxiv.org/html/2608.14140#bib.bib20)]。它非常适合处理物流、规划与生产调度中遇到的复杂优化挑战。SCIP采用多种方法与算法，包括分支定界、割平面法、约束传播、启发式、分解方法与整数规划。这些技术涉及分解问题、添加约束、利用推理、应用经验法则以及求解整数规划问题以找到最优解。总之，SCIP是一款综合优化软件，利用多样化算法与方法有效且准确地解决复杂优化问题。

除SCIP外，我们还选择了OR-Tools（运筹学工具）[3 (https://arxiv.org/html/2608.14140#bib.bib3)]，这是一个在解决VRP（车辆路径问题）挑战方面广受好评的高效框架。OR-Tools是一款通用软件，旨在解决组合优化问题、方程与不等式求解以及调度与路径问题。它提供了多样化的优化方法与算法，包括线性规划（LP）方法、整数规划（IP）方法、离散优化方法以及方程与不等式求解方法。值得注意的是，OR-Tools在路径规划与调度方面表现出色，提供了解决各种路径问题的算法，如旅行商问题和车辆路径问题。这些方法涵盖了启发式与精确技术，如局部搜索与元启发式算法。凭借其