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

Lu Zhen, Zhiyuan Yang, Gilbert Laporte, Wen Yi, Tianyi Fan

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

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

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

作者信息 +

Unmanned Aerial Vehicle Inspection Routing and Scheduling for Engineering Management

Author information +
History +

摘要

无人机(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.

Keywords

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

引用本文

导出引用
Lu Zhen, Zhiyuan Yang, Gilbert Laporte. 工程管理背景下的无人机巡检路径调度优化. Engineering. 2024, 36(5): 223-239 https://doi.org/10.1016/j.eng.2023.10.014

参考文献

[1]
M. Sajid, H. Mittal, S. Pare, M. Prasad. Routing and scheduling optimization for UAV assisted delivery system: a hybrid approach. Appl Soft Comput, 126 ( 2022), Article 109225
[2]
M.R. Salama, S. Srinivas. Collaborative truck multi-drone routing and scheduling problem: package delivery with flexible launch and recovery sites. Transp Res, Part E Logist Trans Rev, 164 ( 2022), Article 102788
[3]
X. Qu, Z. Zeng, K. Wang, S. Wang. Replacing urban trucks via ground-air cooperation. Communications in Transportation Research, 2 ( 2022), Article 100080
[4]
S. Manyam, K. Sundar, D. Casbeer. Cooperative routing for an air-ground vehicle team—exact algorithm, transformation method, and heuristics. IEEE Trans Autom Sci Eng, 17 (1) ( 2020), pp. 537-547
[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.
[6]
Y. Zheng, Y. Du, W. Sheng, H. Ling. Collaborative human-UAV search and rescue for missing tourists in nature reserves. INFORMS J Appl Analy, 49 (5) ( 2019), pp. 371-383
[7]
M. Li, L. Zhen, S. Wang, W. Lv, X. Qu. Unmanned aerial vehicle scheduling problem for traffic monitoring. Comput Ind Eng, 122 ( 2018), pp. 15-23
[8]
W. Yi, H. Wang, Y. Jin, J. Cao. Integrated computer vision algorithms and drone scheduling. Commu Transp Res, 1 ( 2021), Article 100002
[9]
J. Du, F. Weng. Construction management and technology innovation for main projects of Quanzhou Bay Bridge. Front Eng Manag, 8 (1) ( 2021), pp. 151-155
[10]
S.I. Khan, Z. Qadir, H.S. Munawar, S.R. Nayak, A.K. Budati, K.D. Verma, et al.. UAVs path planning architecture for effective medical emergency response in future networks. Phys Commun, 47 ( 2021), Article 101337
[11]
S. Chowdhury, O. Shahvari, M. Marufuzzaman, X. Li, L. Bian. Drone routing and optimization for post-disaster inspection. Comput Ind Eng, 159 ( 2021), Article 107495
[12]
W. Liu, T. Zhang, S. Huang, K. Li. A hybrid optimization framework for UAV reconnaissance mission planning. Comput Ind Eng, 173 ( 2022), Article 108653
[13]
L. Shen, Y. Hou, Q. Yang, M. Lv, J. Dong, Z. Yang, et al.. Synergistic path planning for ship-deployed multiple UAVs to monitor vessel pollution in ports. Transp Res Part D Transp Environ, 110 ( 2022), Article 103415
[14]
A.A. Munishkin, D. Milutinović, D.W. Casbeer. Min-max time efficient inspection of ground vehicles by a UAV team. Robot Auton Syst, 125 ( 2020), Article 103370
[15]
B. Spencer, V. Hoskere, Y. Narazaki. Advances in computer vision-based civil infrastructure inspection and monitoring. Engineering, 5 (2) ( 2019), pp. 199-222
[16]
B.J. Perry, Y. Guo, R. Atadero, J. Van de Lindt. Streamlined bridge inspection system utilizing unmanned aerial vehicles (UAVs) and machine learning. Measurement, 164 ( 2020), Article 108048
[17]
J. Hu, H. Niu, J. Carrasco, B. Lennox, F. Arvin. Fault-tolerant cooperative navigation of networked UAV swarms for forest fire monitoring. Aerosp Sci Technol, 123 ( 2022), Article 107494
[18]
R. Bailon-Ruiz, A. Bit-Monnot, S. Lacroix. Real-time wildfire monitoring with a fleet of UAVs. Robot Auton Syst, 152 ( 2022), Article 104071
[19]
D. Meng, Y. Xiao, Z. Guo, A. Jolfaei, L. Qin, X. Lu, et al.. A data-driven intelligent planning model for UAVs routing networks in mobile Internet of Things. Comput Commun, 179 ( 2021), pp. 231-241
[20]
Y. Xia, R. Batta, R. Nagi. Controlling a fleet of unmanned aerial vehicles to collect uncertain information in a threat environment. Oper Res, 65 (3) ( 2017), pp. 674-692
[21]
R. Mbiadou Saleu, L. Deroussi, D. Feillet, N. Grangeon, A. Quilliot. The parallel drone scheduling problem with multiple drones and vehicles. Eur J Oper Res, 300 (2) ( 2022), pp. 571-589
[22]
D. Sacramento, D. Pisinger, S. Ropke. An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones. Transport Res C Emer, 102 ( 2019), pp. 289-315
[23]
L. Zhen, J. Gao, Z. Tan, S. Wang, R. Baldacci. Branch-price-and-cut for trucks and drones cooperative delivery. IIE Trans, 55 (3) ( 2022), pp. 271-287
[24]
S. Rajan, K. Sundar, N. Gautam. Routing problem for unmanned aerial vehicle patrolling missions: a progressive hedging algorithm. Comput Oper Res, 142 ( 2022), Article 105702
[25]
C. Xu, M. Xu, C. Yin. Optimized multi-UAV cooperative path planning under the complex confrontation environment. Comput Commun, 162 ( 2020), pp. 196-203
[26]
W. Qin, Z. Shi, W. Li, K. Li, T. Zhang, R. Wang. Multiobjective routing optimization of mobile charging vehicles for UAV power supply guarantees. Comput Ind Eng, 162 ( 2021), Article 107714
[27]
M. Hu, W. Liu, J. Lu, R. Fu, K. Peng, X. Ma, et al.. On the joint design of routing and scheduling for vehicle-assisted multi-UAV inspection. Future Gener Comput Syst, 94 ( 2019), pp. 214-223
[28]
L. Zhen, M. Li, G. Laporte, W. Wang. A vehicle routing problem arising in unmanned aerial monitoring. Comput Oper Res, 105 ( 2019), pp. 1-11
[29]
Y. Wang, Y. Li, F. Yin, W. Wang, H. Sun, J. Li, et al.. An intelligent UAV path planning optimization method for monitoring the risk of unattended offshore oil platforms. Process Saf Environ Prot, 160 ( 2022), pp. 13-24
[30]
B. Coelho, V. Coelho, I. Coelho, L. Ochi, K. Haghnazar, M. Lima, et al.. A multi-objective green UAV routing problem. Comput Oper Res, 88 ( 2017), pp. 306-315
[31]
M. Moshref-Javadi, A. Hemmati, M. Winkenbach. A truck and drones model for last-mile delivery: a mathematical model and heuristic approach. Appl Math Model, 80 ( 2020), pp. 290-318
[32]
S. Huang, Y. Huang, C. Blazquez, G. Paredes-Belmar. Application of the ant colony optimization in the resolution of the bridge inspection routing problem. Appl Soft Comput, 65 ( 2018), pp. 443-461
[33]
L. Zhen, B. Wang, M. Li, W. Wang, L. Huang. Inspection routing problem for coal mine safety personnel in underground mines. Comput Ind Eng, 130 ( 2019), pp. 526-536
[34]
E. Jeong, J. Seo, J. Wacker. UAV-aided bridge inspection protocol through machine learning with improved visibility images. Expert Syst Appl, 197 ( 2022), Article 116791
[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]
PDF(3393 KB)

Accesses

Citation

Detail

段落导航
相关文章

/