徐秀珍，吳國(guó)林，牛義鋒，陳思祁

重慶郵電大學(xué) 現(xiàn)代郵政學(xué)院，重慶 400065

物流運(yùn)輸網(wǎng)絡(luò)是商品安全有效流通的重要基礎(chǔ)設(shè)施，高效穩(wěn)定的物流運(yùn)輸網(wǎng)絡(luò)對(duì)社會(huì)和經(jīng)濟(jì)的發(fā)展至關(guān)重要[1-2]。在實(shí)際運(yùn)作過(guò)程中，由于受不確定因素的影響，運(yùn)輸網(wǎng)絡(luò)各條運(yùn)輸路線上的運(yùn)輸工具可能處于正常工作狀態(tài)、部分失效狀態(tài)、完全失效狀態(tài)等多種狀態(tài)。因此，各條運(yùn)輸線路的配送容量是隨機(jī)的，從而導(dǎo)致整個(gè)運(yùn)輸網(wǎng)絡(luò)的運(yùn)輸容量也是隨機(jī)的。在理論研究中，物流運(yùn)輸網(wǎng)絡(luò)可以看作由一系列點(diǎn)和邊組成，其中，每個(gè)點(diǎn)可以代表需求地、供應(yīng)地、轉(zhuǎn)運(yùn)中心或者配送中心等，每條邊代表兩點(diǎn)之間的物流活動(dòng)[3]；并且，運(yùn)輸網(wǎng)絡(luò)常常被建模為一個(gè)多態(tài)網(wǎng)絡(luò)模型，網(wǎng)絡(luò)中每條邊具有相互獨(dú)立的、有限的、取非負(fù)整數(shù)的隨機(jī)容量。在多態(tài)網(wǎng)絡(luò)模型下，運(yùn)輸網(wǎng)絡(luò)可靠性是指，網(wǎng)絡(luò)能夠把一定數(shù)量的商品從供應(yīng)地s配送到需求地t的概率。該可靠性指標(biāo)是衡量網(wǎng)絡(luò)在隨機(jī)事件（惡劣天氣、交通事故、車(chē)輛故障等）影響下能否持續(xù)提供高效、穩(wěn)定物流配送服務(wù)能力的重要指標(biāo)，在網(wǎng)絡(luò)規(guī)劃、設(shè)計(jì)與運(yùn)營(yíng)等方面越來(lái)越受到人們的關(guān)注與重視。

運(yùn)輸距離對(duì)物流運(yùn)輸網(wǎng)絡(luò)的服務(wù)效率影響巨大，它不但決定了運(yùn)輸網(wǎng)絡(luò)的規(guī)模大小而且影響著物流運(yùn)輸時(shí)間的長(zhǎng)短，因此，運(yùn)輸距離是評(píng)估物流運(yùn)輸網(wǎng)絡(luò)可靠性的重要因素與指標(biāo)。例如，由于冷鏈商品保質(zhì)期短、易損耗，運(yùn)輸距離需要控制在合適范圍內(nèi)，如果運(yùn)輸距離太長(zhǎng)，會(huì)導(dǎo)致冷鏈商品質(zhì)量受損，服務(wù)品質(zhì)下降，最終給商家和消費(fèi)者都會(huì)帶來(lái)?yè)p失[4-6]。為此，本文關(guān)注運(yùn)輸距離約束的物流運(yùn)輸網(wǎng)絡(luò)可靠性問(wèn)題。

在多態(tài)網(wǎng)絡(luò)模型下，Jane[7]提出了一個(gè)包括配送成本的可靠性指標(biāo)Rd,b來(lái)評(píng)估配送網(wǎng)絡(luò)服務(wù)能力，Rd,b表示網(wǎng)絡(luò)能夠把d單位的商品流從供應(yīng)地s配送到需求地t，且總的配送成本不超過(guò)給定預(yù)算費(fèi)用b的概率[8]。Niu等人[8]研究了計(jì)算Rd,b的極小容量向量（簡(jiǎn)稱(d,b)-極小路）方法，并構(gòu)建了求解(d,b)-極小路的改進(jìn)數(shù)學(xué)模型。在傳統(tǒng)(d,b)-極小路模型的基礎(chǔ)上，Xu 等人[9]最近提出了新的(d,b)-極小路求解模型，并提出了一種高效的重復(fù)(d,b)-極小路識(shí)別方法。在考慮運(yùn)輸損耗的基礎(chǔ)上，Lin等人[3]將配送網(wǎng)絡(luò)可靠性定義為網(wǎng)絡(luò)輸送到目的地的完整商品數(shù)量能夠滿足市場(chǎng)需求，且總的配送成本不超過(guò)給定預(yù)算費(fèi)用的概率，并且提出了一種計(jì)算該可靠性指標(biāo)的方法。

此外，也有學(xué)者從滿意度角度出發(fā)對(duì)物流配送網(wǎng)絡(luò)可靠性進(jìn)行了研究。尹小慶等人[7]將行程時(shí)間可靠性作為滿意度評(píng)價(jià)指標(biāo)，構(gòu)建了城市冷鏈末端配送站點(diǎn)選址模型。謝婷[8]將托運(yùn)貨物到達(dá)時(shí)間是否滿足要求作為時(shí)間滿意度的評(píng)判標(biāo)準(zhǔn)，將貨物運(yùn)輸時(shí)間滿意度與運(yùn)輸時(shí)間可靠度作為主要約束條件，以運(yùn)輸總成本最小為優(yōu)化目標(biāo)，建立了多式聯(lián)運(yùn)網(wǎng)絡(luò)優(yōu)化模型。Lin等人[9]將商品運(yùn)輸時(shí)間和中途停留次數(shù)引入滿意度評(píng)價(jià)，構(gòu)建了多狀態(tài)配送網(wǎng)絡(luò)可靠性評(píng)估模型和方法。注意到現(xiàn)有研究在可靠性分析中沒(méi)有考慮運(yùn)輸距離約束問(wèn)題，而運(yùn)輸距離對(duì)物流運(yùn)輸網(wǎng)絡(luò)的服務(wù)效率影響巨大，不僅決定運(yùn)輸網(wǎng)絡(luò)的規(guī)模大小而且影響物流運(yùn)輸時(shí)間的長(zhǎng)短。因此，運(yùn)輸距離是評(píng)估物流運(yùn)輸網(wǎng)絡(luò)可靠性的重要因素與指標(biāo)。以冷鏈物流為例，由于冷鏈商品保質(zhì)期短、易損耗，運(yùn)輸距離需要控制在合適范圍內(nèi)，如果運(yùn)輸距離太長(zhǎng)，會(huì)導(dǎo)致冷鏈商品質(zhì)量受損，服務(wù)品質(zhì)下降，最終給商家和消費(fèi)者都會(huì)帶來(lái)?yè)p失[10-12]。為此，本文關(guān)注距離約束的物流運(yùn)輸網(wǎng)絡(luò)可靠性問(wèn)題。

目前，針對(duì)距離約束的網(wǎng)絡(luò)可靠性研究大多集中于二態(tài)網(wǎng)絡(luò)（邊只有連通和不連通兩種工作狀態(tài)），其定義為網(wǎng)絡(luò)存在一條距離不超過(guò)給定上限的通路的概率[10-11]。注意到二態(tài)網(wǎng)絡(luò)模型只考慮兩種極端狀態(tài)，不適用于物流運(yùn)輸網(wǎng)絡(luò)可靠性分析[12-13]。Zhang 等人[6]首先研究了距離約束的多態(tài)網(wǎng)絡(luò)可靠性問(wèn)題，并提出了可靠性評(píng)估算法。該算法首先利用距離約束判定并刪除冗余邊，然后尋找網(wǎng)絡(luò)所有的d-極小路，最后，將d-極小路代入容斥定理公式計(jì)算可靠性。需要指出的是，Zhang等人提出的算法只考慮將冗余邊刪除，而忽略了不存在冗余邊的網(wǎng)絡(luò)中仍然可能存在不滿足距離約束的d-極小路，導(dǎo)致計(jì)算結(jié)果出現(xiàn)錯(cuò)誤。

為了精準(zhǔn)評(píng)估物流運(yùn)輸網(wǎng)絡(luò)的服務(wù)效率，本文考慮運(yùn)輸距離約束的物流運(yùn)輸網(wǎng)絡(luò)可靠性指標(biāo)，計(jì)算該可靠性指標(biāo)的關(guān)鍵是求解運(yùn)輸距離約束下的d-極小路問(wèn)題。為了克服現(xiàn)有方法的缺陷，在確定網(wǎng)絡(luò)冗余邊的基礎(chǔ)上，本文構(gòu)建了運(yùn)輸距離約束下的d-極小路數(shù)學(xué)模型，并提出運(yùn)輸距離約束下的物流運(yùn)輸網(wǎng)絡(luò)可靠性評(píng)估方法。最后，本文將提出的可靠性指標(biāo)和評(píng)估方法應(yīng)用于物流運(yùn)輸網(wǎng)絡(luò)可靠性分析。結(jié)果表明，距離約束的網(wǎng)絡(luò)可靠性指標(biāo)能夠更加精準(zhǔn)評(píng)估物流運(yùn)輸網(wǎng)絡(luò)的服務(wù)水平，從而為管理者在物流配送網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)方面提供決策指導(dǎo)。

1 網(wǎng)絡(luò)模型及預(yù)備知識(shí)

1.1 網(wǎng)絡(luò)模型

本文將物流運(yùn)輸網(wǎng)絡(luò)看做一個(gè)無(wú)圈有向網(wǎng)絡(luò)，并用G(N,A,W)表示，其中，N={s,1,2,…,n,t}表示節(jié)點(diǎn)集，A={ai|1 ≤i≤m} 表示運(yùn)輸邊的集合，W=(W1,W2,…,Wm)表示各運(yùn)輸邊最大運(yùn)輸能力組成的容量向量，也稱作最大容量向量。在網(wǎng)絡(luò)中，極小路代表一條從s到t的路徑，且不包含有向圈。令P={P1,P2,…,Pp}表示網(wǎng)絡(luò)中所有極小路組成的集合，其中Pi是第i條極小路，p是極小路的總數(shù)量。受隨機(jī)事件的影響，各條運(yùn)輸邊可能會(huì)有不同的容量狀態(tài)。因此，用xi表示邊ai的一種容量狀態(tài)，其中0 ≤xi≤Wi；并且，用X=(x1,x2,…,xm) 表示容量向量，表明各條邊所處的容量狀態(tài)。其中網(wǎng)絡(luò)G各邊容量狀態(tài)如表1所示。

表1 圖G各邊的容量數(shù)據(jù)Table 1 Capacity data for each edge in network G

鑒于本文所討論的網(wǎng)絡(luò)為無(wú)圈有向網(wǎng)絡(luò)，本文將極小路也稱作st-路徑，此外，將st-路徑包含的邊的數(shù)量稱為該st-路徑或極小路的長(zhǎng)度，記為L(zhǎng)(Pj)(1 ≤j≤p)，disG－a(u,v)表示包含有向邊a=(u,v)的最短路徑的長(zhǎng)度（不包括邊a的長(zhǎng)度），本文的網(wǎng)絡(luò)模型滿足以下假設(shè)條件：（1）每個(gè)點(diǎn)都完全可靠；（2）各邊的容量狀態(tài)是一個(gè)隨機(jī)變量，且服從給定的概率分布；（3）不同邊的容量狀態(tài)在統(tǒng)計(jì)上是相互獨(dú)立的；（4）網(wǎng)絡(luò)中的流滿足流守恒定律。如圖1 所示的多態(tài)網(wǎng)絡(luò)G中st-路徑集合P={P1,P2,…,P6}，p=|P|=6，st-路徑的長(zhǎng)度L(Pj)(1 ≤j≤6)如表2所示。

圖1 網(wǎng)絡(luò)GFig.1 Network G

表2 圖G中st-路徑Table 2 st-paths in network G

1.2 預(yù)備知識(shí)

給定網(wǎng)絡(luò)G(N,A,W)，傳統(tǒng)的網(wǎng)絡(luò)可靠性Rst(G,d)是指網(wǎng)絡(luò)能夠把d單位的需求從供應(yīng)地s運(yùn)輸?shù)叫枨蟮豻的概率[14-16]，其中d也稱需求水平。計(jì)算Rst(G,d)最常用的方法是利用滿足需求水平d的極小容量向量，簡(jiǎn)稱d-極小路，Lin 等人[17]最先提出求解d-極小路的數(shù)學(xué)模型，現(xiàn)有研究也大多采用該模型。令fj(1 ≤j≤p)代表第j條st-路徑中的流量，所有fj(1 ≤j≤p)組成的向量稱為可行流向量，記作F=(f1,f2,…,fp)，則Lin 等人[17]的模型由引理1給出。

引理1 在無(wú)圈有向網(wǎng)絡(luò)G中，容量向量X=(x1,x2,…,xm)是d-極小路，當(dāng)且僅當(dāng)下面的條件成立：

其中，CPj=min{Wi|ai∈Pj}是第j條st-路徑的最大容量。引理1 中，約束條件（1）保證網(wǎng)絡(luò)的最大需求水平為d，約束條件（2）保證通過(guò)每條st-路徑上的流量低于該路徑的容量限制，約束條件（3）指出邊的容量狀態(tài)與通過(guò)該邊的網(wǎng)絡(luò)流之間的關(guān)系。當(dāng)找到網(wǎng)絡(luò)所有的d-極小路，Rst(G,d)可以利用不交和方法[18-19]來(lái)計(jì)算。給出該方法之前，容量向量的比較運(yùn)算闡明如下。

定義1 給定兩個(gè)容量向量X=(x1,x2,…,xm)和Y=(y1,y2,…,ym)，X≥Y是指對(duì)于i=1,2,…,m都有xi≥yi成立；X＞Y是指X≥Y且至少存在一個(gè)i使得xi＞yi成立。

假設(shè)網(wǎng)絡(luò)所有的d-極小路為X1,X2,…,Xθ，令Φ1={X|X≥X1} ，Φ2={X|X≥X2},…,Φθ={X|X≥Xθ} ，則 利用不交和算法可計(jì)算Rst(G,d)如下[20]：

2 距離約束下的網(wǎng)絡(luò)可靠性計(jì)算

2.1 距離約束下的網(wǎng)絡(luò)可靠性

對(duì)于給定的需求水平d和距離約束D，距離約束下的網(wǎng)絡(luò)可靠性Rst(G,D,d)是指網(wǎng)絡(luò)能夠?qū)單位的需求從供應(yīng)地s運(yùn)輸?shù)叫枨蟮豻，且運(yùn)輸距離不超過(guò)D的概率，其中，運(yùn)輸距離等于流量大于0 的st-路徑的最大長(zhǎng)度。根據(jù)Rst(G,D,d)的定義易知，如果網(wǎng)絡(luò)中某條邊只出現(xiàn)在長(zhǎng)度大于D的st-路徑中，則這條邊對(duì)可靠性沒(méi)有任何貢獻(xiàn)，稱這樣的邊為冗余邊。

定義2 在網(wǎng)絡(luò)G中，如果邊ai只包含在長(zhǎng)度大于D的st-路徑中，則稱ai是冗余邊。

例如，給定D=3，圖1 中的邊a5只出現(xiàn)在st-路徑P1={a1,a5,a6,a9}中，且該條st-路徑的長(zhǎng)度為4，因此，a5為冗余邊。檢測(cè)冗余邊的方法由下面的引理給出。

引理2[6]如果disG－a(s,u)+disG－a(v,t)≥D，則邊a是冗余邊。

如果網(wǎng)絡(luò)在X下能夠?qū)單位的需求從供應(yīng)地s運(yùn)輸?shù)叫枨蟮豻，且所有流量大于0的st-路徑的長(zhǎng)度不超過(guò)D，則稱X為合格容量向量。因此，根據(jù)定義可知Rst(G,D,d)=Pr{X|X為合格容量向量}。為了更高效地計(jì)算Rst(G,D,d)，Zhang等人[6]提出首先應(yīng)檢測(cè)并刪除冗余邊；然后再利用引理1 求解d-極小路；特別地，Zhang等人[6]認(rèn)為不存在冗余邊的網(wǎng)絡(luò)的d-極小路全部是合格容量向量，于是將d-極小路代入公式（4）計(jì)算Rst(G,D,d)。但需要指出的是，不存在冗余邊的網(wǎng)絡(luò)的d-極小路不一定滿足距離約束，因此，不一定是合格容量向量。以圖1中的網(wǎng)絡(luò)G為例，假設(shè)D=3，d=2，冗余邊a5被刪去后的化簡(jiǎn)網(wǎng)絡(luò)G*如圖2 所示。根據(jù)定義2 可知G*中不存在冗余邊，但對(duì)于2-極小路X=（1，1，0，1，1，1，0，2）來(lái)說(shuō)，極小路P3={a1,a4,a7,a9}運(yùn)輸?shù)牧髁縡3=1 且L(P3)=4 ＞D。

圖2 化簡(jiǎn)后的網(wǎng)絡(luò)G*Fig.2 Simplified network G*

2.2 距離約束下的d-極小路模型

前面已經(jīng)指出，不存在冗余邊的網(wǎng)絡(luò)仍然可能存在長(zhǎng)度大于D的st-路徑，從而無(wú)法保證化簡(jiǎn)后的網(wǎng)絡(luò)的d-極小路全部是合格容量向量。為了保證所有d-極小路滿足距離約束，可以將長(zhǎng)度大于D的st-路徑的流量設(shè)置為0?；诖耍跇?gòu)建d-極小路模型時(shí)，應(yīng)首先對(duì)st-路徑按照長(zhǎng)度大小進(jìn)行升序排列，假定L(P1)≤L(P2)≤…≤L(Pg)≤L(Pg+1)≤…≤L(Pp)，其中L(Pg+1)＞D且L(Pg)≤D，將長(zhǎng)度大于D的st-路徑上的流量設(shè)置為0（即不參與流的輸送），則滿足距離約束D的候選d-極小路模型由下面的定理給出。

定理1 在無(wú)圈有向網(wǎng)絡(luò)G中，假定L(P1)≤L(P2)≤…≤L(Pg)≤L(Pg+1)≤…≤L(Pp),L(Pg+1)＞D，L(Pg)≤D，容量向量X=(x1,x2,…,xm)為滿足距離約束D的d-極小路當(dāng)且僅當(dāng)下面的條件成立：

需要注意的是，在引理1中，j的取值范圍為1 ≤j≤p，但是在約束條件（5）中，j的取值范圍為1 ≤j≤g，其中，g≤p。

2.3 算法

下面給出一種計(jì)算Rst(G,D,d)的算法，該算法首先求解滿足距離約束的d-極小路，然后根據(jù)公式（4）計(jì)算可靠性值，具體步驟如下：

輸入：網(wǎng)絡(luò)G(N,A,W)，需求水平d，距離約束D。

輸出：可靠性Rst(G,D,d)。

步驟1 利用引理2檢測(cè)并刪除G中的所有冗余邊，得到網(wǎng)絡(luò)G*(N*,A*,W*)。

步驟2 利用現(xiàn)有算法（文獻(xiàn)[17]中的算法）搜索網(wǎng)絡(luò)G*(N*,A*,W*)的所有st-路徑。

步驟3 計(jì)算所有st-路徑的長(zhǎng)度，并按照長(zhǎng)度大小 進(jìn)行 升序排列，假 定L(P1)≤L(P2)≤…≤L(Pg)≤L(Pg+1)≤…≤L(Pp),L(Pg+1)＞D且L(Pg)≤D。

步驟4 利用2.2節(jié)定理1求解所有d-極小路。

步驟5 利用公式（4）計(jì)算Rst(G,D,d)。

下面分析算法每一步的時(shí)間復(fù)雜度：步驟1可以利用經(jīng)典的Dijkstra 算法求解，需要O(m(m+nlogn))[6]時(shí)間。找出網(wǎng)絡(luò)中所有st-路徑需要O(λp*)[17]，λ為st-路徑的平均長(zhǎng)度，p*為無(wú)冗余邊網(wǎng)絡(luò)中極小路的數(shù)量。步驟3 需要O(p*(m*+logp*)) 時(shí)間。根據(jù)Forghanielahabad and Bonani等人[18]提出的最新算法求解定理1中的模型需要O(m*gθ)時(shí)間，其中m*為網(wǎng)絡(luò)G*(N*,A*,W*)中邊的數(shù)量，g為化簡(jiǎn)網(wǎng)絡(luò)中滿足直徑約束的st-路徑數(shù)量，θ為定理1求得的所有d-極小路數(shù)量。步驟5 中利用不交和算法計(jì)算Rst(G,D,d) 需要時(shí)間。注意到，該算法復(fù)雜程度與距離約束D有關(guān)，若網(wǎng)絡(luò)中所有st-路徑的長(zhǎng)度都不大于距離約束，則算法求得無(wú)距離約束的網(wǎng)絡(luò)可靠性值。

2.4 算例

考慮圖3所示多態(tài)網(wǎng)絡(luò)H，其中，N={s,1,2,3,4,t}，n=4。邊集A=(a1,a2,…,a10)，m=|A|=10。為方便計(jì)算，現(xiàn)假設(shè)邊ai(1 ≤i≤10)的容量狀態(tài)為0，1，2，狀態(tài)概率分別為0.03，0.07，0.90，距離約束D=3，需求點(diǎn)t的需求為d=5?，F(xiàn)用提出的算法計(jì)算Rst(H,3,5)。

圖3 算例網(wǎng)絡(luò)HFig.3 Example network H

步驟1 計(jì) 算Dis(ak)=disG－a(s,u)+disG－a(v,t) 。得Dis(a1)=2，Dis(a2)=1，Dis(a3)=1，Dis(a4)=2，Dis(a5)=2，Dis(a6)=2，Dis(a7)=2，Dis(a8)=1，Dis(a9)=2，Dis(a10)=1。判斷Dis(ak)≥3？判斷得，D=3 時(shí)網(wǎng)絡(luò)圖H中不存在冗余邊。輸出新網(wǎng)絡(luò)圖H*(N*,A*,W*)。其中，N*={s,1,2,3,4,t} ，n=4 ，邊集A*=(a1,a2,…,a10)，m=|A|=10。

步驟2 網(wǎng)絡(luò)圖H*(N*,A*,W*)中所有的st-路徑為P1=(a2,a10)，P2=(a1,a5,a10)，P3=(a2,a6,a9)，P4=(a1,a5,a6,a9) ，P5=(a1,a4,a8) ，P6=(a3,a7,a9) ，P7=(a1,a4,a7,a9)，P8=(a3,a8)。

步驟3 步驟2 中st-路徑長(zhǎng)度分別為L(zhǎng)(P1)=2 ，L(P2)=3，L(P3)=3，L(P4)=4 ，L(P5)=3，L(P6)=3，L(P7)=4 ，L(P8)=2 ，排 序 得L(P1)≤L(P8)≤L(P2)≤L(P3)≤L(P5)≤L(P6)≤D＜L(P4)≤L(P7)。其中L(P4)＞D和L(P7)＞D。

步驟4 所有滿足定理的5-極小路為X1=（1，2，2，1，0，1，2，0，2，1），X2=（2，1，2，2，0，1，2，0，2，1），X3=（2，2，1，1，1，1，2，0，2，1），X4=（1，2，2，0，1，0，2，1，2，1），X5=（2，1，2，1，1，0，2，1，2，1），X6=（2，2，1，0，2，0，2，1，2，1），X7=（2，2，1，2，0，2，2，0，1，2），X8=（1，2，2，1，0，1，2，1，1，2），X9=（2，1，2，2，0，1，2，1，1，2），X10=（2，2，1，1，1，1，0，0，2，2），X11=（1，2，2，0，1，0，2，2，1，2），X12=（2，1，2，1，1，0，2，2，1，2），X13=（1，2，2，1，0，2，1，0，2，2），X14=（2，2，1，1，1，2，1，0，2，2），X15=（1，2，2，0，1，1，1，1，2，2），X16=（2，1，2，1，1，1，1，1，2，2），X17=（2，2，1，0，2，1，1，1，2，2），X18=（2，1，2，0，2，0，1，2，2，2）。

步驟5 利用不交和方法求得D=3，d=5 時(shí)網(wǎng)絡(luò)可靠性為Rst(H,3,5)=0.803 005。

注意到，當(dāng)D=3 時(shí)，本文算法中共有6條st-路徑參與流量分配，最后求得18個(gè)5-極小路；而Zhang等人[6]的算法利用8條極小路去分配流量，最后產(chǎn)生了20個(gè)5-極小路。二者數(shù)量不同是因?yàn)閆hang等人[6]的算法只考慮了冗余邊的刪除，沒(méi)有考慮到刪除冗余邊后的網(wǎng)絡(luò)仍可能存在不滿足距離約束的st-路徑。在本例中，刪除后的網(wǎng)絡(luò)仍有2 條st-路徑并不滿足距離約束D=3，這就導(dǎo)致5-極小路的計(jì)算錯(cuò)誤。

3 實(shí)際案例分析

本章將提出的算法應(yīng)用于物流運(yùn)輸網(wǎng)絡(luò)可靠性分析。圖4 所示的網(wǎng)絡(luò)是關(guān)于A、B 兩城市之間的一個(gè)物流運(yùn)輸網(wǎng)絡(luò)，該網(wǎng)絡(luò)引自文獻(xiàn)[19]，包含13個(gè)節(jié)點(diǎn)、22條邊。網(wǎng)絡(luò)中各邊ai(1 ≤i≤22)的容量狀態(tài)如表3 所示。在數(shù)值分析中，提出的算法用MATLAB 程序語(yǔ)言實(shí)現(xiàn)。表4列出了計(jì)算可靠性所消耗的CPU時(shí)間，數(shù)值計(jì)算的結(jié)果如表4、表5 所示（注意到max(L(Pj))=9，因此，D=9 時(shí)等同于沒(méi)有距離約束），包括不同距離約束下的冗余邊數(shù)量、st-路徑數(shù)量，滿足距離約束的st-路徑數(shù)量，CPU 時(shí)間，以及網(wǎng)絡(luò)可靠性等；為了便于比較，圖5展示了在需求水平d保持不變時(shí)，距離約束對(duì)可靠性產(chǎn)生的影響。根據(jù)表4、表5、圖5的結(jié)果可以看出：

圖4 一個(gè)物流運(yùn)輸網(wǎng)絡(luò)Fig.4 Logistics transportation network

圖5 不同距離約束下的網(wǎng)絡(luò)可靠性Fig.5 Reliabilities under different distance constraints

表3 圖4網(wǎng)絡(luò)各條邊的容量狀態(tài)Table 3 Capacity data for each edge in Fig.4

表4 CPU時(shí)間Table 4 CPU time

表5 數(shù)值計(jì)算結(jié)果Table 5 Numerical results

（1）保持距離約束D不變，當(dāng)5 ≤D≤10 時(shí)，隨著網(wǎng)絡(luò)需求水平d的增加，網(wǎng)絡(luò)可靠性下降，算法的運(yùn)行時(shí)間呈增加趨勢(shì)。但當(dāng)D=3 時(shí)，因?yàn)榫W(wǎng)絡(luò)中不存在滿足距離約束的st-路徑，也不存在滿足距離約束的d-極小路，網(wǎng)絡(luò)的可靠性為0，此時(shí)CPU 時(shí)間為計(jì)算st-路徑花費(fèi)的時(shí)間。當(dāng)D=4 時(shí)，刪去冗余邊后的網(wǎng)絡(luò)只有一條st-路徑，當(dāng)d=1 或2 時(shí)，對(duì)應(yīng)的可靠性分別為0.962 498 312 928 和0.596 240 371 78，但當(dāng)d＞2 時(shí)，因?yàn)樵搒t-路徑的最大容量為2，所以網(wǎng)絡(luò)可靠性為0。

（2）注意到當(dāng)網(wǎng)絡(luò)中不存在冗余邊時(shí)，仍有可能存在不滿足距離約束D的st-路徑。比如，距離約束D=6或7 或8 時(shí)，刪去冗余邊的網(wǎng)絡(luò)中仍然存在不滿足距離約束的st-路徑。因此，需要利用定理1求解滿足距離約束的所有d-極小路。

（3）在網(wǎng)絡(luò)中，距離約束D取值的變化影響著st-路徑的數(shù)量，進(jìn)而對(duì)d-極小路的數(shù)量和網(wǎng)絡(luò)可靠性值產(chǎn)生影響。注意到在某個(gè)區(qū)間范圍內(nèi)，不同的D值對(duì)應(yīng)不同的可靠性值，其中，當(dāng)D≥max(L(Pj))=9 時(shí)，Rst(G,D,d) 等于無(wú)距離約束下的可靠性Rst(G,d) ；當(dāng)D＜min(L(Pj))=4 時(shí)，網(wǎng)絡(luò)中不存在滿足距離要求的st-路徑，所以Rst(G,D,d)=0。

（4）當(dāng)距離約束D在某個(gè)區(qū)間范圍變化時(shí)，網(wǎng)絡(luò)可以保持較為穩(wěn)定的可靠性。譬如，對(duì)于圖4 所示網(wǎng)絡(luò)，當(dāng)D的取值從9 減少為7 時(shí)，無(wú)論需求水平d取何值，Rst(G,D,d)與無(wú)距離約束的可靠性Rst(G,d)并無(wú)太大差別，此時(shí)，不同需求水平下網(wǎng)絡(luò)可靠性最大變化率不足0.01‰。此外，當(dāng)d=1，2，3，4時(shí)，可靠性計(jì)算時(shí)間分別節(jié)約了0.21 s、4.36 s、72.905 s、691.114 s。這說(shuō)明對(duì)于某些需求水平來(lái)說(shuō)，利用距離約束可以減少可靠性計(jì)算時(shí)間，同時(shí)獲得比較準(zhǔn)確的可靠性值。

（5）值得注意的是，刪去冗余邊后的網(wǎng)絡(luò)雖然只包含很少的st路徑，但仍能夠保持較高的可靠性水平。譬如，當(dāng)D=4，d=1 時(shí)，網(wǎng)絡(luò)只存在一條st-路徑（該路徑由4 條邊，5 個(gè)節(jié)點(diǎn)組成），但此時(shí)網(wǎng)絡(luò)的可靠性水平仍高達(dá)0.962 498，即Rst(G,4,1) =0.962 498。這說(shuō)明，從供應(yīng)地s配送到需求地t傳輸d單位需求流量，運(yùn)輸距離較短的配送路徑對(duì)網(wǎng)絡(luò)可靠性具有重要影響。

綜上，本文提出的可靠性評(píng)估方法克服了現(xiàn)有算法的缺陷，且數(shù)值結(jié)果表明，合理的運(yùn)輸距離約束不會(huì)對(duì)物流運(yùn)輸網(wǎng)絡(luò)可靠性產(chǎn)生較大影響，但能夠提升可靠性的計(jì)算效率；需求水平也同樣影響著距離約束下的網(wǎng)絡(luò)可靠性，當(dāng)需求水平越接近于運(yùn)輸網(wǎng)絡(luò)的最大承載量時(shí)，網(wǎng)絡(luò)可靠性下降越大；較短st-路徑對(duì)網(wǎng)絡(luò)可靠性有顯著影響。因此，管理者在物流運(yùn)輸網(wǎng)絡(luò)運(yùn)營(yíng)過(guò)程中，應(yīng)合理平衡配送距離、承載容量、可靠性之間的關(guān)系。

4 結(jié)語(yǔ)

運(yùn)輸距離對(duì)物流運(yùn)輸網(wǎng)絡(luò)服務(wù)質(zhì)量有重要影響，本文聚焦距離約束下的物流運(yùn)輸網(wǎng)絡(luò)可靠性，并提出有效的評(píng)估方法。該可靠性評(píng)估方法仍然屬于兩階段方法，第一階段求解滿足距離約束的d-極小路，第二階段利用不交和算法計(jì)算可靠性值。為了求解滿足距離約束的d-極小路，在確定網(wǎng)絡(luò)冗余邊的基礎(chǔ)上，本文構(gòu)建了距離約束下的d-極小路數(shù)學(xué)模型。最后，通過(guò)數(shù)值實(shí)驗(yàn)對(duì)所提出的可靠性評(píng)估方法的有效性進(jìn)行了驗(yàn)證，并分析了運(yùn)輸距離約束對(duì)網(wǎng)絡(luò)可靠性的影響。注意到運(yùn)輸損耗在物流運(yùn)輸網(wǎng)絡(luò)中是一個(gè)普遍現(xiàn)象，后續(xù)研究考慮將運(yùn)輸損耗和運(yùn)輸距離同時(shí)納入可靠性分析中，建立合適的可靠性指標(biāo)，并提出有效的評(píng)估方法。