復雜軍事物流網絡的配送路徑優化研究＊

陳 曄 張勇明 趙金超

（海軍工程大學管理工程系 武漢 430033）

1 引言

物流網絡是一個與我們的生活、工作、社會經濟環境密切相關的復雜大系統。應用復雜網絡理論分析物流網絡拓撲結構的復雜性，是研究復雜物流網絡的關鍵所在，也是物流網絡研究的基礎理論問題之一［1～4］。

隨著信息化程度的提高，軍事物流體系也實現了信息化、網絡化，例如裝備物資器材的物流網絡，也屬于物流網絡的一種，但是其運行效率受到多種因素的影響，并具有以下兩個顯著特點：一是自主性、選擇性，該物流網絡不僅具有與其它物流網絡相似的拓撲特性，而且具有不同于其他網絡的顯著特點，這些特性要深入分析拓撲結構，對物流網絡的承載能力及物流路徑的優化進行研究；二是適應性和動態性，該物流網絡由于外部作用的驅動或內部因素的作用，網絡的拓撲結構不是固定的、成熟的，所以需要從整個網絡系統角度出發，對物流網絡的節點及節點的物流特性進行分析與合理規劃和管理，以達到有效緩解物流配送瓶頸的目的。

本文以裝備物資器材物流網絡為研究對象，將倉庫抽象成節點，運輸的公路、鐵路、航空線路抽象成邊，隨著節點和邊的數量和連接越來越復雜，可以使用復雜網絡理論來分析該軍事物流網絡。首先建立該物流網絡拓撲結構模型，分析其保障功能區分，然后運用啟發式算法對配送路徑進行優化，最后結合保障實例給出了最佳的配送路徑方案。

2 復雜軍事物流網絡建模及特性分析

這里以裝備物資器材的物流網絡為例，將倉庫所在地抽象成節點，運輸的公路、鐵路、航空線路抽象成邊，為了便于建模和仿真計算，保證網絡中節點和邊相互存在的合理性，需要作出如下假設：

1）國內鐵路、航空、公路可以連接任何一個國內節點，但不一定直接連接；

2）部分交通樞紐開通航空航線，且兩兩直接相連。

根據以上假設，形成裝備物資器材復雜物流網絡的拓撲圖，見圖1。

圖1中圓圈代表倉庫所在地，其中大的圓圈代表開通航空航線的樞紐，小的圓圈代表使用公路、鐵路運輸的樞紐，連線代表運輸的路徑。該圖中共有23個節點和45條邊。

分析該裝備物資器材物流網絡的特性，具有兩個顯著特點：1）網絡的增長性，該物流網絡在運行過程中，隨著保障任務的變化，網絡中的節點數量不是一成不變的，會有節點的增加或者減少；2）優先粘貼性，在保障任務運行中，新加入節點與網絡中已經存在的關鍵節點（如國內交通樞紐等）優先粘貼。這兩個特性，可以用無標度網絡（scale－free）來描述。

圖1 裝備物資器材物流網絡拓撲圖

3 基于啟發式算法的復雜軍事物流網絡路徑優化

3.1 啟發式算法描述及仿真結論

本文運用近期提出的一種啟發式算法［5～8］，優化該復雜物流網絡的路徑來解決網絡的擁塞問題，算法的核心是通過合理分配連接之間的權重來減小或避免信息量過載。但是以上算法沒有考慮節點的等待時間（或者信息處理時間）而造成的時延，缺點是網絡中關鍵節點會高度擁擠，最終會導致網絡分裂成幾個互不連接的網絡。文獻［9］提出使用動態路徑協議（當網絡發生擁塞時以數據包的插入率來優化），來避免關鍵節點引起擁塞以改進網絡的容量。

提出的啟發式算法，是通過調整網絡中最大介數的大小，以改善網絡的路徑結構，最終達到提高網絡信息容量的目的。

為便于比較，本課題使用文獻［9］中的scale－free網絡模型（網絡節點數N在25～1600之間）來描述該算法。假設所有節點在同一時間步長有相同的數據包流量，每個節點在同一時間步長同頻率的插入r個新的數據包，數據包的目的地在剩下的N－1個節點中隨機選擇。

對于給定的路由表，從源節點s到目標節點t經過節點i的數據包數量這樣計算：

首先給源節點s分配權重l，然后沿著t→s的路由表，每一個節點的權重平均分配在其前者上，然后再增加其前者的權重。那么，從源節點s經過給定節點i的平均數據包數為

當達到臨界平均插入率rc后網絡發生擁塞，rc由公式（1）給出：

其中，Bmax是網絡中節點的最大介數。

為了達到最優路徑，Bmax應該最小。本文提出的優化算法通過增加最初空閑節點的流量來降低經過最初繁忙節點的流量，這樣介數分布會變得更加狹窄，最終會重塑網絡的介數結構。

3.2 仿真分析

3.2.1 四種路徑協議

文獻［9］中提到的三種路徑協議，加上本文提出的最優算法路徑協議，比較和其他三種算法的優劣。四種路徑協議分別是最短路徑協議（用SP表示），最優算法（用OR表示），有效路徑協議（用ER表示），hub失效協議（用 HA表示）。

3.2.2 仿真結論

1）四種路徑協議下〈Bmax〉、〈Bavg〉與網絡大小N 的相關性

針對圖1構建的裝備物資器材復雜物流網絡，運用Matlab－Simulink仿真工具，仿真〈Bmax〉（最大介數的平均值）、〈Bavg〉（平均介數的平均值）與網絡中節點數N之間有冪率相關性。這里仿真比較四種路徑協議的優劣。

圖2 四種路徑協議下網絡節點數N與〈Bmax〉之間的關系

圖3 四種路徑協議下網絡節點數N與〈Bavg〉之間的關系

其中：SP表示最短路徑協議，OR表示最優算法，ER表示有效路徑協議，HA表示hub失效協議。

表1 〈Bmax〉、〈Bavg〉與網絡節點數N之間對應的冪率指數（估計誤差為2σ）

從圖2～3可以看出，OR算法較其它三種算法優秀，結果使Bmax、Bavg之間的差值最小。最終，〈Bavg〉OR－〈Bavg〉SP（大于〈Bavg〉ER－〈Bavg〉SP或者〈Bavg〉HA－〈Bavg〉SP）差值保持很低，而且〈Bavg〉OR與網絡大小N 的冪率指數稍高于〈Bavg〉SP對應的指數（詳見表1對應的數據）。

2）Bmax與迭代次數的函數關系

本文提出的啟發式算法，最大介數做為迭代次數的函數并不是單調的，但是表現出遞減的趨勢，最終最大介數限制在一個較窄的范圍內。這里仍以圖1構建的裝備物資器材復雜物流網絡為例，運用 Matlab－Simulink仿真工具，仿真出Bmax與迭代次數之間的函數曲線（見圖4），這樣可以幫助我們找到對應的全局最小Bmax。

圖4 Bmax與迭代次數之間的函數曲線

3）優化前后介數分布情況比對

該算法使用給定路由表的網絡平均介數Bavg提供了最大介數的下限，只有當優化路徑使得所有節點有相同流量時才能達到該下限。網絡的最大介數和平均介數之間的差距，同樣也是衡量介數分布范圍的尺度。而且當最短路徑上的權重都設置為1的時候，使用任意路由表計算的平均介數會達到其下限。由于任何最短路徑的變化會導致更長路徑，這樣會增加整個網絡的介數，顯然一個好的優化算法，應該具備以下兩種特征：

（1）最大介數和平均介數差最小；

（2）同時保持使用最佳路由表和最短路徑兩種方法計算的平均路徑的差盡可能小。

這里針對圖1的網絡，運用 Matlab－Simulink仿真工具，仿真其介數分布，通過控制介數的分布，來優化網絡的路徑結構。

圖5給出了經過優化算法前、后裝備物資器材復雜物流網絡介數分布圖。從圖5可以看出：優化前大多數節點有較低的介數，其中有一小部分節點介數分布在寬廣的范圍，經過啟發式算法優化后，所有節點的介數被限制在一個狹窄的范圍內，尤其是分布上限被嚴格限制，大多數節點統一分布在一個范圍內，其上限有很明顯的峰值而后有顯著的遞減趨勢。這驗證了該算法可以明顯減小最大介數和平均介數的差值，以優化網絡的結構。

圖5 優化前、后網絡中介數分布圖

4 仿真實例分析

這里假設有以下四種保障任務，需要從某倉庫調出某型器材配送到某港口，具體任務見表2。

表2 裝備物資器材復雜物流網絡保障任務

根據優化算法，將每類補給途徑的補給時間和補給成本假設為權重l1，l2，單位分別以小時和萬元表示。根據以上考慮，制定出補給路線的路由表（見表3）。

表3 裝備物資器材補給路由表

根據表3和前面提到的啟發式算法，可以計算出每項補給任務補給路徑的對應值（見表4）。

表4 裝備物資器材補給路徑對應值

考慮到戰時裝備物資器材物流網絡會因為保障任務的增加而變得繁忙，某些節點會因為出入庫物資器材過多而產生網絡擁塞，這里假設圖6中節點2、5出現擁塞，結合本文使用的最優算法路徑協議和節點的保障任務分工，得到最終的優化補給方案，見表5。

圖6 裝備物資器材物流實例圖

表5 優化后的裝備物資器材補給方案

5 結語

本文以裝備物資器材軍事物流網絡為研究對象，建立了其拓撲模型，提出運用啟發式路徑優化算法，并通過Matlab－Simulink對復雜參數的仿真，結合四個保障實例，提出了最佳的保障補給方案，該優化方法為提高軍事物流網絡的保障效率提供了一定的理論參考。

［1］李慈.基于復雜系統理論的配送網絡優化研究［D］.西安：西北工業大學碩上學位論文，2006.

［2］黃建華.快遞網絡的復雜性及魯棒性分析［J］.西南交通大學學報，2009（12）：98－102.

［3］牛永亮，王金妹.物流配送車輛路線求解算法［J］.交通運輸工程學報，2006（6）：83－87.

［4］王佳，池潔，王勇.物流中配送路線選擇的優化分析［J］.物流科技，2009（1）：18－20.

［5］M.Ericsson，M.G.C.Resende and P.M.Padalos，Probability distribution of solution time in GRASP：An experimental investigation［J］.Journal of Combinatorial Optimization，2002（6），299－333.

［6］B.Fortzand M.Thorup，Progessive image compression for a power constrained channel［J］.IEEE Journal on Selected Areas in Communications，2002（20）：4.

［7］Gabrel V，Knippel A，Minoux M.A comparison of heuristics for the discrete cost multicommodity network optimization problem［J］.Journal of Heuristics，2003（9）：429－445.

［8］D.Allen，I.Ismail，J.Kennington and E.Olinick，Wireless Network Design：Optimization Models and Solution Procedures［J］.Journal of Heuristics，2003（9）：375－399.

［9］B.Danila，Y.Yu，John A.Marsh and K.E.Bassler，optimal routing on complex networks［J］.arXiv：cond－mat／0607017.