专栏首页程序猿声JSPRIT在带时间窗的车辆路径规划问题(VRPTW)上的表现总结

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),不一定要在时窗内开始服务顾客,但是在时窗之外开始服务必须要惩罚,以惩罚替代等待与拒收是软时窗与硬时窗最大的不同。

测试样例:

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

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

下方表格中的XCORDYCORD为顾客的位置,Demand为顾客需求,Ready timeDue 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-

本文分享自微信公众号 - 程序猿声(ProgramDream)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【CPLEX教程03】java调用cplex求解一个TSP问题模型

    前面我们已经搭建好cplex的java环境了,相信大家已经跃跃欲试,想动手写几个模型了。今天就来拿一个TSP的问题模型来给大家演示一下吧~

    短短的路走走停停
  • 【算法学习】减治 · 分治 · 变治

    普卢塔克说,萨特斯为了告诉他的士兵坚忍和智慧比蛮力更重要的道理,把两匹马带到他们面前,然后让两个人拔光马的尾毛。一个人是魁梧的大力士,他用力地拔了又拔,但一点效...

    短短的路走走停停
  • 需求可拆分及带时间窗的车辆路径规划问题(SDVRPTW)简介

    今天为大家介绍需求可拆分的带时间窗车辆路径问题(Split Delivery Vehicle Routing Problem with Time Window,...

    短短的路走走停停
  • poj-2551-ones

    Given any integer 0 <= n <= 10000 not divisible by 2 or 5, some multiple of n is...

    瑾诺学长
  • 解决:Unable to open debugger port (127.0.0.1:55017): java.net.SocketException "Socket closed"

    项目以前启动正常,突然报错,启动不起来了,报了个Unable to open debugger port (127.0.0.1:55017): java.net...

    微风-- 轻许--
  • 早报:P2P累计成交量突破6万亿,综合收益率延续下降趋势

    1、市场预测中国商业航天市场将在2020年达到8000亿元 据央广网报道,今日从第五届航天国际化发展论坛上获悉,截至目前,长征火箭已累计为国内外客户提供商业发...

    用户1335017
  • MySQL中数值类型中smallint、mediumint等区别是什么

    数值类型中又可以分为整型、浮点型,或者可以说为严格数值数据类型以及近似数值数据类型

    沈唁
  • 让机器读懂视频:亿级淘宝视频背后的多模态AI算法揭秘

    随着4G的普及和5G的推出,内容消费的诉求越来越受到人们的重视。2019年互联网趋势报告指出在移动互联网行业整体增速放缓的大背景下,短视频行业异军突起,成为“行...

    CV君
  • 高清视频点播-AI让你看片更丝滑

    本文简要介绍了基于强化学习的码率自适应算法,在实践预研验证和分析的基础上,将该AI算法模型应用于实际项目。

    腾讯音视频实验室
  • 高清视频点播-AI让你看片更丝滑

    ? 在线“看片”时,我们经常会遇到这些事情:视频画面突然卡住进入缓冲状态或者视频画面突然变得模糊而不忍直视。这些事情的背后很可能是网络环境突然变差了导致下载速...

    腾讯云视频

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动