APP下载

考虑失灵风险的可靠性设施选址问题综述

2016-05-19

关键词:综述可靠性

周 愉 峰

(1.重庆工商大学 商务策划学院,重庆 400067;2.重庆工商大学 重庆市发展信息管理工程技术研究中心,重庆 400067)



考虑失灵风险的可靠性设施选址问题综述

周 愉 峰1,2

(1.重庆工商大学 商务策划学院,重庆 400067;2.重庆工商大学 重庆市发展信息管理工程技术研究中心,重庆 400067)

摘要:可靠性设施选址问题是当前选址研究领域的一类前沿性问题,分析了设施失灵风险的来源和分类,以及可靠性设施选址相关问题的研究及特点;从决策者风险权衡角度,将可靠性设施选址问题分为最小期望成本问题和最坏情形成本问题,其中前者又分为可靠性无容量约束的固定费用选址问题和可靠性P-中位问题,分别从建模及求解角度对这些问题的研究现状进行了综述;最后,总结了可靠性设施选址问题的研究现状和启示,并提出了未来的发展方向。

关键词:设施选址;设施失灵;可靠性;综述

0引言

设施选址是设施规划的一个重要环节,国内外已有大量学者对其进行了研究[1-2]。但无容量限制的固定费用选址问题(Uncapacitated Fixed-charge Location Problem,UFLP)、P-中位问题(P-median Problem,PMP)等经典的设施选址问题都有一个隐含的假设:设施一旦建立,将一直运行而不失灵,即设施是完全可靠的。可事实上,由于自然灾害、人为灾害、罢工、所有权更替及其他因素,设施失灵(Facility Disruptions,或Facility Failures)现象时有发生。当分派的设施发生失灵时,客户不得不选择距离更远的设施为其服务,这就可能导致运输成本增加,由此产生了可靠性设施选址问题(Reliability Facility Location Problem,RFLP)。

传统的设施选址问题通常不会改变设施网络的拓扑结构,但RFLP由于在选址阶段考虑了失灵风险,设施网络的拓扑结构是可变的。RFLP最早由Snyder等[3]提出,研究如何选择低成本且可靠的设施点。由于设施选址属于战略性决策问题,短期内不会改变,故在设计阶段就考虑失灵风险很有必要,而且这样可以大大降低应急成本,因而研究RFLP具有非常重要的意义。

近年来,考虑设施失灵风险的RFLP引起了国外一些学者的重视,已成为当前选址研究领域的前沿性问题。本文旨在回顾这一问题的研究现状和特点,并分析现有研究中的局限性和未来的发展趋势。希望通过本文能引起国内学术界对该问题研究的重视,并结合我国经济社会发展中的实际问题开展相关的研究。

1设施选址问题中的失灵风险与可靠性

1.1失灵风险的来源与分类

设施选址问题中失灵风险的研究源于对供应链中断风险(Disruption Risks)的研究。Kleindorfe等[4]按照风险来源将供应链中断事件分为3类:自然灾害、运营事故、恐怖主义及政治不稳定性。其中自然灾害主要包括地震、飓风和暴风雪等;运营事故包括机器故障和系统性问题,如停电、罢工、关键供应商的倒闭等。Chen等[5]从供应链构成角度,将供应链中断分为供应中断、协调中断和需求中断3类。供应中断可能是由设施容量约束和设施可靠性等因素造成;需求中断和协调中断通常由需求、运输时间和成本的不确定性引起。在某些情况下,即使设施在运行也可能被认为处于失灵状态,如拥塞,这种短期失灵在现实中很常见[6]。

1.2可靠性概念、分类

由于设施失灵风险的存在,就产生了系统可靠性问题。关于系统可靠性的定义在不同的学科领域不尽相同,但大多侧重于考察系统在规定的条件下和规定的时间内完成规定功能的能力。在设施选址研究领域,大部分学者将可靠性定义为“在系统内部某些部分失灵的情况下,整个系统仍能良好运行的能力”[7]。设施系统可靠与否的一个标准在于“系统运行对设施中断具有一定的弹性和稳健性”[8]。

处理可靠性问题时一般把设施失灵风险分为两类:一类假设失灵风险是由外部因素(停电,罢工等)引起的,将它看成是系统的外生变量;另一类假设失灵风险是由于客户需求和拥塞等因素造成的,失灵风险是系统的内生变量[9]。

2RFLP相关问题的研究及其差异性

在RFLP研究之前,许多研究者对其他相关问题进行了大量研究。这些问题与RFLP既有联系,又有区别,主要包括以下几个方面。

2.1供应不确定下的选址问题

早期针对该问题的研究主要考虑由于随机需求引起的设施拥塞现象,通常借助大量过剩供应来保证系统的可用性。近年来,由设施失灵引起的供应不确定性越来越受到关注,因而考虑这一情况下的设施选址问题也逐渐得到重视[10]。RFLP是对此类问题的延伸与扩展,可有效解决随机设施失灵情况下的设施选址及客户分派问题。

2.2防御性选址问题

网络中关键设施一旦遭到攻击而失灵,会导致整个网络系统性能的重大损失,由此产生了防御性R-中断型中位问题(R-interdiction Median Problem with Fortification,RIMF),即识别出网络中R个关键设施,并保证在这些设施中断后每个需求点仍有一个后备设施为其服务,从而提高系统的抗攻击能力和安全性。文献[11-15]都对RIMF进行过研究。不过,这类问题重在识别现存网络中的关键设施及其中断后的补救措施,而RFLP则是在选址阶段就考虑设施的可靠性,因此前者往往需要付出更高的成本。

另有一些文献是研究基础设施系统中保护性装置的最优安装位置问题,以降低可能的破坏事件带来的影响。如Carr等[16]研究了供水网络中用来检测是否有蓄意注入污染物的传感器的最优安装位置优化模型。James等[17]研究了电网中保护性装置的最优安装位置问题,以减少由于意外引起的断电时间。截流(Flow Interception)模型常被用来解决保护性设施选址问题,如Gendreau等[18]和Teodorovic等[19]都采用截流模型研究运输网络中检查站的选址问题,以尽量避免危险和降低风险。

2.3网络可靠性问题

网络可靠性理论主要研究网络(如通讯网络、电网等)在遭遇拥塞或中断等引起随机失效后仍然保持连通的概率最大化。现有研究大多考虑网络中断现象发生在线路上,较少考虑网络节点的失灵或两者兼有的情况[20]。鉴于给定网络的可靠性计算较困难,现有研究通常寻找具有期望性能(如二连通、k连通、特殊的环结构等)且构建成本最低的网络[21]。网络可靠性模型与RFLP模型之间的区别在于:前者主要关心网络的连通性,只考虑网络构建成本,不涉及网络中断后引起的成本;而后者同时考虑两类成本,并保证网络遭遇中断后仍然连通。

综上所述,虽然RFLP与上述问题有一定联系,却有着明显的区别。RFLP的特点是在选址阶段就考虑了设施的可靠性且只需增加少量系统成本,从而保证设施一旦失灵后系统仍然能良好运行。

3RFLP建模及求解

从决策者风险权衡的角度,可以将现有对RFLP的研究分为最小期望成本模型(Minimum Expected Cost Model)和最坏情形成本模型(Worst-case Cost Model)两类。其中,最小期望成本模型是当前研究的重点,主要源于对无容量限制的固定费用选址问题(UFLP)和P-中位问题(PMP)这两类经典的设施选址问题的扩展,分别称为可靠性无容量限制的固定费用选址问题(Reliability Uncapacitated Fixed-charge Location Problem,RUFLP)和可靠性P-中位问题(Reliability P-median Problem,RPMP)。

3.1最小期望成本模型

3.1.1RUFLP模型

经典的UFLP给定以下条件:已知客户点集,候选设施点集,在每个候选点构建设施的固定成本,以及从每个设施点到每个客户点的单位运输成本。目标是确定待建设施点的数量、位置以及将每个客户点分派给一个设施,使设施构建成本与运输成本之和最小。

Snyder等[3]扩展了经典的UFLP,在模型中考虑设施失灵风险,首次提出了RUFLP,研究考虑设施失灵风险条件下的设施选址及其客户分派,以寻求设施开设成本、日常运行成本和期望失灵成本之和最小的选址方案。该问题描述如下:

设I是客户集(i∈I);J是候选设施集合(j∈J);NF表示不会失灵的候选设施集,F是可能会失灵的候选设施集,有NF∪F=J。hi为客户i在单位时间内的需求量;fj表示设施j的初始设置成本;dij表示设施j到客户i的单位运输成本;q表示可能失灵设施的失灵概率。决策变量:Xj=1表示在j处开设设施,否则为0;Yijr=1表示r级分派中设施j服务于客户i,否则为0。

对于每个客户i,根据设施与其距离的远近,最多在m个梯级上各分派一个常规设施为其服务。令r表示设施分派所处的级,r=0,1,…,m-1,其中r=0表示初始设施分派,其他为后备设施分派。若客户i在第r级上被分派给了某个设施,则表明该客户在0,1,…,r-1级上也分派有后备设施,只有这前r个更近的设施都失灵后,第r级上的设施才为其服务。

由于为客户i分派的各级常规设施有可能都失灵,为此引入一个虚拟的应急设施u,且u∈NF,其固定开设成本和失灵概率均为零,无容量限制。若客户i在某一级中被分派给应急设施,则产生惩罚成本θi,令diu=θi。即客户的需求未被满足时都将产生惩罚成本,该成本可理解为订单流失成本或为满足该客户需求而从竞争者处紧急采购的成本。产生惩罚成本的情形包括两类:分派给该客户的所有设施都失灵(即无可用设施服务该客户);由任何一个分派设施为该客户服务的成本均超过惩罚成本。

理想情况下,每个客户i恰好分派有m个常规设施,除非客户i在s(s

表示期望的设施失灵成本;α为权重系数,0≤α≤1。

则RUFLP可描述为

minαw1+(1-α)w2

(1)

r=0,…,m-1

(2)

Yijr≤Xj,∀i∈I,j∈J,r=0,…,m-1

(3)

(4)

Xu=1

(5)

Xj∈{0,1},∀j∈J

(6)

Yijr∈{0,1},∀i∈I,j∈J,r=0,…,m-1

(7)

其中,目标式(1)表示使设施固定成本、运输成本和期望失灵成本之和最小。约束式(2)表示对于每一后备分派级r,客户i要么分派给级r上的可能失灵设施,要么分派给级s上的不失灵设施(s

Snyder等[3]提出了一种拉格朗日松弛(Lagrangian Relaxation,LR)算法来求解该模型,并且讨论了如何用该模型产生一条日常运营成本与期望失灵成本之间的平衡曲线,以证明在选址阶段考虑设施的可靠性,通过少量增加系统成本可以大大提高系统可靠性,从而实现期望运输成本与系统可靠性的协调优化,得到更加可靠的并且近似最优的UFLP解决方案。

Li等[22]在文献[3]的基础上考虑设施设防与预算约束,只设立一个后备设施的RUFLP模型,并设计了相应的LR算法。与之相似,同样只考虑设立一个后备设施。Bahri等[23]将分销中心分为失灵与不失灵两类(两类设施的建设成本不同),研究了三阶段的分销网络设计问题。

但上述模型有一个明显的缺陷:假设设施失灵基于一个相同的失灵概率,该假设在多数现实情况下是不合理的。Lee等[29]放宽这一假设,建立了一类RUFLP模型。Cui等[25]则提出了一个混合整数规划(Mixed Integer Program,MIP)模型和连续近似(Continuum Approximation,CA)模型来研究设施具有不同失灵概率下的RUFLP。针对MIP模型和SA模型,分别设计了一种LR算法和快速启发式算法来求解。结果表明:LR算法可以得到解的上下界,而CA方法只能得出一个近似最优解。LR算法对于解决中小规模的RUFLP更为有效,但对于大规模问题,CA模型的快速启发式算法比LR算法好,计算效率较高。此外,通过CA模型还可方便地进行灵敏性分析,为决策者提供一些有益的管理启示。Aboolian等[26]在文献[25]的基础上针对离散的RUFLP研究了更为有效的精确算法与近似算法。Hong等[27]以设施失灵下救灾物资损失量最小作为可靠性目标(但未进行后备设施指派),以不考虑失灵风险下的系统总成本最小作为经济性目标,建立了一个多目标的应急物流网络设计模型。Yun等[28]研究了失灵信息不确定条件下的RUFLP。

上述文献均未考虑设施失灵的空间相关性。但Li等[29-30]认为现实世界中许多失灵事件表现出很强的空间(位置)相关性(site-dependent or spatially-correlated),原因在于相邻的设施很有可能受同一灾害的影响。指出这种相关性极大地影响了设施失灵的空间模式以及系统的运行模式:在正相关下,邻近的设施更有可能同时失灵;在负相关下,相邻设施可以相互支援以避免客户长距离旅行。由此扩展了Snyder等[3]和Cui等[25]的研究,建立了一个RUFLP的CA模型。此外,绝大多数文献在处理设施失灵概率时都将其视为确定的参数。

以上文献考虑了设施失灵风险,研究低成本且可靠的选址方案,但是没有对系统可靠性进行定量描述。Berman等[7]基于可靠性冲突理论提出了系统可靠性的计算方法,且认为可靠度是指系统能够提供满意的客户服务的概率,是设施点与客户之间距离的单调减函数。在此基础上,Tang等[31]针对传统选址模型片面追求物流成本最小化而忽视物流服务水平的情况,将可靠性作为物流服务水平的一种测度,建立了一个基于可靠性的物流设施选址优化模型。

3.1.2RPMP模型

经典的PMP是通过建立P个设施来满足所有客户的需求,目标是使所有客户点到设施的加权平均距离最短。Snyder等[3]扩展了传统的PMP,提出了RPMP,这是当前RFLP研究的另一个热点。

表示客户由其初始分派设施服务的运输成本;

表示期望的设施失灵成本。则RPMP可描述为

minαw1+(1-α)w2

(8)

∀i∈I,r=0,…,P-1

(9)

Yijr≤Xj,∀i∈I,j∈J,r=0,…,P-1

(10)

(11)

(12)

Xu=1

(13)

Xj∈{0,1},∀j∈J

(14)

Yijr∈{0,1},∀i∈I,j∈J,r=0,…,P-1

(15)

与RUFLP模型相比,RPMP模型中少了固定成本fj,设施数量变成了确定的P。Snyder等[3]通过平衡曲线分析发现,RPMP模型同样说明了在少量增加系统成本的条件下,可以显著提高系统的可靠性。但该文也是假设所有设施具有相同的失灵概率。Li等[22]也建立了一个考虑相同失灵概率、设施设防与预算约束、单个后备设施的RPMP模型及其LR算法。

在文献[22]的基础上Li等[32]扩展研究了不同失灵概率下的RPMP,并设计了一种求解大规模问题的禁忌搜索算法。Berman等[33]也允许不同的设施有不同的失灵概率,假设设施失灵概率是设施设计的函数,但是独立于设施位置。他们提出一个类似的可靠性P-中位选址问题,构建了一个非线性规划模型,并采用一种改进的贪婪算法来求解。研究发现,失灵概率对最优设施选址决策有重要影响:当失灵概率大时,设施点变得更加集中,以便在失灵事件发生时提供更好的支撑条件。但该模型假设客户拥有设施的运行情况信息,能够相应地规划旅行线路。Berman等[8]放宽了这一假设,研究了不完全信息条件下的RFLP。An等[34]基于两阶段鲁棒优化方法进一步改进了RPMP。

3.2最坏情形成本模型

当失灵概率等信息也不确定时,无法应用期望(概率)模型,此时,基于情景规划的建模方法具有更好的适用性[35]。现有的基于情景的RFLP研究模型大多为最坏情形成本模型。风险中立者在不确定性环境下进行决策时往往选择期望成本最小模型,而风险规避者则倾向于最坏情形成本模型。由于设施修复以及网络重构的成本太高,最坏失灵情景模型更加具有现实意义[36]。

最坏情形成本模型需要考虑所有可能出现的情景,但考虑所有可能的情景显然是不现实的。由于最坏的情景在理论上是指所有设施都失灵的情况,因而在研究最坏情形成本模型时,通常采取两种处理方法:一是假设所有的情景中最多有若干个设施失灵;二是假设所有的情景概率至少为某一定值。

基于Snyder等[3]研究的问题,Snyder等[37]提出一个极小化最大成本RFLP模型(Minimax-cost RFLP,MMRFLP),考虑各种失灵情景下设施的最优选址以及客户分派问题,目标是使最大的系统成本最小。

设U表示最大的系统成本;S表示失灵情景集。若设施j在情景s中失灵,ajs=1,否则为0;若客户i在情景s中分派给设施j,Yijs=1,否则为0。则MMRFLP可描述为

minU

(16)

(17)

(18)

Yijs≤(1-ajs)Xj,∀i∈I,j∈J,s∈S

(19)

Xj∈{0,1},∀j∈J

(20)

Yijs∈{0,1},∀i∈I,j∈J,r=0,s∈S

(21)

其中,目标式(16)表示使最大的系统成本最小。约束式(17)表示U为最大的系统成本;约束式(18)保证每个客户在每种情景中都有一个设施为其服务;约束式(19)保证客户在每种情景中只能分配给已开设且未失灵的设施。

Shen等[38]考虑失灵概率依赖于设施,基于情景规划方法构建了一个两阶段随机规划模型。在失灵概率依赖于设施时,通过界定不同情景可以很容易地获得不同设施的失灵概率。如果情景数量足够多,基于情景规划所描述的可靠性无容量限制的设施选址问题是合理的,并且能够有效求解。但当失灵概率独立时,可能的情景集规模巨大,模型的变量和约束条件数量将呈指数级增长,从而使得问题难以得到有效求解。为此,他们又构建了一个非线性整数规划模型来描述它,并采用样本均值逼近启发式(Sample Average Approximation)、贪婪增加(Greedy Adding)、贪婪增加和替代(Greedy Adding and Substitution)等启发式算法来求解。Zhang等[39]基于最坏失灵情景,建立了预期成本最小及最大覆盖范围最大的两类双层规划模型。Peng等[40]则采用鲁棒优化(Robust Optimization)方法研究了考虑设施失灵风险的可靠性多级物流网络设计问题,建立了一种MIP模型,并设计了一种结合局部改进(Local Improvement)和最短增广路(Shortest Augmenting Path)方法的混合遗传算法。

与极小化最大成本模型相比,极小化最大后悔模型(Minimax Regret Model)可能需要更多的情景数量,因为哪些情景会产生最大的后悔值在失灵发生前是不明确的。为此,Snyder等[41]进一步讨论了RFLP的极小化最大成本模型和极小化最大后悔模型。Chen等[5]扩展研究了随机距离情况下的极小化最大后悔模型。此外,Church等[42]、Hanley等[43]也进行了类似的研究。

总体而言,当前关于最坏情形成本模型的研究尚不多见。在此类模型中,最坏情景的设定通常具有较强的主观性,情景设定依赖于模型、参数结构和数据。当情景数量较多时,模型的变量和约束条件数量增长很快,此时对算法性能的要求很高。

3.3其他RFLP模型

最小期望成本模型与最坏情形成本模型之外,也有少量文献研究了其他的RFLP模型。例如,Hassani等[44]在传统的轴辐式网络设计(Hub-and-spoke network)及枢纽站选址(Hub Location)模型中引入中断风险与可靠性概念,提出了可靠性中心枢纽站选址问题(Reliable Center Hub Location problem,RCHLP)。Lim等[45-46]基于CA模型研究了考虑随机失灵概率、概率不完全估计、失灵概率与容量相关条件下的RFLP,研究发现:与高估风险相比,低估风险引起的预期成本增长更快 ;若规划得当,降低误判风险的成本不会太高;失灵概率的误判风险大于失灵概率的相关程度,因此管理者应更加注重失灵概率的准确估计。Aydin等[35]研究了一类有容量限制的可靠性固定费用选址问题(Capacitated Reliable Facility Location Problem,CRFLP)。通过线性0~1整数规划模型来对问题加以描述。由于采用了情景设定,降低了模型的复杂性。尽管考虑了容量限制,但该文不允许多个设施服务于同一个客户(即协同定位)。

3.4RFLP求解

与RFLP模型方面的研究相比,目前对RFLP求解算法的研究成果较有限。

现有对RFLP的研究绝大多数都考虑离散设施选址问题,一般采用MIP方法予以描述。求解此类模型时,常用LR算法,而且一般都将原问题分解为两个线性化的子问题。对于给定的拉格朗日乘子,这两个子问题都比较容易求解。但是针对不同的选址问题,松弛的约束条件不尽相同。对于RUFLP和RPMP模型,LR算法通常松弛设施开放约束,将原问题分解为设施选址子问题和客户分派子问题,然后通过拉格朗日乘子的迭代更新来协调两个子问题的求解,得到原问题的上下界(如文献[25])。也有文献针对RPMP模型,采用LR算法松弛客户分派约束,将模型转化成一个求解最优下界的子问题,如文献[3]。

LR算法可以求得较精确的计算结果,但它仅适用于模型不太复杂的情况以及中小规模问题。放宽各种建模假设后,模型的复杂性会显著增加,LR算法的应用就受到很大的局限。为此,不少学者设计了各种启发式算法来求解复杂的MIP模型(如文献[38,40]等)。可以预见,随着对RFLP的进一步深入研究,各种启发式算法的设计也将成为研究重点。

也有个别文献研究了连续空间上的RFLP,基于CA方法进行建模,并采用解析法,如文献[29,47];或近似算法进行快速求解,如文献[25]。CA模型的实际应用意义较小,但在解决大规模复杂问题时效率较高,而且便于进行灵敏性分析,从而得出一些管理启示。

4研究展望

综上所述,RFLP已日渐引起学者们的关注,相关研究正在逐步深入和拓展。通过对以往研究的分析可以发现:

(1) 在研究目标方面,现有研究主要集中于两个方面:一是在考虑设施失灵风险的条件下,探讨系统中不可靠设施的最优选址;二是从中得出一些有益的管理启示,以帮助决策者更好地进行系统管理。目标一主要通过各种模型的建模求解来实现,而目标二则主要通过灵敏性分析来探讨各个参数和系统目标之间的关系。

(2) 在模型构建方面,现有研究大多针对离散空间的RFLP,建立线性或非线性的MIP模型。也有少量文献采用了随机规划等方法进行建模。

(3) 在求解算法方面,不少学者都采用LR算法来求解RFLP。若问题规模不大,LR算法很有效;但对于大规模问题,LR算法的效果也不太理想。为此,不少学者倾向于设计启发式或亚启发式算法来求解,以提高计算效率。事实上,绝大多数离散设施选址问题都属于NP-hard问题,考虑设施可靠性因素后,问题变得更为复杂,因而采用各种启发式算法求解是未来的趋势。

相对于已有百年研究历史的传统选址问题,RFLP还是一个新兴研究领域。鉴于RFLP的复杂性,现有研究通常设置了一些与现实情况不符的假设条件,如无容量限制、确定性参数、完全信息条件等。因此,对该问题的研究还存在许多有待完善的地方:

(1) 设施容量限制与协同定位。现有研究大都假设设施容量是无限的。在模型中考虑设施容量限制,尽管会增加模型和算法的复杂性,却更加切合实际。此外,在有容量限制的情况下,设施间的协同定位成为可能,这是一个很具吸引力的研究方向。

(2) 内生性假设。目前不少文献关于设施失灵风险的外生性假设是一个明显的缺陷,且大多认为设施失灵风险与可靠性是独立的,只有个别文献(如文献[7,30])将可靠性视为设施点与客户之间距离的函数。但设施的可靠性应该是由多个因素(如距离、需求规模、地理位置等)综合决定的,而不是某一单个因素的函数。因此,如何对各种内生性因素进行综合分析,为后续的研究提供了一个新的视角。

(3) 客户行为假设。现有文献对客户行为存在两个基本假设:一是针对客户搜索行为,假设客户总是搜索下一个最近的设施,而不是规划最优的路径(这条路径使总的期望旅行成本最低)。可见,基于最优客户行为研究RFLP具有重要前景,当然也相当困难。另一个假设是客户知道所有设施的位置,这一点在很多情况下是不合理的(如对于ATM机、加油站等情况),因此放宽这一假设将使构建的模型更加切合实际。

(4) 随机性与鲁棒性。现有研究大多建立确定性模型,但事实上研究各种不确定信息(如需求、风险信息)条件下的RFLP更具现实意义,对此可采用随机优化、鲁棒优化等方法进行研究。

(5) 动态决策。现有研究仅考虑静态决策规则,忽略了设施失灵的频率和持续时间,有必要进一步研究动态环境下的最优决策规则。

(6) 集成决策。在选址与库存、路径等的集成决策问题中也应考虑设施失灵风险。已有少量文献在RFLP决策中引入库存成本,建立了考虑失灵风险的定位-库存问题(Location-Inventory Problem)优化模型[48-50]。而考虑失灵风险的定位-路径问题(Location-Routing Problem)、定位-路径-库存问题(Location-Routing-Inventory Problem)等尚未见研究。

(7) 有效算法。RFLP大多属于NP-hard问题,在模型方面进行诸多扩展后,问题将变得更为复杂。因此,设计更加有效的算法来求解复杂的RFLP模型将是今后研究的重点。

5结语

设施网络可能面临各种失灵风险,因而在进行选址时有必要充分考虑设施的非完全可靠性。尽管现实中设施失灵现象不会经常发生,但一旦发生,后果可能很严重。总结以往有关RFLP的研究成果,可以得到以下启示:

(1) 设施选址是一个战略决策问题,在短期内一般不会改变,因而在选址阶段就考虑其失灵风险和相应的保护性措施是十分必要的,可以显著降低将来的应急成本。

(2) 尽管系统成本与系统可靠性之间存在悖反关系,但通过增加少量的系统成本就可以显著提高系统的可靠性,从而实现系统成本与系统可靠性之间的协调优化。

(3) 设施失灵概率的准确估计具有重要作用。若失灵概率的准确估计困难,则适度高估风险更有利于构造可靠的设施网络,因为低估失灵概率的造成的后果更严重。

(4) 最优选址决策受多种因素的影响。当设施失灵概率较大时,应该选择较集中的选址模式,以便在设施失灵发生后可以实现有效的相互支援。在某 些特殊情况下,甚至可以考虑将几个设施定位在相同的网络节点上。此外,不同类型风险的相关性及其强度也会影响选址模式。设施选址应充分考虑空间(位置)、距离和服务需求等失灵风险相关的因素。

RFLP已成为选址研究领域的一个重要研究方向,其研究成果对于提高设施网络的可靠性具有重要的意义。但目前国内关于这一问题的研究成果匮乏,亟待加强这方面的研究。为此,本文系统地回顾了考虑设施失灵风险的RFLP研究现状,并结合实际提出了今后应重视的几个发展方向。尽管所涉及的范围较广,解决问题的难度也很大,未来对该问题的研究应建立更切合实际情况的模型,并探索是否有一种普遍适用的算法,允许相关专业人员用其有效地解决现实中的问题,以便有效提高设施网络的可靠性。

参考文献(References):

[1]SNYDER L V.Facility Location under Uncertainty:A Review[J].IIE Transactions,2006,38(7):537-554

[2] FARAHA R Z,SteadieSeifib M,Asgari N.Multiple Criteria Facility Location Problems:A Survey[J].Applied Mathe-matical Modelling,2010,34(7):1689-1709

[3] SNYDER L V,Daskin M S.Reliability Models for Facility Location:The Expected Failure Cost Case[J].Transporta-tion Science,2005,39(3):400-416

[4] KLEINDORFER P R,Saad G H.Managing Disruption Risks in Supply Chains[J].Production and Operations Management,2005,14(1):53-68

[5] CHEN G,DASKIN M S,SHEN Z.The ∂-Reliable Mean-Excess Regret Model for Stochastic Facility Location Modeling[J].Naval Research Logistics,2006,53(7):617-626

[6] WITLIN D.Ambulance Diverted Each Minute[J].Boston Herald,2006,17(2):11-14

[7] BERMAN O,KRASS D,MENEZES M.Locating Service Facilities Whose Reliability Is Distance Dependent[J].Com-puters & Operations Research,2003,30(11):1683-1695

[8] RAFIEI M,MOHAMMADI M,TORABI S.Reliable Multi Period Multi Product Supply Chain Design with Facility Disruption[J].Decision Science Letters,2013,2(2):81-94

[9] BERMAN O,KRASs D,MENEZES M.Locating Facilities in The Presence of Disruptions and Incomplete Information[J].Decision Sciences,2009,40(4):845-868

[10]王国利,胡丹丹,杨超.需求和供应不确定下的选址研究[J].工业工程与管理,2011,16(1):74-78

WANG G L,HU D D,YANG C.Location Problem with Uncertain Demands and Supplies[J].Industrial Engineer-ing and Management,2011,16(1):74-78

[11] CHURCH R L,SCAPARRA M P,MIDDLETON R S.Identifying Critical Infrastructure:the Median and Covering Facility Interdiction Problem[J].Annals of the Association of American Geographers,2004,94(3):491-502

[12] CHURCH R L,SCAPARRA M P.Protecting Critical Assets:the R-Interdiction Median Problem with Fortification[J].Geographical Analysis,2006,39(2):129-46

[13] SCAPARRA M P,CHURCH R L.A Bilevel Mixed-Integer Program for Critical Infrastructure Protection Planning[J].Computers & Operations Research,2008,35(6):1905-1923

[14] FEDERICO L,MARIA P,DASKIN M S.Analysis of Facility Protection Strategies Against An Uncertain Number Of Attacks:the Stochastic R-Interdiction Median Problem with Fortification[J].Computers & Operations Research,2011,38(1):357-366

[15] ZHU Y,ZHENG Z,ZHANG X,et al.The R-Interdiction Median Problem with Probabilistic Protection and Its Solution Algorithm[J].Computers & Operations Research,2013,40(1):451-462

[16] CARR R D,GREENBERG H J,HART W E,et al.Robust Optimization of Contaminant Sensor Placement For Community Water Systems[J].Mathematical Program-ming,2005,107(1-2):337-356

[17] JAMES J C,SALHI S.A Tabu Search Heuristic for The Location of Multi-Type Protection Devices on Electrical Supply Tree Networks[J].Journal of Combinatorial Optimization,2002,6(1):81-98

[18] GENDREAU M,LAPORTE G,PARENT I.Heuristics for the Location of Inspection Stations on A Network[J].Naval Research Logistics,2000,47(4):287-303

[19] TEODOROVIC D,SELMIC M.Locating Flow-Capturing Facilities in Transportation Networks:A Fuzzy Sets Theory Approach[J].International Journal for Traffic & Transport Engineering,2013,3(2):103-111

[20] PAN Y,DU Y,WEI Z.Reliable facility systems design subject to edge failures:based on the uncapacitated fixed-charge location problem[J].American Journal of Opera-tions Research,2014,4(3):164

[21] FORTZ B,LABBE M.Polyhedral Results for Two-Connected Networks with Bounded Rings[J].Mathematical Program-ming Series,2002,93(1):27-54

[22] LI Q,SAVACHKIN A.Reliable Distribution Networks Design with Nonlinear Fortification Function[J].International Journal of Systems Science,2014 (ahead-of-print):1-9

[23] BAHRI S,RUSMAN M.Reliable Facility Location Model Considering Disruption Risk in Logistic Model[J].Journal of Engineerir1g and Applied Sciences,2013,8(6):177-182

[24] LEE S D,CHANG W.On Solving the Discrete Location Problems When the Facilities Are Prone to Failure[J].Applied Mathematical Modeling,2007,31(5):817-831

[25] CUI T,OUYANG Y,SHEN Z.Reliable Facility Location Design under the Risk of Disruptions[J].Operations Research,2010,58(4):998-1011

[26] ABOOLIAN R,CUI T,SHEN Z J M.An Efficient Approach for Solving Reliable Facility Location Models[J].Informs Journal on Computing,2012,25(4):720-729

[27] HONG J D,JEONG K,XIE Y,et al.A Multi-Objective Approach to Modeling Cost-Effective,Reliable and Robust Emergency Logistics Networks[J].Reliable and Robust EmergencyLogisticsNetworks,2013(12):1-11

[28] YUN L,JI C,LI X,et al.A Reliability Model for Facility Location Design under Imperfect Information[C]∥Transpor-tation Research Board 93rd Annual Meeting,2014:14-4267

[29] LI X,OUYANG Y.A Continuum Approximation Approach to Reliable Facility Location Design under Correlated Probabilistic Disruptions[J].Transportation Research Part B:Methodological,2010,44(4):535-548

[30] LI X,OUYANG Y,PENG F.A Supporting Station Model for Reliable Infrastructure Location Design under Interdependent Disruptions[J].Procedia-Social and Behavioral Sciences,2013,80(1):25-40

[31] TANG X,MAO H.Logistics Facility Location Model Based on Reliability Within the Supply Chain[C]∥Proceedings of the 4th IEEE International Conference on Management of Innovation and Technology,2008:1099-1103

[32] LI Q,SAVACHKIN A.A Fast Tabu Search Algorithm for The Reliable P-Median Problem[M].Advances in Global Optimization.Springer International Publishing,2015

[33] BERMAN O,KRASS D,MENEZES M.Facility Reliability Issues in Network P-Median Problems:Strategic Centralization and Co-Location Effects[J].Operations Research,2007,55(2):332-350

[34] AN Y,ZENG B,ZHANG Y,et al.Reliable P-Median Facility Location Problem:Two-Stage Robust Models and Algorithms[J].Transportation Research Part B:Methodo-logical,2014,64(10):54-72

[35] AYDIN N,MURAT A.A Swarm Intelligence Based Sample Average Approximation Algorithm for the Capacitated Reliable Facility Location Problem[J].International Journal of Production Economics,2013,145(1):173-183

[36] LI Q,ZENG B,SAVACHKIN A.Reliable Facility Location Design under Disruptions[J].Computers & Operations Research,2013,40(4):901-909

[37] SNYDER L V,CAPARRA M,DASKIN M S.Planning for Disruptions in Supply Chain Networks[C]∥Tutorials in Operations Research,INFORMS,2006:234-259

[38] SHEN Z,ZHAN R,ZHANG J.The Reliable Facility Location Problem:Formulations,Heuristics and Approximation Algorithms[R].INFORMS Journal on Computing,2011,23(3):470-482

[39] ZHANG M,HUANG J,ZHU J.Reliable Facility Location Problem Considering Facility Failure Scenarios[J].Kyber-netes,2012,41(10):1440-1461

[40] PENG P,SNYDER L V,LIM A,et al.Reliable Logistics Networks Design with Facility Disruptions[J].Transportation Research Part B:Methodological,2011,45(8):1190-1211

[41] SNYDER L V,DASKIN M S.Models for Reliable Supply Chain Network Design.In Murray A,Grubesic T H.(Ed),Reliability and Vulnerability In Critical Infrastructure:A Quantitative Geographic Perspective[M].Springer,New York,2006

[42] CHURCH R L,SCAPARRA M P,HANLEY J.Optimizing Passive Protection in Facility Systems[R].Working paper,ISOLDEX,Spain,2006

[43] HANLEY J,CHURCH R L.Planning for Facility-Loss:A Bilevel Decomposition Algorithm for The Maximum Covering Location-Interdiction Problem[R].Working paper,Oxford University,Oxford,England,2005

[44] HASSANI A,KHATAMI M,TABRIZI P H.Reliable Center Hub Location Problem:Formulation and Methodology[J].Expert Systems with Applications,2014

[45] LIM M K,BASSAMBOO A,CHOPRA S,et al.Facility Location Decisions with Random Disruptions and Imperfect Estimation[J].Manufacturing & Service Operations Manage-ment,2013,15(2):239-249

[46] LIM M,DASKIN M S.A Facility Reliability Problem:Formulation,Properties and Algorithm[J].Naval Research Logistics,2010,57(1):58-70

[47] WANG X,OUYANG Y.A Continuum Approximation Approach to Competitive Facility Location Design under Facility Disruption Risks[J].Transportation Research Part B:Methodological,2013,50:90-103

[48] JEON H M.Location-Inventory Models with Supply Disruptions[D].PhD thesis,Lehigh University,2008

[49]QI L,SHEN Z,SNYDER L V.The Effect of Supply Disruptions on Supply Chain Design Decisions[J].Trans-portation Science,2010,44(2):274-289

[50] CHEN Q,LI X,OUYANG Y.Joint Inventory-Location Problem under the Risk of Probabilistic Facility Disruptions[J].Transportation Research Part B:Methodolo-gical,2011,45(7):991-1003

责任编辑:天虹

A Review of Reliability Facility Location Problem under theRisk of Facility Disruptions

ZHOU Yu-feng1,2

(1.School of Business Planning,Chongqing Technology and Business University,Chongqing 400067,China;2.Chongqing Engineering Technology Research Center for Information Management in Development,Chongqing Technology and Business University,Chongqing 400067,China)

Abstract:The reliability facility location problem is a frontier problem of the current location research area.The sources and classifications of disruption risk,as well as the characteristics of some issues related to reliability facility location problem (RFLP) were analyzed.Based on the decision-maker's risk attitude,RFLP was categorized as minimum expected cost problem and worst-case cost problem.And the former was further divided into two categories:reliability uncapacitated fixed-charge location problem and reliability P-median problem.Then the state-of-art of these studies was reviewed from the aspects of models and algorithms. Finally,the current status and managerial insights of RFLP were summarized,and its future research directions were put forward.

Key words:facility location; facility disruptions; reliability; literature review

中图分类号:O221.2

文献标志码:A

文章编号:1672-058X(2016)02-0058-10

作者简介:周愉峰(1984-),男,湖南双峰人,讲师,博士,从事应急物流与应急管理、物流系统优化研究.

*基金项目:教育部人文社会科学研究项目(15XJC630009);重庆市教委科学技术研究项目(KJ1500603);重庆市自然科学基金项目(CSTC2013JCYJA0998).

收稿日期:2015-11-02;修回日期:2015-12-12.

doi:10.16055/j.issn.1672-058X.2016.0002.013

猜你喜欢

综述可靠性
MAXIMO系统在数控设备可靠性维护中的应用
可靠性管理体系创建与实践
SEBS改性沥青综述
NBA新赛季综述
近代显示技术综述
5G通信中数据传输的可靠性分析
JOURNAL OF FUNCTIONAL POLYMERS
JOURNAL OF FUNCTIONAL POLYMERS
Progress of DNA-based Methods for Species Identification
基于可靠性跟踪的薄弱环节辨识方法在省级电网可靠性改善中的应用研究