设施失灵风险下不确定需求应急定位-路径鲁棒优化研究

孙华丽，项美康

(上海大学管理学院，上海 200444)

1 引言

地震、洪涝和雪灾等自然灾害的频繁发生不仅威胁着人类的生命，也对国家经济运转和社会稳定发展产生重大影响。科学地进行应急救援设施选址和应急救援物资配送体系优化可以最大限度地降低灾害带来的损失。突发灾害具有破坏力强，难以准确预测等特点，常致使道路或救援设施等受损，应急物资需求难以准确预测，增加救援物资配送工作的挑战性。应急物流定位-路径(location-routing problem，LRP)问题将应急救援设施的选址问题和救援物资配送路径问题集成研究[1]，可以增强应急救援物流系统的抗风险性。

应急物流定位-路径优化问题受到国内外很多学者的关注。早期学者对单目标信息确定的应急定位-路径问题进行研究。曾敏刚等[2]将减灾系统定位-路径问题划分为应急设施选址和应急资源运输路线安排两个子问题，建立了最小化总成本为目标的应急LRP优化模型，采用混合启发式算法进行求解。王绍仁和马祖军[3]以最小化总救援时间为目标，设计了基于两阶段分解思想的“三角”启发式算法。也有学者对信息确定的多目标应急定位-路径问题进行了研究， Abounacer等[4]构建了以运输时间和应急设施点规模最小为目标的应急物流定位-路径模型，并将Pareto优化算法运用到模型的求解中。Wang Haijun等[5]建立了一个考虑运输时间、总成本和分配可靠性的非线性整数规划定位-路径模型，并以汶川地震为例，对模型与算法的有效性进行验证。楼振凯[6]以应急物流系统响应时间最小为上层目标，以配送成本和时间惩罚成本之和最小为下层目标，建立了设施定位-运输路线问题的双目标规划模型。还有学者对信息不确定的应急定位-路径问题进行了研究。针对需求的不确定，Goli和Alinaghian[7]以最长路径救援时间最小为目标建立定位-路径模型。Caunhye等[8]建立了最小化设施建设成本和最长路径救援时间为双目标的两阶段LRP模型。李双琳等[9]以最小化应急物资配送总时间和受灾点应急物资未满足的总损失为双目标，建立了多式联运问题优化模型，采用非支配排序多目标遗传算法求解。对于时间不确定的应急定位-路径问题研究，Toro-Díaz等[10]建立了整数规划的选址-配送决策模型和解决排队及拥堵现象的超立方体综合模型，采用改进的遗传算法求解。Zarandi等[11]考虑需求点的时间窗约束，基于模糊机会约束规划建立了最小化总成本模型。也有学者开展多不确定信息的应急定位-路径问题研究，刘长石等[12]考虑救灾点应急物资需求量的不确定及车辆行驶时间的随机性，以最小化救援物资运达总时间和总成本为目标，建立了模糊机会约束规划模型。Bozorgi-Amiri和Khorsi[13]等假设应急资源需求、应急救援时间和费用不确定，建立了以需求不满足率、总救援时间和总救援成本最小为目标的LRP模型。Moreno等[14]考虑应急救援中多阶段、多物资、多模态环境下的不确定问题，以救援总成本最小为目标建立两个随机混合整数规划模型。孙华丽等[15]假设需求量和单位运输费用均为模糊变量，采用模糊机会约束理论，以最小化系统总成本和灾害损失成本之和为双目标建立了应急物流定位-路径模型。Bai Xuejie[16]考虑到需求和道路连通性的不确定，以物资需求的未满足率、应急响应时间和总成本最小为目标建立多目标期望值模型。Chang Keliang等[17]假设需求及运输速度不确定，建立了最大化最长路径满意度和最小化总成本及道路运输能力为目标的非线性定位-路径问题。

综上，当前研究的不足如下：(1)实际中很多不确定信息是离散的，或随机变化的，而现有文献多是用模糊数来表示需求等不确定信息，或假定其服从某种概率分布。(2)实际救援中，因灾害的破坏性或次生灾害常造成区域内道路等基础设施中断或设施点失灵，而现有文献很少考虑上述风险对救援系统的影响。为此，针对需求的不确定，本文采用区间数进行表述，基于偏差鲁棒优化的思想解决应急设施点的失灵风险，采用直升机进行运输以规避路径中断风险，构建了最小化总救援时间及系统总成本的双目标LRP鲁棒优化模型，基于遗传算法对其求解。

2 模型描述

2.1 问题描述

突发自然灾害后，快速选择机场，火车站等作为临时应急设施点，及时安全地将救援物资运送到各个受灾点是应急救援的关键。由于存在道路受损中断风险，采用直升机将物资从临时应急设施点配送至灾害需求点，但次生灾害可能导致临时设施点突然失灵，无法及时完成受灾点的物资配送任务。问题是如何在物资需求不确定，设施点存在失灵风险下，集成救援设施点选址和物资运输路径规划，以最小化系统总成本及总救援时间。本文假设灾害发生区域有l个应急候选救援设施点，n个物资需求点，h架救援直升机。所有直升机都为同质的。每个候选应急设施点都可能失灵，但每次失灵至多一个设施点，失灵的设施点不能提供服务。此时，直升机选择从离该需求点最近的临时应急救援设施点运送物资到需求点。救援直升机容量不超过任何一个应急候选救援设施点的容量；每个需求点只能被一架直升机服务，其需求量不超过直升机容量。每架直升机起飞于应急设施点，完成任务后原地待命。

2.2 符号说明

为了方便描述问题，定义如下符号和变量：

临时应急救援设施点集合J={1,2,3,…,l},j∈J；灾区物资需求点集合I={1,2,3,…,n},i∈I,r∈J∪I；救援直升机集合H={1,2,3,…,h},h∈H；dij-两点之间的距离；qri-灾区物资需求点i的物资需求量；dhi-直升机到达需求点i时已经行驶的距离；thi-直升机到达点i的时间；vh-直升机的速度；qli-需求点i的物资缺少量；wji-直升机从应急设施点j运送到灾区物资需求点i的物资总量；cj-选择应急救援设施点j的固定费用；cl-直升机单位载货量的装载费用；ct-直升机单位距离单位运量的运费；m1,m2分别为临时应急救援设施点，救援直升机的最大装载能力。

Xji=

2.3 模型构建

在前述假设基础上，可以构建应急救援物资配送的双目标确定LRP模型如下：

(1)

(2)

*qri,h∈H

(3)

(4)

(5)

(6)

(7)

(8)

m2≤m1

(9)

dhi=(dhr+dri)Zrih,r∈(I∪J),

i∈I,h∈H

(10)

(11)

Uj,Xji,Zrih∈{0,1}

(12)

模型中式(1)为最小化系统总救援时间，式(2)为最小化包括应急救援设施点的固定费用、直升机的装载费和运输费等系统总救援成本。式(3)表示直升机h在保证不超过自身装载能力的前提下，尽可能地满足其所服务需求点的需求量；式(4)表示直升机装载能力约束；式(5)表示应急设施点的容量限制；式(6)保证需求点接受直升机和应急设施点服务的唯一性；式(7)表示直升机不会从未选中的应急救援设施点发出；式(8)保证应急救援设施点之间不连通；式(9)表示应急救援设施点与直升机容量关系；式(10)直升机飞行距离dhi的表达式；式(11)给出了直升机到达救援物资需求点i的时间表达式；式(12)为整数变量非0即1约束。

2.4 双目标的转化

(13)

2.5 基于鲁棒优化的不确定信息处理

鲁棒优化基于鲁棒控制思想处理不确定数据集合，它不必掌握不确定参数的分布函数或取值的发生概率，通过求解问题的鲁棒对应转换模型以求解不确定优化问题[18]。灾害发生时，决策者无法及时准确得到受灾点物资需求情况，采用区间型集合描述受灾点物资需求情况：

qri={qi|qi∈[q1i-q2i,q1i+q2i]},i∈I

(14)

q1i表示需求点i物资需求量的名义值，q2i表示偏离名义值的最大扰动值。在实际需求中，qri一般可根据灾害级别、受灾人口密度等信息预测。各种物资到达区间边界的可能性极小，因为若qri=q1i-q2i，会造成需求的预期估计不足；若qri=q1i+q2i，为绝对鲁棒问题，基于最大需求的情况会有失最优性决策的意义，造成物资的浪费。为此，参照相对鲁棒模型[19]，在q2i中引入需求控制系数Γh描述需求的变化情况(控制系数越大，需求不确定越大)，代入式(3)中得：

h∈H

(15)

为了求解上述模型，引入引理1对式(15)进行转化。

(16)

则等价于下面问题的最优目标值：

0≤zij≤1,∀j∈Ji

(17)

引入需求扰动系数ηh来控制需求量扰动的范围，进而调节模型解的保守性和最优性。依据强对偶定理及上述引理将前述模型转化为下列鲁棒优化模型：

ηh≥0,h∈H

ρhi≥0,h∈H,i∈I

(18)

(19)

因此，上述问题可转换为以(1)-(2)为目标函数，以(4)-(13)和(18)-(19)为约束条件的设施点失灵风险下不确定需求定位-路径鲁棒优化模型。

3 遗传算法设计

本文的应急物流LRP问题是一个NP-hard问题，精确算法很难有效求解，采用遗传算法对其进行求解。

3.1 编码

将每个染色体分为三段，用自然数进行编码，第一段表示各救援直升机归属的应急设施点，有h个基因位，h为救援直升机数目，每个基因位都是在1到l的自然数中随机产生；第二段表示将物资配送到各个受灾需求点的救援直升机编号，随机产生；第三段表示救援路径中各受灾需求点的服务顺序，长度为n，每个基因位从1到n的自然数中随机产生，与第二段基因位对应，但不能相互重复，则每条染色体长度可表示为(h+2n)。

3.2 初始种群及适应度函数

随机产生N个初始种群，设第i条染色体为δi；第i条染色体的总目标函数值为Z；M为正大数。适应度函数为：

3.3 遗传操作及终止条件

染色体的选择策略采用轮盘赌和精英保留相结合的方法。染色体第一段基因采用单点交叉和对换变异操作；第二段基因使用两点交叉和对换变异操作，第三段基因使用部分匹配交叉和逆转变异操作。当遗传算法的繁衍代数达到最大值时，输出最优个体，终止算法。

4 算例分析

为验证相对鲁棒优化方法处理需求不确定和偏差鲁棒思想解决设施点失灵的有效性和模型的适用性，本部分设计三个算例进行仿真分析。参照已有文献并经试算，种群规模设置为100，最大迭代次数为500，权重为0.6，交叉概率和变异概率分别为0.7和0.05。采用Matlab7.11.0 (R2016a)编程，并在CPU为Intel 2.60GHz，内存为4G的计算机上进行仿真求解。

算例1选取4个候选应急救援设施点，15个受灾需求点，8架同质的直升机运输物资。部分数据选自文献[3]的LRP问题。直升机飞行速度为210km/h，每份物资每千米的运输费用为30元，每份物资装载费为30元，最大装载量为400份。设需求扰动系数为5%-20%，控制系数为1-15。表1-表2为候选应急救援设施点和受灾需求点的相关数据。

表1 应急设施点数据

表2 受灾需求点数据

4.1 不确定需求处理的有效性

对于不考虑设施点失灵和仅存在一个设施点失灵的情景，采用相对鲁棒优化方法处理需求不确定对应急救援时间和成本的影响来验证该方法的有效性。

限于篇幅，仅列出无设施点失灵和仅设施点1失灵情景下不同控制系数和需求扰动系数(5%，10%，15%，20%)对总目标函数值的影响，如图1和图2所示。由图可看出，无论是否考虑设施点失灵，总目标函数值均随着控制系数的增加而增大，且同一控制系数下需求扰动系数越大，总目标函数值增加越快。无设施点失灵情景下的总目标函数增长速度与仅考虑设施点1失灵情景下的总目标函数增长速度相似。

图1 无设施点失灵情景下总目标函数增长比

图2 设施点1失灵情景下总目标函数增长比

表3是不考虑设施点失灵和仅考虑设施点1失灵情景下，需求不确定时的目标函数值。Z1,Z2,Z含义同模型目标函数。由表3可知，无论是否考虑设施点失灵，总目标函数值和系统总成本随需求变化范围的增大，均呈现增长趋势；总救援时间目标函数基本稳定在5.5-6.7小时，且受需求不确定的影响较小，这是因为应急救援直升机均仅需飞行一次即可满足各需求点的物资需求量。在总目标函数值方面，不确定需求鲁棒优化模型与需求确定模型(此时控制系数为0)的偏差呈现递增趋势。在需求不确定量(需求控制系数、需求扰动系数)相同时，仅考虑设施点1失灵情景的总目标函数值总略大于不考虑设施点失灵时的取值，这是因为有设施点失灵时，整个应急救援系统增加了直升机的额外运输成本，但是这种方案是鲁棒的。而不考虑设施失灵情景，一旦设施点失灵，方案将变得无效。

表3 不同情景下目标函数值

续表3 不同情景下目标函数值

图3 控制系数对偏差鲁棒后悔值的影响

因此，可以得出结论，需求信息不确定性越大，为了满足所有需求，其系统总成本将越大。在实际中，可以依据需求不确定情况确定需求控制水平，最终制定科学的方案。

4.2 设施点失灵处理的有效性

为了验证偏差鲁棒优化方法处理设施点失灵风险的有效性，对比不同需求下偏差鲁棒后悔值的变化情况。图3给出了在需求控制系数为0-15，所有可能情景(仅一个设施点失灵)的偏差鲁棒后悔值随着控制系数的变化情况。由图可知，后悔值最大为6.50；控制系数为9时，后悔值最小为2.34；其次控制系数为5时，后悔值为3.47，其余均在最大后悔值附近，总体上偏差鲁棒后悔值不受控制系数的影响，即模型的最优解对大部分情景下的后悔值比较均衡。这说明偏差鲁棒优化方法能有效处理设施点失灵风险。

4.3 模型的适用性

算例2 为验证模型的适用性，在算例1的基础上增加候选应急救援设施点、受灾点和直升机数量，生成另外两个算例，其中算例2是8个候选应急设施点，20个受灾点，10架直升机。新增候选应急设施点的坐标分别为E5(20,50)、E6(100,235)、E7(225,170)、E8(70,15)，其对应的容量和选择成本分别由集合{1000,800,1000,800}和集合{20841,21961,17570,17497}给出。新增加受灾点分别为D16(60,30)、D17(40,120)、D18(80,40)、D19(150,170)、D20(230,100)，其对应的物资需求名义值由集合{60,20,30,40,40}给出，其他信息同算例1。分别求出需求控制系数为4、12、20时，需求扰动量为5%、10%、20%，不考虑设施点失灵和仅考虑设施点1失灵时确定模型与鲁棒优化模型的总目标函数值对比情况如表4所示。

算例3再次增加候选应急救援设施点、受灾点和直升机数量，使问题变为10个候选应急设施点，25个受灾点，16架直升机。限于篇幅，新增候选应急设施点和受灾点相关信息不再给出，其他信息同算例2。分别求出需求控制系数为5、15、25时，需求扰动量为5%、10%、20%，存在设施点失灵风险的确定模型与鲁棒优化模型的总目标函数值如表4所示。

由表4可以看出，确定模型的总目标函数值随问题规模的扩大而增大；而鲁棒优化模型则在需求不确定范围增大时，总目标函数值也随着增大，且无论是否考虑设施点失灵，鲁棒优化模型的总目标函数值始终大于确定模型的值。表4中的“可行解个数”一列为不考虑设施点失灵时鲁棒优化模型的可行解情况。具体操作如下：在需求名义值区间中随机取20个随机数，将这20个数分别代入不考虑设施点失灵下鲁棒优化模型，得到选址方案，在此选址方案的基础上，观测解的可行性。这时，只有在设施点1刚好未被选择为服务的设施点时，才能得到可行解，因此，表中可行解个数多为0。由此说明鲁棒优化处理需求不确定和设施点失灵应急定位-路径优化问题的适用性。

表4 鲁棒模型与确定模型解的比较

5 结语

本文对应急设施点失灵风险下的需求不确定应急物流定位-路径问题进行了深入研究，针对灾害、后的路径风险，采用直升机运送模式规避。以最小化系统总成本和救援运输时间之和为双目标，分析采用相对鲁棒优化的区间型数据描述方法处理应急需求的不确定和偏差鲁棒优化思想处理应急设施点的失灵风险。为了说明鲁棒优化方法和模型的适用性，对三个算例进行仿真对比分析，结果表明，无论设施点是否失灵，总救援成本和总目标函数值随着需求不确定的增大，呈现递增趋势，而总救援时间几乎不受需求不确定的影响。偏差鲁棒优化处理各设施点失灵时的后悔值基本不受需求不确定的影响。总的来说，采用相对鲁棒优化处理应急物流定位-路径问题的需求不确定和采用偏差鲁棒优化处理设施点失灵风险均表现出较好的适用性，从而提高决策者制定救援方案的抗风险性和科学性。

然而，由于直升机的运输距离受限且费用大，在应急物流系统中，后续研究将考虑车辆运输为主，直升机运输为辅的多式联运三级路网模式，并且同时考虑道路运输超期风险和设施点失灵风险。