基于实时信息的动态车辆路径问题模型与算法研究

发布时间：2020-11-14 01:58

　　 随着现代智慧物流的发展,传统的车辆路径问题(VRP)模型已经很难满足现在客户多元化的需求。因此,动态车辆路径问题(DVRP)的研究对于现代智慧物流的发展至关重要。本文在国内外DVRP研究基础上,重点研究了新的DVRP模型和求解算法。本文主要研究工作如下:(1)结合前人对DVRP的研究,对动态车辆路径问题的研究现状进行了阐述,并总结了存在的问题与不足。同时,根据不同的约束条件,对车辆路径问题进行了归类与分析。此外,还对求解DVRP常用的算法进行分类介绍。(2)对动态单车场车辆路径问题进行了数学建模,设计了混合蚁群算法进行求解。算法首先使用改进的K-means聚类算法进行K值确定和配送区域划分,然后使用蚁群算法生成初始路径和最佳路径交叉优化算法进行路径全局优化,最后采用2-Opt算法进行局部路径优化。实验部分,不仅基于不同规模的数据集进行结果直接比较,同时还对车辆使用率、动态度以及算法收敛性进行分析,以此来验证模型和算法的有效性。(3)对动态多车场车辆路径问题(DMDVRP)进行了建模与求解。按照DMDVRP特征建立对应的数学模型,同时设计了蚁群禁忌算法和实时添加优化算法对问题进行求解。蚁群禁忌算法采用蚁群算法框架,融合了遗传算法的变异操作和禁忌搜索算法。对于新客户的添加和优化部分,设计了新的实时添加优化算法实现添加和优化同步进行。实验部分,经过与最新出版的学术论文实验结果对比,证明了提出的算法可以高效地解决DMDVRP。此外,本文还比较了实时添加优化算法的优化效果,实验表明这是一种高效的添加优化算法。
【学位单位】：杭州电子科技大学
【学位级别】：硕士
【学位年份】：2019
【中图分类】：U116.2;F252;TP18
【部分图文】：

车辆路径问题的基本定义：以路程最短为目标函数，安排一辆或者多辆车按??照给定的配送线路和客户服务顺序，在满足车辆最大载荷约束条件下，完成所有??客户点的配送服务［２４］。图２．１是一个简单ＶＲＰ配送示意图，红色矩形代表配送??中心，黑色圆形代表客户，箭头为规划的配送路径，图中有三辆车分别按照规划??的路线为１０个不同的客户服务。??鲁客户?■?配送中心?——＞?规划路线??图２．１简单ＶＲＰ示意图??２．１．２静态车辆路径问题组成要素??静态车辆路径问题主要由七个要素组成，分别是配送中心、车辆、货物、客??户、运输网络、目标函数和约束条件［２５］。??（１）

况、突发事件等，这种带着大量随机性且需要及时处理的车辆路径问题属于动态??车辆路径问题。??图２．２是一个简单的ＤＶＲＰ示意图，其中黑点代表己知的客户，蓝色三角形??为新客户，红色方块为配送中心，红色箭头和黑色箭头分别代表己经完成的路线??和未来即将服务的路线，黑色虚箭头表示加入新客户后生成的新路线。其中图（ａ）??表示所有客户都是已知的，系统按照既定的路线开始安排配送服务。图（ｂ）表示??—些新的客户开始动态地发起服务请求，需要等待系统安排服务。图（ｃ）图表示系??统根据目前的服务状态，将新客户加入调度系统，并重新规划路线进行服务，最??终车辆完成所有服务回到配送中心。??⑻?（ｂ）?（ｃ）??？?已知客户?△?新增客户?＿?配送中心??——＞?已完成路线?——＞?规划路线?——＞?新路线??图２．２动态车辆路径问题示意图??在现实物流配送过程中，可能出现客户请求的服务时间与实际可执行的服务??时间冲突，部分客户配送任务被安排到下一个工作日。可以使用给工作日设置服??务请求截止时间７；。方式处理该类问题

这些新的客户需求应该立刻被分配给正在为其他客户服务的车辆，或者安排新的??车辆单独处理新需求。因此，在配送服务过程中，总存在一些己经被服务完的客??户和一些等待被服务的客户。一个ＤＶＲＰ示意图如图３．１所示，其中黑点代表已??知需求的客户，红线和黑线分别代表己经完成的路线和未来即将服务的路线，红??线与黑线的组合表示为已知需求客户设计的初始路线。随着时间的推移，新产生??的客户需求（蓝色三角形）被添加到系统中，新客户被插入到现有路线中，并将??产生新的配送路线（红线＋黑色虚线）［５２］。??＃?已知客户?Ａ?新增客户?■?配送中心???灸己完成路线?灸规划路线－－－－＞?新路线??图３．１动态车辆路径问题示意图??２２??
【参考文献】

相关期刊论文 前1条

1 杨弋,顾幸生;物流配送车辆优化调度的综述[J];东南大学学报(自然科学版);2003年S1期

本文编号：2882929