考慮位置信息的物流配送網(wǎng)絡節(jié)點重要性評估

張 俊，李義華，羅大庸

1.中南林業(yè)科技大學 物流與交通學院，長沙410086

2.中南大學 信息科學與工程學院，長沙410075

1 引言

物流配送都是物流過程重要的作業(yè)環(huán)節(jié)。空間分布不同的各個物流配送中心通過網(wǎng)絡實現(xiàn)信息共享。物流企業(yè)就能根據(jù)貨物實際運輸線路和裝載情況對運輸車輛安排合適的配送中心就近進行中途貨物補載或調(diào)配，提高配送和運輸?shù)暮侠砘??；谶@種考慮，不僅物流配送中心的選址十分重要，而且建立的配送中心的規(guī)模設計更加重要。以零售業(yè)物流為例，僅在同一個城市就會設置多個配送中心。這些配送中心通過網(wǎng)絡通信進行數(shù)據(jù)資源的共享，形成一個專門的物流配送中心的網(wǎng)絡系統(tǒng)。

目前研究物流配送網(wǎng)絡的研究方法有如下兩種。一種是基于運籌學為理論基礎，研究配送網(wǎng)絡系統(tǒng)的節(jié)點選址、路徑優(yōu)化等問題[1-3]；第二種是基于復雜網(wǎng)絡系統(tǒng)為理論基礎，研究配送網(wǎng)絡的網(wǎng)絡特性、魯棒性等問題[4-6]。綜合前面所述，本文將采用第二種方法來分析和研究物流配送網(wǎng)絡的節(jié)點評估問題。借助圖論和復雜網(wǎng)絡理論，每個配送中心視為一個網(wǎng)絡節(jié)點，根據(jù)實際貨流量大小，評價出整個配送網(wǎng)絡中關鍵節(jié)點，有助于幫助企業(yè)合理設置物流配送中心的等級，能對物流配送中心的容量及時調(diào)整，特別是一些有零擔運輸業(yè)務的商家需要在各個物流配送中心進行貨物中轉(zhuǎn)、調(diào)運，提高配送有效性。在實現(xiàn)物流配送的過程中，貨運量和運輸距離是影響其配送網(wǎng)絡節(jié)點的關鍵因素。

應用復雜網(wǎng)絡進行節(jié)點重要性分析，在化工、生產(chǎn)制造等領域都得到較多應用，關于物流領域的研究成果較少，涉及有向加權(quán)網(wǎng)絡節(jié)點評估的研究就更少。如文獻[2]分別通過不同算法計算出快遞網(wǎng)絡的配送時間、貨運中轉(zhuǎn)量、運輸費用等，構(gòu)建具有配送時間約束和節(jié)點最大流量約束的網(wǎng)絡模型，逐層得到成本最小的結(jié)果。文獻[5]針對快遞的訂單數(shù)據(jù)，構(gòu)建企業(yè)配送網(wǎng)絡的拓撲結(jié)構(gòu)，運用重要度評價矩陣確定重要節(jié)點，提出優(yōu)化對策;文獻[6]定義了節(jié)點重要度貢獻矩陣，驗證節(jié)點之間重要性依賴關系，且依賴關系與節(jié)點鄰近的位置相關，并根據(jù)構(gòu)建的貢獻矩陣確定網(wǎng)絡中的重要節(jié)點。鑒于配送網(wǎng)絡具有復雜網(wǎng)絡的特性，可借鑒復雜網(wǎng)絡的一些研究成果[7-15]。如文獻[7]綜合考慮節(jié)點效率、節(jié)點度值和相鄰節(jié)點的重要度貢獻，利用重要度評價矩陣來確定復雜網(wǎng)絡關鍵節(jié)點；文獻[8]將衛(wèi)星時變拓撲網(wǎng)絡分解成一系列穩(wěn)定狀態(tài)的拓撲圖結(jié)構(gòu)，綜合考慮節(jié)點介數(shù)、節(jié)點緊密度和節(jié)點距離的重要度貢獻，設計網(wǎng)絡節(jié)點的重要度評估算法，評估出網(wǎng)絡拓撲圖中各節(jié)點的重要度；文獻[9]借鑒通信系統(tǒng)中“信息量”的定義方法，分析特殊條件下網(wǎng)絡的特征屬性，提出一種有向加權(quán)網(wǎng)絡的節(jié)點重要性評估方法，挖掘出網(wǎng)絡中的核心節(jié)點等；文獻[10]基于網(wǎng)絡模型構(gòu)建三個影響力矩陣，依據(jù)交叉強度指標分析節(jié)點;文獻[15]針對pert網(wǎng)絡，優(yōu)化網(wǎng)絡得路徑積關鍵性的指標。

在以往的物流配送過程中，節(jié)點分析都建立在貨運信息的基礎上，但很多沒有考慮方向性問題，更未考慮其權(quán)重關系。同時，物流配送還受其他因素的影響，例如距離的遠近、節(jié)點就近性等。很多文獻資料中并未將相關因素納入考慮范圍。

綜合上面的描述，本文將在復雜網(wǎng)絡的理論分析方法的基礎上，從物流配送網(wǎng)絡自身的特點考慮，提出節(jié)點交叉信息的概念，同時還考慮運輸成本，加入節(jié)點間的位置信息等因素，更具實用價值。綜合考慮更多關鍵因素，構(gòu)造節(jié)點重要性評估因素的相關矩陣來共同分析和評估一個物流配送網(wǎng)絡中關鍵節(jié)點的重要度問題。

2 有向加權(quán)的物流配送網(wǎng)絡關鍵因素分析

對于一個物流配送網(wǎng)絡，配送節(jié)點的重要性與其貨運信息、地理位置等因素息息相關，可以用相關影響因素的矩陣來表述?；谙嗨茩?quán)原則，下面將逐一對這些因素進行分析，討論其對節(jié)點重要性的影響。

首先，對一個物流配送網(wǎng)絡的模型進行描述。具體的模型和相關符號說明如下：首先一個物流配送網(wǎng)絡模型用G=(V,E)表示。其中，V={v1,v2,…,vn}是網(wǎng)絡模型各個節(jié)點集合，E={e1,e2,…,em}是網(wǎng)絡模型的邊集合，見圖1所示。

圖1 配送網(wǎng)絡示意圖

圖1 中，節(jié)點1 至節(jié)點n 分別表示若干個物流配送點。每個節(jié)點之間通過有向的邊進行連接起來。假設以節(jié)點i 為研究節(jié)點，節(jié)點j 為鄰接節(jié)點，考慮網(wǎng)絡的有向加權(quán)問題，即在節(jié)點i 和j 之間，w(i,j)表示有向邊(i,j)的權(quán)值，w(j,i)表示有向邊(j,i)的權(quán)值。一般來說，w(i,j)≠w(j,i)。每個節(jié)點的位置坐標為（Px,Py）。

2.1 配送節(jié)點間貨運量信息分析

貨運量直觀地視為貨物信息從該節(jié)點流入流出的情況。即，貨物從一個供應點運輸?shù)侥康墓?jié)點，涉及到其運輸路徑的選擇，還可能會途經(jīng)其他節(jié)點。另外，配送過程中會出現(xiàn)配貨點缺貨問題，需要從調(diào)配節(jié)點向缺貨節(jié)點完成貨物調(diào)配。同時，考慮到物流配送網(wǎng)絡中節(jié)點間貨運信息存在方向的差異性，信息大小不對等，將配送網(wǎng)絡中的雙向鏈路轉(zhuǎn)化為兩條方向相反的單向鏈路進行分析，實現(xiàn)一個復雜網(wǎng)絡模型從傳統(tǒng)的無向無權(quán)的網(wǎng)絡結(jié)構(gòu)轉(zhuǎn)化為一個有向加權(quán)的網(wǎng)絡結(jié)構(gòu)。

在物流配送網(wǎng)絡中，邊的權(quán)重視為貨運信息流即數(shù)據(jù)流，每個節(jié)點所包含的信息量來代表節(jié)點的重要程度，不同方向上傳遞不同的信息量，分析網(wǎng)絡的加權(quán)互信息。從相似權(quán)原則出發(fā)，即認為連邊的權(quán)重越大，表示物流配送網(wǎng)絡中兩個配送節(jié)點之間的貨運信息越大，關系越親密。以節(jié)點i 為例，節(jié)點強度視為其連接邊的有向權(quán)值之和，包含該節(jié)點的S(i)=Sin(i)+Sout(i)。其中，是節(jié)點i 的出強度，Sout(i)=

進行節(jié)點重要性評估之前，根據(jù)貨運信息的方向?qū)D1的網(wǎng)絡結(jié)構(gòu)劃分出兩層網(wǎng)絡，以節(jié)點i 為研究節(jié)點，配送網(wǎng)絡劃為以節(jié)點i 為出點的一層網(wǎng)絡和以節(jié)點i 為入點的另一層網(wǎng)絡。先定義節(jié)點的出邊概率和入邊概率以及有向信息，具體如下。

定義1 對從節(jié)點i 指向節(jié)點j 的有向邊(i,j)，則定義節(jié)點i 的出邊概率為：；該節(jié)點j 關于來自節(jié)點i 的入邊概率為。令節(jié)點i 與節(jié)點j 之間的互信息為I(i,j)。 I(i,j)包括了節(jié)點i 指向節(jié)點j 的互信息，定義其為如下形式：

定義2 對于從節(jié)點k 指向節(jié)點i 的有向邊(k,i)，則定義節(jié)點i 的入邊概率為：；該節(jié)點k 關于來自節(jié)點i 的出邊概率為。令節(jié)點i 與節(jié)點k 之間的互信息為I(w,i)。 I(w,i)包括了節(jié)點w指向節(jié)點i 的互信息，則定義其為如下形式：

定義3 令節(jié)點i 的信息量為I(i)，該信息量既包括節(jié)點i 指向其他連接節(jié)點的互信息（輸出信息），也包括其他連接節(jié)點指向節(jié)點i 的互信息（輸入信息）。

僅標識該節(jié)點的輸出信息和輸入信息無法區(qū)別兩者的差別，也無法突出顯示該物流配送網(wǎng)點的主要功能。針對這一問題，本文結(jié)合有向的互信息提出節(jié)點交叉信息的概念，即：

其中，Vout(i)代表節(jié)點i 指向的所有節(jié)點集合，Vin(i)代表指向節(jié)點i 的所有節(jié)點集合，λ ∈(0,1)是一常數(shù)，它的不同取值會影響不同節(jié)點的信息量，導致配送節(jié)點的重要性評價結(jié)果不同。

從定義1～3 可知，通過計算后，所有節(jié)點的信息量可按照從小到大進行排列，信息量越大，代表該節(jié)點的重要性越大。節(jié)點的信息量大小不僅與其自身出強度有關，還與其入強度有關。只要總強度越大，代表與該節(jié)點相關連的信息傳遞越多，表示該節(jié)點越重要。在一個物流配送點，貨物的輸出信息量更能反映該節(jié)點的重要性。就好比一篇學術論文的他引次數(shù)比起該篇論文引用他人的論文次數(shù)更加反映出這篇文章的重要性等。采用交叉信息是在節(jié)點互信息的基礎上進行擴展，作為衡量節(jié)點重要性的一個局部指標。λ 的引入可以用來衡量一個出度很大而入度為0 或入度很大而出度為0的節(jié)點重要性，也更加可以用于評價有向加權(quán)網(wǎng)絡中各節(jié)點重要性。

2.2 配送節(jié)點的位置信息分析

配送網(wǎng)絡中各節(jié)點的位置影響了節(jié)點之間的傳輸路徑。令節(jié)點i 的位置坐標為(Pxi,Pyj)，節(jié)點j 的位置坐標為(Pxj,Pyj)，則根據(jù)位置坐標可確定兩節(jié)點的距離Dij，決定配送系統(tǒng)的最短傳輸路徑。配送網(wǎng)絡中各個節(jié)點通過有效途徑傳播各自的影響。需從兩個方面去考慮，一方面是如果一個配送節(jié)點與其他配送節(jié)點的位置距離越接近，則該配送節(jié)點可提供的貨運和調(diào)配的可能性就越大，表明該配送點的緊密度越高，其在網(wǎng)絡中的地位也更重要；另一方面從網(wǎng)絡拓撲圖看，從發(fā)出節(jié)點到目標節(jié)點的最短路徑中會經(jīng)過其他節(jié)點。如果一個節(jié)點的最短路徑條數(shù)越多，意味著路徑過程中關聯(lián)節(jié)點可能更多。

（1）配送節(jié)點的緊密度分析

定義4 假設一個物流配送網(wǎng)絡具有n 個節(jié)點，其中第i 個配送節(jié)點的緊密度Ci到達其他配送節(jié)點的平均距離倒數(shù)，即為該配送點的緊密度，表示為：

其中，dij表示節(jié)點i 和節(jié)點j 之間最短路徑。若節(jié)點i和節(jié)點j 之間沒有可通路徑，則dij→∞。節(jié)點通過其與網(wǎng)絡中其他節(jié)點的緊密關系來反映其在整個網(wǎng)絡中的地位重要程度。

（2）配送節(jié)點的介數(shù)分析

在物流配送過程中，如果節(jié)點A 和節(jié)點B 之間有k條不同的最短運輸路徑，其中如果有b 條經(jīng)過節(jié)點i，則說明節(jié)點i 在節(jié)點A 和節(jié)點B 的最短路徑中的重要性為比值。這個比值越大，說明節(jié)點i 越重要，反映節(jié)點的“橋梁”作用。從實際意義的角度出發(fā)，這也符合現(xiàn)實物流配送流程，在一定程度上有利于節(jié)約運輸資源，降低運輸成本。

從前面所述，本文考慮配送網(wǎng)絡中各節(jié)點介數(shù)。假設從節(jié)點i 到節(jié)點j 進行配送，則節(jié)點介數(shù)具體表示為。其中，Nij表示節(jié)點i 和節(jié)點j 之間的最短路徑條數(shù)，Nij(l)表示節(jié)點i 和節(jié)點j 之間的最短路徑經(jīng)過節(jié)點l 的條數(shù)。為了區(qū)別以往對節(jié)點介數(shù)的定義，下面重新定義一個節(jié)點在整個網(wǎng)絡中的介數(shù)特性。

定義5 假設一個物流配送網(wǎng)絡具有n 個節(jié)點，會形成n×n 條有向配送路徑。令該配送網(wǎng)絡中第l 個節(jié)點的介數(shù)為：

其中，i=1,2,…,n，j=1,2,…,n，l=1,2,…,n。

3 物流配送網(wǎng)絡節(jié)點關鍵性排序算法

根據(jù)第2章的描述，一個物流配送網(wǎng)絡的節(jié)點關鍵性結(jié)合信息論和圖論，選擇節(jié)點的互信息描述節(jié)點的物流量，節(jié)點的緊密度來描述節(jié)點的位置信息以及節(jié)點介數(shù)來描述節(jié)點間的關聯(lián)性。

綜合上述的三種影響因素，可以得到節(jié)點關鍵性評估矩陣見式（6）。式中，矩陣H 專門針對物流配送網(wǎng)絡進行關鍵節(jié)點分析，對計算公式進行新的詮釋。該算法在網(wǎng)絡連接邊有向加權(quán)的基礎上既考慮節(jié)點自身的位置信息，還考慮節(jié)點間互相的影響，更加引入配送網(wǎng)絡中各配送節(jié)點之間的貨物量情況。

綜合節(jié)點的全局重要性和局部重要性，使算法更適用于分析物流配送網(wǎng)絡的真實情況。通過對矩陣H 分解，則該物流配送網(wǎng)絡中各節(jié)點的關鍵性評估值為：

據(jù)此算法得到的配送節(jié)點的重要性排序結(jié)果能提供更有效的指導作用。下面給出一個物流配送網(wǎng)絡節(jié)點關鍵性的算法步驟。

步驟1 劃分一個物流配送網(wǎng)絡范圍，提取一定運作時期內(nèi)的網(wǎng)絡拓撲圖，確定n 個配送節(jié)點。

步驟2 計算物流配送網(wǎng)絡在穩(wěn)態(tài)下的節(jié)點重要度排序。

For i=1 to n：計算網(wǎng)絡中所有節(jié)點對之間的最短距離dij，根據(jù)式（4）計算每個節(jié)點的緊密度Ci。計算節(jié)點的互信息I(i)和介數(shù)Bi。

步驟3 將步驟2 中計算得到各節(jié)點的影響因素帶入式（7），計算節(jié)點關鍵性評估矩陣H 。

步驟4 根據(jù)步驟3，計算其中每個節(jié)點的關鍵值HI(i)（i=1,2,…,n）。

4 驗證

例1 首先以文獻[12]中圖1的有向加權(quán)網(wǎng)絡為例進行進一步討論。在文獻[12]中，網(wǎng)絡考慮節(jié)點之間方向和互信息，但是節(jié)點間的邊的長度沒有考慮其中。

在本例中，加入邊信息，即圖2和圖3中括號里參數(shù)所示，用來表示節(jié)點間的距離。根據(jù)本文方法對網(wǎng)絡中的網(wǎng)絡節(jié)點的重要性進行計算，并進行對比分析。

圖2 等邊距離的對稱結(jié)構(gòu)型有向加權(quán)網(wǎng)絡拓撲

圖3 不等邊距離的對稱結(jié)構(gòu)型有向加權(quán)網(wǎng)絡拓撲

以圖2 為例子，對網(wǎng)絡參數(shù)進行說明。單以節(jié)點3為例，計算節(jié)點3的I(3)、C3和B3。（1）計算I(3)。需要根據(jù)2.1 節(jié)先計算節(jié)點3 的出強度Sout(3)=3 和入強度Sin(3)=5，得到總強度S(3)。然后根據(jù)式（1）和式（2）計算節(jié)點3 與其他節(jié)點間的互信息I(3,j ，I(k,3 ，其中j ∈Vout(3)，k ∈Vin(3)，再根據(jù)式（3）將節(jié)點入信息和出信息進行加權(quán)處理，此處λ 取值0.8，得到節(jié)點3 的信息值I(3)=7.64。（2）計算C3。事先確定網(wǎng)絡總節(jié)點數(shù)量n=10，再計算節(jié)點3 到各節(jié)點的最短距離d3j，根據(jù)式（4）得到C3。（3）計算B3。首先確定網(wǎng)絡總節(jié)點數(shù)量n=10，再逐一列出各節(jié)點之間的路徑條數(shù)，從其中計算出通過節(jié)點3 的路徑數(shù)量為18 條，根據(jù)式（5）得到B3=0.18。（4）依據(jù)（1）、（2）和（3）的計算方法，依次計算出其他網(wǎng)絡節(jié)點的相關參數(shù)。（5）根據(jù)前面已得的各參數(shù)，進行歸一化處理，計算出式（6），得到節(jié)點重要性評估值。

圖2 基于等位置距離的前提下得到的網(wǎng)絡節(jié)點的重要性排序經(jīng)過計算與文獻[12]中圖1 的計算結(jié)果（兩者的網(wǎng)絡拓撲結(jié)構(gòu)完全相同）進行對比可知，本文中提出的新的網(wǎng)絡節(jié)點關鍵性評估方法是有效的。而在實際的物流配送網(wǎng)絡中，配送節(jié)點的實際位置距離是不相同的（見圖3 中括號所示），就會影響相關節(jié)點的關鍵性。換句話而言，位置距離較短的配送節(jié)點具有更大的優(yōu)先被選擇的優(yōu)勢，其在整個配送網(wǎng)絡中的地位就更加重要。因此，本文中提出的方法考慮節(jié)點的位置信息，將配送節(jié)點的關鍵性排序更加具體化和細化，在表1的最右一豎列已一一列出。對比表1 中前兩個豎列的排序結(jié)果，處于網(wǎng)絡拓撲具有對稱位置結(jié)構(gòu)的節(jié)點也進行關鍵性排序，如節(jié)點1和節(jié)點9，節(jié)點2和節(jié)點10，節(jié)點5和節(jié)點6都分別進行前后排序，更加驗證本文中提出的排序方法比文獻[12]的方法更加合理。

表1 各方法對對稱結(jié)構(gòu)網(wǎng)絡節(jié)點進行重要性評估排序

例2 本例以文獻[9]中的圖1 為基礎網(wǎng)絡模型。該模型是一個包含10節(jié)點的混合加權(quán)網(wǎng)絡。在此將其轉(zhuǎn)換為有向加權(quán)網(wǎng)絡，見圖4。

圖4 混合加權(quán)型非對稱網(wǎng)絡模型

圖4 中考慮各節(jié)點間等距離和不等距離這兩種情況，在圖中用括號表示，形式如（1/*）。等邊距離的情況下圖4的網(wǎng)絡模型與文獻[13]的圖1模型相同。根據(jù)圖4提供的兩種情況，采用本文中提出的方法分別計算圖4中各節(jié)點的關鍵性，并進行排序比較，見表2所示。

文獻[13]利用總強度法對網(wǎng)絡各節(jié)點進行關鍵性排序。該方法容易出現(xiàn)關鍵性評價值相同的情況而無法區(qū)分相應的節(jié)點，例如節(jié)3 和節(jié)點4 的總強度都是5.5。且對于潛在節(jié)點的關鍵性無法準確評估。文獻[9]基于互信息理論，結(jié)合節(jié)點自身強度、節(jié)點之間的強度使得節(jié)點的差異性更為細化，但是不能保證在任何條件下都能做到完全區(qū)分。本文不僅結(jié)合節(jié)點自身強度、節(jié)點之間的強度，而且還賦予兩種強度的權(quán)重比例關系。同時，還充分考慮節(jié)點間的位置信息，分析節(jié)點間距相同和不等的兩種情況下網(wǎng)絡節(jié)點關鍵性的評估值并進行相應排序。從網(wǎng)絡拓撲圖上來看，節(jié)點3、4和8 處于網(wǎng)絡節(jié)點鏈接位置，應該比較重要，排序相對靠前。文獻[13]中這幾個節(jié)點排名較靠后，文獻[9]中節(jié)點3的排序也較靠后，其與靠前一個排序的節(jié)點評估值相差較大。采用本文方法，在等距條件下節(jié)點2、3、4、6和8 排序靠前。這幾個節(jié)點都處于網(wǎng)絡拓撲圖的節(jié)點鏈接位置，一旦出現(xiàn)其中任何一個節(jié)點處斷了，會造成整個或較大局部的網(wǎng)絡不能連通。特別是節(jié)點3、4 和8，會造成整個網(wǎng)絡不能連通。本文方法結(jié)合了節(jié)點的互信息量以及節(jié)點的位置信息，通過計算驗證本文的算法簡單有效，而且更加符合物流配送網(wǎng)絡結(jié)構(gòu)的實際情況。

5 小結(jié)

本文針對配送網(wǎng)絡，構(gòu)建其網(wǎng)絡拓撲圖，綜合考慮節(jié)點間的位置信息以及物流信息量，借助復雜網(wǎng)絡的理論分析手段，對其互信息、緊密度、介數(shù)等特征進行分析。相比以往的物流配送網(wǎng)絡結(jié)構(gòu)研究中，大多數(shù)的文獻只考慮貨運信息量或者是運輸距離，在很大程度上沒有考慮兩者均共同影響物流配送網(wǎng)絡中各節(jié)點的影響力以及有向性問題?；谏鲜隹紤]，借鑒總強度法，一方面考慮配送節(jié)點間貨運的互信息量并進行加權(quán)處理各自節(jié)點的出強度和入強度的權(quán)重比，另一方面考慮配送節(jié)點間距，以及節(jié)點的介數(shù)特性，滿足物流配送過程路徑最短原則以及貨物組裝聯(lián)合運輸?shù)男枰?，提出一種新的節(jié)點關鍵性評估方法。并對該方法進行對比驗證和優(yōu)勢分析。結(jié)果表明該方法能夠有效地排列出節(jié)點關鍵性，有利于進行中心性評估。對于實際的物流配送中心的網(wǎng)絡結(jié)構(gòu)，有利于分析其網(wǎng)絡的復雜性，幫助每個配送中心合理有效地進行貨物儲備和調(diào)配，提高配送中心的效率，具有有效可行的應用指導意義。

表2 各方法對不對稱結(jié)構(gòu)網(wǎng)絡節(jié)點進行重要性評估排序