基于混合蟻群貪婪算法的路面區(qū)域多裂縫修補(bǔ)路徑規(guī)劃研究

于 靜, 郭嘉偉, 邢立寧 ,魯巍巍

(1.長(zhǎng)沙理工大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長(zhǎng)沙 400114；2.長(zhǎng)沙理工大學(xué) 公路養(yǎng)護(hù)技術(shù)國(guó)家工程研究中心，湖南 長(zhǎng)沙 400114；3.西安電子科技大學(xué) 協(xié)同智能系統(tǒng)教育部重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710068)

0 引言

裂縫類病害是路面最常見的路面病害之一，如不加以及時(shí)處治，將會(huì)增大路面養(yǎng)護(hù)成本及維修難度，給行車安全帶來隱患，增大交通事故幾率，降低公路通行效率。路面裂縫修補(bǔ)是一項(xiàng)龐大工程，主要包括裂縫清理、注入密封膠與壓實(shí)3部分。路面裂縫修補(bǔ)工程若僅由人工完成，不僅工作效率低下，耗費(fèi)大量物力、財(cái)力，而且在道路施工過程中施工人員的安全也很難保障。隨著道路基礎(chǔ)設(shè)施智能化水平的不斷提高，公路工程也朝著自動(dòng)化、智能化發(fā)展。對(duì)于路面裂縫自動(dòng)化修補(bǔ)，科研工作者研發(fā)出了不同的病害自動(dòng)化修補(bǔ)設(shè)備[1-3]，利用少量的人工控制機(jī)器就可以完成路面裂縫的修補(bǔ)工程。路面病害的自動(dòng)化修補(bǔ)系統(tǒng)主要包括圖像獲取與處理模塊、路徑規(guī)劃模塊以及機(jī)械控制模塊。其中圖像獲取與處理模塊已經(jīng)有了較為深入的研究，但關(guān)于路徑規(guī)劃模塊的相關(guān)研究較少。

對(duì)于路面裂縫自動(dòng)化修補(bǔ)的路徑規(guī)劃問題，兩階段樹算法[4]可以求解含有6條以下裂縫的待修補(bǔ)路段，單階段樹算法[4]可以修補(bǔ)7～8條裂縫，貪婪算法[5]、模擬退火算法[6]可以求解9條及以上裂縫的路段。但當(dāng)路面裂縫數(shù)量較多時(shí)，貪婪算法與模擬退火算法易發(fā)生過早收斂現(xiàn)象。Wang等[7]提出的一種基于深度圖像輪廓導(dǎo)引之字形路徑規(guī)劃方法，是知識(shí)型路面裂縫自動(dòng)化修補(bǔ)技術(shù)的一個(gè)新思考方向。但面向待修補(bǔ)區(qū)域包含裂縫數(shù)量較多的復(fù)雜場(chǎng)景，還需要進(jìn)一步研究。為此，本文面向待修補(bǔ)區(qū)域包含40條裂縫的情況，對(duì)基于混合蟻群貪婪算法的路面區(qū)域多裂縫修補(bǔ)路徑規(guī)劃問題進(jìn)行了研究。

1 問題描述與建模

在路面裂縫的自動(dòng)化修補(bǔ)過程中，裂縫修補(bǔ)設(shè)備行走的全部路程可以分為兩部分：一是工作區(qū)域內(nèi)裂縫長(zhǎng)度總和，二是修補(bǔ)車完成一條裂縫修補(bǔ)工作后從裂縫終點(diǎn)行走至下一裂縫起點(diǎn)間的距離之和，稱為冗余距離[8]。顯然，工作區(qū)域內(nèi)裂縫長(zhǎng)度為待修補(bǔ)裂縫長(zhǎng)度，該部分的路徑總長(zhǎng)度不會(huì)改變。唯一改變的路徑長(zhǎng)度為修補(bǔ)車完成一條裂縫修補(bǔ)后行駛到下一條裂縫之間的距離總和，故該路徑規(guī)劃問題的關(guān)鍵是優(yōu)化修補(bǔ)車的冗余距離。

面向路面區(qū)域多裂縫修補(bǔ)路徑的規(guī)劃問題可以描述為：在滿足裂縫修補(bǔ)資源和修補(bǔ)需求的約束條件下，以最短冗余距離為優(yōu)化目標(biāo)，為自動(dòng)修補(bǔ)車制定一條合理的自動(dòng)修補(bǔ)路徑。路面區(qū)域多裂縫修補(bǔ)路徑規(guī)劃問題實(shí)質(zhì)上是求解帶約束條件的最短路徑TSP問題。TSP問題是經(jīng)典的N-P問題，若待修補(bǔ)區(qū)域內(nèi)有n條裂縫，使用精確算法的計(jì)算復(fù)雜度為O(2n×n！)。當(dāng)n較小時(shí)，可采用精確算法求解；當(dāng)n較大時(shí)，精確算法很難及時(shí)獲得可行方案。面向待修補(bǔ)區(qū)域內(nèi)包含多條裂縫的情況，需要設(shè)計(jì)一種同時(shí)兼顧求解質(zhì)量與求解時(shí)間的智能優(yōu)化算法。

設(shè)C={c1，c2，…，c3}表示裂縫集合，ci表示第i條裂縫；ai與bi分別表示裂縫ci的起點(diǎn)和終點(diǎn)；dij表示裂縫ci終點(diǎn)bi與裂縫cj起點(diǎn)aj之間的距離。裂縫的端點(diǎn)集和為V=(a1，b1，…，an，bn)，使用k=1，2，…，2n表示V中的第k個(gè)端點(diǎn)。

面向路面區(qū)域多裂縫修補(bǔ)路徑規(guī)劃問題的數(shù)學(xué)模型為：

(1)

(2)

(3)

(4)

(5)

(6)

其中，式(1)為目標(biāo)函數(shù)，表示在待修補(bǔ)路面區(qū)域中修補(bǔ)車除修補(bǔ)裂縫外行駛的總距離，即修補(bǔ)車行駛的總?cè)哂嗑嚯x；式(2)表示每條裂縫至多被補(bǔ)修1次；式(3)表示可行解的第1條裂縫、第n條裂縫與其他裂縫之間只存在1次連接；式(4)表示除去可行解的首尾2條裂縫后，每條裂縫的起點(diǎn)與終點(diǎn)都與其他的裂縫相連；式(5)表示可行解序列間的連接線有n-1條；式(6)為決策變量，xi=1表示裂縫ci被選擇修補(bǔ)，other表示當(dāng)前沒有被選擇。

2 混合蟻群貪婪算法

對(duì)于路面區(qū)域多裂縫修補(bǔ)路徑規(guī)劃問題，為盡可能訪問到每條裂縫端點(diǎn)從而獲取較優(yōu)解，要求其求解算法必須有較強(qiáng)的隨機(jī)搜索能力；另外，考慮到本研究問題的特性，在完成一條裂縫的修補(bǔ)工作后，一般不會(huì)選擇距離較遠(yuǎn)的裂縫作為下一個(gè)修補(bǔ)工作，故本研究問題同時(shí)存在局部貪婪性。

蟻群優(yōu)化算法(Ant Colony Optimization，ACO/AC)是模擬現(xiàn)實(shí)世界螞蟻覓食行為的一種仿生搜索算法，有較強(qiáng)的隨機(jī)搜索功能和正反饋機(jī)制；貪婪算法是一個(gè)求解速度快、規(guī)則簡(jiǎn)單的高效算法，由于具有總是做出在當(dāng)前看來最好選擇的貪婪性，該算法很容易收斂到局部最優(yōu)解。因此，結(jié)合蟻群算法較強(qiáng)的隨機(jī)搜索功能和正反饋機(jī)制，以及貪婪算法的貪婪規(guī)則，本文構(gòu)造了混合蟻群貪婪算法(Ant Colony and Greedy Algorithm，AC-GA)求解路面裂縫自動(dòng)化修補(bǔ)路徑規(guī)劃問題。

2.1 可行解的構(gòu)造

在蟻群算法中，每只螞蟻隨機(jī)選擇一條裂縫的某個(gè)端點(diǎn)(起點(diǎn)或終點(diǎn))，依據(jù)狀態(tài)轉(zhuǎn)移規(guī)則與貪婪規(guī)則依概率選擇下一條裂縫的某個(gè)端點(diǎn)，直至完成一條可行解的構(gòu)建。每只螞蟻在選擇一條裂縫后，執(zhí)行局部信息素更新，在所有螞蟻完成一條可行解的搜索后，執(zhí)行全局信息素更新(見圖1)。如圖1所示，序列“c1→c2→…→cn”為一條可行解。

圖1 可行解示意

2.2 信息素矩陣與啟發(fā)式矩陣

2.3 狀態(tài)轉(zhuǎn)移規(guī)則

在第m只螞蟻選擇完初始節(jié)點(diǎn)后，根據(jù)下面的規(guī)則選擇其下一個(gè)端點(diǎn)l，即：

(7)

2.4 局部信息素和全局信息素更新

在螞蟻由端點(diǎn)k選擇完下一個(gè)可行端點(diǎn)l后，對(duì)邊(k，l)上的信息素更新，即：

τkl←(1-ρlocal)τkl+ρlocalτ0

(8)

式中：ρlocal為局部信息素?fù)]發(fā)因子；τ0為初始信息素濃度。

在所有螞蟻完成各自可行解的構(gòu)建后，選擇收益值最大的一個(gè)解執(zhí)行更新全局信息素，規(guī)則為：

τu,v←(1-ρglobal)τu,v+ρglobalΔτu,v

(9)

其中，ρglobal為全局信息素?fù)]發(fā)系數(shù)，信息素增量為：

(10)

式中：Lbest為當(dāng)前最優(yōu)路徑。

2.5 AC-GA算法的求解步驟

AC-GA算法的求解步驟具體如下：

1)對(duì)第m只螞蟻，隨機(jī)選擇一個(gè)端點(diǎn)作為其初始點(diǎn)，記錄解并更新后續(xù)可訪問集合J；

2)按照式(7)狀態(tài)轉(zhuǎn)移規(guī)則選擇下一條裂縫端點(diǎn)，記錄解并更新后續(xù)可訪問集合J，按照式(8)更新局部信息素，轉(zhuǎn)步驟3；

3)判斷后續(xù)可訪問集合J，若J為空，得到可行解，轉(zhuǎn)步驟4；若J非空，轉(zhuǎn)步驟2；

4)m=m+1，M只螞蟻依次遍歷尋優(yōu)；

5)按照式(9)更新全局部信息素；

6)輸出最優(yōu)解信息。

3 實(shí)例仿真

仿真實(shí)驗(yàn)所用路面裂縫測(cè)試數(shù)據(jù)為采用大疆DJI Mavic 3無人機(jī)對(duì)長(zhǎng)沙理工大學(xué)云塘校區(qū)云章路某路段瀝青路面實(shí)地拍攝所得，后經(jīng)圖像拼接后得到完整的路面信息，如圖2所示。圖2中待修補(bǔ)區(qū)域?yàn)樵普侣冯p向兩車道某路段，總寬7 m、總長(zhǎng)24m。將圖2中路面裂縫劃分為40條裂縫。測(cè)試實(shí)驗(yàn)環(huán)境為Windows 11，2.1 Ghz CPU 16GB內(nèi)存的筆記本電腦，采用Matlab R2022a實(shí)現(xiàn)編程。

圖2 云章路某路段的瀝青路面裂縫

首先對(duì)圖2進(jìn)行圖像識(shí)別，在圖中標(biāo)定出裂縫位置并提取裂縫的位置坐標(biāo)信息，得到圖2中40條裂縫的擬合曲線圖。然后基于提取的裂縫數(shù)據(jù)信息對(duì)文中的兩種求解算法進(jìn)行驗(yàn)證。

為了驗(yàn)證AC-GA算法的有效性，首先進(jìn)行算法參數(shù)的選取。經(jīng)過多次實(shí)驗(yàn)參數(shù)比較，本實(shí)驗(yàn)中的參數(shù)設(shè)計(jì)為：迭代次數(shù)800；螞蟻個(gè)數(shù)M=8；信息素參數(shù)α=1.1；期望因子β=1.7；全局信息素?fù)]發(fā)系數(shù)為ρglobao=0.2；局部信息素?fù)]發(fā)系數(shù)為ρlocal=0.25；貪婪規(guī)則中的參數(shù)S=5；q0=0.85。

在以上參數(shù)設(shè)置下，AC-GA算法求解待修補(bǔ)區(qū)域包含40條裂縫的路面區(qū)域多裂縫修補(bǔ)路徑規(guī)劃方案如圖3所示，圖中實(shí)線為路面裂縫，虛線為模擬自動(dòng)修補(bǔ)車在裂縫間行走的路徑軌跡(冗余距離)。

圖3 AC-GA算法的當(dāng)前最優(yōu)解

圖4、圖5分別為AC-GA與AC兩種算法在求解質(zhì)量和求解速度兩方面的表現(xiàn)情況。不難發(fā)現(xiàn)兩種求解算法對(duì)于待修補(bǔ)區(qū)域內(nèi)包含40條裂縫的路面區(qū)域多裂縫修補(bǔ)路徑規(guī)劃問題在求解質(zhì)量與求解效率兩方面都表現(xiàn)出其有效性。圖4展現(xiàn)了兩種算法在不同的迭代步數(shù)下最優(yōu)值的變化，從圖中可見，隨著迭代次數(shù)增加，兩種算法獲取當(dāng)前最優(yōu)解的效果越好，整體上AC-GA算法的求解質(zhì)量要優(yōu)于AC算法。圖5展現(xiàn)了兩種算法在不同迭代步數(shù)下運(yùn)行時(shí)間的消耗情況，不難發(fā)現(xiàn)AC-GA算法的求解效率要整體高于AC算法。故面向路面區(qū)域多裂縫修補(bǔ)路徑規(guī)劃問題，綜合求解質(zhì)量與求解效率兩個(gè)方面的性能比較，AC-GA算法的性能優(yōu)于AC算法。

圖4 AC-GA與AC最優(yōu)值的比較

圖5 AC-GA與AC運(yùn)行時(shí)間的比較

4 結(jié)語

面對(duì)日益繁重的公路養(yǎng)護(hù)任務(wù)，亟需通過公路養(yǎng)護(hù)的自動(dòng)化與智能化提升公路養(yǎng)護(hù)效率，保障安全通行。為此，本文面向路面區(qū)域多裂縫修補(bǔ)路徑規(guī)劃問題，構(gòu)建了數(shù)學(xué)模型，并針對(duì)待修補(bǔ)區(qū)域包含40條裂縫的場(chǎng)景，設(shè)計(jì)了混合蟻群貪婪算法進(jìn)行求解。為了驗(yàn)證本算法的有效性，使用無人機(jī)獲取了某路段(雙向兩車道)的路面病害信息(寬7m，長(zhǎng)24m)并開展實(shí)驗(yàn)探究。實(shí)驗(yàn)結(jié)果表明：混合蟻群貪婪算法可以高效地求解待修補(bǔ)區(qū)域包含較多裂縫的問題。

本文在路面區(qū)域多裂縫修補(bǔ)路徑規(guī)劃問題中，對(duì)待修補(bǔ)區(qū)域包含40條裂縫的場(chǎng)景進(jìn)行了模型構(gòu)建與算法研發(fā)。為了更好地實(shí)現(xiàn)路面病害的自動(dòng)化維修，基于裂縫圖像識(shí)別技術(shù)，以修補(bǔ)車行駛的最短冗余距離為優(yōu)化目標(biāo)，基于現(xiàn)實(shí)裂縫修補(bǔ)的約束條件，獲取修補(bǔ)車的最短行走軌跡。首先，對(duì)面向路面區(qū)域多裂縫修補(bǔ)路徑規(guī)劃問題，以最短冗余距離為目標(biāo)構(gòu)建了其路徑規(guī)劃數(shù)學(xué)模型；其次，基于路徑規(guī)劃數(shù)學(xué)模型，研發(fā)了對(duì)應(yīng)的蟻群求解算法與蟻群-貪婪求解算法；最后，以無人機(jī)拍攝的云章路某路段瀝青路面裂縫情況進(jìn)行算法驗(yàn)證。本文研究成果如下：

1)對(duì)面向路面區(qū)域多裂縫修補(bǔ)路徑規(guī)劃問題，以最短冗余距離為目標(biāo)構(gòu)建了路面區(qū)域多裂縫修補(bǔ)路徑規(guī)劃數(shù)學(xué)模型；

2)基于路面區(qū)域多裂縫修補(bǔ)路徑規(guī)劃數(shù)學(xué)模型，研發(fā)了對(duì)應(yīng)的蟻群求解算法與蟻群-貪婪求解算法；

3)以無人機(jī)拍攝的云章路某路段待修補(bǔ)區(qū)域包含40條裂縫場(chǎng)景為例，采用AC、AC-GA算法獲取了自動(dòng)修補(bǔ)車的最短修補(bǔ)路徑。

通過實(shí)例求解，驗(yàn)證了AC、AC-GA算法求解路面病害自動(dòng)化修補(bǔ)問題的可行性與有效性。與AC算法相比，AC-GA算法在求解質(zhì)量與求解效率上表現(xiàn)更優(yōu)，可實(shí)現(xiàn)10 s內(nèi)獲取40條裂縫場(chǎng)景的較優(yōu)自動(dòng)修補(bǔ)方案。

另外，因待修補(bǔ)區(qū)域包含的裂縫數(shù)量不同，其合適的求解算法可能不同。本文只針對(duì)待修補(bǔ)區(qū)域包含40條裂縫的場(chǎng)景進(jìn)行了算法設(shè)計(jì)，未對(duì)待修補(bǔ)區(qū)域內(nèi)不同裂縫數(shù)量級(jí)別的問題進(jìn)行算法設(shè)計(jì)與案例分析。未來還需針對(duì)待修補(bǔ)區(qū)域內(nèi)裂縫數(shù)量分別為10、20、30、35、40條的場(chǎng)景進(jìn)行有效算法設(shè)計(jì)與案例分析。