客户请求频繁变动的VRPSDP分时段干扰管理模型

发布时间：2021-06-26 02:01

　　针对客户请求频繁变动对同时送取货车辆路径方案造成的干扰问题,从配送成本和服务时间两方面,对干扰事件造成的车辆路径方案影响进行干扰辨识.结合客户请求变动频繁程度及其特征,以前期短、后期长不等份原则将配送任务期合理划分为若干个时段,以广义总费用偏离最小为目标,构建同时送取货车辆路径问题的分时段干扰管理模型,设计基于改进遗传和禁忌搜索的求解算法,并选用Solomon标准问题库中的数据进行算例验证分析.结果显示:该方案在优化广义总费用偏离方面较之实时干扰管理、增派车辆和全局重调度等方案均有明显降低. 

【文章来源】：大连海事大学学报. 2020,46(04)北大核心CSCD

【文章页数】：9 页

【部分图文】：

车辆路径偏离情况

在配送时间上,客户对时间窗的要求通常有两种情况:一种是硬时间窗,指在客户要求的时间范围内配送车辆必须完成配送,否则客户将终止服务请求;另一种是软时间窗,指在客户要求的时间范围内配送车辆无法完成配送时,客户不会直接终止配送服务请求,转而给予一定的惩罚. 由于客户往往要求配送时间同时满足硬时间窗和软时间窗约束,因此,本文将时间偏离成本转换成广义时间成本,即时间偏离惩罚函数Pjn(tjn),如图2所示.在图2中,tjn表示在第n时段结束时刻制订的新干扰方案中,配送车辆到达未服务客户点j的时间.[ETj,LTj]为客户j的软时间窗,其中,ETj为客户j最早可以接受服务的时刻,LTj为客户j满意接受服务的最迟时刻. 当配送车辆在该范围内到达时,Pjn(tjn)等于0. [T0,LRj]为客户j的硬时间窗,其中,T0为配送车辆最早可能到达时刻,LRj为客户停止接受服务的时刻. 若配送车辆在客户要求的软时间窗前到达,即在[T0,ETj)内到达,则车辆因等待产生了机会损失成本;若配送车辆在客户要求的软时间窗后、硬时间窗前到达,即在(LTj,LRj]内到达,则服务延迟,产生时间偏离惩罚;若配送车辆在客户要求的硬时间窗后到达,即在tjn>LRj时到达,客户j停止接受服务[16]. 由上可知,Pjn(tjn)可表示为:

由于VRPSPD为NP难题[17],故本文构建的客户请求变动VRPSPD分时段干扰管理模型需要采用启发式算法求解. 考虑到不同启发式算法的优缺点,本文设计改进遗传算法和禁忌搜索相结合的两阶段启发式算法进行求解,算法设计整体框架如图3所示.由图3可见,本文算法设计的总体流程为:首先,通过two-opt操作选出最好的解码结果,将遗传算法与局部搜索算法相结合,对遗传算法加以改进,提高其局部搜索能力,快速得到初始车辆最优路径解(即原始车辆配送路径方案); 然后,在第tn时刻设计干扰管理新方案时,由于遗传算法需要迭代较长,且运行结果的好坏对于编码者水平具有很高的关联性. 为此,本文选用能更好地跳出局部最优困境且搜索速度快的禁忌搜索算法[18],对原方案进行全局逐步寻优调整,最终获得分时段VRPSDP问题干扰管理的满意解.

【参考文献】：
期刊论文
[1]带回程取货车辆路径问题的干扰恢复模型[J]. 王旭坪,阮俊虎,孙自来,曹海艳.  系统工程学报. 2013(05)
[2]基于联合配送的开放式动态车辆路径问题及算法研究[J]. 葛显龙,王旭,邓蕾.  管理工程学报. 2013(03)



本文编号：3250402