混合蟻群算法求解無人靶車路徑問題研究

丁雨康

摘要：針對無人靶車路徑過程中效率低成本高的問題，構建了無人靶車路徑問題（Routing?Problem?of?Unmanned?Target?Vehicle，?RPUTV）的混合整數優化模型，該模型以無人靶車行駛路徑距離最小化為優化目標。首先，為了提高算法的求解效率和求解質量，在算法的初始階段引入貪心算法來構建初始解，同時在蟻群算法中引入了鄰域搜索算法組成了混合蟻群算法（Hybrid?Ant?Colony?Algorithm，HACA）來提高算法的局部搜索能力。其次，采用標準數據集來驗證算法，同其他求解算法進行對比顯示，HACA算法求解RPUTV具有更高效性。

關鍵詞：無人靶車?蟻群算法?鄰域搜索算法?路徑規劃

中圖分類號：U469.691

Research?on?Solving?the?Routing?Problem?of?Unmanned?Target?Vehicles?by?the?Hybrid?Ant?Colony?Algorithm

DING?Yukang

（Anhui?Cusp?Intelligent?Technology?Co.，?Ltd.，?Chuzhou，?Anhui?Province，?239299?China）

Abstract：?In?order?to?solve?the?problem?of?low?efficiency?and?high?cost?in?the?process?of?unmanned?target?vehicle?routing，?a?mixed?integer?optimization?model?for?the?routing?problem?of?unmanned?target?vehicles?（RPUTV）?is?constructed，?which?takes?the?minimization?of?the?driving?route?distance?of?unmanned?target?vehicles?as?the?optimization?goal.?Firstly，?in?order?to?improve?the?solving?efficiency?and?quality?of?the?algorithm，?in?the?initial?stage?of?the?algorithm，?the?greedy?algorithm?is?introduced?to?build?an?initial?solution，?and?the?neighborhood?search?algorithm?is?introduced?into?the?ant?colony?algorithm?to?form?a?hybrid?ant?colony?algorithm?（HACA）?to?improve?the?local?search?ability?of?the?algorithm.?Then，?the?standard?data?set?is?used?to?verify?the?algorithm，?and?compared?with?other?solving?algorithms，?the?HACA?is?more?efficient?in?solving?the?RPUTV.

Key?Words：?Unmanned?target?vehicle;?Ant?colony?algorithm;?Neighborhood?search?algorithm;?Path?planning

無人靶車路徑問題（Routing?Problem?of?Unmanned?Target?Vehicle，?RPUTV）是組合優化領域中熱點問題。無人靶車路徑問題是由經典車輛路徑問題的泛化問題。謝高楊等人[1]首先建立了速度可變的無人靶車路徑規劃問題，其次將航腳與圓弧形搜索算法結合，提出了改進的A*算法，最后通過仿真實驗研究，結果表明：改進的A*算法可以解決不同世俗下的無人靶車路徑規劃問題。成海飛[2]針對靶車行駛的場景提出了面向越野環境下的無人靶車路徑規劃問題，同時為了提高路徑的搜索質量和效率，使用DWA算法進行算法的全局優化，并根據實時路況進行動態情況設計，最后為了驗證所提模型和算法的可靠性，通過MATLAB/Simulink和Carsim聯合仿真平臺進行仿真實驗。肖楠[3]針對移動靶車以傳統的軌道行駛，行駛路線單一的問題，設計了基于嵌入式的慣導技術的移動靶車設計，最后通過實驗仿真驗證了所提方法的有效性。PRUTV現已被證明為NP-hard問題，當前廣大學者在求解此類問題上常采用精確算法[4-6]、傳統啟發式算法[7-8]和元啟發式算法[9]。

1問題描述

RPUTV可以描述為一個中心具有多輛靶車，靶車可以自由選擇路徑移動到目標點，其次本問題以靶車行駛路徑最短為求解目標故作出以下假設：（1）所有靶車均從中心出發，執行完作戰任務后回到作戰中心；（2）一個作戰點由一輛靶車服務一次即可。

定義一個作戰中心具有臺無人靶車，無人靶車集合為，集合中的元素為無人靶車的編號，作戰目標點集合為，其中在，定義無人靶車行駛路徑為一個無向圖，為，其中0為作戰中心，為無人靶車行駛路徑邊的集合，。綜上所述無人靶車的模型如下所示。

• RPUTV的目標函數，其中為無人靶車行駛的距離，為二進制變量，時無人靶車路過兩個點，反之則不經過。為之間的距離。

• 每個目標點只可以訪問一次。

• 完成作戰任務后返回作戰中心。

• 禁止無人靶車行駛路徑中產生回環。

在公示（4）中M為極大數，為決策變量，繼而引入約束。

• HACA算法

2.1貪心算法

貪心算法（Greedy?Algorithm）是一種解決問題的算法范式，它以一種貪心的策略來選擇每一步的最優解，希望通過每一步的局部最優選擇最終達到全局最優解。因此本文為了提高算法的求解效率使用貪心算法來構建初始解其算法步驟如下。

步驟1：讀取當前的數據點的坐標，標記路徑為。

步驟2：判斷是否已經訪問過所有坐標點，若已經將所有點訪問結束則停止算法輸出解，若沒有訪問完所有的目標點則將未訪問的目標點記為。

步驟3：隨機產生的基點，接著將放入。

步驟4：挑選目標點，比較路徑，若路徑短則保留，執行完任務后返回步驟2。

2.2蟻群算法

蟻群算法（Ant?Colony?Optimization，?ACO）是一種仿生學算法其原理是通過模擬螞蟻尋找食物過程中會釋放信息素的行為來獲得路徑最優解。其具體步驟如下。

步驟1：初始化信息素，在通過貪心算法得到的路徑中，隨機放置“螞蟻”，每一對螞蟻分配一個初始問題的信息素。表示“螞蟻”在兩個目標點匯總的可行性。

步驟2：根據選擇概率，“螞蟻”選擇下一個需要移動的目標點，在此過程中會釋放出信息素，信息素濃度為

步驟3：“螞蟻”選擇下一移動的目標點并及時地更新走過的信息素。

步驟4：在每次迭代后更新無人靶車路徑可行解中的信息素濃度。通常使用蒸發和新信息素的沉積來模擬信息素的更新。

步驟5：比較解的質量，即“螞蟻”走過的路徑最短

步驟6：重復步驟2到步驟5。直到滿足停止條件，輸出最優解。

2.2.1鄰域搜索算法

由于蟻群算法容易陷入局部最優，因此在算法的求解過程中加入相應的鄰域變換如單點插入和2-opt操作，算法步驟具體如下。

2.2.2單點操作

單點插入操作作用于無人靶車行駛路徑中，如圖1所示將Route1目標點3插入到Route2目標點1的位置形成Route2。

• 2-opt操作

2-opt是局部搜索（Local?search）算法，同時局部搜索算法是在目標問題的一組可行解上進行鄰域搜索得到新的可行解。圖2為2-opt操作的實例，將中的1插入到3的位置，2插入到1的位置，3插入到2的位置，形成新的路徑

3?實驗仿真

本文涉及的所有算法采用Python語言編程，在Win10操作系統下，硬件為設備名稱DESKTOP-NTUFG2K Intel（R）?Core（TM）?i5-8350U?CPU?@?1.70GHz???1.90?GHz，?RAM16.0?GB?的機器上運行，實驗數據采用Solomon數據庫，實驗仿真結果如下所示。

本文采用一種混合蟻群算法（Hybrid?Ant?Colony?Algorithm，HACA）來解決RPUVT問題。算法的初始階段使用貪心算法對問題的初始解進行構建，接著在蟻群算法的搜索過程中引入鄰域搜索的操作，來加強算法的鄰域搜索能力。為了驗證所提算法的可靠性，本文將HACA與遺傳算法（Genetic?Algorithm，?GA）和模擬退火算法（Simulated?Annealing，SA）。進行仿真比較，算法均設定運行30次，運行時間設定為50s。各算法數據對比如下所示，為行駛總路徑，為平均值，其中較好的數據均用粗體表示，綜合表1所示HACA算法求得的解優于GA和SA。

4結語

本文提出了一種并求解了一種無人靶車路徑規劃問題，首先綜合考慮了無人靶車的行駛距離，同時構建了無人靶車路徑規劃問題的混合整數規劃模型，其次提出了一種混合蟻群算法，算法的初始階段為了提高算法的求解效率，提出使用貪心算法構建目標問題的初始解，接著在蟻群算法中為了防止算法過早收斂，插入鄰域搜索的策略來提高解的質量，最后將該算法通過對比實驗驗證了該算法較GA、SA更加有效。

參考文獻

• 謝高楊，房立清，蘇續軍，等.無人靶車在不同車速下的路徑規劃方法[J].電子測量與儀器學報，2023，?37（2）：?39-47.
• 成海飛.面向越野環境的無人靶車路徑規劃研究[D].南京：南京林業大學，2023.
• 肖楠.基于嵌入式慣導技術的移動靶車設計[D].西安：西安工業大學，2023.
• YU?Y，?WANG?S，?WANG?J，?et?al.?A?branch-and-price?algorithm?for?the?heterogeneous?fleet?green?vehicle?routing?problem?with?time?windows[J].?Transportation?Research?Part?B：?Methodological，?2019，?122（4）：?511-527.
• XIAO?Y，?KONAK?A.?The?heterogeneous?green?vehicle?routing?and?scheduling?problem?with?time-varying?traffic?congestion[J].Transportation?Research?Part?E：Logistics?and?Transportation?Review，2016，88（4）：146-166.
• CIMEN?M，SOYSAL?M.Time-dependent?green?vehicle?routing?problem?with?stochastic?vehicle?speeds：?An?approximate?dynamic?programming?algorithm[J].?Transportation?Research?Part?D?Transport?&?Environment，2017，54：82-98.
• 呂飛，王力，黃石磊.基于混合C-W節約與遺傳算法的多AMR揀選路徑規劃優化方法研究[J].工業控制計算機，2023，36（11）：81-84.
• 崔煥煥，官禮和.優先配送綠色VRP的混合啟發式求解算法[J/OL].系統仿真學報：1-12[2023-12-18].https：//doi.org/10.16182/j.issn1004731x.joss.223-1125.
• 黃雄，史長勝，曹祺.基于改進模擬退火算法的校車路徑規劃研究[J].淮南職業技術學院學報，2023，23（3）：131-133.