应急物资储备库的可靠性P-中位选址模型，本文主要内容关键词为：可靠性论文,模型论文,物资论文,储备库论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
大规模破坏性地震、海啸、特大恐怖袭击等非常规突发事件一旦发生可能导致重大人员伤亡，短时间内引发对救灾物资的大量需求。为了提高救援效率，通常需要对一些关键救灾物资进行战略储备[1]。因此，应急物资储备库是防灾减灾的重要保障，其选址的合理与否直接关系到突发事件应急响应能力，对实施及时有效救援具有重大意义。 传统的设施选址问题(Facility-location Problem，FLP)或选址-分配问题(Location-Allocation Problem，LAP)通常以系统成本最小为目标，其研究已较成熟[2，3]。而应急物资储备库选址一般以时间效益最大化或灾害损失最小化为目标。对此，国内外也有许多学者从不同的角度运用不同的方法进行了探讨。如Berman等[4]研究最坏情景下应对恐怖袭击的竞争性选址模型。Beraldi等[5]研究应急医疗服务设施选址问题。Rawls等[6]研究需求不确定条件下应急设施的预定位问题，并设计了一种拉格朗日L型算法(Lagrangian L-shaped Method)将模型分解为一系列规模较小、更容易求解的子问题。G
rmez等[7]在预期伊斯坦布尔近期将发生地震情况下，构建了一个应急设施选址模型，该模型考虑了服务灾民的平均距离最短和新建设施的数量最少这两个目标。Lin等[8]研究大规模地震发生后存在长期救灾需求背景下临时性救灾物资储备点的选址问题，并提出一种两阶段启发式方法求解问题。Pavankumar等[1]研究应对大规模生化恐怖袭击的应急医疗物资储备设施的最大覆盖选址模型，该模型同时考虑需求不确定性和容量约束，并设计了一种选址-分配的两阶段启发式算法。Yin等[9]考虑容量约束，建立应急车辆的最大覆盖选址模型。杨锋等[10]考虑道路特性，基于DEA法研究了多应急设施选址问题。代颖等[11]研究应急资源需求和应急救援时间范围均模糊的多目标定位-路径问题。 但上述文献都存在一个隐含的假设：设施一旦建立，将一直运行而不失灵，即设施是完全可靠的。在现实中，由于突发事件的复杂性，设施失灵(Facility Disruptions，也称Facility Failures)现象时有发生。当分派设施发生失灵时，客户不得不选择距离更远的设施为其服务，从而导致运输成本增加，由此产生了可靠性设施选址问题。 可靠性设施选址问题最早由Snyder等[12]提出，研究如何选择低成本(传统目标函数)且可靠的设施点。目前有关可靠性设施选址问题的研究主要针对无容量限制的固定费用选址问题(Uncapacitated Fixed-charge Location Problem，UFLP)和P-中位问题(P-median Problem，PMP)这两类经典的设施选址问题进行扩展，分别称为无容量限制的可靠性固定费用选址问题(Reliability Uncapacitated Fixed-charge Location Problem，RUFLP)和可靠性P-中位问题(Reliability P-median Problem，RPMP)。Snyder等[12]对经典的UFLP和PMP进行扩展，考虑了设施失灵，首次提出了RUFLP和RPMP。他们假设所有设施具有相同的失灵概率，且考虑多级设施分派(每个客户有多个梯级后备设施)，分别针对RUFLP和RPMP建立了混合整数规划模型，并设计了拉格朗日松弛(Lagrangian Relaxation，LR)算法进行模型求解。此后，针对RUFLP，Cui等[13]放宽所有设施具有相同失灵概率这一假设，并分别建立了基于混合整数规划的离散优化模型和连续近似(Continuum Approximation，CA)模型；Lee等[14]也考虑所有设施的失灵概率可以不同，但每个客户只选一个后备设施。Li等[15]则进一步考虑设施失灵的空间相关性。而Berman等[16，17]则在文献[12]的基础上对RPMP做了进一步的扩展。 然而，上述文献均针对常规设施的可靠性选址问题，未考虑应急设施的可靠性选址问题。尽管突发事件发生概率较小，但危害却很严重，且储备库选址属于战略性决策问题，短期内不会改变，因此在应急物资储备库选址阶段考虑失灵风险是十分有必要的。但目前仅有个别文献在应急设施选址中考虑失灵风险或者可靠性因素，如Qin等[18]考虑失灵风险研究了防御预算约束下有容量限制的两阶段设施防御规划问题，但针对的是既有设施的防御规划，而未在网络设施选址阶段就考虑失灵风险，且没有研究后备设施的指派问题；Sorensen等[19]在应急医疗设施的最大覆盖选址模型中引入了可靠性的概念，但采取的是通过多个设施同时覆盖需求点的办法来提高可靠性，没有考虑各个设施的失灵风险，同样也未研究网络拓扑结构可变条件下的多级后备设施指派问题。 本文考虑应急物资保障的及时性和可靠性，以及在不同地区建立应急物资储备库的不同失灵概率，建立一种应急物资储备库选址的RPMP模型。与现有的应急物资储备库选址模型的主要区别在于考虑了应急物资储备库的非完全可靠性；与现有的RPMP模型的主要区别体现在：(1)以往的RPMP模型均考虑常规设施选址问题，目标在于建立低成本且可靠的设施网络；本文考虑的是应急设施选址问题，目标在于建立应急物资保障及时性高且可靠的设施网络；(2)本文在模型中考虑了应急物资储备库之间的依附特性，以及应急物资储备库之间、应急物资储备库与需求点之间的应急物资保障时限性约束。此外，本文建立的是考虑不同失灵概率的RPMP模型，需要采用非线性转移概率公式计算，大大增加了目标函数和相关约束的复杂性，导致模型求解难度增加。为此，本文采用线性化技术对模型进行转化，当问题规模不大时，可用CPLEX等软件进行精确求解；同时设计了一种LR启发式算法，以便对大规模问题进行求解。 现实中依据辖区级别的不同，应急物资储备库在规模和功能上存在着一定的差异。在此，把设在地区行政中心或经济中心所在地的储备库称为主供储备库。较之其他储备库，主供储备库的规模更大、功能更全[20]。以应急血液储备为例，在某一行政区域中，一般存在一个主供血站，其他血站与其存在一定的依附关系，即其他血站可对主供血站发出一定比例的调剂需求，具体体现在：当突发事件发生后出现用血量激增或其他血站采供能力受限等情况时，由于血液从采集、检测到血制品制备有一定的时间要求，为了及时保障临床用血需求，其他血站可从主供血站进行血液调剂，如图1所示[21]。
图1 血站依附关系示意图 类似于传统的RPMP，考虑多级设施分派，以应对失灵风险，提高系统可靠性。对于每个需求点i，根据储备库与其距离的远近，最多在R个梯级上各分派一个储备库为其服务。令r表示设施分派所处的级，r=0，1，…，R-1，其中r=0表示初始设施分派，其他为后备设施分派。若需求点i在第r级上被分派给某个储备库，则表明该需求点在0，1，…，r-1级上也分派有后备储备库，只有这前r个更近的储备库都失灵后，第r级上的虚拟储备库才为其服务。 由于为需求点i分派的各级常规储备库有可能都失灵，为此引入一个虚拟的储备库，其失灵概率为零。若需求点在某一级中被分派给虚拟储备库，则产生一个惩罚值。该惩罚值可理解为应急物资从区域外的其他地区进行紧急采集、包装、运输、接收所耗费的时间[8]。 在理想情况下，每个需求点i恰好分派有R个常规储备库，除非需求点i在s(s＜R)级上分派给了虚拟储备库。若需求点i的确在0，1，…，R-1级上各分派了一个常规储备库，那它必须在第R级上被分派给虚拟储备库E，以反映R个常规储备库可能都失灵的情形。 本文考虑某一地区包含多个下属行政辖区，辖区内的需求点向储备库提出物资需求。地区行政中心的主供储备库已经建立，而未建储备库的行政辖区可作为其他储备库的候选点，各个候选点以及主供储备库都存在一定的失灵风险。需要解决的问题是各储备库的选址及其在各个后备级上的服务区域分配问题。 1、建模假设 本文做如下假设：(1)每个储备库的失灵概率相互独立，且均为先验概率。决策者拥有储备库位置、失灵情况等信息；(2)区域内每个行政辖区的应急物资需求量取决于各需求点的人口数，因此应急物资运输耗费可用需求权重距离(即需求点总人口数与需求点至储备库距离的乘积)表示[22]；(3)每个需求点的物资需求只由一个储备库提供，在初始指派上建有储备库的需求点默认由自己的储备库服务，而未建储备库的需求点称为纯需求点。 2、符号说明 A：原有储备库集合，A=｛1，…，n｝； C：新建储备库候选点集合，C=｛n+1，…，n+m｝； D：需求点集合，D=A∪C； o：主供储备库的下标，o∈A； l：原储备库与新建储备库的总数，由决策者根据有关规定或实际需要确定，且l≤n+m；
：需求点i的人口数，i∈D；
：节点间的距离，i，j∈D； Dis：新建储备库与主供储备库之间的最大距离； H：储备库的服务半径；
：储备库j对主供储备库的依附系数，即从主供储备库调剂来的物资量占该储备库总物资用量的比重； E：表示虚拟储备库，当需求点i所有的后备指派设施都失灵时，需求点i指派给虚拟储备库E，这意味着需求点i的需求得不到满足；
：储备库j的失灵概率，且0≤
≤1，
=0；
：需求点i的需求未被满足时的单位惩罚值，且
； R：为每个客户最多可分派的后备设施级数，且1≤R≤l-1； r：设施分派所处的级，r=0，1，…，R，其中r=0为初始设施分派，r=1，…，R-1为后备设施分派，r=R为虚拟设施分派。
：储备库j在r级上被分派给需求点i时为1，否则为0，i，j∈D；
：在j处开设储备库为1，否则为0，j∈D；
：由储备库j在r级上服务需求点i的概率。 3、模型建立 应急物资储备库选址的RPMP模型如下：
目标函数式(1)是使区域内应急物资保障系统的预期需求权重距离最小，该目标同时考虑物资保障的及时性和可靠性。式中第一项是储备库与需求点之间的预期需求权重距离，第二项是其他储备库与主供储备库之间的预期调剂需求权重距离。约束式(2)表示每个需求点要么在第r级上分派给某一个非虚拟储备库，要么在第s(s＜r)级上分派给虚拟储备库(若r=0，令
)；式(3)保证新建储备库与原有储备库的总数为l；式(4)表示需求点只能分配给已经建立的储备库；式(5)为各储备库的服务半径约束；式(6)新建储备库与主供储备库的距离约束，以保证应急物资调剂的及时性；式(7)表示每个需求点必定在某一级上分派给虚拟设施；式(8)和(9)为转移概率公式[13]：当r=0时，
即为设施j不失灵的概率；当1≤r≤R时，若设施k在第r-1级上服务客户i，则
，1≤k≤m+n+1；因为式(2)已表明最多只存在一个k使得
，从而保证了该转移概率公式的正确性；式(10)表示原有的储备库；式(11)表示虚拟储备库；式(12)和(13)为0-1变量约束。 4、模型转化
LRPMP是一个混合整数线性规划模型，可用CPLEX等软件进行求解。但CPLEX等一般适于求解中小规模问题。针对大规模问题，下面提出一种LR启发式算法。 采用拉格朗日乘子
来松弛约束式(4)，将模型转化为如下形式：
s.t.(2)-(3)，(5)-(8)，(10)-(17)，(19) 根据上述模型的变量特性，可以将模型转化为两个相互独立的子问题：选址子问题(SP1)与分派子问题(SP2)。 对于SP1，其目标为
，它等价于
，从而可将SP1写成以下形式：
s.t.(3)，(6)，(10)-(12) 而SP2可写成如下形式：
s.t.(2)，(5)，(7)-(8)，(13)-(17)，(19) 上述两个子问题的求解方法设计如下：
Cui等[13]证明了通过上述转换，RRSP可以产生松弛子问题RSP的一个下界。而RRSP可采用匈牙利算法(Hungarian Algorithm)[24]求解，该算法具有强多项式特性。 SP1和SP2这两个子问题之间的优化则通过拉格朗日乘子进行协调，本文中拉格朗日乘子采用次梯度法进行更新。 至此，可采用标准的次梯度法求解拉格朗日松弛问题，具体计算过程如下： 步骤1：初始化拉格朗日乘子
、最大迭代次数N、步长
。 步骤2：求解选址子问题SP1。 步骤3：基于RRSP求解方法求解客户分派子问题SP2。 步骤4：计算下界解：LRPMP(μ)=SP1(μ)+SP2(μ)，其中SP1(μ)，SP2(μ)分别代表选址子问题和分派子问题的目标值。判断当前的拉格朗日解是否为可行解：若当前解可行，则停止计算，该解即为LRPMP的最优解；否则，转入步骤5更新下界。 步骤5：根据当前解计算次梯度和步长，并按下述拉格朗日乘子迭代方法更新
：若满足收敛或停止条件，则停止迭代；否则，返回步骤2。
在算法执行过程中，下界在迭代中取大，上界在迭代中取小，从而不断缩减上下界之间的界限。 构建两组算例来验证上述模型和算法的可行性和有效性。第1组算例源于“5·12”汶川大地震后四川省阿坝州血站的选址决策问题；第2组算例为随机模拟算例，用来测试不同规模算例下的算法性能。本文采用Matlab语言编程实现上述算法，运行平台为Intel(R)Core(TM)2 Duo CPU T5470@1.60GHz，3GB内存，Windows 7操作系统的PC机。 四川省阿坝州下辖马尔康、汶川等13个县，在“5·12”大地震中汶川、茂县等7个县为重灾区。目前辖区内采集的血液都要送回马尔康检测、制备，并从马尔康发往各县医院。该州地域广阔，原血站的服务半径过大。灾后重建使得阿坝州的社会经济和医疗卫生水平都得到大大提升，从而对血液保障体系也提出了更高的要求。第1组算例以此为背景进行分析，并根据l和R的不同取值设计了16个算例。其中，阿坝州各县人口数、各县间距离、依附系数以及距离约束参数见文献[21]。失灵概率
在[0，0.1]内随机均匀产生，惩罚值
取10000。 第2组算例根据候选节点数以及不同的l和R值设计了24个不同规模的算例。其中，各地人口数(万人)在[5，12]内随机均匀产生；各地的坐标在[1，100]内随机均匀产生，并据此计算各地间的欧氏距离(km)；惩罚值
取1000。其他参数同第1组算例。 LR算法参数设置如下：最大迭代次数N=500；最优容忍度
；初始拉格朗日乘子
，其中
是所有储备库到需求点之间距离的均值[12]。两组算例的计算结果和LR算法性能如表1和表2所示；LR算法的收敛情况如图2和图3所示(均以第1组算例中R=3，l=4时为例)。
图2 LR算法的上下界收敛情况
图3 LR算法上下界的相对偏差收敛情况 大量试验结果表明，LR算法上下界的相对偏差基本上都在1%以内。而LR算法目标值与CPLEX目标值的比较结果说明，通过LR算法基本上可以得到原问题的最优解。此外，分析表2中各种不同规模的算例结果发现，针对小规模问题，CPLEX的表现更优异，而当问题规模扩大以后，LR启发式算法的效率较高。因此，本文提出的LR算法具有较好的性能。此外，可以看出后备设施级数R的取值对最优选址方案决策影响较小，这与文献[12]和[13]针对可靠性设施选址模型的研究结论相一致。
为分析考虑设施失灵风险对选址决策的影响，在此以第1组算例(R=3，l=4)为例，图4给出了不考虑失灵风险的选址-分派方案，表3给出了考虑失灵风险的各个后备级上的选址-分配方案。可以看出，考虑失灵风险后应急物资储备库选址-分派方案发生了变化。这种情况下，设施网络的拓扑结构是可变的；由于在选址设计阶段就充分考虑了各个设施的失灵风险，对需求点进行了多级后备设施指派，因而系统应对灾害的可靠性得到了提高。
图4 不考虑失灵风险的选址-分派方案 进一步地，为分析设施失灵概率对选址决策的影响，在此仍以第1组算例(R=3，l=4)为例，以各个设施的当前失灵概率为基数，将其扩大到一定的倍数，来进行失灵概率的敏感性分析，结果如表4所示。结果表明：失灵概率对选址决策的影响较明显，对系统目标的影响尤其显著；随着失灵概率的增大，系统目标值也快速增大。原因在于随着储备库失灵概率的增大，系统失灵的风险也增大，各个需求点进行紧急调剂的需求也增大，从而导致惩罚值加大，系统目标值上升。
应急设施网络可能面临各种失灵风险，尽管失灵现象不常发生，一旦发生，后果将非常严重。而设施选址是一个战略性决策问题，在短期内一般不会改变，因而在选址阶段就考虑设施失灵风险是十分必要的。 本文建立一类应急物资储备库选址的RPMP模型，针对该混合整数非线性规划模型，通过线性转化技术转化，以便用CPLEX软件对中小规模的问题进行快速精确求解。但对于大规模问题，CPLEX的计算效率较低，为此本文设计了一种LR算法，具有良好的计算性能。算例分析结果表明：设施失灵概率对选址方案和系统目标有显著影响，失灵概率越大，系统目标值越大。因此，在条件允许的情况下，可以考虑对应急物资储备库施加一定的保护性措施，以降低设施的失灵概率，提高系统性能。 本文没有考虑保护性措施对失灵概率的影响，进一步研究可以建立保护性措施与失灵概率之间的函数关系，研究各种防护强度下应急物资储备库的可靠性选址方案。还可考虑设施失灵的频率和持续时间，进一步研究动态环境下的最优决策规则。此外，可在选址与库存、路径等的集成决策问题(如定位-路径问题、定位-路径-库存问题)中考虑设施失灵风险。最后，RPMP属于NP-hard问题，在进行上述扩展后，问题将变得更为复杂，因而设计更加有效的求解算法也是下一步研究的重点。
标签：应急物资论文; 概率计算论文; 设施选址论文; 可靠性分析论文; 风险模型论文; 可靠性论文;
