动态车辆路径问题建模与优化算法研究

发布时间：2020-06-22 00:09

【摘要】：作为一类主要的组合优化问题,车辆路径问题(VRP)一直受到了计算机科学和运筹学界的广泛关注,在实际工业生产调度中发挥了重要的作用。然而随着交通线路的日趋复杂化以及客户需求的多样化与个性化,基本VRP模型很难有效指导物流企业进行配送作业。现代物流企业在进行配送路线规划时,需要考虑方方面面的因素,比如客户的动态请求,时间窗限制,还有企业自身资源的限制。如何从满足顾客需求和优化企业自身网点角度来研究动态车辆路径问题(DVRP)越来越受到理论界的重视并逐渐成为研究热点。本文是在前人研究的基础上,重点对DVRP及其扩展和元启发式求解算法进行了研究,主要研究工作总结如下:(1)研究了基本DVRP问题,提出了一种改进的蝴蝶优化算法。该算法利用自然数编码的方式对DVRP进行离散问题连续编码;在迁移算子和调节算子的操作过程中采用一种贪婪策略接受局部解;每当有新解产生时,利用2-opt*算子对新解进行扰动,旨在帮助搜索过程避免陷入局部最优,增加搜索的多样性,加快搜索速度,从而得到最终的满意解。在通用的22个基准测试集上进行了实验,算法更新了 12个实例的已知最好解,与现有文献中的方法相比平均性能至少提高9.38%,从而验证了算法的有效性。(2)研究了有时间窗DVRP问题,提出一种改进的和声搜索算法。该算法结合了和声搜索算法与变邻域下降算法的优势。与经典和声搜索相比,重新定义了编码方式、初始解构造方式、即兴创作新和声操作及接收方式;设计了四种邻域结构以扩大搜索空间;以信息熵评价种群优劣,防止过早收敛;动态对客户请求进行检查,以提高搜索性能。并在通用的基准测试数据集上将该算法与现有算法进行对比实验,实验结果表示,算法的平均拒绝率最少,即使在相同的拒绝率的条件下,车辆行驶距离与车辆使用数在大部分情况下也优于现有算法,从而检验了算法的有效性。(3)研究了车辆数受限与带时间窗DVRP问题,提出了一种基于自适应大型邻域搜索的改进算法。设计了一系列特殊删除/修复策略;并对每一种策略指定初始评分及权重,在搜索过程根据当前的表现动态更新评分及权重,根据权重按照轮盘赌的机制选择删除/修复策略;引入一个周期性的扰动策略,加快了搜索速度;此外,针对动态客户的插入,设计了一个针对时间窗的提前等待策略。最后通过Lacker基准数据集对算法性能进行测试,更新了 19组实例的最少车辆使用数,检验算法的有效性。(4)研究了众包条件下的带时间窗动态车辆路径问题,在该问题中,假设一部分客户的需求是通过物流公司自营的车队进行运输,另一部分则以外包的形式发布到第三方物流平台,通过临时司机接收任务的方式完成相关运输配送。为了求解该问题提出一种贪婪随机自适应搜索算法。该方法的迭代过程包括构造和局部搜索两个阶段。在解的构造阶段,采用两种不同的贪婪函数来构造初始解;在局部搜索阶段,设计了4种邻域结构,扩展了解的搜索空间。为了促进临时司机的积极性,设计了两个不同的补偿策略。通过Lackner的基准实例验证了算法的有效性,再利用真实案例对其进行测试,验证了众包策略的优越性。(5)开发基于众包的包裹配送平台。从软件开发的角度对系统的功能模块进行分析,设计众包条件下包裹配送的业务流程,集成本文提出的相关求解算法,并展示包裹配送平台的主界面和功能模块。该平台可以为物流公司使用众包进行包裹配送提供有效的物流整合方案。
【学位授予单位】：大连海事大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：TP18
【图文】：

示意图,示意图,调度员,车辆

图２．２单个车辆动态路线事件的时间轴逡逑Ｆｉｇ．邋２．２邋Ｔｉｍｅｌｉｎｅ邋ｏｆ邋ｅｖｅｎｔｓ邋ｆｏｒ邋ｔｈｅ邋ｄｙｎａｍｉｃ邋ｒｏｕｔｉｎｇ邋ｏｆ邋ａ邋ｓｉｎｇｌｅ邋ｖｅｈｉｃｌｅ逡逑在图２．１揭示ＤＶＲＰ如何以持续的方式进行路径调整，在这一过程中需要在逡逑车辆和调度中心之间进行实时通信。图２．２说明了这种实时通信方案，其中环境逡逑指的是真实世界，调度员是向车辆发送调度指令的有关人员。一旦车辆准备就绪逡逑（第一个虚线箭头），调度员做出决策，并指示车辆履行客户Ａ的请求（第一双头逡逑箭头）。当车辆到达客户Ａ邋（第二个虚线箭头）并开始服务时，它会通知调度员并逡逑－８－逡逑

求解算法

．４．１策略算法逡逑通常，策略是指系统应对当前状态和动态问题的属性（例如出现的位置、事逡逑频率、事先已知的订单数、工作日长度、规划周期的持续时间等）所进行的一逡逑列操作［３（＾１］。在有些文献中［３２－３７］策略定义为单一或多个车辆条件，他们考虑动逡逑请求的特殊性和时间分布，并使系统在每次问题发生变化时对服务进行规划。逡逑为了向车辆发送请求和建造路线，策略被反复应用。我们概述了其中的一些：逡逑（１）先到先得（ＦＣＦＳ）：请求是按照调度程序接收到的顺序执行的；逡逑（２）随机队列中值（ＳＱＭ）：车辆位于在服务区域的正中位置，根据ＦＩＲ）策逡逑为客户服务。当服务完成后，车辆返回到中间位置。逡逑（３）最近的邻居（ＮＮ）：它是一种贪婪的策略。在该策略中，车辆在服务当逡逑客户后，选择靠近当前客户最近的未被服务的客户作为下一服务对象。逡逑（４）旅行推销员（ＴＳ）：请求被收集到一个给定大小的集合中。一旦一组需逡逑被批量处理，ＴＳＰ就被解决了。这些需求的服务是按照最佳的路线，从配送中逡逑

【参考文献】