基于混合蚁群贪婪算法的路面区域多裂缝修补路径规划研究

于 静, 郭嘉伟, 邢立宁 ,鲁巍巍

(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条的场景进行有效算法设计与案例分析。