基于蟻群算法的裝備保障路徑規(guī)劃模型*

張 星，杜曉明，蔡紀(jì)偉，張志學(xué)

（1.軍械工程學(xué)院，石家莊 050003；2.解放軍66010部隊(duì)，石家莊 050000）

基于蟻群算法的裝備保障路徑規(guī)劃模型*

張 星1，2，杜曉明1，蔡紀(jì)偉1，張志學(xué)2

（1.軍械工程學(xué)院，石家莊 050003；2.解放軍66010部隊(duì)，石家莊 050000）

現(xiàn)代戰(zhàn)爭(zhēng)中裝備保障路徑規(guī)劃中路徑網(wǎng)絡(luò)節(jié)點(diǎn)多和要優(yōu)化的制約因素等問題成為裝備保障仿真的難點(diǎn)，傳統(tǒng)的蟻群算法尋找最優(yōu)解，往往找不到滿意的解。為了提高尋優(yōu)效率，盡量減少裝備保障中待保障裝備戰(zhàn)斗力恢復(fù)等待總時(shí)間，對(duì)基本蟻群算法進(jìn)行改進(jìn)。首先建立裝備保障路徑規(guī)劃模型，然后基于基本蟻群算法，重新設(shè)計(jì)了啟發(fā)信息的計(jì)算方法和信息素的更新函數(shù)，對(duì)路徑節(jié)點(diǎn)的選擇方法進(jìn)行改進(jìn)，最后通過一個(gè)具體的裝備保障路徑規(guī)劃問題對(duì)傳統(tǒng)的和改進(jìn)的算法進(jìn)行算例分析。計(jì)算結(jié)果表明，所采用的改進(jìn)的蟻群算法可以更好地解決裝備保障路徑規(guī)劃問題，有效減少待保障裝備恢復(fù)戰(zhàn)斗力之前等待的時(shí)間和保障分隊(duì)經(jīng)過的總路程。

蟻群算法，裝備搶修，路徑規(guī)劃，模型

0 引言

裝備保障活動(dòng)的基礎(chǔ)要素之一是暢通的交通運(yùn)輸網(wǎng)，而在此基礎(chǔ)之上的保障路徑優(yōu)化是提高裝備保障時(shí)效性的重要手段。以往裝備保障路線的選取，是參謀人員依據(jù)保障對(duì)象、供應(yīng)倉庫、供應(yīng)分隊(duì)以及修理分隊(duì)的分布，結(jié)合戰(zhàn)時(shí)交通運(yùn)輸規(guī)則和工作經(jīng)驗(yàn)，在紙質(zhì)地圖上手工完成，這種選取過程時(shí)間長、任務(wù)重、實(shí)時(shí)性差，而且以往的裝備搶修任務(wù)執(zhí)行順序也多是靠個(gè)人的主觀感覺、拍腦袋。顯然這種方法已經(jīng)不能滿足現(xiàn)代戰(zhàn)爭(zhēng)突發(fā)性、速?zèng)Q性急劇增強(qiáng)的特點(diǎn)。如何快速、科學(xué)地選擇裝備保障路徑和保障任務(wù)的執(zhí)行順序，已經(jīng)嚴(yán)重影響著保障潛力的挖掘和裝備保障能力的發(fā)揮［1］。蟻群算法是近年來才廣泛應(yīng)用的一種針對(duì)難解的離散優(yōu)化問題的啟發(fā)式優(yōu)化算法，它是從對(duì)蟻群行為研究中產(chǎn)生的。西北工業(yè)大學(xué)的王振華等學(xué)者在文獻(xiàn)［2］中引入了各路徑段與起始點(diǎn)至目標(biāo)點(diǎn)連線的夾角信息作為新的啟發(fā)信息，加快了算法的搜索速度；高虹霓在文獻(xiàn)［3］中針對(duì)軍用物資供應(yīng)道路的特點(diǎn)，給出了基于啟發(fā)函數(shù)下的最短路標(biāo)號(hào)搜索算法及程序流程圖，對(duì)Dijkstra算法進(jìn)行了改進(jìn)，最終找出最佳路徑。但是，他們大多是從路徑搜索角度對(duì)蟻群算法進(jìn)行應(yīng)用考慮的，在多節(jié)點(diǎn)以及多制約因素方面分析的較少。本文是在現(xiàn)有蟻群算法的基礎(chǔ)上，綜合考慮搶修任務(wù)節(jié)點(diǎn)之間的距離及搶修任務(wù)的修復(fù)時(shí)間和完成時(shí)間的問題，建立了兩個(gè)目標(biāo)函數(shù)的優(yōu)化問題，重新設(shè)計(jì)啟發(fā)信息的計(jì)算方法和信息素的更新函數(shù)，使它們成為路徑長度和戰(zhàn)損裝備戰(zhàn)斗力恢復(fù)等待時(shí)間的二元函數(shù)，從而更方便地從最優(yōu)解集中選擇一條路徑，減少待保障裝備恢復(fù)戰(zhàn)斗力之前等待的時(shí)間和保障分隊(duì)經(jīng)過的總路程。

1 基本蟻群算法

下面以商旅問題為例給出基本蟻群算法的思想。

假設(shè)蟻群中螞蟻數(shù)量為M，城市數(shù)量為N，各個(gè)城市之間有許多條不同的路徑。則在t時(shí)刻，第k只螞蟻從城市i轉(zhuǎn)到j(luò)的轉(zhuǎn)移概率Pijk（t）為

螞蟻每走過一個(gè)路徑都要在該路徑上留下信息素，為了避免算法陷入局部最有，引入了信息素?fù)]發(fā)機(jī)制。這樣，信息素的更新按照以下方式進(jìn)行：

2 裝備保障路徑規(guī)劃問題分析

2.1 裝備保障路徑規(guī)劃問題原理描述

一般的路徑優(yōu)化問題，通常就是通過一定的算法，選取最短的路徑，即最短路問題。但在裝備保障中的路徑規(guī)劃問題中，路徑的選擇首先應(yīng)從軍事效益出發(fā)（尤其是戰(zhàn)時(shí)），由于路徑規(guī)劃決定著裝備保障任務(wù)的執(zhí)行順序，所以應(yīng)該優(yōu)先考慮保障任務(wù)的緊迫性，其次才能考慮運(yùn)輸?shù)慕?jīng)濟(jì)效益，即運(yùn)輸里程的最短問題［3］。具體而言，一般的路徑規(guī)劃問題，路徑中各個(gè)節(jié)點(diǎn)的訪問先后次序是無關(guān)緊要的，而在裝備保障路徑規(guī)劃問題中，對(duì)路徑上一些任務(wù)所在節(jié)點(diǎn)的訪問時(shí)間有著嚴(yán)格要求，而且一般還要求按照先易后難的順序執(zhí)行裝備保障任務(wù)，這要求在一定的經(jīng)濟(jì)效益基礎(chǔ)上更早訪問這些任務(wù)節(jié)點(diǎn)。裝備保障路徑規(guī)劃雖然在很多方面可以借鑒車輛路徑選擇問題的研究結(jié)果，但是有其自身的特點(diǎn)。

①路徑網(wǎng)絡(luò)節(jié)點(diǎn)多。戰(zhàn)時(shí)裝備保障的地域?yàn)閼?zhàn)區(qū)范圍內(nèi)所有可通行的路徑構(gòu)成交通網(wǎng)，該網(wǎng)絡(luò)由已存在路徑和戰(zhàn)時(shí)臨時(shí)開辟的道路構(gòu)成。其路徑網(wǎng)絡(luò)節(jié)點(diǎn)非常多，如果通過搜索枚舉所有的路線來找出所需要的滿意解，顯然是不現(xiàn)實(shí)的。

②要優(yōu)化的制約因素多。這些制約因素包括軍事效益、運(yùn)輸里程、運(yùn)輸時(shí)間、運(yùn)輸安全和運(yùn)輸耗費(fèi)等，在進(jìn)行路徑優(yōu)選時(shí)應(yīng)當(dāng)根據(jù)戰(zhàn)時(shí)戰(zhàn)場(chǎng)環(huán)境情況和裝備保障系統(tǒng)情況進(jìn)行綜合考慮并作出決策［6-7］。

因此，在裝備保障路徑規(guī)劃問題上，應(yīng)針對(duì)上述特點(diǎn)，提出符合指揮實(shí)體任務(wù)規(guī)劃實(shí)際需要的路徑搜索規(guī)劃模型。

2.2 裝備保障問題路徑優(yōu)化問題的數(shù)學(xué)描述

針對(duì)裝備保障路徑規(guī)劃問題的特點(diǎn)，設(shè)定某戰(zhàn)術(shù)級(jí)裝備保障小組要根據(jù)裝備保障指揮員的要求，完成n項(xiàng)戰(zhàn)損裝備保障任務(wù)。此n項(xiàng)戰(zhàn)損裝備保障任務(wù)位于n個(gè)不同的地點(diǎn)p1、p2…pn，dij表示pi和pj之間的距離，p0為保障小組的出發(fā)地點(diǎn)，出發(fā)地點(diǎn)沒有保障任務(wù)。這里不妨假設(shè)任意兩點(diǎn)之間的路況是一樣的，保障小組的平均行進(jìn)速度為v，保障小組在pi和pj之間的機(jī)動(dòng)時(shí)間為tij=dij/v，完成保障任務(wù)i需要的時(shí)間TiRepair，而且根據(jù)作戰(zhàn)任務(wù)的需要，保障任務(wù)i需要的在時(shí)間TiLimit之前完成。根據(jù)前文分析知道，應(yīng)該先執(zhí)行較為容易的保障任務(wù)，使戰(zhàn)損裝備盡早恢復(fù)戰(zhàn)斗能力，爭(zhēng)取最優(yōu)的保障效果。所以需要優(yōu)化目標(biāo)有兩個(gè)：一個(gè)是待保障裝備恢復(fù)戰(zhàn)斗力之前等待的時(shí)間最短，一個(gè)是保障小組經(jīng)過的總路程最短，顯然這是一個(gè)多目標(biāo)優(yōu)化的問題。

2.3 模型建立

根據(jù)以上分析，建立如下多目標(biāo)優(yōu)化模型：

其中ti表示保障小組到達(dá)第i個(gè)保障任務(wù)實(shí)施地點(diǎn)的時(shí)間，對(duì)于任意一條裝備保障路徑{P1'，P2'，…，Pn'}，有：

3 對(duì)蟻群算法的改進(jìn)及其求解流程

3.1 對(duì)蟻群算法的改進(jìn)

3.1.1 對(duì)算法設(shè)計(jì)的改進(jìn)措施

①子路徑構(gòu)造過程的改進(jìn)：在基本蟻群算法中，每只螞蟻均要經(jīng)過所有節(jié)點(diǎn)；而在改進(jìn)蟻群算法中，每只螞蟻并不需要遍歷所有節(jié)點(diǎn)。因此，在改進(jìn)后的蟻群算法的每次迭代中，每只螞蟻移動(dòng)次數(shù)是不確定的，只能將是否到達(dá)目標(biāo)位置作為路徑構(gòu)造完成的標(biāo)志。

②改進(jìn)后的蟻群算法螞蟻轉(zhuǎn)移時(shí)不僅要考慮各任務(wù)點(diǎn)之間的距離，還要考慮各任務(wù)點(diǎn)搶修任務(wù)的修復(fù)時(shí)間和完成時(shí)間要求。

③改進(jìn)后的蟻群算法中，每只螞蟻所構(gòu)造的回路可能能夠組成一些可行解，也可能一個(gè)可行解都得不到。

3.1.2 對(duì)信息素更新及路徑節(jié)點(diǎn)選擇方法的改進(jìn)

蟻群算法最大的特點(diǎn)就是創(chuàng)造性地使用了啟發(fā)信息，通過應(yīng)用信息素播撒的方法，將之前搜索到的最優(yōu)解作為反饋來指導(dǎo)后續(xù)螞蟻的路徑搜索。但由于TSP問題中只有惟一的一個(gè)優(yōu)化目標(biāo)，即路徑長度的最小化。所以傳統(tǒng)蟻群算法中啟發(fā)信息的計(jì)算和信息素的更新均為路徑長度的函數(shù)。而對(duì)于本文建立的兩個(gè)目標(biāo)函數(shù)的優(yōu)化問題，需要重新設(shè)計(jì)啟發(fā)信息的計(jì)算方法和信息素的更新函數(shù)，使它們成為路徑長度和戰(zhàn)損裝備戰(zhàn)斗力恢復(fù)等待時(shí)間的二元函數(shù)。

多目標(biāo)優(yōu)化蟻群算法中的啟發(fā)信息的計(jì)算方法為：

當(dāng)所有螞蟻都完成了路徑搜索后，路徑上信息素更新方法為：

其中Q為常量，Lk表示第k只螞蟻在本次循環(huán)中經(jīng)過的路線長度，Tk表示第k只螞蟻在本次循環(huán)中得到的所有戰(zhàn)損裝備戰(zhàn)斗力恢復(fù)等待時(shí)間的總和。其路徑選擇方法描述為：首先取一個(gè)隨機(jī)數(shù)q0，判斷是否滿足q≤q0，q0為事先確定的一個(gè)參數(shù)，且0≤q0≤1。如果滿足則按照式（12）來選擇下一個(gè)路徑節(jié)點(diǎn)，如果不滿足則按式（13）取得的概率隨機(jī)選擇下一個(gè)路徑節(jié)點(diǎn)［8-9］。

3.2 求解流程

Step 1：構(gòu)造初始可行路徑，用任意算法計(jì)算出一條可行路徑，然后分別計(jì)算最短路徑L0和最小的戰(zhàn)斗力恢復(fù)等待時(shí)間T0，并把此可行解加入Pareto最優(yōu)解集；

Step 2：算法開始前首先初始化信息素，為每條邊賦予相等的信息素。同時(shí)初始化禁忌列表為空，設(shè)置信息素保留率為p；

Step 3：while（迭代步數(shù)＜預(yù)定的迭代次數(shù)）；

Step 3.1：初始化螞蟻，將m只螞蟻隨機(jī)放在代表搶修小組的節(jié)點(diǎn)中；

Step 3.2：任取一只螞蟻開始搜尋路徑，循環(huán)1：for k=1 to m步長為1；

Step 3.2.1：螞蟻開始搜尋路徑，循環(huán)2：for k=1 to n步長為1；

Step 3.2.2：根據(jù)式（9）來計(jì)算不在禁忌列表中各個(gè)任務(wù)點(diǎn)的啟發(fā)信息ηij；

Step 3.2.3：產(chǎn)生一個(gè)隨機(jī)數(shù)q根據(jù)式（12）來選擇取值最大的搶修任務(wù)點(diǎn)pj，否則根據(jù)式（13）確定的概率隨機(jī)選擇搶修任務(wù)點(diǎn)pj；

Step 3.2.4：判斷tj+tjRepair≤TjLimit是否滿足，如果不滿足轉(zhuǎn)到步驟3.2.1；

Step 3.2.5：把搶修任務(wù)點(diǎn)pj列入禁忌列表；

Step3.2.6：如果全部搶修任務(wù)點(diǎn)都在禁忌列表中，則循環(huán)2：end for；

Step3.3：用該螞蟻得到的路線r計(jì)算Z1和Z2，同時(shí)和每一個(gè)Pareto最優(yōu)解集里的解相比較，若r為解集的非支配解，則將此解加入Pareto最優(yōu)解集，同時(shí)將被此解支配的解。

Step3.4：如果所有螞蟻都搜尋完畢，則循環(huán)1：end for；

Step4：整理Pareto最優(yōu)解集，開始下一次循環(huán)；

Step5：end while。

在得到Pareto最優(yōu)解集后，決策者就可以根據(jù)自己的偏好和裝備保障系統(tǒng)狀態(tài)，對(duì)總路徑長度和待保障裝備戰(zhàn)斗力恢復(fù)等待總時(shí)間進(jìn)行權(quán)衡，很方便地從Pareto最優(yōu)解集中選擇一條路徑，完成路徑規(guī)劃［10］。

4 算例實(shí)驗(yàn)及結(jié)果分析

這里應(yīng)用某裝備保障想定中的一個(gè)裝備搶修路徑規(guī)劃問題來測(cè)試上述算法，路徑中共有8個(gè)任務(wù)點(diǎn)，由于戰(zhàn)斗進(jìn)行比較激烈，所保障的單位中，其中第4個(gè)和第5個(gè)任務(wù)點(diǎn)的搶修任務(wù)緊急，需要在一定時(shí)間內(nèi)完成，其他節(jié)點(diǎn)緊急情況一般。要求裝備搶修分隊(duì)在綜合考慮任務(wù)點(diǎn)間距離以及各任務(wù)點(diǎn)搶修任務(wù)修復(fù)時(shí)間和完成時(shí)間的情況下，完成搶修任務(wù)。

8個(gè)訪問節(jié)點(diǎn)的具體位置如圖1所示。

戰(zhàn)損裝備搶修任務(wù)地點(diǎn)之間的距離如表1所示，其中∞表示兩個(gè)任務(wù)地點(diǎn)之間沒有直接相連的通路。

各個(gè)搶修任務(wù)的戰(zhàn)損裝備修復(fù)時(shí)間以及各個(gè)任務(wù)搶修完成的時(shí)間限制如表2所示：

如果僅考慮戰(zhàn)損裝備搶修任務(wù)地點(diǎn)之間的距離，運(yùn)用基本蟻群算法進(jìn)行計(jì)算，從初始點(diǎn)0開始搜索，從節(jié)點(diǎn)i轉(zhuǎn)到j(luò)的轉(zhuǎn)移概率根據(jù)式（1），螞蟻每走過一個(gè)路徑都要在該路徑上留下信息素，為了避免算法陷入局部最優(yōu)，引入了信息素?fù)]發(fā)機(jī)制。這樣，信息素的更新按照式（2）和式（3）進(jìn)行，得出其最優(yōu)路徑為（如圖2所示）：

將戰(zhàn)損裝備搶修任務(wù)地點(diǎn)之間的距離和各搶修任務(wù)的修復(fù)時(shí)間及完成時(shí)間綜合考慮，運(yùn)用改進(jìn)的蟻群算法進(jìn)行計(jì)算。

多目標(biāo)優(yōu)化蟻群算法中的啟發(fā)信息的計(jì)算方法為式（10）和式（11），從任務(wù)點(diǎn)0開始搜索，其路徑選擇方法為：判斷是否滿足q≤q0，如果滿足則按照式（12）來選擇下一個(gè)路徑節(jié)點(diǎn)，如果不滿足則按式（13）取得的概率隨機(jī)選擇下一個(gè)路徑節(jié)點(diǎn)，經(jīng)改進(jìn)算法求解，最后得到的最優(yōu)路徑為（如圖3所示）：

在利用本文改進(jìn)算法對(duì)此裝備保障路徑規(guī)劃問題進(jìn)行處理后，由于節(jié)點(diǎn)4和節(jié)點(diǎn)5的TjLimit分別為4.0和3.0，在改進(jìn)算法中判斷tj+tjRepair≤TjLimit是否滿足，如果不滿足則返回重新開始搜索。根據(jù)算例實(shí)驗(yàn)結(jié)果比較得知，改進(jìn)算法可以有效解決需要綜合考慮搶修任務(wù)節(jié)點(diǎn)之間的距離和搶修任務(wù)的修復(fù)時(shí)間和完成時(shí)間的問題，盡可能地減少待保障裝備恢復(fù)戰(zhàn)斗力之前等待的時(shí)間和保障分隊(duì)經(jīng)過的總路程。

5 結(jié)束語

從算法的仿真驗(yàn)證來看，本文設(shè)計(jì)的算法可以很快尋找到部分最優(yōu)解，結(jié)果更接近現(xiàn)實(shí)，也證明了用這種方法具有一定的理論參考價(jià)值和實(shí)際意義。但是，算法本身還存在一些不足之處：首先當(dāng)需求點(diǎn)數(shù)目較大時(shí)，整個(gè)算法的搜索時(shí)間較長，得出的最優(yōu)解不穩(wěn)定，嚴(yán)重限制了該算法的優(yōu)勢(shì)；其次，搜索過程中易陷入局部最優(yōu)解，即在達(dá)到規(guī)定迭代次數(shù)之前很長時(shí)間內(nèi)不再發(fā)生變化，搜索停滯；再次，啟發(fā)因子α和β，揮發(fā)系數(shù)ρ以及常量Q的取值均會(huì)對(duì)算法結(jié)果產(chǎn)生影響。這些問題有待于進(jìn)一步結(jié)合實(shí)際問題進(jìn)行研究。

［1］董家瑞，王精業(yè)，王琴琴.裝備保障路徑選擇算法研究［J］.裝甲兵工程學(xué)院學(xué)報(bào)，2008（6）：9-12.

［2］王振華，章衛(wèi)國，李廣文.基于改進(jìn)多目標(biāo)蟻群算法的無人機(jī)路徑規(guī)劃［J］.計(jì)算機(jī)應(yīng)用研究，2009，26（6）: 2104-2109.

［3］高虹霓，楊建軍，曹澤陽.軍用物資供應(yīng)道路選擇最優(yōu)算法研究［J］.系統(tǒng)工程與電子技術(shù)，2002，24（3）:61-64.

［4］李士勇.蟻群優(yōu)化算法及其應(yīng)用研究進(jìn)展［J］.IT技術(shù)論壇，2003，18（11）:911-917.

［5］石玉峰，金建軍.戰(zhàn)時(shí)不確定性運(yùn)輸路徑優(yōu)化［J］.空軍工程大學(xué)學(xué)報(bào)，2005（6）:56-59.

［6］張最良，李長生，趙文志，等.軍事運(yùn)籌學(xué)［M］.北京:軍事科學(xué)出版社，1993.

［7］黃坤，吳俊.一種改進(jìn)的多目標(biāo)蟻群優(yōu)化算法［J］.微電子學(xué)與計(jì)算機(jī)，2011，23（10）:181-187.

［8］池元成，蔡國飚.基于蟻群算法的多目標(biāo)優(yōu)化［J］.計(jì)算機(jī)工程，2009，35（15）:168-172.

［9］李躍光，張遠(yuǎn)平.一種改進(jìn)的蟻群算法在垃圾運(yùn)輸問題中的應(yīng)用［J］.湖南師范大學(xué)自然科學(xué)學(xué)報(bào)，2010，26（6）：18-23.

［10］范路橋，姚錫凡，卞青青，等.蟻群算法及其在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用 ［J］.機(jī)器人技術(shù)，2008，19（12）：257-261.

Equipment Support Route-planning Model Based on Ant Colony Algorithm

ZHANG Xing1，2，DU Xiao-ming1，CAI Ji-wei1，ZHANG Zhi-xue2
（1.Ordnance Engineering College，Shijiazhuang 050003，China；2.Troops 66010 of PLA，Shijiazhuang 050000，China）

The problem of the network node and the complex constraint in the route-planning of the equipment support during modern wartime becomes the difficulty in the equipment support simulation.The traditional ant colony algorithm will not introduce satisfied explain.In order to improve the optimizing efficiency，the traditional ant colony algorithm is improved.Firstly，the model of the route-planning in equipment support is built，devises the computing method and the updating function，and the choice of the path node is improved，at last，the improved algorithm is tested and verified by using a route-planning problem in some equipment support scenario，proves that the improved ant colony algorithm can solve the problem of the route-planning in equipment support，reduces the waiting time before the waiting equipment recovering fighting ability and the total distance the support elements passes.

ant colony algorithm，equipment rush repairing，route-planning，model

TP391

A

1002-0640（2015）09-0026-05

2014-08-20

2014-09-03

國家自然科學(xué)基金資助項(xiàng)目（60904071）

張 星（1985- ），男，河北石家莊人，碩士研究生。研究方向：裝備保障指揮及自動(dòng)化。