番茄路径优化系统介绍

程序猿声 | 63 2020-06-03 23:21 0 0 0

df307e32b5f4fe798d28d76072bdfee6.webp


程序猿声

代码黑科技的分享区

80742bcfab2b85613b8d2aa7eee1b28e.webp 6964d86d3533aef0a76cc6657f21756b.webp


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


ef5c700590c96f21dbce085609a09619.webp


1

问题背景



整个项目还是基于VRP的一个背景,处理的问题在涵盖经典VRPTW的基础上,还包括了处理以下约束的能力:
1. 多时间窗(一般由于客户营业休息时间等安排,会允许出现多个配送时间窗)2. 多车型(涵盖冷链车型和常规车型,大型车辆和小型车辆等,能够进行混合配送)3. 交通管制约束(有些地方不允许大型的车辆进入,只能安排小型车进行配送)4. 时间窗为硬时间窗(早到等待,不允许晚到)5. 客户需求多样化(常规的货物,冷链配送要求的货物)6. 等等5b81023517d0ca69bffa1d7c59bb4e4c.webp


b7b6992e52571906b45915f2c46bbcae.webp


2

算法性能



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


4060996a5532ebf6951b1a94b1382f37.webp


可以看到,相比较cplex而言,我们的算法有以下特点:
小规模算例对比
1. 质量更高:算例(1-7)我们的算法均取得了与CPLEX同样的最优解,在算例(8-11)上我们的算法取得了比CPLEX在1小时内求得的可行解更优的解(表中值越低越好)
2. 时间更快:除了算例1时间略高于CPLEX外,其余算例时间均比CPLEX低。且CPLEX的求解时间随着问题规模增加呈指数增长。当规模变大时,问题的求解时间急剧增加,在现实中很难应用。而我们的算法求解时间随问题规模增长呈线性增长,能够在较快的时间内求解较大规模的问题(分钟级)。
在大规模算例下(客户节点60-200时),我们的算法求解结果与CPLEX在1小时内求得的可行解进行对比:

a023441c15f02ddc798287366fa425ce.webp

8d8a9afda5b57a36ede93f1823e6f79e.webp
大规模算例下对比
1. 相比商业求解器CPLEX在1小时内求得的可行解,我们的算法得出的解成本更低。
2. 如图所示(时间越少越好),可以看出,在客户规模为60-200的算例下,我们算法的求解时间远低于CPLEX的求解时间。
同时为了弥补启发式算法在求解质量上的不足,我们在算法中应用了一种比较的“邻域搜索多样化”技术


0062f628aa606e9b501b03acb45a53e4.webp

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

594a3396f32d7add86337d4c66e22d87.webp


2f29d0a7bafa682c4bd236e42043fbd1.webp


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



3

系统介绍



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


系统的主界面如下:


a37c859001674f7c65ac3119122dd2bb.webp


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


2d8183e815dc29c66ad9602d7d5f0f13.webp


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


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


944c0726bbf949bc6402b6a6bffb3682.webp


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


ea46e876b43719e2ade21ae05ec5cc27.webp


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


e10d397a659ab17b8cba1cfa14f16736.webp


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


25a99a13e2f916f2afb2d8d2150e51f7.webp


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


55105b88823e45e907f01c12d192dcfc.webp


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


4d24c7d13a3b21c927bf1465ad9c59e1.webp

1999adfaeebe26ec7df161292ef2c707.webp


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



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


推荐阅读:

干货 | 想学习优化算法,不知从何学起?

干货 | 运筹学从何学起?如何快速入门运筹学算法?

干货 | 学习算法,你需要掌握这些编程基础(包含JAVA和C++)

干货 | 算法学习必备诀窍:算法可视化解密

干货 | 模拟退火、禁忌搜索、迭代局部搜索求解TSP问题Python代码分享
a4f6091fab118cf605b8bdbbd12a6e0f.webp记得点个在看支持下哦~44971dd84fa9c218711175959f4584b2.webp



good-icon 0
favorite-icon 0
收藏
回复数量: 0
    暂无评论~~
    Ctrl+Enter