基于ACA的軍事物流車輛配送路徑優(yōu)化研究

譚云恩，張 亮，楊 霞，甄瑞杰TAN Yun-en,ZHANG Liang,YANG Xia,ZHEN Rui-jie

（1.華北物資采購局，天津 300182；2.軍事交通學(xué)院，天津 300161；3.預(yù)備役五七四團(tuán)，遼寧 風(fēng)城 118100）

(1.NC Material Procurement Agency,Tianjin 300182,China;2.Military Transportion College,Tianjin 300161,China;3.Reserve the 574 Regiment,Fengcheng 118100,China)

軍事物流是指軍事力量在生活、訓(xùn)練、執(zhí)勤及作戰(zhàn)時(shí)所需軍事物資經(jīng)過籌措、運(yùn)輸、倉儲、供應(yīng)等環(huán)節(jié)，最終送達(dá)部隊(duì)被消耗使用，實(shí)現(xiàn)其空間與時(shí)間轉(zhuǎn)移的全過程，是社會物流系統(tǒng)中的重要分支。軍事力量正是由于通過軍事物流源源不斷地供應(yīng)其所需物資，才得以有效地開展軍事行動，才得以強(qiáng)化訓(xùn)練提高戰(zhàn)斗力。而軍事物流配送作為軍事物流的重要組成部分，它指的是在一定的區(qū)域范圍內(nèi)，根據(jù)部隊(duì)需求，對軍用物資進(jìn)行揀選、組配等作業(yè)，并按時(shí)送達(dá)部隊(duì)指定地點(diǎn)的物流活動。我軍后勤保障現(xiàn)實(shí)行的是聯(lián)勤保障體制，各大軍區(qū)都設(shè)有聯(lián)勤部，負(fù)責(zé)通過軍事運(yùn)輸對轄區(qū)內(nèi)各部隊(duì)的物資供應(yīng)和補(bǔ)充。通常軍事運(yùn)輸?shù)姆绞街饕形宸N：鐵路、公路、水路、航空和管道，目前公路運(yùn)輸仍然是我軍物資運(yùn)輸?shù)闹饕\(yùn)輸方式。而據(jù)初步調(diào)查研究，在我國軍事物資供應(yīng)過程中，每年由于不合理運(yùn)輸而造成的額外運(yùn)輸量高達(dá)數(shù)百萬噸。可見，車輛配送路徑優(yōu)化選擇問題已經(jīng)成為制約保障能力生成的重要因素之一。

1 軍事物流配送路徑優(yōu)化模型

車輛配送路徑優(yōu)化問題一般可以這樣描述：從某軍事物流配送中心用多輛配送車輛向多個部隊(duì)用戶運(yùn)送物資。每個部隊(duì)用戶的位置和貨物需求量一定，每輛車的載重量一定，其一次配送的最大行駛距離一定。要求合理安排車輛配送路線，使目標(biāo)函數(shù)得到最優(yōu)。并滿足以下條件：

（1）每條配送路徑上各部隊(duì)用戶需求量之和不超過配送車輛的載重量；

（2）每條配送路徑的長度不超過配送車輛一次配送的最大行駛距離；

（3）每個部隊(duì)用戶的需求必須滿足，且只能由一輛配送車送貨。

設(shè)配送中心需要向k個部隊(duì)用戶送貨，每個部隊(duì)用戶的貨物需求量是gi（i=1,2,…,k ），部隊(duì)用戶i與部隊(duì)用戶j 之間的距離為dij，每輛配送車的載重量是Q，且gi＜Q。首先為了安排路線需要對要使用的車輛數(shù)有一個估計(jì)。在現(xiàn)實(shí)情況中，貨物裝（卸）車越復(fù)雜，約束條件越多，一輛車的實(shí)際載貨量就越小。可由用戶選擇參加運(yùn)輸?shù)能囕v數(shù)，或由下面公式來確定需要的汽車數(shù)：

M為所需汽車數(shù)，［］表示取整，a為參數(shù)，0＜a＜1，約束條件越多，貨物裝（卸）車越復(fù)雜，a值越小。實(shí)際應(yīng)用中，可用人機(jī)對話來確定a值。

目標(biāo)函數(shù)：

CR為每輛車出動的固定費(fèi)用，Cm為車輛的每公里費(fèi)用；式（2）表示每一個點(diǎn)都恰好位于某一路徑之中；式（3）表示某車到達(dá)一個點(diǎn)后也必然離開這個點(diǎn)；式（4）表示對車輛的負(fù)載限制；式（5）保證了每個點(diǎn)的運(yùn)輸任務(wù)僅由一輛車完成，而所有運(yùn)輸任務(wù)由M輛車協(xié)同完成；式（6）保證每一條路徑起、止于中心站。

2 求解軍事物流配送問題的ACA算法

1991年，意大利學(xué)者M(jìn).Dorigo等人從生物進(jìn)化的機(jī)理中受到啟發(fā)，通過模擬自然界螞蟻尋徑的行為，提出了一種全新的模擬進(jìn)化算法——蟻群算法。

2.1 螞蟻算法的原理

螞蟻覓食時(shí)，對于從蟻窩到食物源的諸多途徑，開始時(shí)不同的螞蟻會選擇不同的路徑，但最后，幾乎所有的螞蟻都會找到同一條最短的路徑。螞蟻雖沒有視覺，但運(yùn)動時(shí)會在通過路徑上釋放出一種特殊的分泌物——信息素，而且能感知這種信息素的存在及強(qiáng)度并朝該物質(zhì)濃度高的方向運(yùn)動，這些信息素既會隨通過的螞蟻數(shù)量增加而增加，也會隨時(shí)間的流逝而按一定的函數(shù)關(guān)系消逝，這樣便形成了一個正反饋機(jī)制，最終整個蟻群會找出最優(yōu)路徑。同時(shí)蟻群還能夠適應(yīng)環(huán)境的變化，當(dāng)蟻群的運(yùn)動路徑上突然出現(xiàn)障礙物時(shí)，螞蟻也能很快地重新找到最優(yōu)路徑。蟻群算法就是模擬上述螞蟻覓食行為，設(shè)計(jì)虛擬的人工螞蟻，使其隨機(jī)搜索不同的路徑，并留下會隨時(shí)間變化而蒸發(fā)的“信息素”，根據(jù)“信息素”強(qiáng)度來尋找最短路徑。但人工蟻群和自然界蟻群是有區(qū)別的，區(qū)別在于人工蟻群具有一定的記憶能力，它能夠記憶已經(jīng)訪問過的節(jié)點(diǎn)；另外，人工蟻群在選擇下一條路的時(shí)候并不是完全盲目的，而是按一定的算法規(guī)律有意識地尋找最短路徑。

2.2 螞蟻算法的基本模型

基于螞蟻算法的原理，設(shè)n是部隊(duì)用戶數(shù)，k是螞蟻的數(shù)目，dij（i,j=1,2,…,n ）表示用戶i到用戶j所需的路徑長度，bi（t）表示t時(shí)刻位于客戶i的螞蟻數(shù)目。則有表示t時(shí)刻客戶i,j之間的信息素。初始狀態(tài)下，各條路線上信息素濃度相等，設(shè)τij（0）=C（C為常數(shù)）。螞蟻k（ k=1,2,…,m ）在移動過程中，根據(jù)各條路線上的信息素決定前進(jìn)方向。

式中：Q是一個常數(shù)，其數(shù)值由具體實(shí)驗(yàn)給定。

3 仿真結(jié)果

某部隊(duì)有1個配送中心和8個配送點(diǎn)，各配送點(diǎn)的貨運(yùn)量為g（單位：噸）。各需求點(diǎn)的需求量在0,［］4間隨機(jī)生成，使單輛車能承擔(dān)更多的運(yùn)輸任務(wù)。滿載系數(shù)a取0.85，默認(rèn)交叉率為0.6，默認(rèn)變異率為0.02。配送中心與配送點(diǎn)位置及需求量如表1。

根據(jù)各需求點(diǎn)的需求量計(jì)算出需要的汽車數(shù)為：

表1

應(yīng)用螞蟻算法對以上問題進(jìn)行求解，經(jīng)過構(gòu)造螞蟻算法函數(shù)得出最佳路徑為：

子路徑1：0→8→7→4→0

子路徑2：0→6→0

子路徑 3：0→5→3→1→2→0

4 結(jié)束語

精確保障越來越重要、艱巨和復(fù)雜，如何有效提高精確保障能力已成為研究的熱點(diǎn)問題。但現(xiàn)有裝備、保障力量有限，在現(xiàn)有的基礎(chǔ)上，對精確保障決策進(jìn)行優(yōu)化特別是對車輛配送路徑選擇問題進(jìn)行優(yōu)化是提高精確保障能力的事半功倍的重要手段，而螞蟻算法能夠較快發(fā)現(xiàn)和搜索到最優(yōu)路徑，從而合理地安排配送車輛的行車路線以達(dá)到縮短運(yùn)距，提高保障效能。

[1]周勇，陳洪亮.蟻群算法的研究現(xiàn)狀及其展望[J].微型電腦應(yīng)用，2002,18(2)：5-7.

[2]潘震東，唐加福，韓毅.帶貨物權(quán)重的車輛路徑問題及遺傳算法[J].管理科學(xué)學(xué)報(bào)，2001,10(3)：23-28.

[3]萬榮.信息化條件下軍事物流配送[D].重慶：重慶后勤工程學(xué)院，2008.

[4]陶羿，朱建清，李明.軍事物流選址分配模型及遺傳算法優(yōu)化[J].信息工程大學(xué)學(xué)報(bào)，2001,8(1)：110-115.

[5]周屹，李海龍，王銳.遺傳算法求解物流配送中帶時(shí)間窗的VRP問題[J].吉林大學(xué)學(xué)報(bào)（理學(xué)版），2008,46(2)：300-303.

[6]高尚，鐘娟，莫述軍.連續(xù)優(yōu)化問題的蟻群算法研究[J].微機(jī)發(fā)展，2003,13(1)：21-22.

[7]DORIGO M,MAMIEZZO V,COLORNI A.Ant Sys-tem：optimization by a colony of cooperating agents[J].IEEE Transactions on SMC,1996(1)：554-558.