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

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

0 引言

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

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

1 問題描述與建模

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

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

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

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

(1)

(2)

(3)

(4)

(5)

(6)

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

2 混合蟻群貪婪算法

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

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

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

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

圖1 可行解示意

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

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

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

(7)

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

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

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

(8)

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

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

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

(9)

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

(10)

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

2.5 AC-GA算法的求解步驟

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

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

2)按照式(7)狀態(tài)轉(zhuǎn)移規(guī)則選擇下一條裂縫端點，記錄解并更新后續(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ù)據(jù)為采用大疆DJI Mavic 3無人機對長沙理工大學(xué)云塘校區(qū)云章路某路段瀝青路面實地拍攝所得，后經(jīng)圖像拼接后得到完整的路面信息，如圖2所示。圖2中待修補區(qū)域為云章路雙向兩車道某路段，總寬7 m、總長24m。將圖2中路面裂縫劃分為40條裂縫。測試實驗環(huán)境為Windows 11，2.1 Ghz CPU 16GB內(nèi)存的筆記本電腦，采用Matlab R2022a實現(xiàn)編程。

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

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

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

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

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

圖4、圖5分別為AC-GA與AC兩種算法在求解質(zhì)量和求解速度兩方面的表現(xiàn)情況。不難發(fā)現(xiàn)兩種求解算法對于待修補區(qū)域內(nèi)包含40條裂縫的路面區(qū)域多裂縫修補路徑規(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ù)下運行時間的消耗情況，不難發(fā)現(xiàn)AC-GA算法的求解效率要整體高于AC算法。故面向路面區(qū)域多裂縫修補路徑規(guī)劃問題，綜合求解質(zhì)量與求解效率兩個方面的性能比較，AC-GA算法的性能優(yōu)于AC算法。

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

圖5 AC-GA與AC運行時間的比較

4 結(jié)語

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

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

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

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

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

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

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