Jsprit与自研求解器关于VRPTW问题求解的比较

用户1621951

发布于 2022-09-07 16:47:51

8130

发布于 2022-09-07 16:47:51

文章被收录于专栏：数据魔术师数据魔术师

前言

哈啰

又见面啦

上次我们介绍了Jsprit与自研求解器的

简介与使用方法

（Jsprit和自研车辆路径规划求解器的介绍）

这次我们让它们来切磋切磋吧

1 求解准备

• 运行环境：IntelliJ IDEA + Windows10

• 运行问题：VRPTW

• 使用语言：JAVA、JSON

• 辅助工具：Jsprit、VRP_Solver

• 公开数据集：solomon-1987-C1、C2、R1、R2（100 nodes）

2 解的比较

上次推文我们已经介绍了这两个求解器的使用方法啦，这次我们就略过使用的步骤，直接来看看测试结果吧。还不了解如何使用工具的同学可以去看看上一期的求解器工具使用介绍哦。

2.1 solomon-1987-C1、C2

首先我们测试solomon-1987-C1与C2算例集，在这两个算例集中，顾客是集群分布的，具体的测试结果如下表所示。

•第一栏显示具体的算例；

•第二栏展示自研求解器给出解的花费；

•第三栏展示Jsprit展示Jsprit给出解的花费；

•第四栏展示它们的差值，如果为负就说明第二栏比第三栏的值要小，也就是自研求解器的解比Jsprit的更加好。

•第五栏展示这个算例在2008年及之前年代有记录的最优解情况，由小编在网上查得。

通过上面的表格可以看出，在这部分VRPTW问题下，自研求解器得出的解是好于Jsprit得出的解的；并且注意自研求解器和最优解的解对比，可以发现两者除C204算例外是完全相同的（最优解保留了两位小数）。下面我们看看更加直观的线型图吧。

本图中横轴代表算例，竖轴代表解的花费，越低越好。

由线型图更能清楚地得到，对于VRPTW问题，自研的求解器得到的解至少好于或等于Jsprit的解，并且发挥更稳定。

看到这里，是不是有同学想说，上面问题的求解器求出解的差距这么小，能看出什么，不会小编特意挑选几个算例来糊弄我们吧？

别急

我们接着看下去

2.2 solomon-1987-R1、R2

在solomon-1987-R1、R2这两个算例集中，顾客节点是均匀分布的。

我们可以很明显地发现，在这两个VRPTW问题的算例集中，自研求解器得出的解要比Jsprit得出的解好得多。

Best一栏标黄的项目说明，我们自研求解器所得出的解在这个算例下甚至好于小编所查到的最优解数据。

由更加直观的线型图还是可以看到，对于VRPTW问题，自研的求解器得出的解相比于Jsprit波动更小的同时明显更好。这可以理解为，面对不同的VRPTW数据集，自研求解器的发挥都是十分出色的。

怎么样

小编没有糊弄你们吧

2.3 收敛速度比较

为了进一步展示我们自研求解器在求解这类问题上的优势，小编进一步比较了两个求解器的收敛速度。

为了使得Jsprit与我们自研求解器的比较更加明显，小编这里使用上文算例集中性能表现差距最大的算例，也就是R101算例来比较两个求解器的收敛情况。

通过表格资料和线型图的对比我们可以直观地发现，

在收敛情况方面，自研求解器的收敛速度比Jsprit略微快一些，大概在200代左右就开始收敛；而Jsprit是在500代左右开始收敛。

在算法精度方面，Jsprit显然是掉进了局部最优，也就可以断言，Jsprit在这个问题上缺少跳出局部最优的能力；而自研求解器产生的解虽然不能保证是全局最优，但是把握的显然比Jsprit的要好。

从波动情况来看，可以从表格数据中看到（在线型图中可能不太明显），在700代迭代之后，自研求解器将最优解保持得很好，小编猜测可能使用了类似模拟退火的方法，使得解随迭代次数的增加，会变得难以改变；而Jsprit得到的最优解仍然处于不断的变化，可惜就算在变化，仍然是陷入了局部最优。

3 总结

现在做一个小总结吧，总结一下这两篇推文的比较：

Jsprit的优势有：

• 强大的可视化工具

• 在面对简单的CVRP问题更有优势

（但在复杂问题上，容易陷入局部最优）

自研求解器的优势有：

• 数据格式简单

• 云端计算

• 操作简单灵活，不需要编程基础

• 巨大的资源库支撑起的可扩展性

• 收敛速度更快

• 在求解VRPTW等复杂问题具有一定的质量优势

■ 为什么不比较计算时间？

有些小伙伴可能会有这样的疑问。按照小编自己的感受来看，Jsprit比我们自研的求解器慢得多：自研求解器的使用从上传到接收Json文件都可以做到数秒、甚至毫秒级别；而Jsprit可能要一分多钟。但是考虑到小编的电脑比较老了，性能不行；而自研求解器的计算是封装在服务端进行的，因此这方面的比较也就没啥意义了。