
工程管理背景下的无人机巡检路径调度优化
Lu Zhen, Zhiyuan Yang, Gilbert Laporte, Wen Yi, Tianyi Fan
工程(英文) ›› 2024, Vol. 36 ›› Issue (5) : 223-239.
工程管理背景下的无人机巡检路径调度优化
Unmanned Aerial Vehicle Inspection Routing and Scheduling for Engineering Management
无人机(UAV)技术的蓬勃发展革新了各个领域的业态模式,使基于无人机的各类解决方案得以广泛应用。而在工程管理领域当中,基于无人机的巡检监测相较于传统的人工巡检方式有着巨大的优势,能够以较低的风险去高效识别高风险施工环境中的潜在隐患。在此背景下,本文研究了工程领域背景下的无人机巡检路径调度优化问题,在该问题中本文考虑了无人机飞行禁飞区、监测时间间隔以及多轮次巡检路径调度等因素。为高效求解该优化问题,本文提出了一种混合整数线性规划(MILP)模型用于优化无人机巡检任务分配、监测点巡检顺序调度以及无人机充电的三类决策。上述三类复杂因素的考虑使该巡检路径调度问题与传统的车辆调度问题(VRP)有着显著区别,同时模型的复杂程度也使得商业求解器难以在合理时间内高效求解上述模型。为此,本文基于变邻域搜索算法设计了定制化的元启发式算法来高效求解所提出的数学模型。大量的数值实验验证了本文设计算法的有效性,并证明了该算法在大规模算例和真实规模算例中的应用性。此外,本文还基于实际的工程项目开展了敏感性分析和案例研究,为工程管理人员在提高巡检工作效率方面提供了相关管理启示。
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.
工程管理 / 无人机 / 巡检路径调度优化 / 混合整数线性规划模型 / 变邻域元启发式算法 / Engineering management / Unmanned aerial vehicle / Inspection routing and scheduling optimization / Mixed-integer linear programming model / Variable neighborhood search metaheuristic
[1] |
|
[2] |
|
[3] |
|
[4] |
|
[5] |
|
[6] |
|
[7] |
|
[8] |
|
[9] |
|
[10] |
|
[11] |
|
[12] |
|
[13] |
|
[14] |
|
[15] |
|
[16] |
|
[17] |
|
[18] |
|
[19] |
|
[20] |
|
[21] |
|
[22] |
|
[23] |
|
[24] |
|
[25] |
|
[26] |
|
[27] |
|
[28] |
|
[29] |
|
[30] |
|
[31] |
|
[32] |
|
[33] |
|
[34] |
|
[35] |
DJI. The technology parameter of M300 RTK [Internet]. Shenzhen: Shenzhen Dajiang Innovation Technology Co., Ltd; c 2023 [cited 2023 Apr 1].
|
[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
[ 2023 Apr 1]
|
/
〈 |
|
〉 |