• 发文
  • 评论
  • 微博
  • 空间
  • 微信

番茄路径优化系统介绍

程序猿声2020-06-03 17:19发文

程序猿声 代码黑科技的分享区

大家好,最近消失了一阵子。因为这两周一直在折腾一款产品。事情是这样的,此前搞算法一直是和命令行打交道基本上,搞得心烦,然后前阵子上头条偶然看到一些前端框架做的系统,感觉还挺好看的,也蛮有趣的。于是就跃跃欲试想尝试下新的东西,加上此前不是做了很多算法嘛,有了一定的基础积累,于是想着把算法和UI结合起来,搞款能用的算法产品试试。

1、问题背景

整个项目还是基于VRP的一个背景,处理的问题在涵盖经典VRPTW的基础上,还包括了处理以下约束的能力:

- 多时间窗(一般由于客户营业休息时间等安排,会允许出现多个配送时间窗)

- 多车型(涵盖冷链车型和常规车型,大型车辆和小型车辆等,能够进行混合配送)

- 交通管制约束(有些地方不允许大型的车辆进入,只能安排小型车进行配送)

- 时间窗为硬时间窗(早到等待,不允许晚到)

- 客户需求多样化(常规的货物,冷链配送要求的货物)

- 等等

2、算法性能

系统的核心算法引擎基于启发式算法开发,具有比较优秀的性能。不过口说无凭,将我们的算法和cplex进行对比,首先是小规模算例上的对比(规定了CPLEX求解时间上限为1小时):

可以看到,相比较cplex而言,我们的算法有以下特点:

小规模算例对比

- 质量更高:算例(1-7)我们的算法均取得了与CPLEX同样的最优解,在算例(8-11)上我们的算法取得了比CPLEX在1小时内求得的可行解更优的解(表中值越低越好)

- 时间更快:除了算例1时间略高于CPLEX外,其余算例时间均比CPLEX低。且CPLEX的求解时间随着问题规模增加呈指数增长。当规模变大时,问题的求解时间急剧增加,在现实中很难应用。而我们的算法求解时间随问题规模增长呈线性增长,能够在较快的时间内求解较大规模的问题(分钟级)。

在大规模算例下(客户节点60-200时),我们的算法求解结果与CPLEX在1小时内求得的可行解进行对比:

大规模算例下对比

- 相比商业求解器CPLEX在1小时内求得的可行解,我们的算法得出的解成本更低。

- 如图所示(时间越少越好),可以看出,在客户规模为60-200的算例下,我们算法的求解时间远低于CPLEX的求解时间。

同时为了弥补启发式算法在求解质量上的不足,我在算法中应用了一种全新的“邻域搜索多样化”技术

通过对搜索过程中的目标值增加惩罚从而避免陷入局部最优,以扩大搜索过程的多样性达到寻找更优解的目的。

从图上可以看出,加了“邻域搜索多样化”技术后的算法效果明显比未加之前的要好,求解得到的解成本均有降低。

3

系统介绍

好了上面介绍了一下核心算法,这里来介绍下系统的UI界面。整个系统的UI采用的技术栈是springboot+vue前后端分离开发的模式,数据库采用的是mysql。由于我对前后端这些完全没有学过,这两周开发的过程中都是边学边做的。其中踩过的坑和无数吐血的经历等以后有时间再介绍了。唉~

系统的主界面如下:

初次使用需要到任务管理中添加一个任务,填写任务名和任务相关描述,上传算例文件保存任务后,便可以开始对任务进行相应的操作:

系统后端会对算例文件进行一个校验的操作,如果是瞎上传的不符合格式的文件,会被撤掉。

添加完任务后,可以在参数设置模块对算法的参数进行相关的设置,右边是具体参数的详细说明:

然后就可以回到主页面对刚刚添加的任务进行一个求解了。当在任务操作中选择一个任务,左下角的地图便会将算例中的客户节点在地图上标注出来:

随后便可以点击启动算法,进行求解,该过程是动态演示的过程,会随着后端算法的求解不断更新页面上的信息,包括当前进度,当前最优解的详情,算法收敛曲线等,该过程也可以随时点击停止按钮终止算法:

求解完成后,左下角的地图会将求得的路径在地图上给逐一展示出来,同时也能看到整个过程的算法收敛曲线,包括当前解(可能不可行)和最优解曲线(必须为可行解,不然不会画出来),还有最优解的路径具体详情:

同时,求解的结果也可以进一步保存到后台的数据库中,相关详情可以在结果查看中进行管理:

点击某个任务的详情后,便可以将该任务的求解记录详情给展示出来:

当然,小编还为此制作了演示视频(人家说天不怕地不怕就怕咱广东人说普通话……):

关于该系统,有感兴趣的小伙伴可以联系我进一步细聊。不过源码暂时不会公开的。

声明:本文为OFweek维科号作者发布,不代表OFweek维科号立场。如有侵权或其他问题,请及时联系我们举报。
2
评论

评论

    相关阅读

      暂无数据

      程序猿声

      编程爱好者的聚居地,代码黑科技的...

      举报文章问题

      ×
      • 营销广告
      • 重复、旧闻
      • 格式问题
      • 低俗
      • 标题夸张
      • 与事实不符
      • 疑似抄袭
      • 我有话要说
      确定取消

      举报评论问题

      ×
      • 淫秽色情
      • 营销广告
      • 恶意攻击谩骂
      • 我要吐槽
      确定取消

      用户登录×

      请输入用户名/手机/邮箱

      请输入密码