基于ACA的軍事物流車輛配送路徑優化研究

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

（1.華北物資采購局，天津 300182；2.軍事交通學院，天津 300161；3.預備役五七四團，遼寧 風城 118100）

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

軍事物流是指軍事力量在生活、訓練、執勤及作戰時所需軍事物資經過籌措、運輸、倉儲、供應等環節，最終送達部隊被消耗使用，實現其空間與時間轉移的全過程，是社會物流系統中的重要分支。軍事力量正是由于通過軍事物流源源不斷地供應其所需物資，才得以有效地開展軍事行動，才得以強化訓練提高戰斗力。而軍事物流配送作為軍事物流的重要組成部分，它指的是在一定的區域范圍內，根據部隊需求，對軍用物資進行揀選、組配等作業，并按時送達部隊指定地點的物流活動。我軍后勤保障現實行的是聯勤保障體制，各大軍區都設有聯勤部，負責通過軍事運輸對轄區內各部隊的物資供應和補充。通常軍事運輸的方式主要有五種：鐵路、公路、水路、航空和管道，目前公路運輸仍然是我軍物資運輸的主要運輸方式。而據初步調查研究，在我國軍事物資供應過程中，每年由于不合理運輸而造成的額外運輸量高達數百萬噸。可見，車輛配送路徑優化選擇問題已經成為制約保障能力生成的重要因素之一。

1 軍事物流配送路徑優化模型

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

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

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

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

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

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

目標函數：

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

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

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

2.1 螞蟻算法的原理

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

2.2 螞蟻算法的基本模型

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

式中：Q是一個常數，其數值由具體實驗給定。

3 仿真結果

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

根據各需求點的需求量計算出需要的汽車數為：

表1

應用螞蟻算法對以上問題進行求解，經過構造螞蟻算法函數得出最佳路徑為：

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

子路徑2：0→6→0

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

4 結束語

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

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

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

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

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

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

[6]高尚，鐘娟，莫述軍.連續優化問題的蟻群算法研究[J].微機發展，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.