孙 萍，卢俊杰，陈友荣，，赵克华，3
(1. 浙江树人大学信息科技学院，浙江 杭州 310015；
2. 常州大学计算机与人工智能学院&阿里云大数据学院，江苏 常州 213164；
3. 浙江禹贡信息科技有限公司，浙江 杭州310015)
我国地域辽阔，降水局部集中，时间与空间分布不均，且与人口、耕地等分布不相匹配，因而历来水灾频发。据国家水利部发表预测未来我国气象水文年景总体偏差，极端事件增多，涝重于旱，突发洪涝灾害事件随时可能发生[1]。一旦发生灾害，需要保证防洪抢险救灾工作的正常快速运转。其中，防汛物资的快速调度是防汛抢险救灾工作的重要一个环节。一旦抢险救灾工作启动，需要保证防汛物资调得出、运得走、及时到位。因此需要一种防汛物资的车辆运输调度方法，解决防汛物资运得走问题。
目前国内外学者在车辆调度优化领域已取得一定成果。部分学者侧重于以到达时间短，车辆行驶距离和运输费用最小等作为模型优化目标，研究多目标调度优化问题，如文献[2]建立了综合多周期、多物流中心和需求点时间约束的车辆调度模型，提出了一种具有适应性差异控制的混合遗传求解算法。文献[3]以总配送费用最小为目标，提出单次运输的路径规划模型，优化军事应急物流运输。文献[4]构建应急物资调运系统的高效、及时、低成本的动态调度模型，通过弗洛伊德算法对其进行最短路径求解。但是文献[2-4]没有考虑道路受损拥挤和分配公平原则，所建模型较简单。因此部分学者侧重于研究道路受损或拥挤下的车辆调度方法。如文献[5-7]都考虑了对禁行路段和必经路段道路受损的通行时间阻抗，分别提出了等待风险最小和通信时间最短的车辆调度算法和一种带精英策略的混合进化算法。文献[8]考虑路径规划和不确定通行能力等约束，建立不确定信息环境下车辆调度优化模型，并提出基于逆向搜索最短路径和正向反推安全路径的求解算法。文献[9-10]分别构建基于运输时间最短、资源调度最少的多目标应急物资调度计算模型，都采用加权排序法将多目标问题转化为单目标问题，并利用遗传算法进行求解。部分学者侧重于研究分配公平原则下的车辆运输调度算法，如文献[11]建立需求未满足率、交货时间和运输成本的最小化模型，提出基于多目标遗传算法求解配送路径。文献[12]采取加权方法构建权衡多个目标的车辆调度模型，并提出基于亲密函数概念的聚类遗传算法求解。但是文献[8-12]没有同时考虑道路受损拥挤和分配公平原则，且只是采用理想状态建模，没有考虑防汛物资运输的真实场景。
综上所述，目前车辆调度算法仍存在以下问题，不能适应于防汛物资的车辆运输问题：①车辆调度模型没有同时考虑道路受损拥挤和分配公平原则，建模较理想化。②主要考虑运输车辆实现每一个物资储备仓库的物资运输问题，较少考虑物资储备仓库需要的运输车辆调配问题。因此在上述文献的基础上，考虑救灾紧迫性、公平性和道路受损拥挤等情况，提出一种基于储备仓库多目标多约束的运输车辆调度算法(transportation vehicle scheduling algorithm based on multi-objective and multi-constraint of reserve warehouse，TVSA)，根据各个储备仓库所需车辆数量，物流中心位置和拥有车辆数量等信息，提出车辆平均调度预测时间，离规定救援时间的偏离度和平均偏离度方差等数学公式，建立每一个储备仓库的车辆调度优化模型。采用基于Pareto支配策略的多目标遗传算法，即通过非支配等级和精英解保留，提高算法的收敛性，通过拥挤度计算和非支配排序进行交叉和变异操作，保证算法的全局寻优能力，最终可获得一组趋于均匀分布的非支配解集和可权衡调度预测时间和偏离度的车辆运输调度方案，从而降低车辆平均调度预测时间，离规定救援时间的偏离度和偏离度方差，提高算法收敛速度。
问题表述：每一个城市内存在1个以上防汛物资的储备仓库和指定的1个以上车辆物流中心。每个物流中心存在若干辆防汛物资的运输车辆，一辆运输车辆同一个时刻只可前往一个储备仓库。当发生灾难需要进行防汛物资调度时，则接收到储备仓库的运输请求后，物资运输车辆根据车辆调度时间最小和配送公平原则进行调度运输，并尽可能多的满足各个储备仓库对车辆需求。
如图1所示，一个地区存在多级物资储备仓库(省级、市级和区级)和多个车辆物流中心。当灾难发生后启动抢险工作时，物流中心接收到各级储备仓库的物资运输指令后进行车辆调配。首先根据开源平台API计算两点间各路段车流情况，估算预测总体完成运输时间，以尽可能快速的对车辆进行调度。其次引入运输时间偏离度和车辆数量偏离度概念，尽可能保证其救援公平性。目前算法需要解决以下二个问题：一是如何考虑多个储备仓库之间的竞争，建立储备仓库多目标多约束下的运输车辆调度模型；
二是如何求解上述模型，获得最优方案，从而降低车辆到达储备仓库的时间以及离规定运输抵达时间的偏离度。具体模型建立如下。
(1)
图1 运输车辆调度示意图
(2)
依据浙江省水利防汛物资管理办法规定，在制定水利防汛物资应急调度方案中应当考虑交通道路情况。因此结合开源平台API计算储备仓库与物流中心之间的各段道路行驶规划组合，将物流中心及水利平台上报的损毁道路以及禁止通行路段从组合中剔除，再综合考虑道路拥挤情况对车辆的总体运输行驶时间进行预测估算。为了预测道路的总体通畅情况，引入一个道路拥挤因子(Road congestion factor，RCF)作为主要影响因素。令某个物流中心j至某个储备仓库k的总路程划分为n个路段，第i个路段长度为Li，以交通指数计算最小时间单位C(15分钟)为时间段间隔，计算当前时间段和上一时间段该路段的平均通行速度S对比，得到当前路段行驶组合实际通行时间比值Tp。
(3)
根据式(3)计算所得的行程时间比值，通过对比同一路段的相邻两个时间段车辆通行速度预测路段是否处于拥堵减轻或加重，获得当前路段组合的拥挤因子RCF。
(4)
考虑防汛救灾的紧迫性，以所有物资运输车辆平均行驶预测时间最小为首要优化目标。令Tk表示所有运输车辆到达储备仓库k的总预测抵达时间为
(5)
当仅出现单个物流中心对单个储备仓库进行车辆调度时，其解决方案较为简单，随着数量规模的增加，其难度呈指数性增加。考虑发生大规模灾害时需要大量的车辆，且在实际过程中，大型储备仓库往往与某些物流中心事先签订协议要求救灾过程中必须保证其运输车辆需要在一定的时间内达到，即每一辆车辆完成调度任务的行驶时间距离规定的运输车辆抵达时间的偏离程度应尽可能小，则离规定抵达时间的偏离度定义为
(6)
(7)
其中，ωk表示运输车辆抵达储备仓库k的时间总偏离度，ωjk表示从物流中心j到储备仓库k的调度预测时间的偏离值，tjk表示车辆两点间的调度行驶预测时间，μ表示规定车辆到达储备仓库的最大运输时间。
考虑到每个储备仓库都希望其调度方案尽可能的满足自身需求，则可建立每一个储备仓库的调度优化模型：
min(Tk×(1+ωk))
(8)
s.t.：式(1)-(7)
在运输过程中，每一个储备仓库都需要自身防汛物资能快速运输出去，则储备仓库相互竞争运输车辆资源，是一个多目标优化问题。
车辆资源调度问题是一种组合优化的NP难问题，目前研究主要通过精确算法和启发式算法求解。精确算法比较适合规模较小模型求解。启发式算法适用于规模较大模型求解。而遗传算法等元启发式算法是启发式算法的改进，是随机算法与局部搜索算法相结合的产物，能更加有效地发现近似最优解。在多目标求解问题上，考虑到遗传算法具有较高的鲁棒性和较强的搜索能力等特性，更适合求解较为复杂的调度优化问题。因此选择基于Pareto支配策略的多目标遗传算法求解储备仓库竞争的多目标问题(8)，具体求解过程如下。
3.1 染色体编码设计
令一个有效的调度方案为染色体，采用一维实数矩阵编码，在运输车辆调度中，拟定一个地区有J个物流中心，有K个储备仓库，编写矩阵维度为J×K的染色体。如下图2所示，染色体中的基因数值代表某个物流中心派往某个仓库点的运输车辆数量。例如第一行第三列基因值代表由1号物流中心派遣4辆运输车至3号储备仓库。依次循环类推，可形成对所有物流中心和仓库点的运输车辆数量的调配指令。
图2 编码结构图
3.2 种群初始化
种群的初始化就是依据编码规则给出种群的初始解。按照约束条件进行随机数值生成，得到一定数量的初始解集。其染色体初始化的具体程序流程如下：
3.3 染色体适应度评价
针对物资运输车辆调度的紧急性，每个储备仓库都希望尽可能满足自身需求，因此计算单个储备仓库的个体适应度Fk，即
Fk=Tk×(1+ωk)
(9)
而调度最优解应权衡所有储备仓库的运输时间、偏离度和公平方差，则令染色体的总体适应度评价函数为
Fitness=Tave×(1+ωave)×(1+Rat)
(10)
其中，Tave表示所有车辆调度的平均时间，ωave表示所有车辆运输抵达时间的平均偏离度，Rat表示平均偏离度的方差，可定义为
(11)
若该染色体适应度评价值越小，则该调度方案效果越好，反之越差。
3.4 Pareto非支配计算和选择操作
本算法考虑储备仓库之间的竞争，根据储备仓库数量将种群划分成对应数量的子类种群，尽可能使每个子类种群其对应的适应度越优，从而实现储备仓库的多目标求解，具体步骤如下：
步骤1：通过式(9)计算所有染色体中每个储备仓库k的适应度值，得到一个长度为K的个体适应度矩阵Fm。对矩阵Fm中每一列数据进行排序，获得矩阵Fm中每一个元素的邻居个体i+1和i-1，计算拥挤度，即通过染色体i对染色体i+1以及染色体i-1的欧式距离值，计算拥挤度d，即计算每一个个体适应度值Fk的差值之和。拥有最大和最小值的解被指定为无穷大距离的值，即边界解d1=dy=∞。
(12)
步骤2：由于解集合中会出现部分解集中在某个区域，部分区域中解分布稀疏的情况，因此根据染色体的拥挤度，进行降序排序，获得与周围邻居染色体的空间度量，通过式(11)计算染色体被选择概率。
(13)
步骤3：基于非支配排序划分非支配等级。循环比较任意的两个染色体的个体适应度值Fk。若其中一个染色体的个体适应度值均大于或等于另一个染色体，则表示该染色体支配另一个染色体，因此可以获得一组不被其它解支配的非支配解集合Q1，并将之从种群中暂时除去。继续两两比较染色体适应度值Fk得到新的一组非支配解集合Q2。以此循环，直至将双倍初始规模大小的新种群划分为若干个等级。
步骤4：遍历计算父代种群中所有染色体的适应度值，将总适应度最优的染色体直接存入下一代新种群。保留非支配解集合Q1，若Q1中解数量小于初始种群规模，按照步骤3中的非支配等级，逐级进行择优填充，其择优准则为总体适应度Fitness最小，直至种群规模恢复至初始大小。
3.5 交叉操作
根据2.4节确定每个染色体被选中的概率，选择两个父代染色体，采用均匀交叉算子产生下一代染色体，即每个基因都存在一定的概率进行交换，从而形成两个新个体。具体方法为：在[0，1]范围内随机生成一组维度为J×K的浮点数组，若存在数值小于预定交叉概率则进行交换。
3.6 变异操作
采用了移位扰动变异操作，改善遗传算法的局部搜索能力，维持群体的多样性，防止出现早熟现象。具体方法如下：随机生成一个[0，1]范围内的浮点数，若该值小于预定的变异概率则随机选择某一列k，从该列中选择两个基因对进行位置交换。由于在进行交叉变异后其种群中会产生不满足约束条件(1)-(2)的解，因此采用2.2节种群初始化中的修正操作(步骤2-3)，使其染色体满足约束条件(1)-(2)。
如图3所示，本文模型主要使用带Pareto支配策略的多目标遗传算法进行求解，其具体步骤如下所示：
步骤1：获知所有物流中心的坐标位置以及所属的运输车辆数量，获得储备仓库申报的车辆需求数量；
步骤2：根据开源地图获取物流中心与储备仓库两者之间的若干条路线集合。获取路线中各个路段的畅通情况，预测车辆行驶的最短通行时间；
步骤3：初始化种群规模大小M，设定交叉概率，变异概率，迭代终止次数等参数，依据约束条件进行随机组合，得到初始解集；
步骤4：通过式(9)-(10)分别计算针对储备仓库的个体适应度值Fk和总体评价最优值Fitness；
步骤5：根据式(12)计算染色体之间拥挤度，从而确定各个染色体的选择概率；
其次对整个种群进行非支配排序，将整个种群划分为若干个等级，获得各级非支配解集合；
步骤6：保留历史最优解，依据非支配等级保留Pareto最优解，根据总体适应度评价值大小择优保留；
步骤7：循环选择M次，进行交叉和变异操作；
步骤8：验证新产生的染色体是否满足约束条件(1-2)，如果不满足，进行修正操作；
步骤9：进化迭代次数是否等于迭代终止次数，若是，则输出非支配解集，输出总体评价最优解，否则，进化迭代次数加1，跳到步骤4。
5.1 实验参数
选择由合作企业提供的杭州地区的实际储备仓库位置，选择部分储备仓库指定的实际物流中心位置和其车辆数量，选择杭州地区的部分物流中心位置和车辆数量，同时选择以下参数进行仿真：储备仓库个数为11，物流中心个数为10，种群大小为50，模型的终止迭代次数均为80，交叉概率为0.8(经验值)，变异概率为0.01(经验值)，规定车辆到达储备仓库的最大运输时间μ为30分钟。针对某个需求总车辆数，随机生成20组不同实验场景。每组场景中的每个储备仓库所需的车辆数量在[0-40]区间范围内随机生成，且其需求总车辆数相同。分析20个不同实验场景下算法的车辆平均调度预测时间，离规定抵达时间的平均时间偏离度和平均偏离度方差，取其平均值作为仿真结果值。
5.2 算法参数和效果分析
现选择4.1节中仿真参数，共生成11个储备仓库所需车辆总数409辆，随机分布储备仓库所需车辆数量，获得TVSA算法的算法非支配解分布图4和收敛图5。当储备仓库数量大于2时，各储备仓库之间形成相互竞争的态势且各自希望自身的个体适应度值尽可能达到最优。由于储备仓库数量是11，其空间维数较多，为方便数据展示，将其分为2组，计算输出非支配集合中各组的平均个体适应度值。如图4所示，由于车辆调度问题是离散问题，因此其Pareto非支配解集呈现离散点分布，但其总体趋势仍然呈现Pareto曲线特点。根据图5所示，进化迭代次数达到31时，算法完成收敛，这是因为针对多目标问题，TVSA算法采用Pareto支配策略、交叉操作、变异操作和精英保留策略等操作，能较快找到非支配解集，收敛速度较快。
图4 算法非支配解分布图
图5 算法总适应度Fitness收敛图
5.3 算法性能比较
选择SGA(标准遗传算法)和MOPSO(多目标粒子群算法)作为对比算法，分析不同储备仓库所需车辆总数下各算法的车辆平均调度预测时间、平均时间偏离度和平均偏离度方差。其中，SGA算法采用加权法将多个储备仓库之间的3个目标优化求解问题转化为单目标总体寻优问题，采用标准遗传算法求解，从而获得最优解。MOPSO算法在粒子群算法的基础上引入Parto支配策略，寻找目标向量的最优解集。SGA算法仿真参数和TVSA算法仿真参数相同，MOPSO算法的仿真参数取常规经验值，如惯性因子0.8，局部速度因子0.1和全局速度因子0.1。现选择储备仓库所需车辆总数50，100，150，200，250，300，350，400，和4.1节中的其它仿真参数。同一储备仓库所需车辆总数下随机产生20次不同车辆分布场景，计算不同场景下的TVSA，SGA和MOPSO算法的目标函数值，取其平均值作为仿真结果值。
如图6-7所示，不管储备仓库所需车辆数量如何变化，TVSA算法的车辆平均调度预测时间和离规定抵达时间的偏离度都小于SGA和MOPSO算法的车辆平均调度预测时间和离规定抵达时间的偏离度。这是因为：TVSA算法的种群适应度值考虑平均调度预测时间和离规定抵达时间的偏离度，且在选择阶段加入精英保留，并根据支配等级和总体适应度值大小对新种群进行填充，保证了算法收敛的高效性，同时根据拥挤度计算得到的选择概率进行交叉变异操作，扩大算法的搜索效率，使其解在整个多维空间中分布更加均匀，最后基于式(11)计算得到权衡平均调度预测时间和偏离度的全局最优解。而SGA算法仅仅依靠设置权重将多目标问题转化为单目标问题，从而导致其解内部的多目标值分布不均衡，不利于寻优，并且随着储备仓库数量增加，其目标维度增加，权重精确确定困难，从而求解效果下降。MOPSO算法在面对多目标问题时虽然引入了Pareto支配策略，但是随着数据维度的增加，其计算量增大，计算精度变低，导致其寻优能力减弱，容易陷入局部最优。
图6 车辆平均调度预测时间对比图
图7 离规定抵达时间的平均时间偏离度对比图
如图8所示，不管储备仓库所需的车辆总数如何变化，TVSA算法的平均偏离度方差小于SGA和MOPSO算法的平均偏离度方差。这是因为：针对11处储备仓库，SGA算法设置一组均匀分布的紧急性救援权重，并利用加权法计算最优解，但是无法有效权衡各储备仓库之间的调度分配，无法保证其公平性，则其平均偏离度方差最大。MOPSO算法在搜索空间中其粒子速度无法动态调节，降低了精度和多样性，对高维问题处理效果较差。TVSA算法能寻找到权衡各个储备仓库，体现出公平性原则，因此其平均偏离度方差最小。
图8 平均偏离度方差对比图
提出一种储备仓库多目标多约束的运输车辆调度算法(TVSA)。首先，根据各个储备仓库所需车辆数量、地理坐标等信息，通过开源平台API接口记录各路段车辆平均通行时速预测拥堵情况，考虑车辆完成运输的预测时间，时间偏离度和偏离度方差约束，建立运输车辆调度优化的多目标模型。其次，采用多目标遗传算法求解该模型，即通过非支配排序将整个种群分级并计算各个解之间的拥挤度，从而确定各个解被选中参与交叉变异的概率，使得整个解空间趋于均匀分布，避免陷入局部最优，通过交叉操作、变异操作、精英保留策略等寻找最优解，保证算法有效收敛。接着，分析TVSA算法的收敛性和非支配集合的解分布，比较TVSA、SGA和MOPSO算法的车辆平均调度预测时间、离规定抵达时间的偏离度和平均偏离度方差。
仿真结果表明：TVSA算法可获得较优车辆运输调度方案，从而降低车辆平均调度预测时间，离规定救援时间的偏离度和偏离度方差，提高算法收敛速率，比SGA算法和MOPSO算法更优。但是TVSA算法的时间复杂度较高，因此下一阶段将研究低时间复杂度的求解算法，提高调度模型的求解速度。
猜你喜欢 支配适应度仓库 改进的自适应复制、交叉和突变遗传算法计算机仿真(2022年8期)2022-09-28被贫穷生活支配的恐惧意林(2021年9期)2021-05-28填满仓库的方法小天使·一年级语数英综合(2020年11期)2020-12-16四行仓库的悲壮往事学生天地(2020年34期)2020-06-09云南省人均可支配收入首次突破2万元时代风采(2019年3期)2019-03-23跟踪导练（四）4时代英语·高一(2019年1期)2019-03-13小猫看仓库小学阅读指南·低年级版(2017年4期)2017-04-24启发式搜索算法进行乐曲编辑的基本原理分析当代旅游(2016年10期)2017-04-17随心支配的清迈美食探店记Coco薇(2016年8期)2016-10-09消防设备小天使·四年级语数英综合(2015年3期)2015-04-20