基于求解器的路径规划算法实现及性能分析

Part1引言

社会智能化的发展趋势和日益多元化的实际需求，奠定了物流运输行业对于实现智能规划的需求，车辆路径规划问题是其中的重点研究对象。

车辆路径规划问题(Vehicle Routing Problem,VRP)是在现实需求和车辆信息的基础上合理规划运输路线的优化问题。通过智能算法实现运输资源的合理规划，能够达到人力物力财力大幅节约的效果。

车辆路径规划问题的应用场景随着物流运输行业的发展日益丰富化，服务场景及其规模的多样性为车辆路径规划问题的求解增加了难度，信息的高速更迭以及对效率的追求也对其提出了高速求解的新要求。但是针对性的算法设计不仅难度很高，而且难以跟上应用场景和需求信息的变化速度。

VRP求解器应运而生，它能直接调用其中构造好的算法对多种多样的模型进行求解，为路径规划问题提供了便捷的求解方式。

因此研究求解器、学习掌握求解器算法、对实际场景中不同求解器的性能表现进行评估和对比并了解不同VRP求解器对于不同场景的适应性，求解器介绍能够为解决实际问题时求解器的选择提供决策支持，有利于获得更好的求解结果。

本文将以Jsprit、OR-Tools和CPLEX三种求解器为例，围绕旅行商问题(TSP)、带容量限制的路径规划问题(CVRP)、带时间窗限制的路径规划问题(VRPTW)和带时间窗的取送货路径规划问题(PDPTW)四种经典VRP模型展开，对比三种求解器的基本特性以及在不同问题中的性能表现。

Part2求解器介绍

Jsprit

Jsprit是Github上的一个开源项目（点击跳转至项目官网），基于Java语言开发，且仅支持Java语言。

它由Stefan Schröder所创建并由GraphHopper主持，由jsprit-core、jsprit-analysis、jsprit-io、jsprit-instances以及jsprit-example这5个部分组成。

• jsprit-core（核心）:构建问题、核心算法、分析解决方案、报告问题信息；
• jsprit-analysis:将求解结果进行可视化的工具箱；
• jsprit-io:记录和输出求解等过程；
• jsprit-instances:经典算例的数据集及其对应的 Reader 来读入数据。可用于读入相同数据格式的算例的算例，便于实例的构造；
• jsprit-example:对一些VRP使用Jsprit的例子。

JSprit只提供Ruin and Recreate这一种启发式算法，其工作原理如下图：

算法的核心思想是先通过Ruin，即破坏当前解的方式，将当前解中的若干个节点移出路径，再通过Recreate，即重建解的方式，将移出的节点以最优的方式重新插入路径当中（或在插入不可行时生成新路径并插入节点），从而尝试构建更优解。

Ruin策略有很多，主要包括以下三种：

• Random Ruin:在所有顶点中随机选取若干个顶点移出当前解；
• Radial Ruin:在所有顶点中随机选取一个顶点，将其以及与其最近的若干个顶点移出当前解；
• Sequential Ruin:在随机选取的一条路径中选取若干个顶点移出当前解；

Recreate策略包括两种：

• Best Insertion:将移出的节点按随机顺序以最优的方式重新插入路径当中；
• Regret Insertion:先将移出的节点根据最佳插入方式和次佳插入方式之间造成花费增加的差值以及其他评分变量进行综合评分，按照评分顺序将节点以最优的方式重新插入路径当中（如差值较大先插入，避免受其他节点插入导致无法以最佳方式插入）；

该算法的优势在于对复杂问题的适应性。它可以用来求解约束较多、目标复杂或 解空间不连续的复杂问题，并且通过更大范围的变化扩展解空间，从而有更大可 能性获得更优解。

关于Jsprit的具体使用，可以参考这篇文章：

车辆路径优化问题求解工具Jsprit的简单介绍与入门

Or-tools

OR-Tools是Google提供的运筹规划运算工具，基于C++开发，但提供C、C++、Java、Python接口，支持多种编程语言，有较高的语言支持度。它实质上是由多种求解器构成的组件，根据不同场景问题提供对应求解器。

OR-Tools中提供的求解器可以分为四类：线性规划和混合整数规划、约束规划、车辆路径规划和网络流。其中网络流求解器是专门用于求解最大流和最小成本流问题的求解器，使用更为广泛的是另外三类求解器。

OR-Tools对车辆路径规划问题的求解最为特殊，尽管可以构建为线性规划模型，但更优的方法是使用OR-Tools中专门求解VRP问题的库——Vehicle Routing Library。此外可以通过调用约束规划求解器下的约束构建方法丰富约束条件，实现复杂程度更高的 VRP 问题求解。

OR-Tools提供的初始解生成算法有包括节约算法、扫描算法、Christofides算法、插入算法在内的16种算法。而其提供的局部搜索启发式算法则包括贪心算法、导引式局部搜索算法、模拟退火算法、禁忌搜索算法、遗传禁忌搜索算法五种。

CPLEX

CPLEX是由IBM公司开发的商业优化引擎，提供了C、C++、Java、.Net、Python以及MATLAB六种编程语言的接口，具有很好的语言支持度。可以用来求解线性规划、二次规划、二次约束规划、混合整数规划以及网络流问题。CPLEX提供了可用于多个不同优化器，可根据问题类型选择适用的优化器选项。

CPLEX可以多种形式提供服务：

• CPLEX Interactive Optimizer是可执行程序，能够实现问题读取、问题求解和解的交付；
• Concert Technology是提供API的C++、Java、.Net类库；
• CPLEX Callable Library 是使用C语言编写的库，可以在能调用C语言的其它语言编写的应用程序中实现嵌入CPLEX优化器；
• Python API提供支持CPLEX优化功能的Python编程接口；
• CPLEX for MATLAB则是 MATLAB语言使用CPLEX类的接口。

对于连续优化问题，CPLEX 采用的算法为单纯形法和内点法；对于混合整数规划问题，CPLEX 基本的算法框架为分支切割法，求解流程及基本框架如下图所示：

求解器特性对比

综上所述，JSprit、OR-Tools和CPLEX都能满足VRP及其变体问题的求解，Jsprit的优势在于模型设定的灵活性和自带可视化功能的便捷性；OR-Tools的优势在于求解问题的多样性、编程语言和内置算法的丰富性；CPLEX的优势在于能用于求解非线性规划问题，能灵活设定模型约束和目标，并获得全局最优解，具备可视化功能。

Part3求解器性能测试

1旅行商问题(TSP)

我们选择10个标准数据集进行测试。这10个数据集包括了客户规模从51到200的不同场景，设置所有求解器的运行时间为2分钟，分别测试它们的求解质量，测试结果如下表所示：

从上述的求解结果可以看出，对于旅行商问题，在具有相同的运行时间时，CPLEX在求解质量方面有最好的表现，而OR-Tools相较于Jsprit来说求解质量更好。

2带容量限制的车辆路径问题(CVRP)

我们分别从由Augerat、Christofides和Eilon、Fisher、Christofides以及Mingozzi和Toth提出的ABEFMP测试集中选择数据集，共选择10个标准数据集进行测试，保证选择的数据集分布在每个测试集中。对所有求解器均设置运行时间为2分钟，分别测试它们的求解质量，测试结果如下表所示：

不同于VRP问题中，CPLEX在求解质量方面并不具备显著优势。就上表的求解结果来看，当客户规模超过39时，CPLEX的求解质量就不及Jsprit和OR-Tools；并且当求解时间设置为2分钟时，客户规模为135的数据集F-n135-k7无法求得最优解。而在两种开源求解器中，OR-Tools和Jsprit的表现相差不大。

可以看出，对于CVRP模型的求解，在求解时间相同的情况下，CPLEX 对于数据规模较大的算例求解具有劣势，而OR-Tools和Jsprit则具有较好的求解质量，显示出启发式算法的优越性。

3带时间窗的车辆路径问题(CVRPTW)

我们从标准数据集 Solomon 数据集中选取 10 个数据集，确保包括不同分布类型(聚集分布、随机分布、混合分布)以及不同范围的时间窗约束(大时间窗、小时间窗)的数据集。

经测试已知，对于CPLEX求解器来说，客户规模为100的场景在短时间内难以求解，因此从原始数据集中分别截取客户规模为20和40的数据集进行测试，同时将运行时间设置为3分钟。

首先对于客户规模为20的数据集，分别使用Jsprit、OR-Tools和CPLEX进行求解，测试结果如下表所示：

在客户规模为20的大部分情况下，CPLEX的求解质量要优于另外开源两种求解器。对于后者，Jsprit的求解质量整体表现要优于OR-Tools，GAP值最大不超过10%。而且OR-Tools有接近60%的GAP值出现，存在表现很差的测试集场景。

在客户规模为40时，大多数情况下CPLEX的求解质量要优于另外两种求解器，Jsprit和OR-Tools在当前问题中的求解质量上存在较大的差距，Jsprit的求解质量整体表现要优于OR-Tools，并无GAP值超过20%的情况，而OR-Tools甚至出现了高达50%以上的GAP值。

我们又从Gehring&Hombergers数据集中选取客户数分别为200、400、600、800和1000的算例，将迭代次数达到2000次设置为运行终止条件，对Jsprit和OR-Tools进行测试。

可以看到，对于规模为100的算例，在大部分情况下，Jsprit求得的距离值和GAP值大于OR-Tools所求值，说明OR-Tools的整体求解质量要优于Jsprit，而在求解时间方面OR-Tools不及Jsprit，但其求解时间也不超过1分钟。总体来说，OR-Tools的求解质量更优，Jsprit求解速度更快。

从测试结果可以看出，对于规模为200的算例，OR-Tools相较于Jsprit在聚集分布场景的求解优势更加明显，OR-Tools的整体求解质量要优于Jsprit；而在求解时间方面OR-Tools不及Jsprit，求解时间差距非常大。与客户规模为100时相似，OR-Tools的求解质量更优，Jsprit求解速度更快，不同的是两者时间差据增大，是求解器选择时很重要的制约因素。

可以看到，对于客户规模为400的算例场景，OR-Tools相较于Jsprit在聚集分布场景的求解优势更加明显，OR-Tools的整体求解质量要优于Jsprit；在求解时间方面OR-Tools不及Jsprit，求解时间差距相较于客户规模为200的算例来说变得更加显著。总体来看，OR-Tools的求解质量更优，Jsprit求解速度更快，对求解质量和求解时间的需求是直接影响求解器选择的重要因素。

可以看到，对于规模超过600的算例，在求解质量方面，Jsprit对于客户点随机分布以及客户点混合分布的求解效果最佳，对客户点聚集分布的求解效果较差。而 OR-Tools 对于客户点聚集分布的场景求解效果最佳，对于客户点随机分布以及客户点混合分布的求解效果较差。在求解时间方面，就每个求解器自身来说，Jsprit 对于客户点随机分布以及客户点混合分布的求解时间相较最短，对客户点聚集分布的求解时间较长，并且随着客户规模的增加，Jsprit的求解时间也逐渐增加，OR-Tools对于客户点聚集分布的场景求解时间最短，对于客户点随机分布以及客户点混合分布的求解时间较长，将两个求解器对比来说 Jsprit在求解时间方面远胜于 jsprit。

因此，在CVRPTW模型中，对于客户聚集分布的场景而言，OR-Tools具有更好的求解速度和求解质量；而对于随机分布或客户混合分布的场景而言，Jsprit具有更好的求解速度和求解质量。

4带时间窗的取送货车辆路径问题(PDPTW)

由于CPLEX的求解时间较长，为对比Jsprit、OR-Tools和CPLEX三种求解器的性能，我们构造了客户规模为4、10、20、30和40的数据集来进行测试，运行时间上限设为2分钟，测试结果如下表所示：

由上述测试结果可知，CPLEX对于小规模的算例场景有着最好的求解质量，Jsprit 具有最快的求解速度，OR-Tools在求解质量和求解时间方面均不具备优势。

为对比Jsprit和OR-Tools对两种求解器在大算例中的表现，我们再分别选取客户规模

为100、200、400、600、800以及1000的算例进行测试，设定终止条件为迭代次数达到2000次。

可以看到，Jsprit 和 OR-Tools 的求解质量相差并不大，但是在求解时间上OR-Tools的求解时间远大于Jsprit 的求解时间，即相对OR-Tools来说，Jsprit能以较少的时间实现较好的求解质量。

可以看到，Jsprit的GAP值在每一类型的数据集中均小于OR-Tools的GAP值，可见Jsprit的求解质量略优于OR-Tools。并且在求解时间上，相较于

的场景，Jsprit的求解时间增幅远小于OR-Tools 的时间增幅，两者之间的求解时间差距变得更加显著。总体来说，在客户规模为200的情况下，Jsprit的求解质量略优于OR-Tools，而在求解时间方面远胜OR-Tools。

可以看到，对于客户规模大于400的算例场景，Jsprit在求解质量和求解速度两个方面都具有优势，并且随着客户规模的增大，Jsprit的优势越来越明显，它可以实现以很短的时间获得较优的解决方案。

接下来，我们分别绘制不同规模实例下，两种求解器求解过程的迭代图，进而通过观察最优解随着迭代次数的变化趋势，比较两者的求解效率。

可以看到，对于规模为100的算例，OR-Tools的求解质量优于Jsprit，但Jsprit的收敛速度更快。

对于规模为200的算例，OR-Tools的求解质量略优于Jsprit，而Jsprit由于初始解的优越性，在很小的迭代次数下就已经达到了最优解。

对比规模大于400的算例，二者迭代中的目标值呈现类似的变化趋势：

可以看到，对于求解质量而言，在相同迭代次数下，Jsprit的求解质量始终优于OR-Tools；而从收敛性来看，Jsprit能以较少的迭代次数达到最优解，具有较好的收敛性；并且随着客户规模的增大，达到最优解所需要的迭代次数更多，Jsprit相对于OR-Tools来说以更少的迭代次数获取更优的解。

Part4总结

• 求解器自身性质
  • 商用求解器CPLEX的优势在于能直接对构造的数学模型进行求解，具有很强的灵活性，可任意定义目标函数和约束条件；CPLEX不仅可用于求解线性规划问题和混合整数规划问题，还可用求解更复杂的非线性规划问题；CPLEX具有很好的语言支持度，拥有多达 6 中编程语言接口；此外CPLEX基于精确算法进行求解，能够寻求到最优解。
  • 开源求解器Jsprit和OR-Tools基于启发式算法进行求解，优势在于能快速求得可行解，并按照一定的搜索策略逐步靠近最优解，能用于求解规模较大的问题。其中，在求解问题种类、编程语言和内置算法的丰富性方面，OR-Tools优于JSprit；而在在数据分析可视化和模型设定灵活性方面，Jsprit优于OR-Tools。
• 模型求解
  • 对于TSP，当运行时间相同时，CPLEX的求解质量要优于Jsprit和OR-Tools，OR-Tools总体上优于Jsprit。
  • 对于CVRP，当运行时间相同时，在客户规模较小的算例中，CPLEX是三者之中求解表现最好的；而随着客户规模的增大，Jsprit显现出更好的求解质量，OR-Tools同样具有较好的求解质量；
  • 对于CVRPTW，CPLEX面对规模较大的数据集，在短时间内无法有效求解，Jsprit和OR-Tools 具有求解优势。在n=20的情况下，CPLEX具有很好的求解表现，而在n=40时，仅有一部分情况表现最优，Jsprit表现出求解优势。对于两种开源求解器，当客户规模小于400时，OR-Tools在求解质量方面表现优于Jsprit，而后随着客户规模的增大，Jsprit的求解质量变得更优，并且Jsprit始终显示出求解速度方面的优势。
  • 对于PDPTW，CPLEX面对规模较大的数据集，同样无法在短时间内有效求解，Jsprit和OR-Tools具有求解优势。对于构造出的小规模数据集，CPLEX的求解质量显著优于Jsprit和OR-Tools。在两种开源求解器的对比测试中，对于不同规模的数据集，当客户规模为100时，OR-Tools的求解质量优于Jsprit，当客户规模达到200时，两者的求解质量不相上下，而后随着客户规模的增大，Jsprit有着更好的求解质量。Jsprit的求解速度始终要比OR-Tools快，并且Jsprit的收敛速度要更快。

综上所述，CPLEX对于小规模场景具有求解质量上的优势，OR-Tools对于中等规模场景具有一定的求解质量上的优势，Jsprit对于较大规模的场景具有求解优势，能以较少的时间实现较好的求解质量。面向不同场景需求，可以根据对时间的限制以及对求解质量的要求，综合上述结论选择不同的求解器。

-The End-

文案&排版：吕其乐（华中科技大学管理学院本科一年级）

指导老师：秦虎老师 （华中科技大学管理学院）

如对文中内容有疑问，欢迎交流。PS：部分资料来自网络。