曹云+向凤红+毛剑琳+郭宁+赵培瑶

摘要：

针对物流配送客户需求动态变化，车场车型不是唯一特点，建立基于时间轴的多车型动态需求数学模型，根据客户动态需求将动态配送问题转换成一系列静态配送问题。设计了一种将分布估计算法与并行节约算法混合的算法实时优化模型。引入重定位法与2opt法局部搜索算法局部调整线路内子路径及线路间路径，进一步提高算法收敛速度。仿真实验与算法验证了所提算法的有效性与优越性。

关键词：

动态需求车辆调度问题；混合分布估计算法；多车型；重定位法；2opt法

DOIDOI：10.11907/rjdk.172020

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2018）001006806

Abstract：Aiming at the dynamic changes of customer requirements，vehicles diversification in the dynamic vehicle routing problem（DVRP）， the mathematical model of dynamic demand of multivehicle based on time axis is established，according to the dynamic demand information， the dynamic distribution problem is transformed into a series of static distribution problems.An algorithm combining the distributed estimation algorithm and the parallel saving algorithm is designed for realtime ptimization of the dynamic model. The local search algorithm of relocation and 2opt methods are used to adjust the subpaths in the line and the path between the lines to further improve the convergence speed of the algorithm. Combining with a simulated example， the model and algorithm is tested， which achieve good results.

Key Words：dynamic demand vehicle scheduling problem； hybrid distributed estimation algorithm； multivehicle type；relocation method；2opt method

0引言

1959年，Dantzig[1]首次提出车辆调度问题源于现实生活公路运输问题。依据顾客相关信息可知性车辆调度问题主要分为静态车辆调度问题（Static vehicle routing problem，SVRP）与动态车辆调度问题（Dynamic Vehicle Routing Problem，DVRP），静态VRP问题中顾客信息一直不变，但现实生活中，顾客信息随时可变化，因此动态车辆调度更贴近实际并尤为重要。

近年，由于现代物流快速发展，专家学者结合实际深入研究动态车辆调度问题。文献[2]研究了基于动态需求与旅行时间的动态车辆调度问题，但未对动态旅行时间与求解算法作明确说明；文献[3]用遗传算法解决了动态网络车辆路径问题；文献[4]提出了对单车型的混合量子遗传算法求解随机需求车辆调度问题；文献[5]研究了对单

车型的动态车辆调度，设计了两阶段求解策略；文献[6]建立了基于沿途多点补货策略的开放式车辆路径问题模型，但未考虑随机需求对路径优化影响；……