JSPRIT在带时间窗的车辆路径规划问题(VRPTW)上的表现总结

在之前的推文车辆路径优化问题求解工具Jsprit的简单介绍与入门中，相信大家已经对Jsprit这款开源的车辆路径规划问题求解器有了基础的了解，那么Jsprit在具体的车辆路径规划问题上表现到底如何呢？

下面我们将以带时间窗的车辆路径规划问题(Vehicle Routing Problem with Time Windows, 简称VRPTW)为例，详细测试Jsprit在该问题上的表现。

1.VRPTW及输入样例介绍

什么是VRPTW？

相信聪明的你看到VPRTW一定会和VRP模型联系起来：

车辆路径规划问题（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求。配送中心则负责向客户提供货物，分送货物由一个车队负责，通过组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。

而VRPTW在容量约束的前提下，加入了时间窗的约束。对于每一个需求点，设定开始时间和结束时间，要求车辆在时间窗内开始服务顾客。

需求点的时窗限制可以分为两种，一种是硬时窗（Hard Time Window），硬时窗要求车辆必须要在时窗内开始服务顾客，早到必须等待，而迟到则拒收；另一种是软时窗（Soft Time Window），不一定要在时窗内开始服务顾客，但是在时窗之外开始服务必须要惩罚，以惩罚替代等待与拒收是软时窗与硬时窗最大的不同。

测试样例：

下面将给出本次测试样例。在我们的测试样例中，设定的优化的目标为路程最短，时窗限制为硬时窗。

文件最上方给出了车辆的数量和容量。

下方表格中的XCORD，YCORD为顾客的位置，Demand为顾客需求，Ready time和Due time为时间窗的开始时间和结束时间，Service time为服务时间。

下面我们介绍用于测试的几种样例形式：

• C-type：顾客成集群分布
• R-type ：顾客均匀分布
• RC-type ：上述两种的混合

为了测试的准确性，我们选用Solomon数据集和Homberger数据集。其顾客的规模从25一直到到1000。

通过测试不同顾客数量的样例，可以评测Jsprit在不同数据规模下对于带时间窗车辆路径规划问题的表现。

2.测试结果

测试的电脑配置如下：Intel core i5 8300H,关闭睿频，频率保持为2.2Ghz，内存16GB。

我们利用Jsprit求解了Solomon和Gehring and Homberger的全部样例，共497个，顾客规模覆盖了25，100，400，1000几种情况，这里选取了其中部分结果进行展示：

其中纵轴代表了20次求解的平均成本，横轴则是不同的测试样例。

顾客数为25时：

花费指的是Jsprit的求解结果；最好情况是指已知的（从文献中或者某些网站上获取）最好的结果。

在所有顾客数为25的测试样例中，Jsprit的偏差最大值为6.34%，最小为0.23%，偏差平均值为1.84%。

顾客数为100时：

在所有顾客数为100的测试样例中，Jsprit的偏差最大值为18.77%，最小值3.78%，偏差平均值为8.01%。

顾客数为400时：

在所有顾客数为400的测试样例中，Jsprit的偏差最大值27.15%，最小值为16.35%，偏差平均值为20.73%。

顾客数为1000时：

在所有顾客数为1000的测试样例中，Jsprit的最大偏差为19.86%，最小偏差为4.58%，偏差平均值为12.94%。

下面我们来分析下Jsprit在时间上的表现：

在图中，时间单位为秒，纵轴为求解20次的平均时间，横轴为求解的问题的顾客规模数。

我们可以看到当顾客数逐渐呈线性增加时，时间也几乎呈线性增加，而不是精确算法的指数级别增加。这就是启发式算法的优点所在，以精度换时间。

下面我们来看看Jsprit的收敛情况：

在图中纵轴为求解20次的平均成本，横轴为不同的迭代次数。

我们分别在数据规模为25，100，200的样例中抽取了几个样例作为测试样本，可以看到大部分的样例在迭代次数还不到1000的情况下已经开始收敛，在之后的迭代过程中得到解的改进也很小。这种只能通过达到固定迭代次数的方式来终止迭代的设置导致了一部分的算力的浪费。

总结

可以看到，Jsprit与其在官网上的介绍一致，求解非常方便，对于各种各样的问题都能适用，值得一提的是，求解的可视化也做的很不错。

但Jsprit也存在所求解的质量差的缺点。

欲下载求解的代码，测试样例和测试结果，请移步留言区。

-The End-