徐秀珍,吳國林,牛義鋒,陳思祁
重慶郵電大學(xué) 現(xiàn)代郵政學(xué)院,重慶 400065
物流運輸網(wǎng)絡(luò)是商品安全有效流通的重要基礎(chǔ)設(shè)施,高效穩(wěn)定的物流運輸網(wǎng)絡(luò)對社會和經(jīng)濟(jì)的發(fā)展至關(guān)重要[1-2]。在實際運作過程中,由于受不確定因素的影響,運輸網(wǎng)絡(luò)各條運輸路線上的運輸工具可能處于正常工作狀態(tài)、部分失效狀態(tài)、完全失效狀態(tài)等多種狀態(tài)。因此,各條運輸線路的配送容量是隨機(jī)的,從而導(dǎo)致整個運輸網(wǎng)絡(luò)的運輸容量也是隨機(jī)的。在理論研究中,物流運輸網(wǎng)絡(luò)可以看作由一系列點和邊組成,其中,每個點可以代表需求地、供應(yīng)地、轉(zhuǎn)運中心或者配送中心等,每條邊代表兩點之間的物流活動[3];并且,運輸網(wǎng)絡(luò)常常被建模為一個多態(tài)網(wǎng)絡(luò)模型,網(wǎng)絡(luò)中每條邊具有相互獨立的、有限的、取非負(fù)整數(shù)的隨機(jī)容量。在多態(tài)網(wǎng)絡(luò)模型下,運輸網(wǎng)絡(luò)可靠性是指,網(wǎng)絡(luò)能夠把一定數(shù)量的商品從供應(yīng)地s配送到需求地t的概率。該可靠性指標(biāo)是衡量網(wǎng)絡(luò)在隨機(jī)事件(惡劣天氣、交通事故、車輛故障等)影響下能否持續(xù)提供高效、穩(wěn)定物流配送服務(wù)能力的重要指標(biāo),在網(wǎng)絡(luò)規(guī)劃、設(shè)計與運營等方面越來越受到人們的關(guān)注與重視。
運輸距離對物流運輸網(wǎng)絡(luò)的服務(wù)效率影響巨大,它不但決定了運輸網(wǎng)絡(luò)的規(guī)模大小而且影響著物流運輸時間的長短,因此,運輸距離是評估物流運輸網(wǎng)絡(luò)可靠性的重要因素與指標(biāo)。例如,由于冷鏈商品保質(zhì)期短、易損耗,運輸距離需要控制在合適范圍內(nèi),如果運輸距離太長,會導(dǎo)致冷鏈商品質(zhì)量受損,服務(wù)品質(zhì)下降,最終給商家和消費者都會帶來損失[4-6]。為此,本文關(guān)注運輸距離約束的物流運輸網(wǎng)絡(luò)可靠性問題。
在多態(tài)網(wǎng)絡(luò)模型下,Jane[7]提出了一個包括配送成本的可靠性指標(biāo)Rd,b來評估配送網(wǎng)絡(luò)服務(wù)能力,Rd,b表示網(wǎng)絡(luò)能夠把d單位的商品流從供應(yīng)地s配送到需求地t,且總的配送成本不超過給定預(yù)算費用b的概率[8]。Niu等人[8]研究了計算Rd,b的極小容量向量(簡稱(d,b)-極小路)方法,并構(gòu)建了求解(d,b)-極小路的改進(jìn)數(shù)學(xué)模型。在傳統(tǒng)(d,b)-極小路模型的基礎(chǔ)上,Xu 等人[9]最近提出了新的(d,b)-極小路求解模型,并提出了一種高效的重復(fù)(d,b)-極小路識別方法。在考慮運輸損耗的基礎(chǔ)上,Lin等人[3]將配送網(wǎng)絡(luò)可靠性定義為網(wǎng)絡(luò)輸送到目的地的完整商品數(shù)量能夠滿足市場需求,且總的配送成本不超過給定預(yù)算費用的概率,并且提出了一種計算該可靠性指標(biāo)的方法。
此外,也有學(xué)者從滿意度角度出發(fā)對物流配送網(wǎng)絡(luò)可靠性進(jìn)行了研究。尹小慶等人[7]將行程時間可靠性作為滿意度評價指標(biāo),構(gòu)建了城市冷鏈末端配送站點選址模型。謝婷[8]將托運貨物到達(dá)時間是否滿足要求作為時間滿意度的評判標(biāo)準(zhǔn),將貨物運輸時間滿意度與運輸時間可靠度作為主要約束條件,以運輸總成本最小為優(yōu)化目標(biāo),建立了多式聯(lián)運網(wǎng)絡(luò)優(yōu)化模型。Lin等人[9]將商品運輸時間和中途停留次數(shù)引入滿意度評價,構(gòu)建了多狀態(tài)配送網(wǎng)絡(luò)可靠性評估模型和方法。注意到現(xiàn)有研究在可靠性分析中沒有考慮運輸距離約束問題,而運輸距離對物流運輸網(wǎng)絡(luò)的服務(wù)效率影響巨大,不僅決定運輸網(wǎng)絡(luò)的規(guī)模大小而且影響物流運輸時間的長短。因此,運輸距離是評估物流運輸網(wǎng)絡(luò)可靠性的重要因素與指標(biāo)。以冷鏈物流為例,由于冷鏈商品保質(zhì)期短、易損耗,運輸距離需要控制在合適范圍內(nèi),如果運輸距離太長,會導(dǎo)致冷鏈商品質(zhì)量受損,服務(wù)品質(zhì)下降,最終給商家和消費者都會帶來損失[10-12]。為此,本文關(guān)注距離約束的物流運輸網(wǎng)絡(luò)可靠性問題。
目前,針對距離約束的網(wǎng)絡(luò)可靠性研究大多集中于二態(tài)網(wǎng)絡(luò)(邊只有連通和不連通兩種工作狀態(tài)),其定義為網(wǎng)絡(luò)存在一條距離不超過給定上限的通路的概率[10-11]。注意到二態(tài)網(wǎng)絡(luò)模型只考慮兩種極端狀態(tài),不適用于物流運輸網(wǎng)絡(luò)可靠性分析[12-13]。Zhang 等人[6]首先研究了距離約束的多態(tài)網(wǎng)絡(luò)可靠性問題,并提出了可靠性評估算法。該算法首先利用距離約束判定并刪除冗余邊,然后尋找網(wǎng)絡(luò)所有的d-極小路,最后,將d-極小路代入容斥定理公式計算可靠性。需要指出的是,Zhang等人提出的算法只考慮將冗余邊刪除,而忽略了不存在冗余邊的網(wǎng)絡(luò)中仍然可能存在不滿足距離約束的d-極小路,導(dǎo)致計算結(jié)果出現(xiàn)錯誤。
為了精準(zhǔn)評估物流運輸網(wǎng)絡(luò)的服務(wù)效率,本文考慮運輸距離約束的物流運輸網(wǎng)絡(luò)可靠性指標(biāo),計算該可靠性指標(biāo)的關(guān)鍵是求解運輸距離約束下的d-極小路問題。為了克服現(xiàn)有方法的缺陷,在確定網(wǎng)絡(luò)冗余邊的基礎(chǔ)上,本文構(gòu)建了運輸距離約束下的d-極小路數(shù)學(xué)模型,并提出運輸距離約束下的物流運輸網(wǎng)絡(luò)可靠性評估方法。最后,本文將提出的可靠性指標(biāo)和評估方法應(yīng)用于物流運輸網(wǎng)絡(luò)可靠性分析。結(jié)果表明,距離約束的網(wǎng)絡(luò)可靠性指標(biāo)能夠更加精準(zhǔn)評估物流運輸網(wǎng)絡(luò)的服務(wù)水平,從而為管理者在物流配送網(wǎng)絡(luò)優(yōu)化設(shè)計方面提供決策指導(dǎo)。
本文將物流運輸網(wǎng)絡(luò)看做一個無圈有向網(wǎng)絡(luò),并用G(N,A,W)表示,其中,N={s,1,2,…,n,t}表示節(jié)點集,A={ai|1 ≤i≤m} 表示運輸邊的集合,W=(W1,W2,…,Wm)表示各運輸邊最大運輸能力組成的容量向量,也稱作最大容量向量。在網(wǎng)絡(luò)中,極小路代表一條從s到t的路徑,且不包含有向圈。令P={P1,P2,…,Pp}表示網(wǎng)絡(luò)中所有極小路組成的集合,其中Pi是第i條極小路,p是極小路的總數(shù)量。受隨機(jī)事件的影響,各條運輸邊可能會有不同的容量狀態(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ǎng)絡(luò),本文將極小路也稱作st-路徑,此外,將st-路徑包含的邊的數(shù)量稱為該st-路徑或極小路的長度,記為L(Pj)(1 ≤j≤p),disG-a(u,v)表示包含有向邊a=(u,v)的最短路徑的長度(不包括邊a的長度),本文的網(wǎng)絡(luò)模型滿足以下假設(shè)條件:(1)每個點都完全可靠;(2)各邊的容量狀態(tài)是一個隨機(jī)變量,且服從給定的概率分布;(3)不同邊的容量狀態(tài)在統(tǒng)計上是相互獨立的;(4)網(wǎng)絡(luò)中的流滿足流守恒定律。如圖1 所示的多態(tài)網(wǎng)絡(luò)G中st-路徑集合P={P1,P2,…,P6},p=|P|=6,st-路徑的長度L(Pj)(1 ≤j≤6)如表2所示。
圖1 網(wǎng)絡(luò)GFig.1 Network G
表2 圖G中st-路徑Table 2 st-paths in network G
給定網(wǎng)絡(luò)G(N,A,W),傳統(tǒng)的網(wǎng)絡(luò)可靠性Rst(G,d)是指網(wǎng)絡(luò)能夠把d單位的需求從供應(yīng)地s運輸?shù)叫枨蟮豻的概率[14-16],其中d也稱需求水平。計算Rst(G,d)最常用的方法是利用滿足需求水平d的極小容量向量,簡稱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ǎ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)保證通過每條st-路徑上的流量低于該路徑的容量限制,約束條件(3)指出邊的容量狀態(tài)與通過該邊的網(wǎng)絡(luò)流之間的關(guān)系。當(dāng)找到網(wǎng)絡(luò)所有的d-極小路,Rst(G,d)可以利用不交和方法[18-19]來計算。給出該方法之前,容量向量的比較運算闡明如下。
定義1 給定兩個容量向量X=(x1,x2,…,xm)和Y=(y1,y2,…,ym),X≥Y是指對于i=1,2,…,m都有xi≥yi成立;X>Y是指X≥Y且至少存在一個i使得xi>yi成立。
假設(shè)網(wǎng)絡(luò)所有的d-極小路為X1,X2,…,Xθ,令Φ1={X|X≥X1} ,Φ2={X|X≥X2},…,Φθ={X|X≥Xθ} ,則 利用不交和算法可計算Rst(G,d)如下[20]:
對于給定的需求水平d和距離約束D,距離約束下的網(wǎng)絡(luò)可靠性Rst(G,D,d)是指網(wǎng)絡(luò)能夠?qū)單位的需求從供應(yīng)地s運輸?shù)叫枨蟮豻,且運輸距離不超過D的概率,其中,運輸距離等于流量大于0 的st-路徑的最大長度。根據(jù)Rst(G,D,d)的定義易知,如果網(wǎng)絡(luò)中某條邊只出現(xiàn)在長度大于D的st-路徑中,則這條邊對可靠性沒有任何貢獻(xiàn),稱這樣的邊為冗余邊。
定義2 在網(wǎng)絡(luò)G中,如果邊ai只包含在長度大于D的st-路徑中,則稱ai是冗余邊。
例如,給定D=3,圖1 中的邊a5只出現(xiàn)在st-路徑P1={a1,a5,a6,a9}中,且該條st-路徑的長度為4,因此,a5為冗余邊。檢測冗余邊的方法由下面的引理給出。
引理2[6]如果disG-a(s,u)+disG-a(v,t)≥D,則邊a是冗余邊。
如果網(wǎng)絡(luò)在X下能夠?qū)單位的需求從供應(yīng)地s運輸?shù)叫枨蟮豻,且所有流量大于0的st-路徑的長度不超過D,則稱X為合格容量向量。因此,根據(jù)定義可知Rst(G,D,d)=Pr{X|X為合格容量向量}。為了更高效地計算Rst(G,D,d),Zhang等人[6]提出首先應(yīng)檢測并刪除冗余邊;然后再利用引理1 求解d-極小路;特別地,Zhang等人[6]認(rèn)為不存在冗余邊的網(wǎng)絡(luò)的d-極小路全部是合格容量向量,于是將d-極小路代入公式(4)計算Rst(G,D,d)。但需要指出的是,不存在冗余邊的網(wǎng)絡(luò)的d-極小路不一定滿足距離約束,因此,不一定是合格容量向量。以圖1中的網(wǎng)絡(luò)G為例,假設(shè)D=3,d=2,冗余邊a5被刪去后的化簡網(wǎng)絡(luò)G*如圖2 所示。根據(jù)定義2 可知G*中不存在冗余邊,但對于2-極小路X=(1,1,0,1,1,1,0,2)來說,極小路P3={a1,a4,a7,a9}運輸?shù)牧髁縡3=1 且L(P3)=4 >D。
圖2 化簡后的網(wǎng)絡(luò)G*Fig.2 Simplified network G*
前面已經(jīng)指出,不存在冗余邊的網(wǎng)絡(luò)仍然可能存在長度大于D的st-路徑,從而無法保證化簡后的網(wǎng)絡(luò)的d-極小路全部是合格容量向量。為了保證所有d-極小路滿足距離約束,可以將長度大于D的st-路徑的流量設(shè)置為0?;诖?,在構(gòu)建d-極小路模型時,應(yīng)首先對st-路徑按照長度大小進(jìn)行升序排列,假定L(P1)≤L(P2)≤…≤L(Pg)≤L(Pg+1)≤…≤L(Pp),其中L(Pg+1)>D且L(Pg)≤D,將長度大于D的st-路徑上的流量設(shè)置為0(即不參與流的輸送),則滿足距離約束D的候選d-極小路模型由下面的定理給出。
定理1 在無圈有向網(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。
下面給出一種計算Rst(G,D,d)的算法,該算法首先求解滿足距離約束的d-極小路,然后根據(jù)公式(4)計算可靠性值,具體步驟如下:
輸入:網(wǎng)絡(luò)G(N,A,W),需求水平d,距離約束D。
輸出:可靠性Rst(G,D,d)。
步驟1 利用引理2檢測并刪除G中的所有冗余邊,得到網(wǎng)絡(luò)G*(N*,A*,W*)。
步驟2 利用現(xiàn)有算法(文獻(xiàn)[17]中的算法)搜索網(wǎng)絡(luò)G*(N*,A*,W*)的所有st-路徑。
步驟3 計算所有st-路徑的長度,并按照長度大小 進(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)計算Rst(G,D,d)。
下面分析算法每一步的時間復(fù)雜度:步驟1可以利用經(jīng)典的Dijkstra 算法求解,需要O(m(m+nlogn))[6]時間。找出網(wǎng)絡(luò)中所有st-路徑需要O(λp*)[17],λ為st-路徑的平均長度,p*為無冗余邊網(wǎng)絡(luò)中極小路的數(shù)量。步驟3 需要O(p*(m*+logp*)) 時間。根據(jù)Forghanielahabad and Bonani等人[18]提出的最新算法求解定理1中的模型需要O(m*gθ)時間,其中m*為網(wǎng)絡(luò)G*(N*,A*,W*)中邊的數(shù)量,g為化簡網(wǎng)絡(luò)中滿足直徑約束的st-路徑數(shù)量,θ為定理1求得的所有d-極小路數(shù)量。步驟5 中利用不交和算法計算Rst(G,D,d) 需要時間。注意到,該算法復(fù)雜程度與距離約束D有關(guān),若網(wǎng)絡(luò)中所有st-路徑的長度都不大于距離約束,則算法求得無距離約束的網(wǎng)絡(luò)可靠性值。
考慮圖3所示多態(tài)網(wǎng)絡(luò)H,其中,N={s,1,2,3,4,t},n=4。邊集A=(a1,a2,…,a10),m=|A|=10。為方便計算,現(xiàn)假設(shè)邊ai(1 ≤i≤10)的容量狀態(tài)為0,1,2,狀態(tài)概率分別為0.03,0.07,0.90,距離約束D=3,需求點t的需求為d=5?,F(xiàn)用提出的算法計算Rst(H,3,5)。
圖3 算例網(wǎng)絡(luò)HFig.3 Example network H
步驟1 計 算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 時網(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-路徑長度分別為L(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 時網(wǎng)絡(luò)可靠性為Rst(H,3,5)=0.803 005。
注意到,當(dāng)D=3 時,本文算法中共有6條st-路徑參與流量分配,最后求得18個5-極小路;而Zhang等人[6]的算法利用8條極小路去分配流量,最后產(chǎn)生了20個5-極小路。二者數(shù)量不同是因為Zhang等人[6]的算法只考慮了冗余邊的刪除,沒有考慮到刪除冗余邊后的網(wǎng)絡(luò)仍可能存在不滿足距離約束的st-路徑。在本例中,刪除后的網(wǎng)絡(luò)仍有2 條st-路徑并不滿足距離約束D=3,這就導(dǎo)致5-極小路的計算錯誤。
本章將提出的算法應(yīng)用于物流運輸網(wǎng)絡(luò)可靠性分析。圖4 所示的網(wǎng)絡(luò)是關(guān)于A、B 兩城市之間的一個物流運輸網(wǎng)絡(luò),該網(wǎng)絡(luò)引自文獻(xiàn)[19],包含13個節(jié)點、22條邊。網(wǎng)絡(luò)中各邊ai(1 ≤i≤22)的容量狀態(tài)如表3 所示。在數(shù)值分析中,提出的算法用MATLAB 程序語言實現(xiàn)。表4列出了計算可靠性所消耗的CPU時間,數(shù)值計算的結(jié)果如表4、表5 所示(注意到max(L(Pj))=9,因此,D=9 時等同于沒有距離約束),包括不同距離約束下的冗余邊數(shù)量、st-路徑數(shù)量,滿足距離約束的st-路徑數(shù)量,CPU 時間,以及網(wǎng)絡(luò)可靠性等;為了便于比較,圖5展示了在需求水平d保持不變時,距離約束對可靠性產(chǎn)生的影響。根據(jù)表4、表5、圖5的結(jié)果可以看出:
圖4 一個物流運輸網(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時間Table 4 CPU time
表5 數(shù)值計算結(jié)果Table 5 Numerical results
(1)保持距離約束D不變,當(dāng)5 ≤D≤10 時,隨著網(wǎng)絡(luò)需求水平d的增加,網(wǎng)絡(luò)可靠性下降,算法的運行時間呈增加趨勢。但當(dāng)D=3 時,因為網(wǎng)絡(luò)中不存在滿足距離約束的st-路徑,也不存在滿足距離約束的d-極小路,網(wǎng)絡(luò)的可靠性為0,此時CPU 時間為計算st-路徑花費的時間。當(dāng)D=4 時,刪去冗余邊后的網(wǎng)絡(luò)只有一條st-路徑,當(dāng)d=1 或2 時,對應(yīng)的可靠性分別為0.962 498 312 928 和0.596 240 371 78,但當(dāng)d>2 時,因為該st-路徑的最大容量為2,所以網(wǎng)絡(luò)可靠性為0。
(2)注意到當(dāng)網(wǎng)絡(luò)中不存在冗余邊時,仍有可能存在不滿足距離約束D的st-路徑。比如,距離約束D=6或7 或8 時,刪去冗余邊的網(wǎng)絡(luò)中仍然存在不滿足距離約束的st-路徑。因此,需要利用定理1求解滿足距離約束的所有d-極小路。
(3)在網(wǎng)絡(luò)中,距離約束D取值的變化影響著st-路徑的數(shù)量,進(jìn)而對d-極小路的數(shù)量和網(wǎng)絡(luò)可靠性值產(chǎn)生影響。注意到在某個區(qū)間范圍內(nèi),不同的D值對應(yīng)不同的可靠性值,其中,當(dāng)D≥max(L(Pj))=9 時,Rst(G,D,d) 等于無距離約束下的可靠性Rst(G,d) ;當(dāng)D<min(L(Pj))=4 時,網(wǎng)絡(luò)中不存在滿足距離要求的st-路徑,所以Rst(G,D,d)=0。
(4)當(dāng)距離約束D在某個區(qū)間范圍變化時,網(wǎng)絡(luò)可以保持較為穩(wěn)定的可靠性。譬如,對于圖4 所示網(wǎng)絡(luò),當(dāng)D的取值從9 減少為7 時,無論需求水平d取何值,Rst(G,D,d)與無距離約束的可靠性Rst(G,d)并無太大差別,此時,不同需求水平下網(wǎng)絡(luò)可靠性最大變化率不足0.01‰。此外,當(dāng)d=1,2,3,4時,可靠性計算時間分別節(jié)約了0.21 s、4.36 s、72.905 s、691.114 s。這說明對于某些需求水平來說,利用距離約束可以減少可靠性計算時間,同時獲得比較準(zhǔn)確的可靠性值。
(5)值得注意的是,刪去冗余邊后的網(wǎng)絡(luò)雖然只包含很少的st路徑,但仍能夠保持較高的可靠性水平。譬如,當(dāng)D=4,d=1 時,網(wǎng)絡(luò)只存在一條st-路徑(該路徑由4 條邊,5 個節(jié)點組成),但此時網(wǎng)絡(luò)的可靠性水平仍高達(dá)0.962 498,即Rst(G,4,1) =0.962 498。這說明,從供應(yīng)地s配送到需求地t傳輸d單位需求流量,運輸距離較短的配送路徑對網(wǎng)絡(luò)可靠性具有重要影響。
綜上,本文提出的可靠性評估方法克服了現(xiàn)有算法的缺陷,且數(shù)值結(jié)果表明,合理的運輸距離約束不會對物流運輸網(wǎng)絡(luò)可靠性產(chǎn)生較大影響,但能夠提升可靠性的計算效率;需求水平也同樣影響著距離約束下的網(wǎng)絡(luò)可靠性,當(dāng)需求水平越接近于運輸網(wǎng)絡(luò)的最大承載量時,網(wǎng)絡(luò)可靠性下降越大;較短st-路徑對網(wǎng)絡(luò)可靠性有顯著影響。因此,管理者在物流運輸網(wǎng)絡(luò)運營過程中,應(yīng)合理平衡配送距離、承載容量、可靠性之間的關(guān)系。
運輸距離對物流運輸網(wǎng)絡(luò)服務(wù)質(zhì)量有重要影響,本文聚焦距離約束下的物流運輸網(wǎng)絡(luò)可靠性,并提出有效的評估方法。該可靠性評估方法仍然屬于兩階段方法,第一階段求解滿足距離約束的d-極小路,第二階段利用不交和算法計算可靠性值。為了求解滿足距離約束的d-極小路,在確定網(wǎng)絡(luò)冗余邊的基礎(chǔ)上,本文構(gòu)建了距離約束下的d-極小路數(shù)學(xué)模型。最后,通過數(shù)值實驗對所提出的可靠性評估方法的有效性進(jìn)行了驗證,并分析了運輸距離約束對網(wǎng)絡(luò)可靠性的影響。注意到運輸損耗在物流運輸網(wǎng)絡(luò)中是一個普遍現(xiàn)象,后續(xù)研究考慮將運輸損耗和運輸距離同時納入可靠性分析中,建立合適的可靠性指標(biāo),并提出有效的評估方法。