復(fù)雜軍事物流網(wǎng)絡(luò)的配送路徑優(yōu)化研究＊

陳 曄 張勇明 趙金超

（海軍工程大學(xué)管理工程系 武漢 430033）

1 引言

物流網(wǎng)絡(luò)是一個(gè)與我們的生活、工作、社會(huì)經(jīng)濟(jì)環(huán)境密切相關(guān)的復(fù)雜大系統(tǒng)。應(yīng)用復(fù)雜網(wǎng)絡(luò)理論分析物流網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的復(fù)雜性，是研究復(fù)雜物流網(wǎng)絡(luò)的關(guān)鍵所在，也是物流網(wǎng)絡(luò)研究的基礎(chǔ)理論問題之一［1～4］。

隨著信息化程度的提高，軍事物流體系也實(shí)現(xiàn)了信息化、網(wǎng)絡(luò)化，例如裝備物資器材的物流網(wǎng)絡(luò)，也屬于物流網(wǎng)絡(luò)的一種，但是其運(yùn)行效率受到多種因素的影響，并具有以下兩個(gè)顯著特點(diǎn)：一是自主性、選擇性，該物流網(wǎng)絡(luò)不僅具有與其它物流網(wǎng)絡(luò)相似的拓?fù)涮匦裕揖哂胁煌谄渌W(wǎng)絡(luò)的顯著特點(diǎn)，這些特性要深入分析拓?fù)浣Y(jié)構(gòu)，對(duì)物流網(wǎng)絡(luò)的承載能力及物流路徑的優(yōu)化進(jìn)行研究；二是適應(yīng)性和動(dòng)態(tài)性，該物流網(wǎng)絡(luò)由于外部作用的驅(qū)動(dòng)或內(nèi)部因素的作用，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不是固定的、成熟的，所以需要從整個(gè)網(wǎng)絡(luò)系統(tǒng)角度出發(fā)，對(duì)物流網(wǎng)絡(luò)的節(jié)點(diǎn)及節(jié)點(diǎn)的物流特性進(jìn)行分析與合理規(guī)劃和管理，以達(dá)到有效緩解物流配送瓶頸的目的。

本文以裝備物資器材物流網(wǎng)絡(luò)為研究對(duì)象，將倉庫抽象成節(jié)點(diǎn)，運(yùn)輸?shù)墓贰㈣F路、航空線路抽象成邊，隨著節(jié)點(diǎn)和邊的數(shù)量和連接越來越復(fù)雜，可以使用復(fù)雜網(wǎng)絡(luò)理論來分析該軍事物流網(wǎng)絡(luò)。首先建立該物流網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)模型，分析其保障功能區(qū)分，然后運(yùn)用啟發(fā)式算法對(duì)配送路徑進(jìn)行優(yōu)化，最后結(jié)合保障實(shí)例給出了最佳的配送路徑方案。

2 復(fù)雜軍事物流網(wǎng)絡(luò)建模及特性分析

這里以裝備物資器材的物流網(wǎng)絡(luò)為例，將倉庫所在地抽象成節(jié)點(diǎn)，運(yùn)輸?shù)墓贰㈣F路、航空線路抽象成邊，為了便于建模和仿真計(jì)算，保證網(wǎng)絡(luò)中節(jié)點(diǎn)和邊相互存在的合理性，需要作出如下假設(shè)：

1）國內(nèi)鐵路、航空、公路可以連接任何一個(gè)國內(nèi)節(jié)點(diǎn)，但不一定直接連接；

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

根據(jù)以上假設(shè)，形成裝備物資器材復(fù)雜物流網(wǎng)絡(luò)的拓?fù)鋱D，見圖1。

圖1中圓圈代表倉庫所在地，其中大的圓圈代表開通航空航線的樞紐，小的圓圈代表使用公路、鐵路運(yùn)輸?shù)臉屑~，連線代表運(yùn)輸?shù)穆窂健Ｔ搱D中共有23個(gè)節(jié)點(diǎn)和45條邊。

分析該裝備物資器材物流網(wǎng)絡(luò)的特性，具有兩個(gè)顯著特點(diǎn)：1）網(wǎng)絡(luò)的增長性，該物流網(wǎng)絡(luò)在運(yùn)行過程中，隨著保障任務(wù)的變化，網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量不是一成不變的，會(huì)有節(jié)點(diǎn)的增加或者減少；2）優(yōu)先粘貼性，在保障任務(wù)運(yùn)行中，新加入節(jié)點(diǎn)與網(wǎng)絡(luò)中已經(jīng)存在的關(guān)鍵節(jié)點(diǎn)（如國內(nèi)交通樞紐等）優(yōu)先粘貼。這兩個(gè)特性，可以用無標(biāo)度網(wǎng)絡(luò)（scale－free）來描述。

圖1 裝備物資器材物流網(wǎng)絡(luò)拓?fù)鋱D

3 基于啟發(fā)式算法的復(fù)雜軍事物流網(wǎng)絡(luò)路徑優(yōu)化

3.1 啟發(fā)式算法描述及仿真結(jié)論

本文運(yùn)用近期提出的一種啟發(fā)式算法［5～8］，優(yōu)化該復(fù)雜物流網(wǎng)絡(luò)的路徑來解決網(wǎng)絡(luò)的擁塞問題，算法的核心是通過合理分配連接之間的權(quán)重來減小或避免信息量過載。但是以上算法沒有考慮節(jié)點(diǎn)的等待時(shí)間（或者信息處理時(shí)間）而造成的時(shí)延，缺點(diǎn)是網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)會(huì)高度擁擠，最終會(huì)導(dǎo)致網(wǎng)絡(luò)分裂成幾個(gè)互不連接的網(wǎng)絡(luò)。文獻(xiàn)［9］提出使用動(dòng)態(tài)路徑協(xié)議（當(dāng)網(wǎng)絡(luò)發(fā)生擁塞時(shí)以數(shù)據(jù)包的插入率來優(yōu)化），來避免關(guān)鍵節(jié)點(diǎn)引起擁塞以改進(jìn)網(wǎng)絡(luò)的容量。

提出的啟發(fā)式算法，是通過調(diào)整網(wǎng)絡(luò)中最大介數(shù)的大小，以改善網(wǎng)絡(luò)的路徑結(jié)構(gòu)，最終達(dá)到提高網(wǎng)絡(luò)信息容量的目的。

為便于比較，本課題使用文獻(xiàn)［9］中的scale－free網(wǎng)絡(luò)模型（網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)N在25～1600之間）來描述該算法。假設(shè)所有節(jié)點(diǎn)在同一時(shí)間步長有相同的數(shù)據(jù)包流量，每個(gè)節(jié)點(diǎn)在同一時(shí)間步長同頻率的插入r個(gè)新的數(shù)據(jù)包，數(shù)據(jù)包的目的地在剩下的N－1個(gè)節(jié)點(diǎn)中隨機(jī)選擇。

對(duì)于給定的路由表，從源節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t經(jīng)過節(jié)點(diǎn)i的數(shù)據(jù)包數(shù)量這樣計(jì)算：

首先給源節(jié)點(diǎn)s分配權(quán)重l，然后沿著t→s的路由表，每一個(gè)節(jié)點(diǎn)的權(quán)重平均分配在其前者上，然后再增加其前者的權(quán)重。那么，從源節(jié)點(diǎn)s經(jīng)過給定節(jié)點(diǎn)i的平均數(shù)據(jù)包數(shù)為

當(dāng)達(dá)到臨界平均插入率rc后網(wǎng)絡(luò)發(fā)生擁塞，rc由公式（1）給出：

其中，Bmax是網(wǎng)絡(luò)中節(jié)點(diǎn)的最大介數(shù)。

為了達(dá)到最優(yōu)路徑，Bmax應(yīng)該最小。本文提出的優(yōu)化算法通過增加最初空閑節(jié)點(diǎn)的流量來降低經(jīng)過最初繁忙節(jié)點(diǎn)的流量，這樣介數(shù)分布會(huì)變得更加狹窄，最終會(huì)重塑網(wǎng)絡(luò)的介數(shù)結(jié)構(gòu)。

3.2 仿真分析

3.2.1 四種路徑協(xié)議

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

3.2.2 仿真結(jié)論

1）四種路徑協(xié)議下〈Bmax〉、〈Bavg〉與網(wǎng)絡(luò)大小N 的相關(guān)性

針對(duì)圖1構(gòu)建的裝備物資器材復(fù)雜物流網(wǎng)絡(luò)，運(yùn)用Matlab－Simulink仿真工具，仿真〈Bmax〉（最大介數(shù)的平均值）、〈Bavg〉（平均介數(shù)的平均值）與網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)N之間有冪率相關(guān)性。這里仿真比較四種路徑協(xié)議的優(yōu)劣。

圖2 四種路徑協(xié)議下網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)N與〈Bmax〉之間的關(guān)系

圖3 四種路徑協(xié)議下網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)N與〈Bavg〉之間的關(guān)系

其中：SP表示最短路徑協(xié)議，OR表示最優(yōu)算法，ER表示有效路徑協(xié)議，HA表示hub失效協(xié)議。

表1 〈Bmax〉、〈Bavg〉與網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)N之間對(duì)應(yīng)的冪率指數(shù)（估計(jì)誤差為2σ）

從圖2～3可以看出，OR算法較其它三種算法優(yōu)秀，結(jié)果使Bmax、Bavg之間的差值最小。最終，〈Bavg〉OR－〈Bavg〉SP（大于〈Bavg〉ER－〈Bavg〉SP或者〈Bavg〉HA－〈Bavg〉SP）差值保持很低，而且〈Bavg〉OR與網(wǎng)絡(luò)大小N 的冪率指數(shù)稍高于〈Bavg〉SP對(duì)應(yīng)的指數(shù)（詳見表1對(duì)應(yīng)的數(shù)據(jù)）。

2）Bmax與迭代次數(shù)的函數(shù)關(guān)系

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

圖4 Bmax與迭代次數(shù)之間的函數(shù)曲線

3）優(yōu)化前后介數(shù)分布情況比對(duì)

該算法使用給定路由表的網(wǎng)絡(luò)平均介數(shù)Bavg提供了最大介數(shù)的下限，只有當(dāng)優(yōu)化路徑使得所有節(jié)點(diǎn)有相同流量時(shí)才能達(dá)到該下限。網(wǎng)絡(luò)的最大介數(shù)和平均介數(shù)之間的差距，同樣也是衡量介數(shù)分布范圍的尺度。而且當(dāng)最短路徑上的權(quán)重都設(shè)置為1的時(shí)候，使用任意路由表計(jì)算的平均介數(shù)會(huì)達(dá)到其下限。由于任何最短路徑的變化會(huì)導(dǎo)致更長路徑，這樣會(huì)增加整個(gè)網(wǎng)絡(luò)的介數(shù)，顯然一個(gè)好的優(yōu)化算法，應(yīng)該具備以下兩種特征：

（1）最大介數(shù)和平均介數(shù)差最小；

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

這里針對(duì)圖1的網(wǎng)絡(luò)，運(yùn)用 Matlab－Simulink仿真工具，仿真其介數(shù)分布，通過控制介數(shù)的分布，來優(yōu)化網(wǎng)絡(luò)的路徑結(jié)構(gòu)。

圖5給出了經(jīng)過優(yōu)化算法前、后裝備物資器材復(fù)雜物流網(wǎng)絡(luò)介數(shù)分布圖。從圖5可以看出：優(yōu)化前大多數(shù)節(jié)點(diǎn)有較低的介數(shù)，其中有一小部分節(jié)點(diǎn)介數(shù)分布在寬廣的范圍，經(jīng)過啟發(fā)式算法優(yōu)化后，所有節(jié)點(diǎn)的介數(shù)被限制在一個(gè)狹窄的范圍內(nèi)，尤其是分布上限被嚴(yán)格限制，大多數(shù)節(jié)點(diǎn)統(tǒng)一分布在一個(gè)范圍內(nèi)，其上限有很明顯的峰值而后有顯著的遞減趨勢(shì)。這驗(yàn)證了該算法可以明顯減小最大介數(shù)和平均介數(shù)的差值，以優(yōu)化網(wǎng)絡(luò)的結(jié)構(gòu)。

圖5 優(yōu)化前、后網(wǎng)絡(luò)中介數(shù)分布圖

4 仿真實(shí)例分析

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

表2 裝備物資器材復(fù)雜物流網(wǎng)絡(luò)保障任務(wù)

根據(jù)優(yōu)化算法，將每類補(bǔ)給途徑的補(bǔ)給時(shí)間和補(bǔ)給成本假設(shè)為權(quán)重l1，l2，單位分別以小時(shí)和萬元表示。根據(jù)以上考慮，制定出補(bǔ)給路線的路由表（見表3）。

表3 裝備物資器材補(bǔ)給路由表

根據(jù)表3和前面提到的啟發(fā)式算法，可以計(jì)算出每項(xiàng)補(bǔ)給任務(wù)補(bǔ)給路徑的對(duì)應(yīng)值（見表4）。

表4 裝備物資器材補(bǔ)給路徑對(duì)應(yīng)值

考慮到戰(zhàn)時(shí)裝備物資器材物流網(wǎng)絡(luò)會(huì)因?yàn)楸Ｕ先蝿?wù)的增加而變得繁忙，某些節(jié)點(diǎn)會(huì)因?yàn)槌鋈霂煳镔Y器材過多而產(chǎn)生網(wǎng)絡(luò)擁塞，這里假設(shè)圖6中節(jié)點(diǎn)2、5出現(xiàn)擁塞，結(jié)合本文使用的最優(yōu)算法路徑協(xié)議和節(jié)點(diǎn)的保障任務(wù)分工，得到最終的優(yōu)化補(bǔ)給方案，見表5。

圖6 裝備物資器材物流實(shí)例圖

表5 優(yōu)化后的裝備物資器材補(bǔ)給方案

5 結(jié)語

本文以裝備物資器材軍事物流網(wǎng)絡(luò)為研究對(duì)象，建立了其拓?fù)淠Ｐ停岢鲞\(yùn)用啟發(fā)式路徑優(yōu)化算法，并通過Matlab－Simulink對(duì)復(fù)雜參數(shù)的仿真，結(jié)合四個(gè)保障實(shí)例，提出了最佳的保障補(bǔ)給方案，該優(yōu)化方法為提高軍事物流網(wǎng)絡(luò)的保障效率提供了一定的理論參考。

［1］李慈.基于復(fù)雜系統(tǒng)理論的配送網(wǎng)絡(luò)優(yōu)化研究［D］.西安：西北工業(yè)大學(xué)碩上學(xué)位論文，2006.

［2］黃建華.快遞網(wǎng)絡(luò)的復(fù)雜性及魯棒性分析［J］.西南交通大學(xué)學(xué)報(bào)，2009（12）：98－102.

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

［4］王佳，池潔，王勇.物流中配送路線選擇的優(yōu)化分析［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.