混合分布估计算法求解动态需求多车型车辆调度问题

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

摘要：

针对物流配送客户需求动态变化，车场车型不是唯一特点，建立基于时间轴的多车型动态需求数学模型，根据客户动态需求将动态配送问题转换成一系列静态配送问题。设计了一种将分布估计算法与并行节约算法混合的算法实时优化模型。引入重定位法与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]建立了基于沿途多点补货策略的开放式车辆路径问题模型，但未考虑随机需求对路径优化影响；文献[7]研究了一类随机需求VRP问题，利用基于Inverover操作的粒子群算法，并将动态规划算法嵌入粒子群算法求解；文献[8]应用混合粒子群算法成功解决了大型VRP问题；文献[9]研究了城市拥堵情况下公交调度问题；文献[10]提出了一种种群增量学习算法解决VRPTW问题。

分布估计算法（Estimation of Distribution Algorithms，EDA）是一种基于统计的进化模式，利用概率模型描述候选种群问题解空间分布，通过统计学习手段构建一个描述解分布的概率模型，对该模型进行随机采用产生新种群，如此反复实现对问题解空间的搜索。该算法能利用已获得的较优解构建概率模型，较合理地确定算法搜索区域或方向，近年得到广泛关注。武燕等[11]提出一种自适应的PBIL用于求解一类动态优化问题，用2个动态优化问题进行仿真实验，表明其算法可快速跟踪最优解变化。袁利永等[12]设计了基于PBIL的物流中心选址优化算法，进行了算法实现与测试。谢勇[13]等提出了一种改进PBIL用于求解带软时间窗的车辆调度问题，仿真实验证明了所提算法的有效性。

经文献调研可知，基于分布估计算法求解动态车辆调度优化问题的研究还很少。本文在文献[4]基础上，根据新增客户信息变化的时间顺序变化，基于时间轴建立数学模型，根据客户动态需求信息把动态配送问题转换成一系列静态配送问题，并在此基础上考虑了车型变化。设计了一种将分布估计算法与并行节约算法混合的算法求解此问题。仿真实验验证了所提算法的有效性。

1概述

设有一个配送中心，負责配送整个网络顾客，且配送中心车型不是唯一，顾客配送需求随时变化。某个时间段内，根据顾客是否提前订货与订货计划是否有变，将配送网络中顾客分为静态顾客与动态顾客，其中静态顾客信息（顾客位置坐标，顾客需求量）为已知。配送网络中未出现动态顾客信息（静态顾客需求量变化与动态顾客需求）时，配送中心依据已知信息进行路径规划与车辆配送；随着时间变化，有动态顾客产生时，配送中心调度系统需要改变原先路线或增加新车辆以满足动态顾客需求。endprint

由于动态需求多车型车辆调度顾客信息随时间变化，因此引入时间轴概念，如图1所示。动态需求调度环境下，建立一个时间轴，每个新顾客需求产生时间为t，在t时刻时，动态顾客信息与静态顾客信息均为已知，因此可将动态配送网络通过时间t看成普通静态配送网络。

在时刻t时，根据车辆所处位置将所有顾客大致分为4类：①已完成配送顾客；②正在被配送顾客或车辆正要前往配送顾客；③未完成配送顾客；④产生新需求顾客。其中第二类配送过程中不可更改，这类顾客点是配送网络关键点，如图1的顾客点2、4、8。可知，所有随机需求车辆调度问题都可根据时间轴概念转化成一系列静态车辆调度问题，其中静态调度网络关键点识别非常重要，调度中心可根据关键点位置、车辆容载量及未完成顾客信息安排调度方案。

3.3种群初始化

种群初始化阶段，首先令gen表示当前进化代数，pop表示种群规模，GM表示算法最大运行代数，r是随机变量，取值范围为[0，1]，r0是控制车辆选择顾客j的参数，取值范围同r。随机产生一个概率r，若r

Step 1随机产生一个r；

Step 2若r

Step 3轮盘赌选择客户过程：假设确定pathi中第j个值pathi [j]，即车辆中第j个可服务客户，则从概率矩阵αgenijk进行轮盘赌选择。αgenijk为第i辆车服务第j个客户的概率，k代表子路径中第k个客户；

Step 4将选择客户加入pathi中，判断第i辆车是否满足容量要求，若满足则加入pathi中，否则派出下一辆车，即k+1辆车，并将客户j加入pathi+1中，跳转步骤1。

3.5基于重定位与2opt的局部搜索

EDA算法进化过程中，极易对解空间分布出现过拟合情况，导致构造的概率模型不能有效表达解空间信息，算法陷入早熟收敛。为保证算法有效性，加入局部搜索操作，以解决分布估计算法劣势，保持种群多样性。

所提算法主要是改进线路间局部搜索，包括针对单条线路的 2opt法，即将线路内2条边与另外2条边交换，如图3所示，将该线路内边（i，i+1）与（j+1，j）用边（i，j）与（i+1，j+1）替换，形成一条新路径。若新线路目标函数比原线路更优，用新个体代替原来个体。

针对多条线路的优化重定位法，即将一个顾客从一条线路转移到另一条线路，如图4所示，将结点i由线路r1移动到线路r2中j与j+1间，形成两条新线路。采用重定位是随机选取一个顾客结点重定位到其余线路每个位置上，从中选择最优线路代替原线路。

3.6混合分布估计算法

根据动态需求车辆调度问题特点，设计了针对该问题的混合分布估计算法，该算法基本思想是：采用分布估計算法对已知静态车辆信息进行路径规划，有随机顾客提出请求时，统计此时配送网络关键点及未完成配送顾客，采用并行节约插入算法，将随机需求顾客信息插入到已规划好静态路线。由混合的分布估计算法完成静态顾客与随机需求顾客配送。

3.6.1传统并行节约法

传统并行节约法生成配送路线，具体操作如下：

静态车辆调度配送线路构造：①将所有需求顾客分别与配送中心相连；②计算需求顾客之间是否满足连接条件，如车载容量限制，若满足，计算节约值；③选取节约值最大的2个顾客进行连接。重复②、③步骤，直到所有需求顾客均连接完毕，输出最优值。

动态需求车辆调度配送路线构造：①静态车辆调度配送路线基础上，有随机顾客提出服务请求时，调度中心检查当前车辆位置及路线，判断配送网络所有关键点；②依次判断随机任务是否满足插入条件，并计算所有可能插入点的配送成本，选取配送成本最小的2个顾客，将随机需求顾客插入该线路。

3.6.2混合算法

采用两阶段算法求解随机需求车辆调度问题，第一阶段利用分布估计算法求解静态车辆调度模型；第二阶段采用并行节约算法实将随机需求顾客插入配送网络。混合算法具体步骤如下：

Step 1给定初始参数，如顾客需求信息（动态顾客与静态顾客）、车辆装载量及车辆位置信息；

Step 2根据初始信息，利用改进的分布估计算法对静态顾客进行路径规划；

Step 3配送中心检查是否有随机顾客提出配送请求，若没有，则输出优化结果；否则转入步骤4；

Step 4统计该时刻配送网络所有关键点与未完成配送顾客信息；

Step 5依据配送网络关键点信息与未完成配送顾客信息，将随机顾客服务请求由并行节约算法实现动态插入，并转到步骤2。

4仿真实验与结果分析

本文提出了一种HEDA算法求解动态需求多车型车辆调度问题，对其进行实验仿真。所用算法与测试程序均在Matlab 2014仿真环境进行仿真。

4.1单车型动态需求车辆调度问题仿真实验

为验证本文所提HEDA算法可行性，对单车型动态需求车辆调度问题进行仿真。实验1测试数据为Matlab随机生成数据，包含一个配送中心（编号为0）与20个需要服务的顾客，其中静态顾客15个（编号为1，2，3，…），动态顾客5个（编号为D1，D2，D3，…）。各顾客点需求量及坐标见表1、表2。由配送中心出发的每辆车装载量均为6t。

设置种群数pop=30，最大迭代次数GM=100，求解随机需求车辆调度问题，结果见表3、表4。

由表4可知，HEDA能解决动态需求车辆调度问题，并取得了较好结果。

4.2多车型动态需求车辆调度问题仿真实验

由于随机数据偶然因素较大，因此采用文献[15]实验数据。配送中心共有3种车型，所有车辆均无最远行驶距离限制，3种车型费用参数设置见表5。一个配送中心（编号为0）坐标为（40km，71km）、30个静态顾客（编号为1，2，3，…，30）及5个动态顾客（编号为D1，D2，…，D5），静态顾客位置坐标与需求量见表6，动态顾客位置坐标与需求量见表7。要求安排合理配送路线，使所需费用达到最小。

设置种群数pop=30，最大迭代次数GM=100，对静态顾客进行线路规划，产生初始规划路线见表8。

动态调度路线见表9。

由表9可看出，对于动态需求多车型车辆调度问题，车辆使用应以装载率为依据，满载时车辆费用最低。本文首次提出应用HEAD算法解决此问题，并取得了良好结果。

为验证算法优越性，对于实验2例子，分别采用粒子群算法，遗传算法与本章HEDA算法进行对比分析，收敛情况如图5所示。

由图5可知，遗传算法与粒子群算法均在25代左右收敛，基于混合分布估计算法在16代左右即可收敛，这得益于混合分布估计算法具有较好全局搜索能力，同时又对优秀个体使用了局部搜索方法。

5结语

本文针对动态需求多车型车辆调度问题，将动态需求问题转化为两阶段静态车辆调度问题，根据问题特点首次将分布估计算法与最大并行节约算法结合。通过Matlab仿真试验，结果表明，该算法有效提高搜索成功率，验证了算法可行性。

参考文献：

[1]DANTZIGC RAMSERJ.The truck dispatching problem[J].Management Science，1959（6）：8091.

[2]JEANYVES POTVIN，YING XU，ILHAM BENYAHIA. Vehicle routing and scheduling with dynamic travel times[J].Computers & Operations Research，2006，33（4）：11291137.

[3]肖增敏.动态网络车辆路径问题研究[D].成都：西南交通大学，2005.

[4]葛显龙，王旭，代应.基于混合量子遗传算法的随机需求车辆调度问题[J].系统工程，2011，29（3）：5359.

[5]王旭，葛显龙，代应.基于两阶段求解算法的動态车辆调度问题研究[J].控制与决策，2012，27（2）：175181.

[6]张景玲，王万良，赵燕伟.基于沿途补货的多配送中心动态需求VRP建模及优化[J].计算机集成制造系统，2013，（04）：869878.

[7]彭勇. 变需求车辆路线问题建模及基于Inverover操作的PSODP算法[J]. 系统工程理论与实践，2008，（10）：7681.

[8]MARINAKIS Y， MARINAKIS M， DOUNIAS G. A hybrid particle swarm optimization algorithm for the vehicle routing problem [J]. Engineering Applications of Artificial Intelligence，2010，23（4）：463472.

[9]陈磊.基于随机需求的城市公交车辆调度问题的研究[D].北京：北京交通大学，2011.

[10]孟祥虎，胡蓉，钱斌.求解带时间窗车辆路径问题的有效混合PBIL算法[J].系统工程理论与实践，2014，（10）： 239247.

[11]武燕，王宇平，刘小雄.自适应PBIL 算法求解一类动态优化问题[J].吉林大学学报：工学版，2008，38（6）：136140.

[12]袁利永，金炳尧，曹振新.PBIL算法求解物流中心选址优化问题[J].计算机系统应用，2010，19（ 11） ：242245.

[13]谢勇，胡蓉，钱斌，等.一种改进的种群增量学习算法求解带软时间窗的车辆路径优化问题[J].南京理工大学学报，2016，40（1）：110116.

[14]蹇洁，王旭，葛显龙.云自适应遗传算法有能力约束的车辆调度优化[J].重庆大学学报，2013（8）：4046.

[15]葛显龙，王旭，邢乐斌.动态需求的多车型车辆调度问题及云遗传算法[J].系统工程学报，2012（6）：823832.

（责任编辑：何丽）endprint