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

丁雨康

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

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

中圖分類號(hào)：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

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

1問題描述

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

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

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

• 每個(gè)目標(biāo)點(diǎn)只可以訪問一次。

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

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

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

• HACA算法

2.1貪心算法

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

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

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

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

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

2.2蟻群算法

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

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

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

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

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

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

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

2.2.1鄰域搜索算法

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

2.2.2單點(diǎn)操作

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

• 2-opt操作

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

3?實(shí)驗(yàn)仿真

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

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

4結(jié)語(yǔ)

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

參考文獻(xiàn)

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