裝備搶修車多目標路徑優化

李眾　謝曉東　余選召　吳迪

摘 要：針對戰場搶修工作的特點，建立了考慮安全性、時間損耗等因素的多目標路徑優化模型，采用蟻群算法對問題求解，并對蟻群算法進行改進，提升了算法的收斂速度。

關鍵詞：搶修車；多目標；路徑優化；蟻群算法

1 基于功效函數法[1]的搶修車路徑優化模型

⑴優化目標：1）安全性：安全性表現為安全通過概率。2）道路狀況：道路狀況表現為路面良好程度。3）時間損耗：時效性是戰時主要考慮的因素。4）機動距離：機動距離對應著機動費用。

⑵利用層次分析法確定指標權重，本文采用1～9標度。

⑶設有m條備選路段，n項評估指標，共有L條可選路線，共有p個節點。備選路段d的各項評估指標數值為：{cd}={cd（1），cd（2），…cd（e），…cd（n）}，e=1，2…n。

①指標無量綱化處理方法

顯然，處理后的指標yd（e）越小，表明備選路段d的評估指標e評價越優。

②建立目標函數：

Sij、Rij、Tij、Eij分別為路段（i，j）的安全性、道路狀況、時間損耗、機動距離；式（5）表示任意路段只通過一次，式（6）表示一系列路段連通性約束。

2 最短路算法[2]

改進蟻群算法[3，4]（采用蟻周系統）：

⑴選擇概率改進：q和q0都是[0，1]之間的隨機數。

⑵懲罰策略：引入懲罰因子pn對路段進行懲罰。

式中， 和 分別表示懲罰前后路段（i，j）上的信息素濃度。

3 算法驗證與分析

搶修車由V1出發至V10對戰損裝備進行搶修，要求進行路徑優化，尋找最優路徑。

S、R、T、E的權重分別為：0.1268、0.2612、0.5224、0.0897。對各指標值進行無量綱化處理，采用功效函數法得出各路段的綜合分數。

基本和改進蟻群算法求最優路徑，得出最優路徑：1->2->5->8->10，最優路徑值：5.6748。參數設置：M=30、α=1、β=1、C=100、Q=10、ρ=0.65、pn=0.3、循環30次。

基本蟻群算法在第8次循環之后收斂，改進蟻群算法第1次循環即收斂，通過改進提高了蟻群算法的收斂速度。

4 結語

從戰時角度出發，建立了基于功效函數的搶修車路徑優化模型，改進了基本蟻群算法，通過實例驗證，證明改進蟻群算法具有更快的收斂速度，適于求解最優路徑問題。

[參考文獻]

[1]百度百科.功效函數法.http：//baike.baidu.com/view/1796103.htm.

[2]施寅躍.城市道路網中蟻群最短路徑算法研究[D].南京理工大學，2010.06.

[3]段海濱.蟻群算法原理及其應用[M].北京：科學出版社，2005.12.

[4]Badr A，Fahmy A.A proof of convergence for ant algorithms[J].International journal of Intelligent Computing and Information，2003，3（1）：22-32.