工程管理背景下的无人机巡检路径调度优化

镇璐 ,  杨志远 ,  Gilbert Laporte ,  伊文 ,  范天一

工程（英文） ›› 2024, Vol. 36 ›› Issue (5) : 239 -257.

PDF (3070KB)
工程（英文） ›› 2024, Vol. 36 ›› Issue (5) : 239 -257. DOI: 10.1016/j.eng.2023.10.014
研究论文

工程管理背景下的无人机巡检路径调度优化

作者信息 +

Unmanned Aerial Vehicle Inspection Routing and Scheduling for Engineering Management

Author information +
文章历史 +
PDF (3142K)

摘要

无人机（UAV）技术的蓬勃发展革新了各个领域的业态模式，使基于无人机的各类解决方案得以广泛应用。而在工程管理领域当中，基于无人机的巡检监测相较于传统的人工巡检方式有着巨大的优势，能够以较低的风险去高效识别高风险施工环境中的潜在隐患。在此背景下，本文研究了工程领域背景下的无人机巡检路径调度优化问题，在该问题中本文考虑了无人机飞行禁飞区、监测时间间隔以及多轮次巡检路径调度等因素。为高效求解该优化问题，本文提出了一种混合整数线性规划（MILP）模型用于优化无人机巡检任务分配、监测点巡检顺序调度以及无人机充电的三类决策。对上述三类复杂因素的综合考虑使该巡检路径调度问题与传统的车辆调度问题（VRP）有着显著区别，同时模型的复杂程度也使得商业求解器难以在合理时间内高效求解上述模型。为此，本文基于变邻域搜索算法设计了定制化的元启发式算法来高效求解所提出的数学模型。大量的数值实验验证了本文设计算法的有效性，并证明了该算法在大规模算例和真实规模算例中的应用性。此外，本文还基于实际的工程项目开展了敏感性分析和案例研究，为工程管理人员在提高巡检工作效率方面提供了相关管理启示。

Abstract

Technological advancements in unmanned aerial vehicles (UAVs) have revolutionized various industries, enabling the widespread adoption of UAV-based solutions. In engineering management, UAV-based inspection has emerged as a highly efficient method for identifying hidden risks in high-risk construction environments, surpassing traditional inspection techniques. Building on this foundation, this paper delves into the optimization of UAV inspection routing and scheduling, addressing the complexity introduced by factors such as no-fly zones, monitoring-interval time windows, and multiple monitoring rounds. To tackle this challenging problem, we propose a mixed-integer linear programming (MILP) model that optimizes inspection task assignments, monitoring sequence schedules, and charging decisions. The comprehensive consideration of these factors differentiates our problem from conventional vehicle routing problem (VRP), leading to a mathematically intractable model for commercial solvers in the case of large-scale instances. To overcome this limitation, we design a tailored variable neighborhood search (VNS) metaheuristic, customizing the algorithm to efficiently solve our model. Extensive numerical experiments are conducted to validate the efficacy of our proposed algorithm, demonstrating its scalability for both large-scale and real-scale instances. Sensitivity experiments and a case study based on an actual engineering project are also conducted, providing valuable insights for engineering managers to enhance inspection work efficiency.

关键词

工程管理 / 无人机 / 巡检路径调度优化 / 混合整数线性规划模型 / 变邻域元启发式算法

Key words

工程管理 / 无人机 / 巡检路径调度优化 / 混合整数线性规划模型 / 变邻域元启发式算法 / Engineering management / Unmanned aerial vehicle / Inspection routing and scheduling optimization / Mixed-integer linear programming model / Variable neighborhood search metaheuristic

引用本文

引用格式 ▾
镇璐,杨志远,Gilbert Laporte,伊文,范天一. 工程管理背景下的无人机巡检路径调度优化[J]. 工程（英文）, 2024, 36(5): 239-257 DOI:10.1016/j.eng.2023.10.014

登录浏览全文

4963

注册一个新账户 忘记密码

1 引言

随着无人机（UAV）遥感技术的进步，无人机最近已被广泛应用于多个领域，如包裹配送[1‒3]、军事侦察[4‒5]、灾后救援[6]、交通监控[7]、建筑项目质量检查[8‒9]以及医疗援助[10]。无人机通常体积小、机动性高且成本低，非常适合用于巡检和监控任务。更重要的是，使用无人机执行此类任务不仅能够大大减少劳动力投入，还能避免人工巡检过程中固有的一些风险。然而，尽管执行巡检检测任务的无人机路线调度优化问题在各个领域已进行了广泛研究[11‒14]，但在工程管理领域，尤其是工程建设中的大型项目，有关无人机基础巡检方面的研究却很少。本文开发了一种新方法来研究工程项目中无人机的巡检和监控模式的优化，旨在提高工程管理的质量和效率。

在工程建设中，管理者通常需要在特定的建设区域内执行多轮检查任务，以动态筛选出任何可能导致重大事故的潜在危险，如未锁的围栏、混凝土裂缝或可能坠落的物体。然而，传统工程领域采用的人工检查方法可能导致高劳动力成本、低检查效率和巡检信息反馈延迟。此外，在设施复杂或地形复杂的区域执行检查任务对巡检人员来说可能是危险的。但使用无人机进行检查则能够有效地克服上述问题，因为无人机是一种非接触解决方案[15]。此外，使用无人机进行检查不仅能在短时间内收集监控现场的实时图像，还能将信息上传到云平台进行历史存档。最重要的是，为了满足定期检查的需求，管理者可以使用无人机重复访问监控现场，而不必亲自执行巡检作业，有效防止执行检查任务的管理者处于危险之中。

尽管在工程项目中基于无人机的巡检效率很高，但无人机电池的限制要求管理者考虑多种因素来规划无人机的科学巡检路线。首先，鉴于建设项目所需巡检范围的广泛性，单一无人机仅凭一块电池难以完成全部巡检任务。因此，必须考虑多种类型的无人机及其充电需求的调度。其次，建设环境的动态变化要求无人机必须进行多轮巡检任务，以挖掘潜在的施工风险。因此，科学的无人机巡检路线必须确保无人机在电量耗尽前能返回充电站，同时确保所有监测点在规定的时间（如一天）内被多轮次地进行监控。第三，为了防止无人机与工程设施发生碰撞，需要设立禁飞区，以限制无人机从一个监控点到另一个点的路线可访问性。上述所有因素对于无人机的巡检路线规划和调度都施加了重大限制，这使得此类规划与传统领域（如物流和递送服务）中遇到的经典车辆路径问题（VRP）大相径庭。在传统的VRP场景中，无人机通常需要在已知时间窗口内访问每个客户点一次，而客户点之间不存在网络不可访问的情况。然而，在我们研究的背景下，无人机需要在周期性时间窗口内对特定监控点进行多次访问。此外，由于建筑结构和大型设备的存在，不同监控点之间的直接访问可能受阻，同时还必须考虑无人机充电位置的决策。这些复杂性使得工程应用中无人机巡检的路径规划比在其他领域遇到的标准无人机路径规划问题要复杂得多。因此，即使对于小规模问题也难以获得最优解，更不用说通过经验方法找到实际规模工程项目的最优解了。这一区别凸显了工程领域中无人机路线规划的独特性和必要性，将其与其他领域的无人机路线问题区分开来。

在这一背景下，本文探讨了工程项目中应用基于无人机的巡检，考虑了无人机的巡检路线和调度优化。本文构建了相应的数学模型和定制算法，用于规划无人机巡检路线，以便在工程项目中识别潜在风险。与针对目标监视或包裹配送的经典车辆路径问题不同，工程项目的无人机巡检路线要求每个无人机多轮次地访问监控站点。因此，给定站点的连续巡检任务需要通过时间窗进行分隔。此外，构建地数学模型需要考虑电池限制和禁飞区在规划实际巡检路线中的限制。由于需要综合考虑上述因素和限制，因此必须对无人机的监控任务分配和监控序列调度做出复杂的决策。

本文的主要科学贡献如下：制定了一个混合整数线性规划（MILP）模型，以考虑周期性巡检需求以及充电和禁飞区约束，确定异质无人机的巡检路线和调度；由于该模型太过复杂，仅能通过使用商业求解器解决小规模实例，因此设计了一种基于变邻域搜索（VNS）的定制算法来求解这一复杂模型；进行了数值实验以确认模型的有效性和算法的效率，并进行了模型的灵敏度分析，为工程管理者提供了关于巡检任务的见解；以世界级工程项目——狮子洋大桥项目作为实际案例，展示了所设计的数学模型和定制算法在实际工程项目的巡检工作中的应用。

本文剩余部分安排如下：第2节回顾了相关的文献；第3节详细阐述了在大型桥梁项目中巡检路线和调度优化的问题背景；第4节和第5节分别描述了数学模型和定制算法；第6节分析了实验结果；第7节介绍了以狮子洋大桥为背景的案例研究，最后一节概述了结论。

2 相关文献

近年来，许多文章研究了无人机在各个领域的应用，这些领域涵盖了无人机技术框架[16‒19]和无人机运营研究[6,20‒21]的多个视角。本节在此基础上回顾了三个研究领域：第一个领域涉及无人机的应用领域和相应能完成的任务；第二个领域包括无人机路线和调度的优化；第三个领域涵盖了由无人机执行的巡检和监控任务的优化。

第一个研究领域专注于无人机的应用领域和任务。分配给无人机的任务可分为应急管理、工业产品或包裹配送、实时监控和巡逻任务，以及军事作战任务。Chowdhury等[11]研究了无人机在灾后管理中的巡检路线优化，并开发了一个MILP模型，以最小化灾区巡检成本。Khan等[10]讨论了无人机在高效率配送急救和医疗用品中的重要作用，并展示了无人机在医疗救援响应中的价值。关于包裹配送的研究主要集中在卡车和无人机的协同配送调度上[2,22‒23]。根据学者们提供的调度解决方案，采用卡车和无人机的协同配送模式已经很好地解决了末端配送问题。Shen等[13]进行了关于无人机在监控船舶空气排放中应用的开创性研究，联合优化了船舶部署多无人机在监测船舶排污中的路线和调度决策。Rajan等[24]采用了两阶段随机规划方法来优化无人机在巡逻任务背景下的路线问题，揭示了无人机在信息收集中的价值。此外，Li等[7]研究了多周期实时监控道路交通的无人机调度问题，其中使用配备不同成像传感器的无人机来捕获道路交通的多周期目标图像，并构建了一个MILP模型，以最小化无人机的运营成本。在军事作战任务领域，无人机通常执行目标监视和侦察任务，它们从基地出发，前往目标收集信息，同时受到电力限制。Liu等[12]设计了一个混合优化框架，其中侦察任务规划问题被分解为目标选择子问题和路径规划子问题。学者们分别采用进化算法和深度强化学习方法解决目标选择子问题和路径规划子问题。尽管无人机已广泛应用于医疗、物流、城市管理和军事领域，但关于将无人机应用于工程领域，特别是探索无人机在工程管理中的价值的讨论却很少。因此，本文探讨了工程项目中无人机路线和调度问题。

第二个领域涉及无人机路线和调度问题的优化研究。大多数无人机路线和调度问题可以视为经典VRP或旅行商问题（TSP）的变体。然而，与VRP和TSP中的决策相比，各种场景中的不同目标在无人机的路线和调度规划中的决策差异很大。Xia等[20]研究了一队无人机在给定任务时间窗口内从敌方领土的一组区域收集信息的路线规划，优化目标是最大化由舰队收集的总预期奖励。同样，Xu等[25]研究了复杂对抗环境中多无人机协同路线规划，并开发了一个多约束目标优化模型，以确保每架无人机迅速到达任务区域，减少被捕获和摧毁的可能性。其他研究[26‒27]在军事领域考虑了无人机和车辆（移动充电车辆或巡检辅助车辆）的联合路线和调度规划。Zhen等[28]制定了一个整数规划模型，通过采用无人机监测一组具有不同准确性要求的区域，最小化完成监控任务的总时间，从而优化监控的路线和调度。Wang等[29]研究了无人值守海上石油平台的无人机监控路线问题，并建立了一个以最短飞行路径和最小校正次数为目标的多目标数学模型。物流递送领域涉及多种异构无人机的调度[21,30]以及无人机和卡车的联合路线和调度规划[23,31]，其主要优化目标是客户等待时间之和、无人机行驶的总距离、无人机的总递送时间和协同递送的总成本。在工程管理领域，无人机在执行巡检和监控任务中具有显著优势。类似于上述无人机的应用，工程项目中无人机的路线和调度必须考虑电池和充电站的限制、多种异构无人机的复杂性以及监控区域的集合。此外，必须为收集每个监控站点的图像规划巡检路线，在一定间隔内进行多轮收集，并考虑地形障碍（如建设设施）使路线不可达。然而，目前尚没有研究全面考虑了上述因素以及现实决策需求，因此在工程项目中的无人机巡检路线和调度决策制定中缺乏参考。

最后一个领域回顾了涉及巡检和监控任务的优化工作。Huang等[32]调查了桥梁巡检路线问题。与传统的VRP不同，桥梁巡检问题还必须考虑巡检团队的过夜住宿选择，因为访问的桥梁分布在广阔的地理区域。因此，巡检路线不仅需要确定访问桥梁的顺序，还要选择住宿地点。Zhen等[33]研究了煤矿安全人员在地下矿井中的巡检路线问题，该问题被定义为带时间窗口的多仓库VRP。在MILP模型中考虑了任务和工作量平衡、多个检查员-车辆对接站点以及巡检任务的时间窗口。类似于巡检任务，巡逻任务[24]的路线优化可以是VRP的一个新变种。区别在于，当无人机收集的信息不完整时，巡逻任务必须在初始路线中访问一组目标，然后在调整路线中访问一组额外的目标。至于监控任务，相关的优化研究[7,13,28]通常致力于最小化完成任务的总监控时间。无人机的信息存储能力、对监控站点或区域的特定监控要求以及无人机的电力限制是这些研究的数学模型中考虑的主要因素。然而，关于在固定时间窗口内以间隔检查每个监控站点的路线问题的优化研究很少。此外，与无人机飞行路径不受建设阻碍的环境不同，工程建设现场存在许多障碍。因此，禁飞区是一个需要在确定工程项目中无人机巡检路线时考虑的新约束因素。

为了清晰地展示，表1 [2,7,10‒13,20‒26,28,30,32]根据问题背景、考虑因素和采用的解决方案对上述研究进行了分类。与当前关于无人机路线和调度问题的运营研究相比，本文采用了新的视角来探索工程管理领域中无人机巡检路线问题，并在数学模型中全面考虑了充电决策、定期监控的需求和禁飞区约束。尽管在工程建设中无人机巡检和监控任务的目标识别和图像收集技术已经相当成熟[15,34]，但在这一特定领域中，缺乏专门针对无人机巡检路线和调度优化的研究。因此，本文通过提出一个解决工程项目中无人机巡检路线和调度问题的实用方法，填补了这一研究空白。

3 问题描述

3.1 问题背景

考虑在重大工程项目的建筑区域中，有一组需要被多轮巡检的监控点。当前有一支性能各异的无人机编队（不同的飞行速度、电池容量和充电时间）被要求以一定的时间间隔访问每个站点，收集图像以协助工程管理者筛查建筑环境中的潜在施工风险。因此，工程管理者需要为每架无人机分配巡检任务，并规划访问不同监控点的飞行路线。首先，巡检路线应确保在规划期限（如一天）内，每个监控点都由无人机在一定时间间隔内被多次访问。其次，巡检路线应确保无人机能在电源耗尽前返回附近的充电站进行充电。最后，巡检路线应防止无人机与建筑设施相撞。因此，存在我们假定了某些飞行路线不可达的禁飞区。此外，为了简化问题，本文仅考虑了二维的无人机路线规划问题，因此无人机的飞行高度大致保持恒定。

图1描述了两架无人机执行巡检任务的过程，其中两架无人机负责监控一个施工区域内的四个监测点。其中两个站点至少需要进行三轮巡检，另外两个监测点至少需要进行两轮巡检。无人机在每个监控点收集的图像会实时上传至云平台。然后，负责巡检任务的管理者将巡检结果记录在日志中（如图所示的底部），以追踪区域的建筑安全。如果在监控点检测到潜在风险，管理者将立即向现场主管发出警告，并指导他们检查情况并采取措施消除潜在风险。因此，基于无人机的巡检不仅减少了大范围巡逻的人工成本，而且通过巡检路线的优化，高效且动态地发现了工程项目的潜在风险。

此外，图1直观地展示了一个多轮次无人机巡检路径规划问题，该问题涉及充电决策和禁飞区的存在。以1号无人机为例，访问监控点I1和I4后，无人机首先前往充电站C1补充电池。随后，1号无人机执行第二轮在点I1和I4的巡检，然后前往充电站C2进行充电。最后，在完成I2监测点第三轮的监控任务后，返回起点。在传统的VRP问题中，可能只需要规划无人机一次访问监控点I1、I4和I2的路线。然而，在本文研究的问题中，由于以下因素，规划无人机巡检路线的难度显著增加：①无人机路线规划涉及对单个监控点的多次访问，且后续访问的时间窗口取决于前次访问的时间。例如，如果第一次访问I1发生在8:05，第二次访问应在时间窗口[8:25, 8:55]内进行，以监测该点的动态变化情况，以此类推。②不同监控点之间存在禁飞区，需要对无人机巡检任务进行合理分配和访问路线规划。例如，在C2充电后，1号无人机不能直接访问I3，而只能选择I2或I1。③考虑到上述因素，无人机只能在其充电期间在可达的充电站充电。同时，飞行时间和充电时间不能影响下一次巡检任务的时间窗口要求，使得充电决策同样复杂和具有挑战性。图1仅展示了两架无人机在三轮巡检任务中访问四个监控点的示例，当前路线的复杂性凸显了为多架异构无人机规划访问数十个监控点的大规模问题的难度。

鉴于上述问题背景，工程管理者的目标是确定异构无人机组的巡检路线，以最小化完成多轮巡检任务的总工作时间。通过聚焦最小化总时间，本研究旨在满足工程管理中无人机的巡检路线规划及高效率调度的关键需求。实现此目标有助于优化建筑项目的效率、降低成本并确保项目按时完成，与更广泛的目标相吻合。在这一决策问题中，面临的挑战包括：①电池的限制要求无人机必须在巡检期间返回充电站进行充电，增加了路线规划的复杂性；②禁飞区限制飞行路线的可达性，使得巡检任务的分配和路线的规划更加复杂；③多轮监控的需求和时间间隔要求需要对每个监控站点的巡检序列及其时间进行精确调度，进一步增加了路线和调度决策的复杂性。一个理想的解决方案应全面考虑以上挑战并安排访问每个监控站点的最佳序列，以最大限度地减少无人机充电和等待时间。此外，考虑到禁飞区可能导致的绕路，从而延长巡检时间，理想的解决方案还应确保无人机总是能通过最短路线从一个站点飞往下一个站点（包括充电站）。

3.2 研究假设

在提出第4节的数学模型之前，本文的研究假设如下：

（1）每架无人机在近似恒定的高度执行监测任务，因此，暂不考虑无人机在垂直方向上的飞行。

（2）所有无人机都从唯一的起点出发去执行各自的巡检监测任务，只有在完成所有巡检任务后才返回至指定的目的地。

（3）每个监测点的巡检要求均为已知信息，例如相邻两轮的监测时间间隔、在每个监测点执行巡检作业的时间以及所需要的巡检轮次。

（4）任意监测点之间的飞行距离和异构无人机的各类性能指标均为已知参数，因为它们是确定性参数。

4 数学模型

为刻画工程项目中的无人机巡检路径调度问题，本文构建了一个MILP模型，其目标为最小化所有无人机完成指定巡检任务的总时间，包括无人机的飞行时间、等待时间、在监测点开展监测作业的时间以及充电时间。与传统运输调度问题中的处理方式类似，本文构建的MILP模型中将不同的监测点视为一个无向拓扑图中的各个节点，其中每个节点和其他节点均为直达连接，且连接权重为已知参数。唯一不同的是，本文的模型在拓扑图中考虑了实际工程中的禁空区阻碍，因此无人机能够从一个节点直达另一个节点的前提是两个节点之间不存在禁飞区。此外，无人机在一个监测点开展监测作业的飞行路径本文暂不考虑，不纳入目标函数的考量体系中。

4.1 模型符号

本文模型中所使用的集合、参数以及决策变量定义如表2所示。为方便下文描述，本文分别使用罗马字母和希腊字母来表示参数和决策变量。

4.2 模型构建

基于表2所示的模型参数和决策变量，我们构建了如下的混合整数规划模型。

M 0 M i n i m i z e ∑ k ∈ K π k

subject to:

∑ k ∈ K α k , i , l = 1             ∀ i ∈ I , l ∈ Q i
∑ j ∈ I ⋃ e ˙ ∑ l ' ∈ Q j β k , i , l , j , l ' = α k , i , l = ∑ j ∈ I ⋃ e ∑ l ' ∈ Q j β k , j , l ' , i , l ∀ k ∈ K , i ∈ I , l ∈ Q i
∑ b ∈ B φ k , i , l , b ≤ ∑ j ∈ I ⋃ e ˙ ∑ l ' ∈ Q j β k , i , l , j , l ' ∀ k ∈ K , i ∈ I , l ∈ Q i
∑ j ∈ I ⋃ e ˙ ∑ l ' ∈ Q j β k , e , l , j , l ' = 1                    ∀ k ∈ K , l ∈ Q e
∑ j ∈ I ⋃ e ∑ l ∈ Q j β k , i , l , e ˙ , l ' = 1                    ∀ k ∈ K , l ' ∈ Q e ˙
β k , i , l , j , l ' ≤ f i , j 1 + M ∑ b ∈ B φ k , i , l , b ∀ k ∈ K , i ∈ I ⋃ e , j ∈ I ⋃ e ˙ , l ∈ Q i , l ' ∈ Q j
β k , i , l , j , l ' ≤ f i , b 2 + M 1 - φ k , i , l , b ∀ k ∈ K , i ∈ I ⋃ e , j ∈ I ⋃ e ˙ , l ∈ Q i , l ' ∈ Q j
β k , i , l , j , l ' ≤ f j , b 2 + M 1 - φ k , i , l , b ∀ k ∈ K , i ∈ I ⋃ e , j ∈ I ⋃ e ˙ , l ∈ Q i , l ' ∈ Q j
λ k , i , l + t k , i + d i , j 1 v k ≤ λ k , j , l ' + M 1 - β k , i , l , j , l ' ∀ k ∈ K , i ∈ I ⋃ e , j ∈ I ⋃ e ˙ , l ∈ Q i , l ' ∈ Q j
λ k , i , l + t k , i + d i , b 2 v k + r k - θ k , i , l + h k d i , b 2 c k + d b , j 2 v k ≤ λ k , j , l ' + M 2 - φ k , i , l , b - β k , i , l , j , l ' ∀ k ∈ K , i ∈ I ⋃ e , b ∈ B , j ∈ I ⋃ e ˙ , l ∈ Q i , l ' ∈ Q j
λ k ' , i , l + 1 ≥ λ k , i , l + t k , i + m i - M 2 - α k , i , l - a k ' , i , l + 1 ∀ k , k ' ∈ K , i ∈ I , l ∈ Q i / | Q i |
λ k ' , i , l + 1 ≤ λ k , i , l + t k , i + n i + M 2 - α k , i , l - a k ' , i , l + 1 ∀ k , k ' ∈ K , i ∈ I , l ∈ Q i / | Q i |
θ k , j , l ' ≤ θ k , i , l - g k , i - h k d i , j 1 + M ∑ b ∈ B φ k , i , l , b + 1 - β k , i , l , j , l ' ∀ k ∈ K , i ∈ I ⋃ e , j ∈ I ⋃ e ˙ , l ∈ Q i , l ' ∈ Q j
θ k , j , l ' ≥ θ k , i , l - g k , i - h k d i , j 1 - M ∑ b ∈ B φ k , i , l , b + 1 - β k , i , l , j , l ' ∀ k ∈ K , i ∈ I ⋃ e , j ∈ I ⋃ e ˙ , l ∈ Q i , l ' ∈ Q j
θ k , j , l ' ≥ r k - h k d j , b 2 - M 2 - φ k , i , l , b - β k , i , l , j , l ' ∀ k ∈ K , i ∈ I ⋃ e , b ∈ B , j ∈ I ⋃ e ˙ , l ∈ Q i , l ' ∈ Q j
θ k , j , l ' ≤ r k - h k d j , b 2 + M 2 - φ k , i , l , b - β k , i , l , j , l ' ∀ k ∈ K , i ∈ I ⋃ e , b ∈ B , j ∈ I ⋃ e ˙ , l ∈ Q i , l ' ∈ Q j
θ k , i , l ≥ g k , i + h k m i n   m i n b ∈ B d i , b 2 , d i , e ˙ 1 - M 1 - α k , i , l ∀ k ∈ K , i ∈ I , l ∈ Q i
π k = λ k , e ˙ , 0 - λ k , e , 0                   ∀ k ∈ K
α k , i , l ∈ 0,1                   ∀ k ∈ K , i ∈ I ⋃ e , e ˙ , l ∈ Q i
β k , i , l , j , l ' ∈ 0,1 ∀ k ∈ K , i ∈ I ⋃ e , j ∈ I ⋃ e ˙ , l ∈ Q i , l ' ∈ Q j
φ k , i , l , b ∈ 0,1           ∀ k ∈ K , i ∈ I ⋃ e , b ∈ B , l ∈ Q i
0 ≤ λ k , i , l ≤ T           ∀ k ∈ K , i ∈ I ⋃ e , e ˙ , l ∈ Q i
0 ≤ θ k , i , l ≤ r k           ∀ k ∈ K , i ∈ I ⋃ B ⋃ e , e ˙ , l ∈ Q i
0 ≤ π k ≤ T                    ∀ k ∈ K

目标函数（1）旨在最小化所有无人机完成多轮次巡检任务的总时间，包括无人机的飞行时间、等待时间、在监测点开展监测作业的时间以及充电时间；约束（2）保证了每个监测点每次巡检任务总是分配给唯一的无人机执行；约束（3）保证了无人机巡检路径的流平衡；约束（4）保证了每台无人机总是在执行完某个监测点的某轮巡检任务后，才会前往充电站充电，即不会存在从一个充电站直接到另一个充电站的路由；约束（5）和约束（6）保证了每台无人机总是从指定的起点出发，在完成所有巡检任务后，回到指定的终点；约束（7）保证了当监测点 i和监测点 j存在禁飞区时，无人机 k将无法直接从监测点 i前往监测点 j。约束（8）和约束（9）保证了当监测点 i和监测点 b或监测点 j和监测点 b之间存在禁飞区时，无人机 k将无法从监测点 i前往充电站 b充电后再飞往监测点 j执行巡检任务。约束（10）和约束（11）计算了无人机在不同监测点开始执行任务的时间。约束（12）和约束（13）确保了每个监测点相邻两轮巡检任务的间隔时间不小于最小时间间隔，也不大于最大时间间隔要求。约束（14）和约束（15）为无人机从一个监测点飞向另一个监测点过程中的电量守恒约束。约束（16）和约束（17）为无人机从一个充电站前往下一个监测点过程中的电量守恒约束。约束（18）确保了每台无人机总是有足够的电能支持其从当前节点飞向最近的充电站或临近的监测点。约束（19）基于每台无人机完成其所有巡检任务时间，计算了最终无人机巡检调度方案的总作业时间。约束（20）~（25）定义了决策变量的范围。

5 算法设计

众所周知，经典的VRP问题是一个NP难问题。而第四节构建的数学模型，在基础的VRP问题框架下还综合考虑了无人机的充电决策、禁飞区约束以及多轮次巡检监测时间窗因素，这使得原模型M0，即便在小规模算例下，也较难在合理时间内被CPLEX等商业求解器直接求解。因此，本文基于VNS设计定制化的元启发式算法来高效求解提出的数学模型。VNS算法的优势在于能够高效地探索不同的解空间，避免过早地收敛到局部最优，并通过不断迭代来提高解的质量。这使得VNS特别适合解决NP难类型的优化问题。

5.1 算法框架

本文研究的问题可以划分为三类子问题，第一个子问题聚焦于解决巡检任务的分配（如 α k , i , l），第二个子问题决策每台无人机执行各自巡检任务的先后顺序（如 β k , i , l , j , l '），第三个子问题则关注无人机完成某个巡检任务后在何处充电的决策问题（如 φ k , i , l , b）。由于这三类子问题相互关联，因此当巡检任务分配方案不够合理时，极有可能导致与巡检时间窗相关的约束（12）和约束（13）无法满足；而通过局部贪婪思想得到的调度方案，也有可能会造成一架无人机的充电流平衡约束无法被满足，即出现无人机在完成某个巡检任务后无法凭借剩余电量前往最近的充电站。因此，生成一个可行的初始解对于求解原模型至关重要。此外，算法还需要设计高效的邻域搜索策略来不断通过邻域搜索迭代找到全局更优的解，从而尽可能收敛到全局最优解。最后，无人机的充电决策同样应当从全局角度进行优化，从而能够有效地评估巡检方案的优劣。

为解决上述算法设计过程中存在的挑战和难题，本文基于VNS算法设计的元启发式算法框架如下所示。

步骤1：初始化原模型M0的可行解。

步骤1.1：通过迭代求解模型 M 1 _ n来获得原模型的一个可行解。

步骤1.2：定义最优的巡检计划为 I P *以及最优的目标函数值为 F ( I P * )，并定义局部最优巡检计划 I P '。

步骤2：重复下述步骤，直到满足迭代停止条件。

步骤2.1：基于 I P '进行变邻域下降（VND）来获得一个新解 I P ̃。

步骤2.2：通过求解模型 M 2评估当前的新解 I P ̃，并得到一个新的目标函数值 F ( I P ̃ )。

步骤2.3：若 F ( I P ̃ ) -   F ( I P * ) < 0，定义 I P *= I P ' = I P ̃ 以及 F ( I P * ) =   F ( I P ̃ )。

步骤2.4：通过解的扰动策略生成一个新的可行解 I P .，并设置 I P ̃ = I P .。

步骤3：输出最优的全局最优巡检方案 I P *以及其对应的目标函数值 F ( I P * )。

上述算法的迭代停止条件如下：①邻域搜索的迭代总次数超过某个阈值；② F ( I P * )在指定迭代次数下没有改进。

5.2 初始解生成策略

在本文研究中，制定无人机巡检监测方案综合考虑了多轮次时间间隔、无人机电量限制以及禁飞区因素，在该问题背景下，仅考虑局部最优的启发式策略得到的巡检方案往往难以平衡充电约束和监控时间间隔约束之间的冲突。此外，本文研究的巡检监测路线调度问题相较于经典的充电车辆调度问题（EVRP）以及带时间窗的充电车辆调度问题（EVRPTW）更为复杂，CPLEX等商业求解器较难在合理时间求出原问题的可行解（将在第6.2节的实验中予以证明）。面对该难题，本文采用了一种“滚动时域优化”的算法思想来得到原模型的一个可行解。该算法的核心思想在于以“滚动、分批、迭代”的方式挨个求解每一轮巡检监测任务的分配和访问顺序方案。该算法求解原问题的实现过程如图2所示。为方便下文阐述，本文将第 i个监测点的第 j轮巡检任务表示为 i - j。

每一次迭代都将求解一个子模型 M 1 _ n ( n = 1 ,   .   . .   , m a x i ∈ I   { Q i })，该子模型的详细内容见附录A中的第S1节和图S1。模型 M 1 _ n与原模型 M 0非常相似，但唯一不同是，该模型每次求解时只需要决策包含一轮监测需求的无人机巡检路线方案。在第一次迭代时（求解模型 M 1 _ 1），该模型可以等价为一个经典的EVRP问题，而在后续的迭代过程中则可以视为EVRPTW问题 （求解模型 M 1 _ 2至 M 1 _ n）。通过这种方式求解原模型，商业求解器尽管不能在短时间内获得原问题的最优解，但可以在合理时间内获得原问题的一个可行解，从而作为初始解开展后续的邻域迭代。

5.3 邻域搜索策略

在开展带扰动操作的邻域搜索时，本文结合问题特征，设计了多种不同的邻域结构，以便充分探索原问题的解空间。下文分别展示了四类不同的邻域搜索策略。这些邻域搜索策略主要启发于多轮监测的问题特征以及禁飞区限制因素。由于原问题考虑了无人机巡检路线可达性限制因素，因此在搜索一个新解时，可直接通过检验该新解是否满足约束（7）~（9）来判断该巡检方案的无人机飞行路线是否为一个可行方案，并在解不可行情况下重新搜索新的邻域解直至找到满足约束（7）~（9）的可行解。在邻域搜索的过程中，本文设置了全局的禁忌搜索列表用于存储不可行的邻域搜索和新生成的解决方案，以避免重复搜索的需要。

5.3.1 邻域搜索策略1：交换监测任务

策略1旨在通过交换两个监测任务的相关决策结果来改变原有的巡检方案。这种策略可以改变任意两个监测任务的分配或监测顺序，从而获得改进的巡检方案。图3展示了采用策略1来搜索新解的两种场景。第一种场景下，策略1改变了原始解中 α k , i , l以及 β k , i , l , j , l '的部分结果。而在第二种场景下，策略1仅改变了原始解中 β k , i , l , j , l '的部分结果。具体而言，以场景1为例，在原始解中， α 2,5 , 1、 α 1,3 , 2、 β 2,5 , 1,4 , 2以及 β 1,1 , 2,3 , 2均等于1，而在执行策略1后，上述决策变量的值均等于0。相应地， α 1,5 , 1、 α 2,3 , 2、 β 2,3 , 2,4 , 2以及 β 1,1 , 2,5 , 1的值则等于1。

5.3.2 邻域搜索策略2：插入监测任务

策略1在交换监测任务后，每台无人机的监测任务总数总是恒定的。而策略2旨在通过插入操作来改变分配给不同无人机的监测任务数量。由于本文考虑了异质无人机组的调度分配问题，因此电池容量更大的无人机相较于电池容量较小的无人机，在相同的作业周期内极有可能完成更多的巡检任务，故通过改变不同无人机监测任务的分配数量能够有助于找到更优的解。此外，策略2同样也可通过插入操作来改变无人机访问监测点的顺序，这同样可能让巡检路线相较于改变之前更优。上述两类场景分别在图4中进行了说明。当执行策略2时，我们随机选择已分配给某架无人机的某一个监测任务，并将其插入到该无人机访问序列中的其他位置或插入到另一架无人机的任意位置，从而生成新的巡检调度方案，上述两类情况分别如图4中左、右两种场景所展示。决策变量 α k , i , l 以及 β k , i , l , j , l '在上述过程中的变换规律与附录A中的第5.3.1节描述类似。

5.3.3 邻域搜索策略3：插入监测轮次的任务

策略3与策略2类似，但不同的是，该策略旨在将某一架无人机的某一轮的部分巡检任务插入到另一架无人机的合适位置，从而来改变原始的巡检任务分配以及监测顺序方案。本文定义了监测间隔时间窗 [ n i , m i ]来表示相邻两次访问同一监测点的最小和最大间隔时间。因此最优的巡检方案应当确保每架无人机尽可能连续地执行巡检作业，即无人机在执行完一轮监测任务后开始执行下一轮监测任务之前的等待时间尽可能少。因此，策略3将随机选择一架无人机的某一轮监测任务，并将其中的部分监测任务重新分配给另一架无人机。具体的邻域搜索解如图5所示。在初始解的方案中，监测任务3‒2、4‒2和2‒2分配给1号无人机，并在任务1‒2之后执行。在通过策略3进行邻域搜索后，这些任务一起插入到了2号无人机开展巡检任务的开头。决策变量 α k , i , l 以及 β k , i , l , j , l '在上述过程中的变换规律与第5.3.1节描述类似。策略3有助于将某一轮次的部分监测任务分配给性能更好的无人机并通过分离属于不同轮次的监测任务来优化工作连续性，从而找到更优的巡检方案。

5.3.4 邻域搜索策略4：交换巡检路线

策略4旨在通过交换两架无人机的巡检路线来找到更优的巡检方案。由于本文考虑了异质无人机组的任务分配调度问题，因此性能较优的无人机相较于性能较弱的无人机，总是能够以更短的时间完成相同的巡检作业。图6展示了采用该搜索策略找到更优解的示例。在采用策略4生成新解时，仅有 α k , i , l会发生改变。同时需要注意的是，对于有 | K |架无人机的巡检调度问题，采用该策略至多生成 | K | ( | K | - 1 ) / 2种解，而当这些解都无法改进当前解或为非可行解时，本文将随机选择前三类搜索策略中的一种来替换本策略，以完成当次迭代。

5.4 VND框架

基于前文设计的邻域搜索策略，本文设计了一个VND框架来寻找更优的巡检方案（VND算法的伪代码在附录A中的第S2节中进行了展示）。首先，我们将随机选择某一种邻域搜索策略并基于给定的初始解得到一个新解。当采用该邻域策略未找到更优解后，则采用另一种邻域搜索策略得到新解。一旦在当前邻域中找到更好的解，则返回到第一个邻域中并重复上述搜索过程，直至满足迭代停止条件。

在邻域搜索的过程中，本文设计了一个简化的子模型 M 2，用于评估生成的新巡检方案的优劣，该模型在附录A中的第S3节进行了展示。模型 M 2和原模型 M 0的区别在于，在求解模型 M 2时，决策变量 α k , i , l以及 β k , i , l , j , l '均为已经确定的参数，因此 M 2中只剩下变量 φ k , i , l , b以及连续变量 λ k , i , l、   θ k , i , l和 π k，此时即便是在大规模算例下，该模型也可以被商业求解器在短时间内快速求解。当给定的巡检方案出现无解的情况，本文将该方案的目标函数值设置为 M，并继续执行邻域搜索来获得新解。

5.5 邻域扰动策略：重新生成原模型可行解

在邻域搜索的过程中，往往需要通过执行扰动策略来避免当前的解陷入局部最优。为此，本文基于图7所描述的启发式策略来得到原模型的一个初始解，以对迭代过程中的当前解进行扰动。该启发式策略获取原模型初始解的步骤如下：首先，我们将第一轮的监测任务以随机但分配任务数尽可能平均的方式将第一轮的监测任务分配给不同的无人机，从而固定决策变量 α k , i , 1。紧接着，我们通过求解附录A第S1节中给出的子模型 M 1 _ 1来生成第一轮监测任务的巡检方案。最后，我们采用5.2节描述的滚动优化算法，在给定第一轮各监测点巡检方案下生成后续轮次的巡检方案。

为更清楚地说明上述启发式规则中的“随机但平均”的任务分配策略，我们以一个包含 | K |架无人机与 | I |个监测点的巡检规划问题为例来说明上述策略。首先，我们将第一轮的| Q |（| Q | = | I | / | K |）个监测任务（如巡检任务1‒1、2‒1以及3‒1）按照无人机电量降序的顺序挨个循环地分配给每架无人机，直至第一轮中所有的监测任务都被分配给某一架无人机。通过上述启发式策略，决策变量 α k , i , 1可在求解前提前固定为参数。然而在该初步任务分配方案下，利用模型 M 1 _ n  ( n > 2)来求解后续轮次的监测任务分配方案时，可能会出现不可行的情况。因此我们随机地改变第一轮监测任务中分配给不同无人机的数量，即[ Q - τ, Q + τ]，其中 τ是一个整型参数，范围为[1, Q / 2]。最后，通过重复上述操作直至得到一个新的巡检方案，即完成邻域搜索过程中的扰动操作。

6 数值实验

为验证本文设计的元启发式算法的有效性，下文开展了大量的数值实验。此外，为了给工程项目管理者提供有价值的管理启示，本文还进了一系列的敏感性分析实验。本文所用实验平台的中央处理器（CPU）为Intel Xeon Gold 5218R、2.10 GHz，内存为32 GB，采用Windows 10 64位处理系统。程序在Visual Studio v2022中使用C#编程语言进行编译，并使用 CPLEX 12.6.1作为MILP求解器。考虑到实际项目在施工期间，每日的监测点可能会发生动态变化（即每天的监测点可能有所不同），因此实际案例中，决策无人机巡检路线调度方案有着较高的时效性。基于该现实需求，下文的模型求解时间均限制为3600 s。

6.1 参数生成设置

为验证算法的有效性，本文基于工程项目巡检的实际需求，生成了一系列无人机在执行相关巡检作业时的算例以仿真模拟实际的无人机巡检规划决策场景。在实际施工过程中，人工开展巡检作业通常会在早上或下午时段（如8~12点或14~17点之间），并且早晨或下午需要进行巡检的监测点也可能会发生变化。而基于无人机的巡检手段则是采用无人机组去识别不同施工区域内存在的潜在隐患。基于该现实背景，本文将决策的规划周期设定为4 h，即要求所有的无人机组必须在4 h内完成所有的巡检监测任务。关于监测点以及无人机充电站，本文将其设定为分布在一个100 m2的正方形区域中，任意两个节点之间的飞行距离采用欧式距离计算。关于无人机的性能参数，表3给出了本文实验中无人机参数设定（参考大疆公司的M300 RTK系列无人机性能指标[35]）。不同监测点的监测时间间隔设置为 [ 0.5 × T m a x i ∈ I   { Q i } , T m a x   { i ∈ I   Q i } ]，以满足无人机能够在整个规划周期内多轮次地访问不同的监测点，识别施工环境中的潜在隐患。禁飞区的数量影响着无人机的路线可达性，同时为了保证问题存在有解的情况，我们设定禁飞区存在于20%的飞行路径设定。

根据表3中给出的参数设定，我们生成了9组算例（ISG）来评估算法的求解效率。表4给出了不同实验组的关键参数设定，其中ISG1、ISG2和ISG3为小规模算例；ISG4、ISG5和ISG6为中规模算例；ISG7、ISG8 和 ISG9 则为大规模算例。

6.2 算法求解有效性验证

第一组实验包含ISG1~ISG3这三组小规模算例，我们将算法求解的结果和求解时间均与CPLEX求解器以及第5.2节阐述的初始解结果进行了对比，如表5所示。结果表明，CPLEX求解器仅能在3600 s内求出前两组小规模算例的原问题最优解，而本文设计的算法则均能够在30 s内获得与CPLEX一致的最优解。而在ISG3规模中，此时CPLEX已无法在3600 s内求出最优解，故本文将算法得到的结果与求解器在3600 s内得到的上界解进行对比。两者之间的平均gap值约为-16.85%，且算法求解的时间均小于120 s。这表明在ISG3算例下，相较于CPLEX求解器，本文设计的算法能够以更短的时间求得原问题更优的解。此外，三组实验中，算法与初始解之间的平均gap值分别为18.2%、17.56%以及23.85%。这表明第5.3节设计的邻域搜索策略有效地在初始解基础上搜索到了更优质的巡检方案，得到了更优的解。

第二组实验包含ISG4~ISG6这三组中规模算例。表6的实验结果显示，我们的算法在3600 s内得到的解要远优于CPLEX求解器所得到的解，两者的平均差值为-30.74%。而随着监测站点和监测轮数的增加，CPLEX已无法在3600 s内获得ISG5和ISG6的可行解，而本研究所设计的算法仍能在300 s内求解原模型。此外，该算法与初始解之间的平均gap值为19.21%，进一步证实了基于VNS的元启发式算法在探索全局更优解方面的优势。

第三组实验包含ISG7~ISG9这三组大规模算例。由于CPLEX已无法在合理时间内求出大规模算例下的原问题可行解，因此本文在此部分实验中仅将算法求解结果（即gap2）与初始解进行了对比（表7）。两者的gap值为21.32%，对初始解的优化效果要显著高于小规模实验（19.87%）和中规模实验（19.21%）。该结果证实了本文设计算法在不同规模算例下探索最优巡检方案的结果是稳健且有效的。而从求解效率来看，算法求解9组不同算例实验的计算时间远短于3600 s，表明本文设计的算法可以有效地帮助工程项目的管理者高效地制定工程施工过程中的无人机巡检监测路径方案。

6.3 敏感性分析实验

为给工程项目的管理者提供巡检监测方面的管理启示，下文开展了两类敏感性实验。第一小节研究了无人机数量对巡检时间的影响，第二小节则研究了无人机性能带来的影响。

6.3.1 无人机数量的敏感性分析

用于巡检监测的无人机数量很显然会影响总的巡检作业时间。使用过多的无人机去执行巡检作业可能会带来低效率的作业结果，譬如每架无人机只执行少量的巡检任务。而使用过少的无人机则又可能导致单架无人机需要执行较多的巡检任务而需要频繁地进行充电，从而导致无人机完成所有巡检任务的时间大大延长。因此，使用无人机开展巡检作业过程中，决定合适的无人机数量去执行待巡检任务至关重要。为探究上述因素对总作业时间的影响，本文在小规模算例下（ISG1、ISG2、ISG3）开展了敏感性实验。同时在实验过程中为了排除无人机性能（飞行速度、电量等因素）带来的干扰，我们设定实验中每架无人机的性能是同质的。图8展示了无人机数量对总作业时间的影响，结果表明，对于ISG1和ISG2问题规模下的巡检任务，两架无人机的效率最高。而对于ISG3问题规模下的巡检任务，则最好采用5架无人机去执行巡检作业。

上述敏感性实验结果表明，在ISG1和ISG2的算例规模下，两架无人机去完成所有巡检任务是完全足够的。因此，在该规模下投入更多的无人机去执行相同数量的巡检任务只有可能增加不必要的飞行时间和各部分无人机的等待时间，从而无效地增加总的作业时间。然而，随着巡检轮次和监测点数量的大幅增加，在ISG3算例规模下，两架无人机则难以高效地完成所有巡检任务。此时，增加用于巡检无人机的数量则能够有效的缩短总的作业时间。上述结果启示工程项目管理者需要结合实际的监测需求动态地调整当天投入的无人机资源数量，从而以合理的资源数量来完成巡检监测任务，而无人机数量和监测需求之间的匹配关系则可能受监测区域面积、无人机性能等多方面因素影响。

6.3.2 无人机性能的敏感性分析

无人机的性能同样会影响总的巡检作业时间。本节实验主要探讨了无人机不同性能指标的变化对总巡检作业时间的影响，包括电池容量（ r k）、平均速度（ v k）以及单位距离能耗（ h k）。为了探究该三类性能指标的影响，本文为每一项指标设定了一个基准值，然后围绕该基准值进行20%的浮动，开展多组实验来探究不同指标带来的影响。需要补充的是，由于无人机平均速度越高，其能耗往往越大，因此在探究平均速度带来的影响时，本文将无人机能耗参数按照同向比例进行浮动。上述三类参数的变化范围以及对应的总作业时间变化分别在ISG1、ISG2以及ISG3三个算例规模下开展实验，结果如图9所示。

由上述实验结果得出的管理启示如下：首先，唯有当无人机的电量增大到某个阈值后，总作业时间才会由于充电时间的减少而出现降低。其次，无人机的平均飞行速度与巡检作业总时间并非呈现完全的负相关关系，尤其当巡检任务数量和巡检轮次均较少时[图9（a）和（b）]。该现象归咎于平均速度的提高，无人机的单位距离能耗也在提升，从而带来充电时间的提高，另一方面在监测任务较少时，平均速度的提高也会产生额外的等待时间。但在问题规模较大的算例下（如至少为ISG3的问题规模），提高无人机的平均飞行速度仍然是缩短总作业时间的一个有效方法。最后，无人机单位距离能耗的提高将增加所有巡检作业的完成时间，这归咎于单位距离能耗的增加会导致无人机在一个用电周期内的飞行距离减少。上述敏感性的分析结论有助于为工程项目管理者在购买无人机开展巡检监测作业时提供相关指导，如无人机速度是首要考虑因素，其次是无人机的续航能力（电池容量和单位距离能耗）。

6.4 实验总结

本节开展了一系列的数值实验来评估基于VNS的元启发式算法在求解无人机巡检路径调度问题的性能。在小、中、大三组算例规模下，本文分别将算法求解的结果与CPLEX求解器以及通过初始解生成策略得到的结果进行对比，结果表明本研究设计的算法在求解质量与计算时间方面显著优于CPLEX求解器。在小规模算例下，本研究设计的算法能够在较短的时间内获得与CPELX一致的最优解。而在中规模算例下，VNS则同样能够在较短的时间内获得比CPLEX求解器更优的解。而对于CPLEX已无法在合理时间内获得可行解的大规模算例中，基于VNS算法得到的解相较于初始生成策略得到的解，则有着显著的优化效果。

此外，本文还进行了敏感性分析实验，从无人机数量和无人机性能两个维度对无人机巡检规划的优化问题进行了深入分析。在小规模算例下，实验结果表明两架无人机是相对最优的巡检作业资源配置；而在中大规模问题下，增加用于巡检监测的无人机数量则有助于缩短总的巡检作业时间。此外，无人机的平均速度是缩短总工作时间的关键因素，特别是对于具有大量检查任务的问题场景。另一方面，无人机的单位距离能耗决定了一家无人机在一个充电周期内的飞行距离长度，因此无人机单位距离能耗的增加将有可能延长总的巡检作业时长。

上述敏感性实验的结果为工程管理人员在规划无人机巡检监测路径方案时提供了些许管理启示。利用无人机开展巡检作业时，应根据实际的监测点数量合理安排执行作业的无人机数量，并设定合适的无人机飞行速度，从而提高巡检作业的效率。这些发现有助于无人机在工程项目中的有效应用，从而推动无人机代替巡检人员去全面地监控施工区域，最大限度地减少人工作业。

7 案例研究

在本节中，我们以狮子洋大桥工程项目作为实际案例，展示了如何使用所设计的模型和算法来优化决策无人机巡检计划。由于狮子洋大桥仍在建设中，因此它为我们的研究提供了一个模拟的现实世界问题规模。本节通过使用现实世界参数设置进行数值实验，并对实验结果进行了详细分析。

7.1 案例背景

如第1节所述，基于无人机的巡检方法在复杂、高风险的建筑环境中具有巨大优势，能够持续筛查潜在的风险（图10）。本文所提出的数学模型和算法为工程管理者提供了一个科学工具，用于确定无人机的巡检计划（巡检任务分配、监控序列和充电决策）。因此，为了展示我们的解决方案在确定无人机巡检计划方面的实际应用，我们选择狮子洋大桥作为案例研究，并模拟基于实际案例数据估计的决策过程。

狮子洋大桥横跨珠江，全长2180 m，位于广东省广州市，是专门加强周边城市和地区连通性的狮子洋航道的工程控制项目。图11显示了狮子洋大桥的大致位置，并提供了一个概念性的插图。这样一个超大跨度、高负荷、超宽甲板的悬索桥在建造技术上难度很大。此外，狮子洋大桥的建设还面临额外的困难，因为其工程特点（如超大的建设范围、高技术难度和长建设周期）意味着在整个建设周期中有许多高风险的建设区域。因此，工程管理者通过连续筛查操作来识别潜在风险并以此减少重大事故的发生是至关重要的。

7.2 案例结果

本小节基于狮子洋大桥实例的数据，对模型的相关参数进行了设置。同时，对所提出的算法在实际案例中的求解效果进行了测试。

7.2.1 解决实际规模实例的性能

本节首先明确了现实世界实例的参数设置，然后进行了数值实验，以验证所设计算法求解模型的效率。根据广东省交通厅保留的规划文件[36]，狮子洋大桥的建设区域可以大致模拟为一个12 km长、2 km宽的矩形（附录A中的图S2）。本文设计了与之相关的问题规模，该规模涉及8架无人机、22个监控站点、4轮监控和6个充电站，远大于ISG9中的问题规模。该新的实例组称为ISG10，其他参数设置与第6.1节中的相同。以下计算结果是针对ISG10 和图S2中所示的问题模拟获得的。

表8显示，本研究所设计的算法在3600 s内获得了大多数现实世界实例的最优解。使用所设计算法获得的结果与第5.2节描述的策略获得的结果之间的平均差异为23.64%，这些结果证实了所设计算法解决现实世界实例的效率。数值实验计算出的差值强调了从全局最优性角度改进多轮巡检任务分配和访问序列的重要性，可以大幅度提高巡检任务的效率。因此，在规划需要多次访问监控点的任务的路径时，考虑无人机的任务分配和访问序列是至关重要的，这些考虑对总体巡检时间有显著影响。

为了加快解决所设计模型的计算时间，使其低于3600 s阈值，可以采用区域分割的策略，即将全局的监控站点分割成一系列较小的区域。更具体地说，监控站点可以被聚集成四个矩形区域，每个区域长4 km、宽2 km。随后，可以使用所设计的模型和算法分别确定每个对应区域的巡检计划。这将涉及同时解决四个子问题，每个问题涉及两架无人机、五或六个监控站点和两个充电站。虽然这种方法可能由于分别解决中等规模问题而损失一些最优性，但它将作为一种实际的解决方案，减少具有众多监控站点的现实世界实例中的计算时间。值得注意的是，每个中等规模实例的计算时间已经验证不超过5 min（实验结果已证实，见表6）。因此，开发一种有效的方法，将监控站点聚类成不同的子区域，以减轻最优性损失的程度，将作为未来研究的主题。

7.2.2 算法在制定巡检计划中的实际应用

上述数值实验提供了目标值的计算结果，以验证所设计算法解决现实世界实例的有效性和效率，但它们没有展示获得的无人机巡检计划。本小节展示了我们的方法在制定现实世界巡检计划中的实际应用。

为了尽可能真实地模拟现实世界情况，我们基于现实情况生成了一个实例，该实例包括6架无人机、20个监控站点和8个充电站，其中：①监控站点在狮子洋大桥的建设区域内平均放置；②充电站分布在相应的建设区域以满足充电需求；③每架无人机在狮子洋大桥的一侧开始其巡检任务，并在另一侧结束这些任务。基于这些要求，一个现实世界实例如附录A中的图S3中所示，我们需要在此基础上为一定数量的无人机生成一个实际的巡检计划。

使用本文的方法获得的巡检计划如表9中所示，巡检计划的甘特图在图12中呈现。由于空间限制，无人机的充电决策信息从图表中省略。从现实世界案例的结果中可以获得以下启发。首先，除了3号无人机和4号无人机外，所有无人机都连续长时间执行巡检任务，因此3号无人机和4号无人机可以被视为“紧急工作者”，专门执行其他“忙碌”无人机可能无法完成的巡检任务。其次，一架无人机连续两次巡检任务之间的时间间隔通常短于10 min，但有时会长得多（例如，任务13-1和2-2之间有18 min）。除非两个巡检任务之间距离较远，否则该时间主要用于充电。所有时间间隔都短于30 min，意味着无人机倾向于频繁充电，而不是在电量几乎耗尽时返回充电站。后一种充电策略将导致无人机花费很长时间等待充满电，这将违反监控站点的时间间隔要求。

8 结论

本文探讨了在工程项目建设背景下的无人机巡检路线和调度问题，制定了一个MILP模型，以优化无人机完成一系列监控任务的总工作时间。所设计的模型全面考虑了禁飞区限制、多轮次监测时间间隔要求和每架无人机的电力限制，以制定无人机巡检路线和调度计划。同时开发了一个基于VNS的元启发式算法来高效解决所构建的数学模型。并且进行了数值实验以验证所设计模型和算法的有效性。最后，基于狮子洋大桥项目开展了案例研究，为工程管理者在优化巡检工作效率方面提供了相应的管理启示。本研究的主要贡献总结如下。

（1）从建模角度而言，本文设计的MILP模型全面考虑了确定无人机巡检计划的特定约束，即禁飞区限制、滚动监控间隔时间窗口约束和电池容量限制。这些特定约束使得所设计的模型区别于专门用于EVRP或EVRPTW的典型模型。据我们所知，很少有论文在工程管理背景下将上述实际约束纳入数学模型中，或专注于在上述背景下无人机的路线和调度。

（2）从算法角度而言，本文开发了一个基于VNS的元启发式算法，以高效解决所设计的模型，因为本文的模型过于复杂，即使是商业求解器也难以在大规模实例中找到该模型的可行解。本文根据问题的特征开发了定制的邻域结构和初始解生成方法，大量的数值实验验证了所设计算法在30 min内解决大规模实例的效率。

（3）从实际应用角度而言，本文从大量敏感性实验中获得了实用的管理启示。例如，应提前评估执行巡检任务的无人机数量。大量投资购买用于巡检的无人机可能不一定能减少总工作时间，相反可能会增加不必要的成本。敏感性实验显示，工程管理者在有限预算内购买无人机时，应优先考虑无人机的速度，其次是单位距离能耗，最后是电池功率。对于执行众多巡检任务的无人机来说，频繁充电可能是更好的，因为这样可以减少它们等待充满电的时间。

本文对工程管理背景下无人机巡检路线和调度优化做出了贡献；然而，仍有值得研究的主题。如上所述，应进一步探索不同巡检工作问题规模下的最佳无人机作业数量。此外，当前研究尚未充分考虑无人机巡检过程中的不确定性问题（如天气条件和建筑活动的变化），这些因素可能显著影响无人机的能耗。最后，探索如何更好地对监控点进行区域分组以缩小无人机巡检范围同样值得进一步探索。

参考文献

原文顺序 | 出版日期 | 本文引用
[1]

Sajid M, Mittal H, Pare S, Prasad M. Routing and scheduling optimization for UAV assisted delivery system: a hybrid approach. Appl Soft Comput 2022;126:109225. . 10.1016/j.asoc.2022.109225
[2]

Salama MR, Srinivas S. Collaborative truck multi-drone routing and scheduling problem: package delivery with flexible launch and recovery sites. Transp Res, Part E Logist Trans Rev 2022;164:102788. . 10.1016/j.tre.2022.102788
[3]

Qu X, Zeng Z, Wang K, Wang S. Replacing urban trucks via ground‒air cooperation. Communications in Transportation Research 2022;2:100080. . 10.1016/j.commtr.2022.100080
[4]

Manyam S, Sundar K, Casbeer D. Cooperative routing for an air‒ground vehicle team—exact algorithm, transformation method, and heuristics. IEEE Trans Autom Sci Eng 2020;17(1):537‒47. . 10.1109/tase.2019.2931894
[5]

Sundar K, Venkatachalam S, Manyam S. Path planning for multiple heterogeneous unmanned vehicles with uncertain service times. In: Proceedings of 2017 International Conference on Unmanned Aircraft Systems (ICUAS); 2017 Jun 13‒16; Miami, FL, USA. Piscataway: IEEE; 2017. . 10.1109/icuas.2017.7991336
[6]

Zheng Y, Du Y, Sheng W, Ling H. Collaborative human‒UAV search and rescue for missing tourists in nature reserves. INFORMS J Appl Analy 2019;49(5):371‒83. . 10.1287/inte.2019.1000
[7]

Li M, Zhen L, Wang S, Lv W, Qu X. Unmanned aerial vehicle scheduling problem for traffic monitoring. Comput Ind Eng 2018;122:15‒23. . 10.1016/j.cie.2018.05.039
[8]

Yi W, Wang H, Jin Y, Cao J. Integrated computer vision algorithms and drone scheduling. Commu Transp Res 2021;1:100002. . 10.1016/j.commtr.2021.100002
[9]

Du J, Weng F. Construction management and technology innovation for main projects of Quanzhou Bay Bridge. Front Eng Manag 2021;8(1):151‒5. . 10.1007/s42524-020-0147-8
[10]

Khan SI, Qadir Z, Munawar HS, Nayak SR, Budati AK, Verma KD, et al. UAVs path planning architecture for effective medical emergency response in future networks. Phys Commun 2021;47:101337. . 10.1016/j.phycom.2021.101337
[11]

Chowdhury S, Shahvari O, Marufuzzaman M, Li X, Bian L. Drone routing and optimization for post-disaster inspection. Comput Ind Eng 2021;159:107495. . 10.1016/j.cie.2021.107495
[12]

Liu W, Zhang T, Huang S, Li K. A hybrid optimization framework for UAV reconnaissance mission planning. Comput Ind Eng 2022;173:108653. . 10.1016/j.cie.2022.108653
[13]

Shen L, Hou Y, Yang Q, Lv M, Dong J, Yang Z, et al. Synergistic path planning for ship-deployed multiple UAVs to monitor vessel pollution in ports. Transp Res Part D Transp Environ 2022;110:103415. . 10.1016/j.trd.2022.103415
[14]

Munishkin AA, Milutinović D, Casbeer DW. Min-max time efficient inspection of ground vehicles by a UAV team. Robot Auton Syst 2020;125:103370. . 10.1016/j.robot.2019.103370
[15]

Spencer B, Hoskere V, Narazaki Y. Advances in computer vision-based civil infrastructure inspection and monitoring. Engineering 2019;5(2):199‒222. . 10.1016/j.eng.2018.11.030
[16]

Perry BJ, Guo Y, Atadero R, Van de Lindt J. Streamlined bridge inspection system utilizing unmanned aerial vehicles (UAVs) and machine learning. Measurement 2020;164:108048. . 10.1016/j.measurement.2020.108048
[17]

Hu J, Niu H, Carrasco J, Lennox B, Arvin F. Fault-tolerant cooperative navigation of networked UAV swarms for forest fire monitoring. Aerosp Sci Technol 2022;123:107494. . 10.1016/j.ast.2022.107494
[18]

Bailon-Ruiz R, Bit-Monnot A, Lacroix S. Real-time wildfire monitoring with a fleet of UAVs. Robot Auton Syst 2022;152:104071. . 10.1016/j.robot.2022.104071
[19]

Meng D, Xiao Y, Guo Z, Jolfaei A, Qin L, Lu X, et al. A data-driven intelligent planning model for UAVs routing networks in mobile Internet of Things. Comput Commun 2021;179:231‒41. . 10.1016/j.comcom.2021.08.014
[20]

Xia Y, Batta R, Nagi R. Controlling a fleet of unmanned aerial vehicles to collect uncertain information in a threat environment. Oper Res 2017;65(3):674‒92. . 10.1287/opre.2017.1590
[21]

Mbiadou Saleu R, Deroussi L, Feillet D, Grangeon N, Quilliot A. The parallel drone scheduling problem with multiple drones and vehicles. Eur J Oper Res 2022;300(2):571‒89. . 10.1016/j.ejor.2021.08.014
[22]

Sacramento D, Pisinger D, Ropke S. An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones. Transport Res C Emer 2019;102:289‒315. . 10.1016/j.trc.2019.02.018
[23]

Zhen L, Gao J, Tan Z, Wang S, Baldacci R. Branch-price-and-cut for trucks and drones cooperative delivery. IIE Trans 2022;55(3):271‒87. . 10.1080/24725854.2022.2060535
[24]

Rajan S, Sundar K, Gautam N. Routing problem for unmanned aerial vehicle patrolling missions: a progressive hedging algorithm. Comput Oper Res 2022;142:105702. . 10.1016/j.cor.2022.105702
[25]

Xu C, Xu M, Yin C. Optimized multi-UAV cooperative path planning under the complex confrontation environment. Comput Commun 2020;162:196‒203. . 10.1016/j.comcom.2020.04.050
[26]

Qin W, Shi Z, Li W, Li K, Zhang T, Wang R. Multiobjective routing optimization of mobile charging vehicles for UAV power supply guarantees. Comput Ind Eng 2021;162:107714. . 10.1016/j.cie.2021.107714
[27]

Hu M, Liu W, Lu J, Fu R, Peng K, Ma X, et al. On the joint design of routing and scheduling for vehicle-assisted multi-UAV inspection. Future Gener Comput Syst 2019;94:214‒23. . 10.1016/j.future.2018.11.024
[28]

Zhen L, Li M, Laporte G, Wang W. A vehicle routing problem arising in unmanned aerial monitoring. Comput Oper Res 2019;105:1‒11. . 10.1016/j.cor.2019.01.001
[29]

Wang Y, Li Y, Yin F, Wang W, Sun H, Li J, et al. An intelligent UAV path planning optimization method for monitoring the risk of unattended offshore oil platforms. Process Saf Environ Prot 2022;160:13‒24. . 10.1016/j.psep.2022.02.011
[30]

Coelho B, Coelho V, Coelho I, Ochi L, Haghnazar K, Lima M, et al. A multi-objective green UAV routing problem. Comput Oper Res 2017;88:306‒15. . 10.1016/j.cor.2017.04.011
[31]

Moshref-Javadi M, Hemmati A, Winkenbach M. A truck and drones model for last-mile delivery: a mathematical model and heuristic approach. Appl Math Model 2020;80:290‒318. . 10.1016/j.apm.2019.11.020
[32]

Huang S, Huang Y, Blazquez C, Paredes-Belmar G. Application of the ant colony optimization in the resolution of the bridge inspection routing problem. Appl Soft Comput 2018;65:443‒61. . 10.1016/j.asoc.2018.01.034
[33]

Zhen L, Wang B, Li M, Wang W, Huang L. Inspection routing problem for coal mine safety personnel in underground mines. Comput Ind Eng 2019;130:526‒36. . 10.1016/j.cie.2019.03.003
[34]

Jeong E, Seo J, Wacker J. UAV-aided bridge inspection protocol through machine learning with improved visibility images. Expert Syst Appl 2022;197:116791. . 10.1016/j.eswa.2022.116791
[35]

DJI. The technology parameter of M300 RTK [Internet]. Shenzhen: Shenzhen Dajiang Innovation Technology Co., Ltd.; c 2023 [cited 2023 Apr 1]. Available from:

[36]

Department of Transport of Guangdong Province. The new member of the cross-river channel group in the Greater Bay Area—the Shiziyang Passage project started the survey and design. Guangzhou: Guangdong Provincial Department of Transportation; 2021 Mar 3 [cited 2023 Apr 1]. Available from:

AI Summary AI Mindmap
PDF (3070KB)

9221

访问

0

被引

详细
导航
相关文章

AI思维导图

/

〈 〉