多类应急资源配置的鲁棒选址-路径优化

彭 春，李金林，王珊珊，冉 伦

(北京理工大学管理与经济学院，北京 100081)



多类应急资源配置的鲁棒选址-路径优化

彭 春，李金林，王珊珊，冉 伦

(北京理工大学管理与经济学院，北京 100081)

本文基于应急资源配置的灾前预防准备和灾后的响应分配，在多类应急资源配置选址-路径优化名义模型的基础上，考虑多类应急资源成本的不确定性，引入两类不确定集合(box 和ellipsoid)刻画该不确定性，分别建立多类应急资源鲁棒选址-路径优化模型，运用鲁棒优化方法，将其转化为易求解处理的鲁棒等价模型，并通过CPLEX和GAMS混合编程算法求解。最后，本文对我国四川北部和西部自然灾害多发区的19个县市进行应急资源优化配置分析，确定应急资源临时供应点的最优选址布局、应急资源的分配路径，同时考虑扰动比例的灵敏度分析，验证模型的可行性和有效性。结果表明在其他条件相同的情况下，ellipsoid不确定集合下的鲁棒模型较保守，配置的总成本较高，因此决策者可以根据自己的风险厌恶程度选择不确定水平参数的值，确定应急资源的配置方案，进而为相关应急救灾部门在灾前预防准备工作提供决策支持。

应急资源；选址-路径；成本不确定性；鲁棒优化；不确定集合

1 引言

我国是世界上自然灾害严重的国家之一，灾害种类多，发生频率高，灾害损失严重。2009年国务院新闻办公室发布的《中国的减灾行动》白皮书中重点提出，建立完善的减灾工作管理体制和运行机制，灾害监测预警、防灾备灾、应急处置、灾害救助、恢复重建能力大幅提升，公民的减灾意识显著增强、减灾技能显著提高，人员伤亡和自然灾害造成的直接经济损失明显减少[1]。在应急灾害管理中，最有效的方式是尽力做好灾害发生前的预防和准备工作，以及灾后的第一时间应急救灾网络的响应工作，尽可能的降低灾后的损失和影响，具有重要意义。应急资源的配置问题，涵盖灾害发生前的应急物资的配置问题(选址和储备)和灾害发生后的资源分配问题(分配、路径)，具体包括临时救灾点的选址、应急资源运输的路径和分配，力图解决应急资源的供应地点应该选在何处，每个供应地点应配置多少资源，应急资源的运输路线及最优的调度资源数量，使得应急资源的需求被满足，总成本最小。

Altay和Green[2]通过分析之前已有成果，回顾OR/MS方法在应急灾害管理中的应用，并指出了几个未来研究方向，其中之一为如何度量应急管理过程中的不确定性；Galindo和Batta[3]在Altay, Green基础上，对近年来OR/MS方法在应急管理方面的文献进行综述，同时指出了新的方向，包括利用新的方法(如鲁棒优化)来建立优化模型。Mete 和Zabinsk[4]考虑不同的灾害类型及级别，建立两阶段应急医疗服务站选址布局的随机优化模型，考虑选址和资源的分配路径优化，并利用情景分析求解；葛洪磊和刘南[5]提出基于区域灾害系统理论来构建复杂灾害情景描述突发事件的复杂性和高度不确定性，建立两阶段随机规划模型，进行应急设施的定位决策、应急资源的库存决策和不同灾害情景下应急资源分配预案的制定。

早期对于应急资源配置的研究均假设应急资源的需求、成本或运输路线的信息(或概率分布)已知，但是实际上，由于对应急资源配置过程中存在较大的不确定性，获取准确数据或概率分布非常困难。目前研究应急资源配置问题主要途径之一是基于随机优化[4-8]，但随机优化存在一些局限：确定有代表性的情景及其概率比较困难；通常选取相对较少数量的情景，一定程度上限制了决策范围；目标为最小化期望成本，未能体现决策者的风险偏好，如最坏情况下的策略等；大多为NP难问题，需用启发式算法得到近似最优解。

近年来鲁棒优化方法得到了迅速发展，在一定程度上弥补了随机优化模型的局限，该方法早期由Ben-Tal等[9]提出，后经Bertsimas 和Sim[10]不断发展，其关键是如何衡量不确定性，以特定不确定集合的形式表示未知参数的信息，其目标为最优系统最坏情况下的绩效。此外，而且从某种程度上考虑了决策者的风险偏好。Ben-Tal 等[11]研究了不确定需求下的人道主义救援应急物流计划问题，基于interval不确定需求集合，提出了可调节仿射变换的鲁棒等价问题；Baron 和Naseraldin等[12]建立鲁棒网络设施选址模型，考虑多周期、多产品的不确定需求，确定新建设施的位置、数量、容量、产量等参数，且考虑box和ellipsoid需求不确定集合；张玲等[13]利用鲁棒优化方法建立基于interval不确定需求集合的灾后应急救灾网络规划模型；陈涛等[14]在调研国内外相关研究的基础上，以地震为背景提出了基于信息更新的资源调配决策问题，建立了两阶段鲁棒-随机优化模型；俞武扬[15]针对灾害发生前受灾地点的应急资源需求和交通网络的不确定性，建立了不确定网络结构下的两阶段应急资源鲁棒配置模型。从目前的文献来看，基于鲁棒优化的应急资源的配置问题研究较少，大多仅考虑选址(Location)、选址-分配(Location-allocation)决策，基本采用离散情景分析或者简单的interval或box不确定集合。

鉴于此，基于应急资源配置的灾前预防准备和灾后的响应分配问题，本文研究多类应急资源配置的鲁棒选址-路径优化分配问题，重点突出多类应急资源临时供应点的选址布局和各类应急资源的路径分配。考虑多类应急资源(水、食物、药品和帐篷等)成本的不确定性，引入两类不确定集合(box 和ellipsoid)来刻画应急资源的不确定成本，建立两个多类应急资源鲁棒选址-路径优化调度模型，确定应急资源最优的供应点布局、资源分配路径。由于鲁棒模型本身不易求解，借助鲁棒优化的独特优势，将其转化为易求解处理确定的鲁棒等价模型，同时引入两个不确定水平参数，调节解的最优性和鲁棒性；最后通过我国四川北部和西部自然灾害多发区的19个县市进行四类应急资源的优化配置分析，验证模型的可行性和有效性，为相关的应急救灾部门提供建议。

2 多类应急资源鲁棒选址-路径优化模型

2.1问题描述

假设在自然灾害发生前的预防准备阶段存在多个潜在的受灾点和应急资源供应的候选点，本文中受灾点同时也是应急资源临时供应的候选地点，考虑多类应急资源(食品、水、帐篷、药品等)的配置，要在潜在的受灾点中选出应急资源的临时供应点，并对各类资源的最优供应量和路径做出预决策，以满足灾区需求。基本的符号说明如下：D为所有的节点的集合，假设每一个节点既是受灾点j又是潜在的临时供应点i，i,j∈D；L为路线的集合，(i,j)∈L；M为应急资源种类的集合，m∈M；k为建立临时供应点的最大数量；fi为临时供应点i处的建立成本；tijm为在路线(i,j)上单位应急资源m的运输成本；djm为受灾点j处对应急资源m的需求量；vim为应急资源m在临时供应点i处的最大容量；Φ为一个充分大的数；cim为临时供应点i处应急资源m的单位成本。决策变量：xi=1，如果在受灾点i处建立临时供应点，否则xi=0；zijm为在路线(i,j)上应急资源m的调度数量；yijm为临时供应点i满足受灾点j应急资源m的比例。因此，应急资源配置的选址-路径优化名义(Nominal)模型为：

(1)

(2)

(3)

yijm≤xi∀i,j∈D,m∈M

(4)

(5)

(6)

(7)

(8)

xi∈{0,1},yijm,zijm≥0 ∀i,j∈D,m∈M

(9)

在名义模型中，目标函数式(1)为总成本最小化，包括建立临时供应点的成本、运输成本和资源成本；约束式(2)表示每个受灾点的需求都要满足；约束式(3)表示建立临时供应点数量限制；约束式(4)表示只有建立临时供应点才能够提供需求；约束式(5)表示临时供应点的应急资源分配量，即流入量与流出量之差，至少满足受灾点的需求；约束式(6)表示临时供应点的流入、流出和需求应该不大于容量限制；约束式(7)和(8)表示受灾点的流入、流出等于需求；约束式(9)为0-1变量和非负变量。

2.2不确定成本下应急资源鲁棒选址-路径模型

自然灾害发生前后，由于应急资源紧缺，资源成本波动较大，应急资源的成本具有明显的不确定性，因此，本文在名义模型的基础上，考虑应急资源的成本不确定性，分别引入box和ellipsoid不确定集刻画多类资源的不确定成本c，运用鲁棒优化方法，建立多类应急资源配置的鲁棒选址-路径优化模型。

(1)基于box不确定集合的应急资源鲁棒选址-路径模型

(10)

s.t.(2), (3), (4), (5), (6), (7), (8), (9)

当Γ=0时，box不确定集鲁棒模型等价于名义模型。此目标函数中存在内层最大化问题，接下来将其转换为更易于求解的鲁棒等价模型。

考虑内层最大化的线性规划问题:

0≤uim≤1,∀i∈D,m∈M

(11)

根据强对偶原理，该问题等价为(12)，其中ρim,θ为对偶变量。

ρim,θ≥0,∀i∈D,m∈M

(12)

综上，将(11)和(12)，代入问题(10)，将非线性的鲁棒模型转化为确定的线性鲁棒等价模型(13)，且该模型为混合线性整数规划问题，因此较易求解。

yijm≤xi∀i,j∈D,m∈M

xi∈{0,1},yijm,zijm,ρim,θ≥0 ∀i,j∈D,m∈M

(13)

(2)基于ellipsoid不确定集的应急资源鲁棒选址-路径模型

mint

(14)

(15)

(16)

令:

(17)

则:

(18)

因此，借助鲁棒优化，建立应急资源配置的鲁棒选址-路径优化模型，并转化为易求解处理确定的鲁棒等价模型。由于鲁棒等价模型为混合线性整数规划(13)或二阶锥规划(19)，当求解问题的规模不是很大时，尤其对于二次规划问题时，可使用现有的数学软件求解。本文所有代码用GAMS编程，并调用CPLEX中的分支-切割算法和内点算法求解。

mint

djmyijm+ΩW≤t

yijm≤xi∀i,j∈D,m∈M

xi∈{0,1},yijm,zijm≥0 ∀i,j∈D,m∈M

(19)

3 算例分析

四川北部和西部地区是地震、泥石流、滑坡等自然灾害发生比较密集的区域[16]，选取龙门山断裂带及其邻区作为地震等自然灾害发生的潜在区域。模型中的潜在的受灾点同时也是应急资源临时供应的候选地点，选取可能的受灾点有理县、汶川、茂县、都江堰、崇州、郫县、彭州、什邡、绵竹、安县、北川、江油、广汉、中江、三台、盐亭、射洪、大英和梓潼共19个县市，依次标号1, 2, …, 19，从其中选出5个应急资源临时供应点，满足各受灾点的需求。根据2014年四川省统计年鉴、物价水平以及各地区的人均GDP，考虑饮用水、食品、药品和帐篷四种应急资源，且1升水的体积为0.01立方米，1千克食品的体积为0.1立方米，1盒药品的体积为0.05立方米，1顶帐篷的体积为0.2立方米，各潜在的受灾点的各类资源的需求和临时供应点的仓库容量及建设成本如表1所示，其中各受灾点的需求是根据各地区人口密度估计；表2为各受灾点应急资源的单位成本，根据各受灾点的人均生产总值估计；路线(i,j)单位运输成本根据google地图的路线距离和单位资源的体积得到；本文考虑各类应急资源单位成本的不确定性，则成本的扰动比例ε为10%。

接下来选取Γ=Ω=7，扰动比例ε为10%，并且选取应急资源中的饮用水资源为例，对两个鲁棒选址-路径优化模型进行求解。通过算法求解，名义模型、box和ellipsoid不确定集合下的鲁棒模型的最优的选址点和运输路径分别见图1、图2、图3，其中椭圆表示选择的最优的临时资源供应点，箭头表示最优的分配路径，具体路线按照google地图上自动获得。在确定的名义模型和box不确定集模型中，均选取汶川、崇州、广汉、北川和三台共五个县市作为应急资源的临时供应点，但资源分配路径不同，例如确定模型中都江堰的饮用水来自于汶川，即汶川→都江堰，而在box不确定集合模型中，都江堰的饮用水来自于崇州，中间经郫县，即崇州→郫县→都江堰，即崇州作为饮用水的临时供应点，为崇州、郫县、都江堰供应饮用水，载满饮用水的车辆从崇州出发(先满足自身需求)，在前往都江堰的途中经过郫县，满足郫县的饮用水资源的需求(它的下一个节点是都江堰，并没有其它的分支)，然后继续沿着这个路线前往都江堰。表3为box不确定集下的鲁棒选址-路径模型的饮用水的调度分配量，正如图2所显示的应急资源的运输路径一样，其中北川为6个灾区县市提供饮用水资源；而ellipsoid不确定集模型的最优资源临时供应点则有所不同，具体是汶川、崇州、什邡、北川和三台，没有选取广汉，而新增加什邡，如表3和4中加粗显示的部分，因此饮用水的调度分配路径发生变化，如图3所示，表4为ellipsoid不确定集下的鲁棒选址-路径模型的饮用水的调度分配量，与表3相比，在其他所有条件不变的情况下，供应点北川供应的6个受灾点相同，但是饮用水资源的供应量发生变化，如表3和表4中加粗部分。类似，新增加的供应点什邡供应受灾点的需求也发生变化。

表1 潜在受灾点应急资源的容量限制、需求(万)及建设成本(万元)

表2 受灾点应急资源的成本(元/单位)

图1 名义( nominal)模型的最优选址布局和分配路径，资源：水

图2 box不确定集合模型的最优选址布局和分配路径，资源：水

图3 ellipsoid不确定集合模型的最优选址布局和分配路径，资源：水

当Γ=Ω=0时，box和ellipsoid不确定集合下的鲁棒模型与确定的名义模型等价，此时最小成本为5.68亿，图4为三个模型的总成本随不确定水平参数Γ,Ω变化的曲线，随着不确定水平参数的增加，总成本逐渐增加，其中Γ=Ω时，ellipsoid不确定集模型增加迅速，对于box不确定集模型，总成本不断增加，但是增加的幅度逐渐减少，当Γ≥19时保持不变，因为选取19个候选地点，则0≤Γ≤19，当Γ=19时，该问题等价于绝对鲁棒模型，此时总成本最大为6.25亿。但是ellipsoid不确定集模型的成本明显高于box不确定集模型，这是因为Γ=Ω时，ellipsoid不确定集的几何空间大于box不确定集，因此结果表明，对于相同参数设置的环境下，ellipsoid不确定集合模型比box不确定集合模型保守，成本较高。由于在鲁棒优化模型中不确定水平参数在一定程度上度量决策者的保守性和风险厌恶程度，因此决策者可根据自己的风险厌恶程度选择适当Γ和Ω，进而确定应急资源的分配方案。

表3 box不确定集下应急资源(水)的最优调度数量Γ=7,εi=0.1

表4 ellipsoid不确定集下应急资源(水)的最优调度数量Ω=7,εi=0.1

此外，改变扰动比例εi，选取5%、10%、15%，Γ/Ω分别取0, 1, 3, 5, 7, 9，此时在不同的不确定水平参数，不同的扰动比例组合下的最小总成本和最优的应急资源的临时供应选址点如表5所示。随着不确定水平参数和扰动比例的增加，最优的选址点发生变化，发生变化的部分加粗显示，最小总成本增加，但ellipsoid不确定集模型的成本相对较高，这与前面提到的ellipsoid不确定集合下的鲁棒模型较保守的结论一致。

表5 box 和ellipsoid不确定集及成本扰动比例组合下的总成本和选址点

图4 nominal, box, ellipsoid模型的总成本随不确定水平参数的变化

4 结语

本文基于应急资源配置的灾前预防准备和灾后的响应分配问题，考虑多类应急资源(饮用水、食品、药品、帐篷)成本的不确定性，引入两类不确定集合(box 和ellipsoid)来刻画应急资源成本的不确定性，并提出两个多类应急资源鲁棒选址-路径优化模型，这在一定程度上降低不确定性带来的风险。最后，通过我国四川北部和西部自然灾害多发区的19个县市的相关数据进行分析，确定最优的应急资源临时供应点选址布局、应急资源的运输分配路径方案，同时考虑资源成本扰动比例的灵敏度分析，验证模型的可行性和有效性。通过确定模型与两类不确定集合的鲁棒模型的比较，发现在其他条件相同的情况下，ellipsoid不确定集合下的鲁棒模型较保守，资源配置的总成本较高。由于在鲁棒优化模型中的不确定水平参数在一定程度上度量决策者的保守性和风险厌恶程度，因此决策者可以根据自己的风险厌恶程度选择适当不确定水平参数的值，确定应急资源的配置方案，进而为相关应急救灾部门在灾前预防准备工作提供参考和决策支持。然而本文仅考虑应急资源成本不确定性，而在应急资源配置过程中存在供给、需求及路径中断等不确定性，可以研究更多不确定因素，同时考虑动态多阶段的应急资源配置问题，这是接下来的研究方向。

[1] 中华人民共和国国务院新闻办公室. 《中国的减灾行动》白皮书[EB/OL].[2009-05-11].news.xinhua net.com/newscen-ter/2009-05111/cont-ent_12351082.htm.

[2] Altay N, Green W G. OR/MS research in disaster operations management[J]. European Journal of Operational Research, 2006, 175(1): 475-493.

[3] Galindo G, Batta R. Review of recent developments in OR/MS research in disaster operations management[J]. European Journal of Operational Research, 2013, 230(2): 201-211.

[4] Mete H O, Zabinsky Z B. Stochastic optimization of medical supply location and distribution in disaster management[J]. International Journal of Production Economics, 2010, 126(1): 76-84.

[5] 葛洪磊, 刘南. 复杂灾害情景下应急资源配置的随机规划模型[J]. 系统工程理论与实践, 2014, 34(12): 3034-3042.

[7] Jia Hongzhong, Ordóez F, Dessouky M. A modeling framework for facility location of medical services for large-scale emergencies[J]. IIE Transactions, 2007, 39(1): 41-55.

[8] Verma A, Gaukler G M. Pre-positioning disaster response facilities at safe locations: An evaluation of deterministic and stochastic modeling approaches[J]. Computers & Operations Research, 2015, 62: 197-209.

[9] Ben-Tal A, El Ghaoui L, Nemirovski A. Robust optimization [M]. Princeton:Princeton University Press, 2009.

[10] Bertsimas D, Sim M. The price of robustness[J]. Operations Research, 2004, 52(1): 35-53.

[11] Ben-Tal A, Do Chung B, Mandala S R, et al. Robust optimization for emergency logistics planning: Risk mitigation in humanitarian relief supply chains[J]. Transportation Research Part B: Methodological, 2011, 45(8): 1177-1189.

[12] Baron O, Milner J, Naseraldin H. Facility location: A robust optimization approach[J]. Production and Operations Management, 2011, 20(5): 772-785.

[13] 张玲, 王晶, 张敏. 基于不确定需求的灾后应急救灾网络规划模型与算法[J]. 运筹与管理, 2014, 23(3): 49-55.

[14] 陈涛, 黄钧, 朱建明. 基于信息更新的两阶段鲁棒-随机优化调配模型研究[J]. 中国管理科学, 2015, 23(10): 66-77.

[15] 俞武扬. 不确定网络结构下的应急物资鲁棒配置模型[J]. 控制与决策, 2013, 28(12): 1898-1902.

[16] 杨涛, 邓荣贵. 四川地区地震崩塌滑坡的基本特征及危险性分区[J]. 山地学报, 2002, 20(4): 456-460.

Multiple Relief Resources Robust Location-Routing Optimization

PENGChun,LIJin-lin,WANGShan-shan,RANLun

(School of Management and Economics, Beijing Institute of Technology, Beijing 100081, China)

Decisions to support preparedness activities for disastermanagement are challenging due to the uncertainties of parameters,the balance preparedness and risk, so it is a hot topic. In this paper multiple relief resources location-routing problem is addressed to determine optimal deployment of supply facilities for multiple relief resources, transport distribution route. However, traditional methods addressing this problem mainly focus on stochastic optimization by assuming probability distribution to measure the uncertainty, there are some drawbacks. Multiple relief resources cost uncertainty is considered, introducing two types of uncertainty sets, i.e. box and ellipsoid, to capture the uncertain cost of multiple relief resources, and multiple relief resources robust location-routing models are proposed respectively, which are converted into the deterministic robust equivalent models, and can be solved by hybrid programming algorithm coded in GAMS and CPLEX. Finally, the 19 cities in the north and west of Sichuan Province are chosen to conduct the numerical study. Results show that the proposed robust models is feasible and effective, and compared to the robust model based on box uncertainty set, under the same parameter setting, robust model based on ellipsoid uncertainty set usually is more conservative, and leads to a higher total cost. Decision-makers, according to their risk aversion and conservativeness, choose an appropriate value for the uncertain level parameters Γ/Ω to get the optimal solution, and provide decision support to the department of Emergency Disaster Relief.

relief resource; location-routing; cost uncertainty; robust optimization; uncertainty set

1003-207(2017)06-0113-08

10.16381/j.cnki.issn1003-207x.2017.06.015

2016-05-04；

：2016-07-29

国家自然科学基金资助重点项目(71432002)；国家自然科学基金面上资助项目(71172172);北京理工大学研究生国际学术交流项目(1320012351601)

李金林(1955—)，男(汉族)，北京理工大学管理与经济学院，教授，博士生导师，研究方向：医疗与健康数据分析与决策、收益管理，E-mail:jinlinli@bit.edu.cn.

O224;F224.3

：A