基于两阶段混合整数规划模型的洪涝灾害应急管理研究

张 庆，余 淼

(1.南京航空航天大学 经济与管理学院,江苏 南京 211106; 2.浙江大学 管理学院,浙江 杭州 310058)

0 引言

我国每年南方多个省份都会遭遇到严重的洪涝灾害，尽管政府部门已经投入了大量的人力财力物力，但是洪涝灾害还是给灾区的人民造成了巨大的生命财产损失。为了应对洪涝灾害，降低其恶劣影响，灾害管理部门需要在灾害发生前进行足够应急物资的存储，灾害发生后对物资进行迅速有效的分配。本文旨在提出一个集成灾前准备和灾后响应两阶段的应急管理方案，以应对大规模的突发洪涝灾害，为有关部门制定决策时提供参考。

有关灾害应急管理的国内外研究成果较为丰富，是近年来研究的热点问题，本文着重从以下几个方面介绍相关的研究成果：

关于洪涝灾害情景刻画的研究，灾害情景的刻画包括灾害发生后受灾点的受灾情况、灾民对于应急物资的需求等，其基础是灾害的准确预测，对于洪涝灾害的预测，通常有两种方法：一是基于数理模型的方法，Kelly K S等[1]基于历史数据通过贝叶斯方法预测了一洪涝灾害发生的频率和强度；二是利用地理信息系统等技术，赵珂等[2]利用DEA方法和逆DEA方法，借助于GIS空间拓扑叠加、空间统计功能和数字高程数据，对不同的受灾区域在不同的淹没水深时造成的相对损失进行评估和预测。所以结合过往抗洪救灾经验和地理信息系统及新兴的气象预测技术，可以对洪灾进行初步预测，并刻画不同严重程度的受灾情景，基于此，情景分析法在灾害应急管理的研究中应用广泛。Chang M S等[3]利用地理信息系统软件构造了一洪涝灾害的地图，包括可能的受灾点的位置以及受灾点的物资需求，进而展开应急资源分配决策。

灾害应急管理主要包括两部分工作：灾前准备和灾后响应。灾前准备工作包括应急物资存储点的选址和物资的存储两部分。陈志宗等[4]分析了覆盖模型、p中心模型和p中值模型等常用的选址模型，但是上述模型并没有考虑到重大突发事件的特点，而是建立了一个兼具公平与效率的多目标决策模型，整合了上述经过的选址模型；葛春景等[5]为了应对重大突发事件过程中受灾点的多点同时需求和多次需求问题，建立了应急服务设施布局的多重数量和质量覆盖模型；杜博等[6]则研究了动态选址问题，基于灾情信息更新构建了一种反应式修复和调整策略的新建设施“重选址”模型。

灾后响应阶段的工作是应急物资的分配和分配，其核心是将足够的应急物资第一时间运送到相应的受灾点，该阶段需要考虑的因素多且复杂。张华丽等[7]等着眼于应急物资的配送研究，考虑了灾后响应中需求的随机性，路网通行能力的下降，设施点失灵和多式联运等情形，建立了多目标定位-路径模型；程碧荣等[8]研究了应急物资供应不足的背景下灾后响应中的物资分配和路径优化问题；刘长石等[9]也是研究了灾后响应的物资配送问题，先后考虑了应急路网连通情况、时间窗限制、车辆随机行驶时间、应急物资满载直配与巡回配送等特性；胡忠君等[10]侧重于应急救灾中的物资公平分配问题，并以此为模型优化目标；朱莉等[11]则面对灾后应急救援工作涉及的多种异构过程，包括物资调配，伤员救援，灾民疏散三种活动，构建了各类车型协同的运输路径优化模型；Sheu J B等[12]从应急物资供应商分组与合作的角度对灾后响应问题进行了研究，发现应急物资供应商的分组与合作可以明显减小救济的不均衡水平。

也有学者进行了兼顾灾前准备和灾后响应两阶段的研究。Espíndola O等[13]研究的是面对大规模洪涝灾害时，多个人道主义组织协同应急救灾的优化问题，兼顾两阶段，旨在降低救灾成本的同时实现更高的应急满意度，并以2013年墨西哥一洪水灾害为例，说明了其模型与体系的有效性和必要性。

灾害的应急管理充满了诸多不确定性，尤其是各地区灾情严重程度的不确定性，所以有必要在优化模型中引入随机性。Hoyos M C等[14]就随机模型在灾害运营管理中的应用做了全面而深入的文献综述；Garrido R A等[15]建立了随机规划模型优化应急物资的库存水平。

综合两阶段应急管理和随机性，王海军等[16]利用情景分析法模拟了不同程度的地震灾害发生的概率及需求，建立了随机规划模型研究两阶段应急决策问题，并利用混合遗传算法得到了系统成本最小化的情况下应急储备库选址，应急资源存储和调度方案，为应对突发自然灾害做出了有益的工作。但是该论文没有充分考虑到灾害应急管理的多目标性，而灾后及时有效的响应和灾前充分的准备又常常是冲突的，所以非常有必要考虑决策方案在多目标之间的权衡。

综上，本文以洪涝自然灾害为背景，综合考虑了多种应急物资，灾情严重程度的不确定性和应急救灾的多目标性，将应急管理中的灾前准备和灾后响应两阶段集成优化。通过设置最大救援时间的大小以反映救灾紧迫性程度，降低总运输延迟损失保证应急物资及时送达受灾点，降低总物资不足惩罚保证物资在受灾点的公平分配，进而建立了一定最大救援时间下的两阶段双目标混合整数规划模型。本文设计了一种多目标遗传算法用于模型的求解，可以得到模型的pareto最优解，并进一步得到不同最大救援时间的洪涝灾害应急方案，最后结合算例给出了确定最大救援时间的方法，进一步适应了决策者不同需求。

1 模型准备

1.1 问题分析

假设有一洪涝灾害多发地区，经过灾前调研确定了若干待选物资存储点，本文需要根据洪涝灾情的预测，确定最优的应急物资存储和分配方案，以在洪灾发生后第一时间将足够的应急物资配送到受灾点，缓解灾害给人们造成的伤害。由于灾前的应急物资存储方案会影响到灾后的应急物资分配决策，进而影响到抗洪救灾的效果，而应急物资的分配决策逆向决定了应急物资的存储方案，所以必须综合考虑灾前准备和灾后响应两阶段。

基于此，本文利用情景分析法刻画灾害情景，建立了两阶段多目标混合整数规划模型，第1阶段是洪灾发生前的物资存储决策；第2阶段是洪灾发生后，在第1阶段应急物资的存储方案的基础上，进行一定最大救援时间条件下的应急物资分配决策。考虑到应急管理的核心是在灾害发生后及时有效地展开救援，即第二阶段的灾后响应，所以将优化模型的目标1设定为最小化灾后响应阶段的物资分配成本，由总物资不足惩罚和总运输延迟损失两部分组成，目标2设定为最小化灾前准备和灾后响应两阶段的总成本，灾前准备的成本由物资存储点的建造成本和物资存储成本两部分组成，灾后响应和灾前准备的成本最小化是互有矛盾的。然后本文设计了多目标遗传算法用于模型求解，得出的决策方案最大程度保障了受灾点需求的同时，兼顾了灾前物资存储的成本较小化。

1.2 模型假设

为了简化问题同时尽量符合实际情况，模型考虑以下假设：

(1)假设自然灾害为洪涝灾害，考虑应急分配车、净水设备、帐篷、棉被、应急包和方便食品等六种应急物资，并通过单位待紧急转移安置人口所需应急物资的系数将六种物资折合成一种假想物资，得到各受灾点假想物资需求量，折算方式如下：

(1)

其中：dj(ξ)为ξ情境下受灾点j所需假想物资的需求量；qj(ξ)为ξ情境下受灾点j紧急转移安置人口总数；rk为单位受灾人口所需相应应急物资的系数，受灾点的灾情越严重，rk越大。

(2)假设待选物资存储点的位置是已知的，也就是本文不涉及物资存储点的选址问题，而是侧重于应急物资的灾前存储和灾后分配决策。

(2)假设根据历史洪涝灾害的灾情分布、严重程度和救援经验，以及新兴的气象预测技术，可以初步预测不同严重程度的洪灾发生的概率和位置，以及相应情景下，各受灾点待紧急转移安置人口数和各应急物资折算系数。

(3)设置最大救援时间，反映决策者对总体抗洪救灾紧迫性的判断，假设其为外生决策变量。若一受灾点到一存储点的运输时间小于等于最大救援时间，即该物资存储点可能给该受灾点分配救援物资，反之，不考虑该救援路线。

(4)考虑物资分配的公平性问题，即受灾点分配到的物资要与其实际需求匹配。因此，模型中设置了受灾点单位物资不足的惩罚，假设灾情严重的地方该惩罚越大，提高其获得有限物资的优先级。

(5)洪涝灾害发生后，首要任务就是及时将应急物资运送到受灾点，尤其是灾情严重的地方，物资耽误会对灾区人们造成更深的伤害。为此，模型中设置了单位时间、单位物资的运输延迟损失，假设灾情严重的地方，该值更大。

(6)考虑到灾后响应的关键是灾害发生后应急物资分配的公平性和配送的及时性，所以不考虑物资配送过程中的运输成本。

1.3 符号说明

符号说明i受灾点i∈{1,2,…,M}j待选物资存储点j∈{1,2,…,N}Bi物资存储点i的最大存储能力fi在i处建造物资存储点的固定成本hi物资存储点i的单位物资存储成本k(ξ)情景ξ发生时单位时间、单位物资未能第一时间送达受灾点造成的延误损失ωj受灾点j需求未被满足的单位物资不足惩罚tij(ξ)情景ξ发生时从存储点i到受灾点j的运输时间T外生的最大救援时间Cj{i∈I|tij⩽T}能够给受灾点j配送物资的存储点i的集合Di{j∈J|tij⩽T}能够被物资存储点i覆盖的受灾点j的集合p(ξ)情景ξ发生的概率dj(ξ)情景ξ下受灾点j假想物资需求量αj(ξl)情景ξ下受灾点j最低需求满意度si物资存储点i存储的物资总量zi在待选物资存储点i存储物资则为1,反之为0yij由物资存储点i向受灾点j配送物资则为1,反之为0xij物资存储点i到受灾点j的应急物资运输量Q灾后响应阶段应急物资分配总成本E(Q)不同洪灾情景下应急物资分配总成本的期望C灾前准备阶段应急物资存储点建造成本及物资存储成本F两阶段总成本

2 两阶段双目标混合整数规划模型

本文建立的两阶段双目标混合整数规划模型如下:

(2)

minF(z,s)=C(z,s)+Eξ[Q(z,s,ξl)]

(3)

(4)

(5)

其中，式(2)为目标函数1，使得不同情景下灾后响应阶段应急物资分配成本的期望值最小化；式(3)为目标函数2，使得不同情景下两阶段总物资存储成本及分配成本最小化；式(4)计算了在给定z和ξl的情况下，灾后响应阶段应急物资分配的总物资不足惩罚和延误损失；式(5)给出了在给定应急物资存储方案下，灾前准备阶段物资存储点建造成本及物资存储成本；式(6)反映了存储点i存储的物资总量受其存储容量的限制；式(7)、(8)为灾前准备阶段的决策变量；式(9)保证了至少有一个物资存储点可以向受灾点j配送物资；式(10)表示若存储点i到受灾点j的运输时间不能超过最大救援时间，则不能展开救援；式(11)为分配给受灾点j的物资量不大于其需求量；式(12)保证了分配给受灾点j的物资不能低于其最低需求满意度；式(13)控制了来源于物资存储点i的总物资不超过其存储量；式(14)、(15)为灾后响应阶段的决策变量。

3 基于多目标遗传算法的模型求解

大规模多目标混合整数规划问题属于NP-hard问题。本文根据决策变量的类型结合了染色体二进制编码和自然数编码，并在生成新的染色体的过程中根据模型的约束条件进行了调整。为了获得多目标优化模型更好的pareto解，本文借鉴了基于非支配解排序的遗传算法(Non-dominated Sorting Genetic Algorithm II, NSGA-II)中的非支配解排序和精英保留机制，并结合遗传操作，使得模型能在较短的时间内获得较好的pareto解。

算法流程:

(1)染色体的编码与种群初始化

每个染色体由两个片段组成，片段一采用二进制编码，对应决策变量zi(ξ)，片段二采用自然数编码，对应决策变量xij(ξ)。编码要符合以下三个约束条件：①片段一中0的位置对应的储备点i′，片段2中存储点i′对应的N个位置，全部置0，即未选用的储备点无法给任何受灾点配送物资；②若ξ情景下存储点i到受灾点j的运输时间tij(ξ)大于最大救援时间T，则片段2中对应位置置0，即不考虑运输时间超过最大救援时间的存储点和受灾点之间的物资配送；③ξ情景下受灾点j所需的总物资不超过其需求量dj(ξ)，也不低于其需求满足率αj(ξ)dj(ξ)，对应的存储点i存储的物资不超过其最大容量Ui。满足上述约束条件的情况下随机产生一定数目的染色体以初始化种群，种群规模为N。

(2)计算适应度函数，得到当前子代的非支配染色体

考虑到适应度函数是越大越有利于种群进化，本文中的两个目标是越小越好，所以取两个目标的倒数作为适应度函数。为了计算适应度函数，作以下定义:

si=max{si(ξ1),…,si(ξl)},∀i=1,2,…,M

(16)

(17)

得到当前种群所有染色体对应的适应度函数之后，进行快速非支配染色体的排序，文献给出了快速非支配排序的具体操作[17]，目的是找出当前子代中无法在两个目标上同时得到优化的染色体，将其作为种群的精英染色体。

(3)遗传操作

对种群中不属于精英染色体的其他染色体进行遗传操作，需要注意两个片段分别进行遗传操作，并且交叉和变异产生新的染色体时，都要根据(1)中的三个约束条件对染色体进调整。

①交叉，根据给定的交叉概率Pc随机选择父代个体进行交叉，使用部分映射交叉法得到新的染色体；

②变异，根据给定的变异概率Pm随机选择染色体进行变异，得到新的染色体；

③选择，将交叉、变异操作得到的新的染色体以及父代种群的精英染色体进行非支配解排序，按照排序结果选择与原种群规模相同的新种群。

(4)进化迭代

设置最大进化代数MAXGEN，重复步骤(2)和(3)，迭代次数达到MAXGEN，算法结束，得到模型的pareto最优解。

4 算例

4.1 算例构造

本文假设有一洪涝灾害多发地区，有关部门通过调研，确定了5个待选物资存储点，表1给出了待选物资存储点的容量上限、建造成本和存储成本。15个受灾点，每种受灾点可能发生四种灾害情景：ξ1，ξ2，ξ3，ξ4，灾害严重程度依次降低，每种情景发生的可能性分别为：0.523，0.275，0.113，0.089，表2给出了四种情景下受灾点所需假想物资的量。表3给出了物资存储点i到受灾点j的运输时间矩阵(基于物资存储点和受灾点的位置已知的假设)。问题是需要确定两个目标下pareto最优的灾前应急物资存储方案及灾后应急物资分配方案。

表1 待选物资存储点基本参数

表2 四种情景下各受灾点假想物资需求量

表3 情景A下物资存储点i到受灾点j的运输时间矩阵t1

4.2结果分析

(1)在最大救援时间为6，即T=6的条件下

利用MATLAB编写多目标遗传算法，设置种群规模N=50，最大进化代数MAXGEN=100，交叉概率pc=0.75，变异概率pm=0.01，得到多目标混合整数规划模型的pareto最优解如图1。

①如果决策者更看重第二阶段的决策：

根据图1，方案1，2对应的E(Q)较小，分别为4005，4523。

方案1对应的最优应急物资存储和分配方案如表4(以情景A为例)。

图1 多目标混合整数规划模型pareto最优解

表4 应急方案1

方案2对应的最优应急物资存储和分配方案如表5(以情景A为例)。

表5 应急方案2

从表中可以看到在应急方案1下，5个待选物资存储点都作为了实际的物资存储点，在应急方案2下，除了待选物资存储点5之外都作为了实际的物资存储点，两个方案下15个受灾点所需应急物资都得到了完全的满足。

在实际应急方案的决策中，决策者可以根据实际情况选择方案1或2的一种，方案1第二阶段应急物资分配成本E(Q)为4005，需要建造5个应急物资存储库，方案2E(Q)为4523，但是只需要建造4个应急物资存储库。

②如果决策者更看重两阶段的决策：

根据图1，方案5，6对应的总成本F最小，分别为1.171×106，1.151×106。

方案5对应的最优应急物资存储和分配方案如表6(以情景A为例)。

表6 应急方案5

方案6对应的最优应急物资存储和分配方案如表7(以情景A为例)。

表7 应急方案6

方案5和6下所有受灾点的需求同样得到了完全的满足，决策者可以根据实际情况选择应急决策方案5或6的一种，方案5两阶段总成本F为1.171×106，第二阶段应急物资分配成本E(Q)为5187，需要建造3个应急物资存储点，方案6对应的F为1.151×106，E(Q)为5916，只需要建2个应急物资存储点。

(2)更改最大救援时间T

最大救援时间T越小，要求抗洪救灾越及时，受运输距离限制，此时一个物资存储点所能服务的受灾点数目越小。

用多目标遗传算法分别得到不同最大救援时间T下模型的pareto最优解，不同最大救援时间下的pareto最优解的个数Tn，结果如表8。

表8 不同最大救援时间下pareto最优解的个数

再以最大救援时间T为横坐标，最优的第二阶段决策目标E(Q)和两阶段决策目标F(×106)为纵坐标，结果如表9和图2。

表9 不同最大救援时间下最优E(Q)、最优 F(×106)

图2 最优E(Q)和F随最大救援时间T变化结果图

结合表8和图2可以直观地看出，随着最大救援时间T的增加，对应的pareto方案的数目Tn、E(Q)以及F的值保持不变，但是随着T的减小，对应的pareto方案的数目Tn、E(Q)以及F的值会有明显的变化，并且pareto方案的数目与F的减小幅度是相对比较均匀的，这与实际情况是相符的，最大救援时间T越小，说明救灾的紧迫性越高，要求救灾越及时，对应的灾前准备和灾后响应所需的成本越高。而E(Q)的减小却是突变的，当T的值由4.2减小到4.19时，E(Q)由4005突变到4143，这与我们的直观想象是有出入的，说明救灾的过程中，在最大救援时间临界位置，灾后响应阶段应急物资分配成本E(Q)对T的变化相当敏感，这也反映了救灾工作的复杂性与紧迫性。

通过图2，还可以得到以下三点用以确定最优的最大救援时间T的结论：

①若T太大，起不到约束作用，即T≥5.7，在该区域，随着T的改变，目标F和E(Q)的值保持不变，这与现实情况相符合；

②T没有必要太小，不仅不能改善应急救灾的效果，反而会增加灾前准备阶段的成本，即4.2

③结合1和2的分析，本案例中最优的最大救援时间是5.7。

5 结语

综上，本文基于构造的灾害情景，利用多目标混合整数规划模型和改进的遗传算法，得到了pareto最优的灾前准备和灾后响应方案，解决了洪涝灾害两阶段的应急管理问题。根据本文的研究结果，决策者可以根据不同的需求进行不同的应急决策。以最大救援时间T=6为例，若决策者更关注应急物资分配的第二阶段，即保证灾害发生时的损失尽可能小时，可以选择应急方案1或2；若决策者更关注灾害应急管理的准备和响应全过程，即使得两阶段总成本尽可能小时，可以选择应急方案5或6。所以在应对洪涝灾害时，利用本文的模型与算法得出的应急方案可以在不同的目标下进行合理的取舍，有效降低灾害应急的成本，使得灾害给人民生命财产造成的损失降到最低。在以后的工作中，我们将细化洪涝灾害情景，考虑受灾人员撤退、转移和安置问题，以及设计更加精确有效的算法。