论文研究 物流运输网络连通可靠性分析的高效分解算法.pdf

可靠性分析是衡量物流运输网络运行服务水平的主要手段之一。给出了一种评估物流运输网络连通可靠性的高效分解算法，算法充分利用分解过程中获得的相关信息，通过引入保持网络可靠性不变的串联边化简、并联边化简以及节点合并等规则，并结合向量集分解方法，能够快速实现对网络状态向量空间的分解，达到提高网络可靠性评估效率的目的。实例分析以及和现有方法的比较验证了算法的性能和分解效率。26016,52(17)Computer Engineering and Applications计算机工程与应用3串联边、并联边化简明的是,这两种化简操作可以反复进行,直到网络中不在引入串联边、并联边化简之前,需要先介绍网络存在串联边、并联边为止。在化简过程中,串联边化简的删边和缩边操作。设X是不确定状态向量集,由于并联边化简的先后次序不影响最后的化简结果A(X)A2(X)中的边的状态是已知的,因此,在网络中可给定不确定状念向量集X,首先确定A1(X)和以对A1(X)和A2(X)中的边进行删边和缩边处理,删4,(x);如果A(X)和A2(X)非空,在网络G中对A1(X)边是指把选定的边从网终中删去;而缩边是指把边删去和A2(X)中的边进行缩边和删边处理;接着搜寻网终中的同时,把被删去的边的起点和末点合并成一个节点。的串联边、并联边,再利川串联边化简,并联边化简对网当该边的状忐为0时,删边处理不影响网络的状态性络实施化简,得到子网络G”。需要注意的是,此时对应能;当该边的状态为1时,缩边处理不影晌网络的状态于子网络G*的状态向量集不再是X。根据网络化简性能"。图2是对这两种操作的解释。前后各边之间的对应关系得到子网终G*的状态向量集x*,显然满足A1(X)=41(X*),A2(X)=A2(X),从而X*仍是不确定状态向量集。在子网络中,容易求得从s到t的一条极小路。特别地,可以利川 Dijkstra最短路算法络G求得子网络中从s到t的一条最短极小路(包含边最少的极小路)MP。假设MP={a2,a2,…,an}是这条最短极小路,基于MP中的边,就可以从中分离出可行状态向量集,而可行状态向量集正是计算网络可靠性所需子树络G-3子树络G3要的。图2对a1的删边和缩边分解方法保持可靠性不变的网络化简在可靠性计算中具有由于MP是了网络的极小路,当MP中的边的状态重要作用。对于拓扑结构角定的网间络,网络化简很容易为1时,MP∪A(x)构成原冈络的极小路。为了不致混实现,而化简后子网络的复杂度将显著降低(点和边减淆,下面仍用符号X表示子网络的不确定状态向量集。少了)。因此,保持可靠性不变的网络化简是提高可给定不确定状态向量集X=(x1,x2,…,x。)x,=1当靠性计算效率最有效的手段之一。下面介绍两种最实a1∈A1(X),x1=0当a1∈A2(X)0≤x,≤1当a1=(A-4X),用的保持可靠性个变的网络化简规则。(1)联边化简:设a和是网络G的两条联和最短极小路MP=(a“。按如下方式被边,则a和a可以用边a替代,得到网络G*,且满足分解成q+1个子集(1)以a.为轴心:Pa=P。Pa,和R(G)=R(G+)。x={(x1,x2,…,x)如果a2∈A(X),则x,=1;如果(2)并联边化简。设a1和a是树终G的两条并联a∈(A2(X)U{a2},则x=0;如果a1∈(A-A(X)-{a2}),边,则a1和a,可以用边a替代,得到网络G*,且满足则0≤x≤1}。Pa=1-4。qa,R(G)=R(G*)。(2)以a.为轴心为了便于理解,这两种网络化简如图3所示。需要X2={(x1,x2…x以如果a1∈(41(X)U{a2),则x;=1指出的是删边和缩边操作的目的是为了方便浮找网络中存在的串联边并联边,因为朋边、缩边以后的网络更如果a∈(A,(X)U{a,}),则x=0;如果a1∈(4-A(X容易确定边之间的申联并联关系;而串联边化简、并联{a2a2}),则0≤x≤1}。边化简的目的是为了降低可靠性计算的复杂度,以及寻找从s到t的最短极小路(后面将会说明)。另外需要说(q)以a.为轴心x={(x1,x2…x)如果a1∈(4(X)J{a1a2…a(a)串联化简则x=1;如果a∈(42(X)U{a2}),则x=0;如果a∈(A-A(X)-MP),则0≤x≤1}q+1)x°={(x12x2,…,x)如果a∈(A(x)儿MP)(b)并联化简则x1=1;如果a1∈A2(X),则x1=0;如果a∈(A-A(X图3网络串联边、并联边化筒MP),则0≤x1≤}。徐秀珍,曾旗:物流运输网络连通可靠性分析的高效分解算法2016,52(17)27定理1(1)状态向量集X=xU∪X2∪…Uⅹ"∪x。持可靠性不变的串联边化简,并联边化简。如果化简后(2)子集X,x2,…,x,x0非空,且气不相交。(3)子集了网络G*的可靠性R(G*)可以直接计算,令R、=R、+x是可行状态向量集(4)子集X(1≤9)不是可行状RG"),停止;香则,确定对应于子网络G*的向量集x态向量集。步骤5根据最短路算法在G*中确定MP,基于证明(1)根据分解结果,显然有x=X∪(xx)=MP,利用定理1中的分解方法把x分解成x,x*,xUxU(X(Ux)=…=XUxU…UX∪(Xk*和X*0步骤6R,=R+P(x4)。Ux)=XUX2U…UXUx步骤7令Ⅹ=(≤q),转向步骤2(2)根据分解结果可知X(0≤iq)非空。考虑向面给出的算法充分利用分解过程中产生的相关信息,在删边、缩边操作基础上,通过引入串联边化简量集X和X(1≤ij≤q),对于x∈X和x+*∈X。显然x中的第z个分量为1,而x*中的第z1个分量为0并联边化简以及节点合并等规则,并结合向量集分解方法,使得可行状态向量集很容易被分离出来;由于采用从而有x≠x*,所以X和X不相交。再考虑X和了各种网络化简方法,算法在求解过程中俑环分解的次x≤i≤q),对于x∈X和x∈x,显然x中的第z个数较少,从而具有更高的计算效率。特别地,当网络化分量为1,而x*中的第21个分量为0,从而有x≠x*,因简以后,如果可靠性在步骤4中就可以直接计算出来此ⅹ和ⅹ不相交。综上,X,X2,…,X,X非空,且则下面的分解过程(即步骤5到步骤7)将不再需要。互不相交(3)如前所述,MPUA1(x)构成原网络的一条极小6实例路,从而X是可行状态向量集把图1所示的网络G作为实例来展示算法的求解(4)假设某个x(≤i≤)是可行状态向量集。则过程,假定网络G中各边的连通状态概率为P=PA(X)U(a,a2…,a}构成原网络的一个极小路,从0.95,72=P24=090,7=096。在求解过程中,X的分而{2“2“,}构成子网络的极小路,这显然与MP解结果用x表示。具体步骤如下是子网络的最短极小路相矛盾,因为{a,an,…,a1}步骤1X=9={(x1x2,x3,x4x)0≤x,≤1当0≤i≤5}步骤2A1(X)=,A2(X)=。A2(X)不能构成网络是MP的子集。因此,x0)不是可行状态向量集。的极小割。定理1的作用主要体现在从不确定状态向量集X步骤3由于A(X)和A(X)都是空集,缩边和删边中分离出可行状态向量集X"。且知道,X1,X2处理取消x和x不是可行状态向量集。因此,需要判定步骤4网络不存在串联边和并联边,网络化简取消。X(≤≤q是不可行状态向量集还是不确定状态向量步骤5子网络还是G,利用最短路算法求得从s到集。如果A2(X)中的边能组成极小割,则x是不可行t的最短极小路为MP-{a1,a}根据定理1,则X被分状态向量集,不可行状态向量集对可靠性计算没有页解成如下子集:X={(x1,x2,x3,x,xx1=0,0≤x≤1献,不再被考虑反之,X就是不确定状态向量集,从而2≤<5;x2=(,x2x,x1,x)x=1,x1=0,0≤x2≤1,0≤按照相同的方式对网络作进一步化简,对X作进一步x3≤1,0≤x3≤B,X0=(x,2x2x,x,xx1=1,x41,0≤分解,使得从ⅹ中再次分离出可行状态向量集。这样x2≤1,0≤x2≤1.0≤5≤1}。的化简和分解过程循环进行下去,直到不存在不确定状步骤6R=R。+P(x")=0+0.855=0.85态向量集为止。鉴于各个子集是坏不相交的,刚络两终端可靠性就等于所有可行状态向量集的概率之和步骤7循环1:%第一轮循环%(1)X=X5算法(2)A1(X)=⑦,A2(X)={a1}A2(X)不能构成网络的根据上面的分析,算法的具体步骤为极小割。步骤1令X=9(3)A1(X)是空集,A4(X)={a},从而对a1进行删步骤2确定A(x)和A2(X)。如果A2(X)能构成边处理。个极小割,则X是不可行状态向量集,停止。(4)在网络中,a3和a4是串联边。a3和a4用边a34步骤3如果A(x)和A2(X)非空,对A(X和A2(替代,且满足Pa1=P2Pa,=0.855;a34又与a3并联,则a34屮的边实施缩边和删边处理和a3用边a34替代,并且满足P2n=1-(1-P2,)1-P2)步骤4搜寻网终的串联边、并联边,对网终实施保0.9942。又因为a25与a1串联,则对应于X的网络可28016,52(17)Computer Engineering and Applications计算机工程与应用靠性可以直接计算出来RG)=41DPn=0.044739。参考文献:则R,=R2,+RG*)=0.8551044739=0899739。1国务院国务院关于印发物流业发展中长期规划(2014循环2:%第二轮循环2020年)的通知[EB/OL](2014-10-04.htp:www.gov.cn(1)X=Xzhengce/content/2014-10/04/content 9120. htm(2)A(X)={a},A2(X)={(a44(Y)不能构成刚络【2凤凰科技双国快递估计7.66亿件,单日峰值14亿EBOI](2015-11-11)htp:/ /tech. ifengn com/a/20151111504746的极小割O.shtml(3)A1(X)={a1},A2(X)={a},从而对a1进行缩边处[3]陈德良物流网络可靠性的关键问题与应用研究[D]长沙理,对a4进行删边处理中南大学,2010(4)在网络中,a2和a3是并联边。a2和a3用边a23[4]许良,高自友基于连通可靠性的城市道路交通离散网络替代,且满足p21=1-1-p2)1-pn)=0995。又因为没计问题[燕山大学学报,2007,31(2):159-163a23与a5串联,则对应于X的网络可靠性可以直接计算5]许良交通运输网络可靠性研究分析门中国安全科学学出来即R(G*)=p2nP0、P=0.090744。则R、,=R+报,2007,17(1):135-1406]牛义锋,韦纯福,赵宁基最大流理论和分解技术的多态R(G*)=0.899739+0.090744-0.990483。即网络的连系统可靠性评佔[J模糊系统与数学,2013,27(5):182-190通可靠性为0.990483「刀]牛义锋,王艳红,徐秀珍计算网络两终端可靠度的新分解为了进一步检验算法的分解效率把图4所示的网算法[J计算机工程与应用,2011,47(30):79-82.络G1作为例子,网络G1中各边的连通状态概率为P1=8]侯本伟,王威,苏经宇,等计算网络s可靠性的百接不交P4=P8=P10=0.95,P2=P3=0.96,P3=P6=0.90,P3=0.92界限值算法门北京工业大学学报,2013,39(4):500-506P。=098用本文算法来计算,只需要7次循环分解就9刘威,李杰网络可靠度分析的最小路算法和最小割算法可以计算出终G的可靠性为0.995845,而其他分解研究门地震工程与工程震动,2008,28(3):33-38算法需要的分解次数则远大于7次。为了便于比铰,不[10刘威,李杰生命线网络可靠度分析的改进最小路递推分同算法求解网络G和网络G1的结果列于表1中。由表1解算法[J地震工程与工程震动,2009,29(5):66-72可以看出,本文提出的算法在分解效率方面明显优于其1 Vilson J M.An improved minimizing algorithm for sumof disjoint products [J].IFFE Transactions on Reliability他算法。990,39(1):42-45[12] Mishra R. Saifi M A, Chaturvedi S K Enumeration ofminimal cutsets for directed networks with comparative reliability study for paths or cuts. Quality andReliability Engineering International, 2015[13 Moskow itz F The analysis of redundancy networks[J]IEEE Transactions on Communications and electronics图4网络G11958,77(5):627-632表1不同算法的比较[14]崔磊,肖宇峰,黄玉清.因子分解二终端网终可靠度近似是否需要枚举所有分解次数计算[门计算机工程与应用,201248(12):53-56.算法极小路(割网终G网终[15 Wood P K Factoring algorithms for computing K-terminal不交极小路(割)需要network reliability[J].IEEE Transactions on Reliability因子分解算法不需要1461986,35(3):269-278文献[7]不需要[16]孙艳蕊,毕继国,张祚德计算有圈有向网络根通信可靠本文方法不需要度的因子分解算法[J东北大学学报:自然科学版,201031(4):486-4897结论[17 Ball M ComputaTional complexity of network reli-可靠性是衡量物流运输网络服务水平的一个重要bility analysis an overview[J].IEEE Transactions on指标。本文提出一种评佔物流运输网络两终端可靠性Reliability,1986,35(13):230-239的高效算法,算法充分利用分解过程中产生的相关信[18] Shier D Network reliability and algebraic structures[M息,通过引入保持可靠性不变的串联边化简、并联边化New York. USA: Clarendon press. 1991简以及节点合并等规则,并结合给出的向量集分解方19] Hardy g, Lucet C., Limnios n.K-terminal network reli法,在较大程度上能够减少向量集的分解次数,从而达ability measures with binary decision diagrams[J]到提高可靠性评估效率的目的IEEE Transactions on Reliability, 2007, 56(3): 506-515