基于混合蟻群貪婪算法的路面區域多裂縫修補路徑規劃研究

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

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

0 引言

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

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

1 問題描述與建模

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

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

設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個端點。

面向路面區域多裂縫修補路徑規劃問題的數學模型為：

(1)

(2)

(3)

(4)

(5)

(6)

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

2 混合蟻群貪婪算法

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

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

2.1 可行解的構造

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

圖1 可行解示意

2.2 信息素矩陣與啟發式矩陣

2.3 狀態轉移規則

在第m只螞蟻選擇完初始節點后，根據下面的規則選擇其下一個端點l，即：

(7)

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

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

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

(8)

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

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

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

(9)

其中，ρglobal為全局信息素揮發系數，信息素增量為：

(10)

式中：Lbest為當前最優路徑。

2.5 AC-GA算法的求解步驟

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

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

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

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

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

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

6)輸出最優解信息。

3 實例仿真

仿真實驗所用路面裂縫測試數據為采用大疆DJI Mavic 3無人機對長沙理工大學云塘校區云章路某路段瀝青路面實地拍攝所得，后經圖像拼接后得到完整的路面信息，如圖2所示。圖2中待修補區域為云章路雙向兩車道某路段，總寬7 m、總長24m。將圖2中路面裂縫劃分為40條裂縫。測試實驗環境為Windows 11，2.1 Ghz CPU 16GB內存的筆記本電腦，采用Matlab R2022a實現編程。

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

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

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

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

圖3 AC-GA算法的當前最優解

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

圖4 AC-GA與AC最優值的比較

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

4 結語

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

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

1)對面向路面區域多裂縫修補路徑規劃問題，以最短冗余距離為目標構建了路面區域多裂縫修補路徑規劃數學模型；

2)基于路面區域多裂縫修補路徑規劃數學模型，研發了對應的蟻群求解算法與蟻群-貪婪求解算法；

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

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

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