《European Journal of Operational Research》：Iterated local search for coverage path planning with imperfect extended detection
编辑推荐：
研究人员针对水雷对抗（MCM）作业中的扫雷任务，研究了非完美扩展检测下的覆盖路径规划（CPPIED）问题。该问题被建模为一种字典序组合优化问题，主要目标为最小化路径长度，次要目标为在满足整个感兴趣区域覆盖比例约束的前提下最小化航向变化次数。现有最先进方法DpS
研究人员针对水雷对抗（MCM）作业中的扫雷任务，研究了非完美扩展检测下的覆盖路径规划（CPPIED）问题。该问题被建模为一种字典序组合优化问题，主要目标为最小化路径长度，次要目标为在满足整个感兴趣区域覆盖比例约束的前提下最小化航向变化次数。现有最先进方法DpSweeper是一种贪心混合启发式算法，虽能快速生成可行解，但受限于其贪心本质，解质量有限。由于实际规划视野和搜索区域的规模，CPPIED对于通用求解器仍然难以处理。因此，研究人员开发了一种专门针对CPPIED的新型迭代局部搜索（ILS）启发式算法。研究人员将CPPIED与车辆路径问题进行关联，调整了原本为车辆路径问题设计的邻域算子以更好地适应CPPIED的结构特性，并开发了专门针对CPPIED的ILS算子，包括动态规划选择启发式、结合树搜索与DpSweeper启发式的重启过程、基于广义旅行商问题（GTSP）归约的大邻域，以及基于重分配模型并用列生成启发式求解的大邻域。在后者的定价子问题中，通过有向无环图（DAG）最短路径公式化归约来利用CPPIED的结构特性，与暴力方法相比将计算复杂度降低了两个数量级。研究人员还提出了CPPIED的字典序双目标整数线性规划（ILP）公式化，从而能够利用Gurobi求解器。计算实验与统计分析表明，所提出的ILS启发式算法在所有基准实例上均能一致地产生比DpSweeper更短的覆盖路径，并在所有指标上优于Gurobi和DpSweeper。该研究证明了运筹学社区开发的方法在解决移动机器人覆盖路径规划问题方面的相关性，所开发的启发式算法可集成到MCM规划系统中以减少预期任务完成时间。
**研究背景与问题**
水雷被认为是海战中最具成本效益的武器之一，至今仍在持续使用和改进。水雷对抗（Mine Countermeasure, MCM）作业中的标准扫雷流程是：在指定的感兴趣区域内，由自主水下航行器（Autonomous Underwater Vehicle, AUV），如装备侧扫声呐的REMUS 100，利用目标识别算法搜索探测水雷。MCM作业涉及多个决策组件，包括任务分配、路径规划和编队控制。路径规划可分为在线和离线两种方式。在线规划允许根据作业过程中的观测调整AUV路径；离线规划则是基于先前水下勘测获取的静态环境信息来规划AUV路径，该问题属于NP难问题。在MCM作业中，侧扫声呐的探测能力是非完美的且依赖于环境，这使得完全覆盖在实际中不可行。探测性能取决于海底特征，如深度和纹理。全局路径效率可通过预期完成时间、水下水雷的条件探测概率以及由航向变化引起的潜在航位推算误差来定义。
为综合考虑上述因素，Drabovich（2008）提出了非完美扩展检测下的覆盖路径规划（Coverage Path Planning with Imperfect Extended Detection, CPPIED）问题，后由Morin et al.（2013）形式化为字典序组合优化问题。其主要目标是最小化路径长度，次要目标是在确保整个感兴趣区域达到满意覆盖比例的前提下最小化航向变化次数。当前CPPIED的最先进方法是混合启发式算法DpSweeper（Morin et al., 2013），它能快速生成可行解，但受限于贪心本质，解质量有限。尽管已有多种其他工作涉及扫雷覆盖路径规划，但所开发的方法要么是贪心的，要么关注问题的不同操作层面。由于实际规划视野和搜索区域的规模，CPPIED对于通用求解器仍然难以处理。因此，研究人员开发了一种专门针对CPPIED的新型迭代局部搜索（Iterated Local Search, ILS）启发式算法。
**关键技术方法**
研究人员采用的主要技术方法包括：（1）将CPPIED建模为字典序双目标整数线性规划（Integer Linear Program, ILP），改编自随机接近弧路径问题（Stochastic Close-Enough Arc Routing Problem, S-CEARP）模型，并采用对数变换线性化覆盖约束；（2）设计迭代局部搜索（ILS）框架，包含初始解构造、局部搜索、扰动和接受准则四个组件；（3）基于DpSweeper启发式构造初始解，结合动态规划寻找覆盖段集合，并通过归约为旅行商问题（Traveling Salesman Problem, TSP）用LKH启发式求解段间连接顺序；（4）采用变量邻域下降（Variable Neighborhood Descent, VND）作为局部搜索组件，包含简单邻域、嵌套邻域和大邻域三层结构；（5）开发三种扰动方法：随机插入扰动、平行轨迹扰动和双桥扰动；（6）设计基于Luby策略的重启方法，结合DpSweeper的回溯策略；（7）在大邻域的重分配模型中，将定价子问题归约为有向无环图（Directed Acyclic Graph, DAG）最短路径问题，将计算复杂度从暴力方法的O(|R|r_max(mn3+nm3))降低至O((r_max+|R|)mn)。实验使用了252个系统变化参数构建的实例，网格规模为16×16、64×64和128×128，侧扫范围r_max∈{1,3,5}，海底类型包括细胞自动机生成的结构化模式和随机非结构化模式。对比方法包括Gurobi求解器（含DpSweeper热启动配置）和DpSweeper启发式。
**研究结果**
**算法配置与消融分析**：通过三阶段局部搜索算法对ILS的11个二进制组件位进行配置，最终选定配置c11101001110。消融分析表明，简单邻域N?,?对解质量影响最大；随机插入扰动的多样化和大邻域N_tsp的强化均显著改善平均偏差（AvgD）；简单邻域N?,?和N?,?、双桥扰动和平行轨迹扰动的联合效应带来最后的显著增益。仅使用简单邻域N?,?和随机插入扰动的配置产生最少航向变化次数，建议在航向变化更重要时使用配置c01000001000作为基础。
**大邻域强化效果**：替换N_tsp为N_gtsp或N_R的比较显示，N_gtsp与N_R之间无显著差异；N_tsp在路径长度上优于N_gtsp和N_R，但在航向变化次数上被二者支配。按字典序，N_tsp优于N_gtsp和N_R；但若更重视航向变化次数，N_R可能产生更好结果。
**扰动优于重启**：算法配置阶段选择了三种扰动方法，凸显了多样化对CPPIED的重要性；重启方法未被选中。添加重启与不添加重启之间无显著差异，表明仅靠扰动即可在实例集上实现充分多样化。
**与Gurobi和DpSweeper的实证比较**：ILS启发式在所有指标上均优于Gurobi和DpSweeper，包括平均偏差、中位偏差、最大偏差、找到最优解数量和5%偏差内解数量。与DpSweeper相比，小实例上ILS将路径长度减少28%、航向变化次数减少19%；中等实例上分别改进15%和26%；大实例上分别改进9%和42%。Wilcoxon符号秩检验在α=0.05显著性水平下，对所有实例规模和两个指标均拒绝ILS与DpSweeper及Gurobi(DpS)平均偏差相同的零假设（p < 0.001），结论为ILS启发式支配DpSweeper和Gurobi(DpS)。
**讨论与结论**
研究人员解决了异构传感能力下机器人在感兴趣区域内规划覆盖路径的问题，该设定源于MCM作业。通过建立CPPIED与车辆路径问题之间的联系，表明高效的路径启发式可适配此类覆盖路径规划问题。所提出的ILS启发式专门针对CPPIED的组合结构设计。尽管ILS已广泛用于大规模车辆路径问题，但其在覆盖路径规划中的应用仍然有限。计算实验与统计分析表明，所提出的启发式在所有基准实例上一致产生比DpSweeper更短的覆盖路径。此外，研究人员引入了CPPIED的字典序双目标整数线性规划公式化，从而能够利用Gurobi求解器。结果表明，所提出的ILS启发式在基准上表现最佳，凸显了运筹学社区开发的方法在解决移动机器人覆盖路径规划问题方面的相关性。移动机器人中的最优覆盖仍是一个具有挑战性的问题，涉及传感、感知、运动建模和通信等多个系统的联合优化，通常面临显著的不确定性和动态环境条件。CPPIED公式化特别解决了传感器能力在感兴趣区域内变化的实际现实。本工作开发的启发式可集成到MCM规划系统中以减少预期任务完成时间。更广泛地说，通过高效的启发式和建模策略来解决带空间覆盖约束的车辆路径问题，似乎是推进移动机器人覆盖问题求解方法的一个有前景的方向。将CPPIED扩展到在线路径规划也是未来研究的一个有前景的方向，此类扩展可涉及仿真与优化，从而能够量化导航误差与推荐路径复杂度之间的关系。
