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

丁雨康

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

關(guān)鍵詞：無人靶車?蟻群算法?鄰域搜索算法?路徑規(guī)劃

中圖分類號：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）是組合優(yōu)化領(lǐng)域中熱點問題。無人靶車路徑問題是由經(jīng)典車輛路徑問題的泛化問題。謝高楊等人[1]首先建立了速度可變的無人靶車路徑規(guī)劃問題，其次將航腳與圓弧形搜索算法結(jié)合，提出了改進的A*算法，最后通過仿真實驗研究，結(jié)果表明：改進的A*算法可以解決不同世俗下的無人靶車路徑規(guī)劃問題。成海飛[2]針對靶車行駛的場景提出了面向越野環(huán)境下的無人靶車路徑規(guī)劃問題，同時為了提高路徑的搜索質(zhì)量和效率，使用DWA算法進行算法的全局優(yōu)化，并根據(jù)實時路況進行動態(tài)情況設(shè)計，最后為了驗證所提模型和算法的可靠性，通過MATLAB/Simulink和Carsim聯(lián)合仿真平臺進行仿真實驗。肖楠[3]針對移動靶車以傳統(tǒng)的軌道行駛，行駛路線單一的問題，設(shè)計了基于嵌入式的慣導(dǎo)技術(shù)的移動靶車設(shè)計，最后通過實驗仿真驗證了所提方法的有效性。PRUTV現(xiàn)已被證明為NP-hard問題，當(dāng)前廣大學(xué)者在求解此類問題上常采用精確算法[4-6]、傳統(tǒng)啟發(fā)式算法[7-8]和元啟發(fā)式算法[9]。

1問題描述

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

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

• RPUTV的目標(biāo)函數(shù)，其中為無人靶車行駛的距離，為二進制變量，時無人靶車路過兩個點，反之則不經(jīng)過。為之間的距離。

• 每個目標(biāo)點只可以訪問一次。

• 完成作戰(zhàn)任務(wù)后返回作戰(zhàn)中心。

• 禁止無人靶車行駛路徑中產(chǎn)生回環(huán)。

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

• HACA算法

2.1貪心算法

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

步驟1：讀取當(dāng)前的數(shù)據(jù)點的坐標(biāo)，標(biāo)記路徑為。

步驟2：判斷是否已經(jīng)訪問過所有坐標(biāo)點，若已經(jīng)將所有點訪問結(jié)束則停止算法輸出解，若沒有訪問完所有的目標(biāo)點則將未訪問的目標(biāo)點記為。

步驟3：隨機產(chǎn)生的基點，接著將放入。

步驟4：挑選目標(biāo)點，比較路徑，若路徑短則保留，執(zhí)行完任務(wù)后返回步驟2。

2.2蟻群算法

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

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

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

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

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

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

步驟6：重復(fù)步驟2到步驟5。直到滿足停止條件，輸出最優(yōu)解。

2.2.1鄰域搜索算法

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

2.2.2單點操作

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

• 2-opt操作

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

3?實驗仿真

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

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

4結(jié)語

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

參考文獻

• 謝高楊，房立清，蘇續(xù)軍，等.無人靶車在不同車速下的路徑規(guī)劃方法[J].電子測量與儀器學(xué)報，2023，?37（2）：?39-47.
• 成海飛.面向越野環(huán)境的無人靶車路徑規(guī)劃研究[D].南京：南京林業(yè)大學(xué)，2023.
• 肖楠.基于嵌入式慣導(dǎo)技術(shù)的移動靶車設(shè)計[D].西安：西安工業(yè)大學(xué)，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節(jié)約與遺傳算法的多AMR揀選路徑規(guī)劃優(yōu)化方法研究[J].工業(yè)控制計算機，2023，36（11）：81-84.
• 崔煥煥，官禮和.優(yōu)先配送綠色VRP的混合啟發(fā)式求解算法[J/OL].系統(tǒng)仿真學(xué)報：1-12[2023-12-18].https：//doi.org/10.16182/j.issn1004731x.joss.223-1125.
• 黃雄，史長勝，曹祺.基于改進模擬退火算法的校車路徑規(guī)劃研究[J].淮南職業(yè)技術(shù)學(xué)院學(xué)報，2023，23（3）：131-133.