考虑道路约束的应急物资调度优化模型与算法

王付宇，张 康

(安徽工业大学 a.管理科学与工程学院;b.复杂系统多学科管理与控制安徽普通高校重点实验室，安徽 马鞍山 243002)

0 引言

近年来，灾害时常发生，如2008年汶川大地震、2020年新冠疫情和2020年南方特大洪涝灾害等，这些灾害对人们的生命财产和安全带来了巨大的威胁。因此，在重大灾害发生后开展及时、有效的救援工作十分重要，而应急物资和车辆调度对灾后救援和恢复有着重要意义。

针对灾后应急物资和车辆调度问题，国内外学者进行了大量的研究。1998年，List等[1]首次在放射性危险物品运输优化模型中引入了应急问题，为应急资源调度问题的研究奠定了基础；王海军等[2]考虑到不同应急响应阶段和目标重要程度不同，通过决策者对总运输时间和应急成本的动态赋权，实现了应急调度的动态决策；段晓红等[3]针对城市路网下多事故应急救援工作的特点，构建双层规划模型，对应急车辆调度和交通疏散进行协同决策；王付宇等[4]等针对灾害初期存在道路受损和救援物资不足的情况，以救援的公平性作为调度目标，使用步长递减的天牛须算法进行求解；Yi W等[5]针对人员疏散问题和应急物资调度的运输问题，设计了集成分布模型；Moreno A等[6]针对灾害救援中车辆运力的可重复利用问题，设计了混合整数规划启发式方法。

上述研究大部分是基于单种配送工具的应急资源调度问题，但是在道路发生损毁的情况下，单种配送工具很难满足现实需求。2010年，Hu Z H[7]使用改进免疫算法，求解基于救援网络的集装箱多式联运问题；Fikar C等[8]针对选取陆运和空运协调运输中转点选择问题，设计了一种决策支持系统，打通了应急救援工作的最后一公里；陈雷雷[9]建立了大规模突发事件下以受灾点满意度为目标的多车辆和多物资的物资优化调度模型；阮俊虎等[10]对应急响应中的“直升飞机+车辆”医疗物资联合运送问题进行研究；Ruan J H等[11]为解决大型自然灾害中的车辆和直升机联运问题，构建了平衡的车辆-直升机联运网络；Erdemir E T等[12]为解决突发事件下陆-空联合救援问题，提出了一种位置覆盖模型和贪婪启发式算法。

以上文献大多未考虑灾害初期运力不足和道路通行受约束等情况。而在现实情景下，由于灾害的突发性，导致灾害发生初期救援工具很难在短时间内集结。2013年，王旭平等[13]针对运力受限情况下的救援车辆路径选择和应急物资分配问题，构建了混合整数模型，使用遗传算法求解模型。2020年，薛星群等[14]针对震后应急资源调度的特点，考虑道路通行受约束和运力受限等条件，构建多目标规划模型，并使用改进的NSGA-II算法求解模型。但是该研究并未考虑物资的装卸时间或者准备时间，在特殊情况下，救援物资准备时间以及装载时间对于整个救援过程来讲不可忽视，该问题仍有改进的空间。因此本文在考虑道路通行受约束和运输能力不足的条件下，将救援物资的装卸或者救援工具的准备时间嵌入模型中，建立了考虑道路约束和多式联运的应急物资调度模型。

对于多目标问题，求解方法大多使用NSGA-II算法，但NSGA-II算法存在收敛速度慢、种群多样性差等[15-16]缺点。多年来，学者对NSGA-II算法进行了大量的研究。张国富等[17]提出一种NSGA-II与蚁群优化的混合智能搜索算法，并应用到多受灾点、多需求点的应急物资调度问题中；李燕等[18]利用改进的NSGA-II对交叉口车辆延误及机动车碳排放两方面进行优化；王付宇等[19]提出了多目标蜂群算法，并将其应用到重大疫情事件下的应急资源调度问题中。从现有文献分析可知，对NSGA-II算法仍有改进的空间，例如，如何根据研究问题的特殊性，设计相应算子以增加算法搜索空间等。

从检索到的文献可知，很少有使用自适应的NSGA-II算法求解多式联运问题。为求解多目标应急调度模型，本文使用带有自适应机制的NSGA-II算法对模型进行求解，所提算法对NSGA-II算法做出如下改进：1)设计自适应机制，综合种群进化的横向信息和纵向信息引导种群进化；2)针对联合调度中多车辆配送的特点，设计随机变邻域搜索算子，对解空间充分搜索；3)将贪婪思想嵌入邻域探索过程。

1 模型构建

1.1 假设条件

本文针对所建立的应急资源调度模型，作出如下假设：

1)受灾点的位置和两两受灾点之间的距离已知；

2)物资集散中心的物资量充足而且种类单一；

3)受灾点的种类以及需求已知，并且各受灾点仅能被访问一次；

4)配送工具平均速度不变，运行时长不受限制。

1.2 模型构建

物资救援体系使用完全有向图构建G=(V，A)，V表示所有节点的集合，V={0,1，…,n},其中v=0表示集散中心。V′=V/{0}表示所有受灾点的集合。A={(i,j)|i,j∈V,且i≠j}表示救援物资网络的弧集；K=K1∪K2表示所有运输工具的集合，K1表示直升机集合，K2表示汽车运输工具集合；Vc表示受交通约束的受灾点的集合。

因此，救援物资调度模型为

(1)

F2=min(W+U+V)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

2 改进的NSGA-II算法原理

NSGA-II算法是解决多目标优化问题常用的算法之一，但经典算法搜索能力较弱并且收敛性较差，为了提高算法的收敛性和搜索范围，提出了基于种群熵的自适应机制，充分利用进化的横向和纵向信息。种群进化的横向信息指种群层级的个体水平，某一阶段种群进化的横向信息包含所有个体目标函数值、Pareto层级数和不同Pareto层级中个体的数量。种群进化的纵向信息指以种群进化的代数为纵向时间轴，种群中非支配解集的分布状况。

2.1 自适应机制

2.1.1 自适应交叉概率

遗传算法中交叉概率和变异概率对算法收敛性和路经求解质量起着至关重要的作用[20]，而固定的交叉概率对种群进化很不利，众多学者对交叉概率做了大量研究[21-22]。本文借鉴文献[23-25]的设计思想，设计了自适应交叉概率公式。

pc=mean(pci)

(11)

(12)

其中，pc1为最大交叉概率；pc2为最小交叉概率；f′i为待交叉染色体中第i个目标函数值较大的个体；pc为个体的交叉概率，具体表示为所有目标函数适应度值的平均值；favgi，fmini，fmaxi为当前种群中第i个目标的平均值、最小值和最大值。

2.1.2 基于种群熵的变异概率

变异概率的大小一定程度上影响了种群进化的速度，因此本文借鉴文献[26]中种群熵的概念，设计了自适应的变异概率，变异概率如式(16)所示。

(13)

(14)

(15)

pm=P0G(i)

(16)

当种群中所有个体都分布在某个子空间中时，由式(15)可知：Gimax最大值为ε。一般来说pmmax最大不超过0.2，因此本文取pmmax=0.2。因此ε=pmmax/p0max=0.33。不同方差下的变异概率如图1所示。

图1 不同方差下变异概率对比图Fig.1 Comparison of variance probabilities under different variances

从图1中任一曲线可以看出，变异概率在算法的前期处于较小的值，在算法的后期，变异概率的值稳定维持在0.08左右。通过变异概率对比图可以看出，当δ=0.1时，变异概率在进化中期有着较大的探索空间，因此本文δ=0.1。

2.2 改进的交叉和变异算子

2.2.1 变异算子

设计合理的变异算子同样是遗传算法中的难点，本文结合配送工具资源可重复利用和多式联运等特点，设计了随机变异算子。随机变异算子的描述如下：

第1种变异(random_v)：随机从染色体中选择一个未受到通行约束的受灾点，随机插入到该染色体中，判断插入之后染色体路径长度是否优化，若未优化，则重复选择插入点，直到产生一个较优的解。

第2种变异(diff_v)：从两个不同配送工具中选择两个受灾点交换位置，若受灾点是受到通行约束的，则在直升机配送路径中选择一个不受约束的受灾点，然后进行交换位置。

第3种变异(road_v)：随机选择一个配送工具，对该配送工具的不同配送路径中的两个受灾点进行交换，若交换之后路径未得到优化，则重新选择，直到路径得到优化为止。

2.2.2 交叉算子

本文在顺序交叉算子基础上进行了改进，改进的顺序交叉算子如下所示。

2.3 混合选择策略

遗传算法中如何从交配池中选择合适的父代,以及如何选择算子是值得关注的问题，本文使用式(17)和式(18)选择父代个体。

(17)

(18)

其中，poprank为种群经过排序后第rank层级群体；T为最大迭代次数，即T=tmax；T1=β*T；T2=(1-β)T，通常β=0.382或者β=0.258；random_v、diff_v和road_v为设计的3种变异算子。

2.4 改进算法流程

改进算法的流程如下：

步骤1：初始化参数，最大迭代次数T_max、最大最小交叉概率pc1和pc2以及最大贪婪搜索次数t_max，产生初始种群；

步骤2：计算个体适应度值；

步骤3：非支配排序，并选择精英个体，形成父代种群；

步骤4：根据式(17)选择交配个体，并进行交配，形成子代种群；

步骤5：根据式(16)计算变异概率；

步骤6：通过式(18)从子代种群中选择变异个体，并使用随机变异算子形成新个体；

步骤7：选出较优的个体，判断贪婪搜索次数是否大于t_max，若满足，则保存较优个体到新子代种群中，并转到步骤8；否则，返回步骤6；

步骤8：合并父代和子代种群，并判断进化次数是否大于T_max，若不满足，返回步骤3；

步骤9：进行非支配排序，输出非支配解集。

具体算法流程图如图2所示。

图2 改进非支配快速排序算法流程图Fig.2 flow chart of the improved non dominated quick sort algorithm

3 算例分析

3.1 算例数据和算法参数

本文采用的数据[14]如下，应急物资集散中心坐标(50,50)，20个受灾点的坐标如表1所示，加黑字体为受约束的受灾点。随机指定3个受约束的受灾点，两架直升飞机，3辆货车，配送工具的相关参数如表2所示。由于文献[14]未考虑物资的装卸时间和成本，因此本文对相关数据进行修改，在文献[14]数据的基础上增加了装卸时间和成本。算法的测试环境为windows 10操作系统，4 G运行内存，intel四核2.5 Ghz，测试软件选择python 3.7版本。

表1 受灾点位置数据Tab.1 Disaster location data

表2 配送工具参数Tab.2 Distribution tool parameters

本文种群中染色体的个数为100，演化的代数定为500，最大贪婪搜索次数设为100，pc1=0.9，pc2=0.7，pc3=0.5。独立运行程序15次，任取其中一次的实验结果，Pareto前沿如图3所示，平均等待时间最小为50.37 min，总成本最小为2 142.67万元。从图3中的变化趋势可以看出，当平均等待时间减少时，总成本将会增加。并且当平均时间变化很小时，总成本会大幅度攀升。

图3 改进NSGA-II算法Pareto前沿Fig.3 Pareto frontier of improved NSGA-II

3.2 实验结果与分析

针对决策人的不同偏好和模型的两个目标，时间偏好型下的时间最小调度结果如表3，经济成本型下的调度结果如表4所示，从表3和表4可以看出，当平均等待时间最小时，总的调度成本高达4 472.96万元；当总成本最小时，平均等待时间为145.38 min。

表3 平均等待时间最小下的调度计划Tab.3 Schedule with minimum average total waiting time

表4 总成本最小下的调度计划Tab.4 Schedule with minimum cost

为检验所提算法的有效性，通过与文献算法和NSGA-II算法进行对比，将3个算法的种群数量和迭代次数均设为500，NSGA-II和文献算法的变异和交叉概率分别设为0.1和0.8。对比结果如图4所示。

图4 算法的对比图Fig.4 Comparison of different algorithms

为避免求解的偶然性，进行15组重复测试，表5中F1的单位为min，F2的单位为万元，由表5的数据可知：所提算法得到的平均等待时间的均值为44 min，比文献[14]和NSGA-II分别优化了6.3%和8.4%；总成本方面，比文献[14]和NSGA分别优化了1.6%和18.21%；稳定性方面，本文所提算法都要优于另外两种算法。

表5 不同算法的对比结果Tab.5 Comparison results of different algorithms

3.3 算法的性能分析

为测试改进算法相关性能[27]，本文采用分布性指标(SP)和覆盖范围(MS)来衡量算法的性能。

多样性SP指标是衡量种群多样性的一个指标。种群分布越均匀，则SP指标越小。SP指标如式(19)所示。

(19)

非支配解集覆盖范围MS指标，衡量Pareto前沿的覆盖范围，如式(20)所示。

(20)

为了说明本文算法在多样性和分布性能的效果，重复运行每个算法30次，得到MS和SP指标的均值和方差，具体数据如表6所示。

表6 SP和MS指标比较Tab.6 Comparison of SP and MS indexes

表6中SP和MS指标数据表明，所提算法结果比传统算法更优，与文献[14]算法相比，结果不比其差。

图5a为文献[14]和所提算法中非被占优解集的对比图，图5b为所提算法与文献[14]中非被占优解集真实占比对比图。由图5a和图5b分析可知，文献[14]的种群含有大量的重复解。从图5中非被占优解集占比收敛点可以看出，所提算法在进化后期有着较强的扰动能力。证明了所设计的交叉算子和消除重复解策略取得了效果。

图5 非被占优解变化趋势Fig.5 trend of non-dominant solutions

图6显示所提算法得到的MS指标值大于文献[14]数据，表明在种群进化过程中，改进NSGA-II算法所得种群覆盖范围更大，搜索范围更大。种群覆盖范围更大是因为设计的变异和交叉算子大大增强了算法的搜索能力。图7表明，与文献[14]相比，所提算法所得SP值更小、一致性更高。

图6 不同算法MS值对比图Fig.6 Comparison of MS values of different algorithms

图7 SP值对比图Fig.7 Comparison of SP values

4 总结

本文主要研究在重大突发事件时，运输能力受限制和道路通行受到约束的情境下的应急调度问题。在求解模型时，本文结合多式联运的特征，通过自适应机制引导种群进化。根据种群进化的横向信息和纵向信息设计了自适应交叉和变异公式，以加速种群进化，提高算法效率。本文结合配送工具可重复利用以及多车辆调度的特点，设计了多种变异算子以增加算法的邻域搜索能力。最后通过算例和相关指标表明，与其他算法相比较，所提算法在改进种群多样性和分布性方面有着较好的结果。

在重大突发事件下，需求的不确定性、受灾点群众的服务满意度和公平性等问题同样是决策者考虑的重要因素，因此，在突发事件下，考虑受灾点的社会公平性、满意度以及绿色调度等可能是未来的研究重点。算法方面，未来调度问题往往是大规模、高维的，因此，使用多目标算法与AI的混合算法解决大规模高维问题，将是未来研究的热点。