Unmanned Aerial Vehicle Inspection Routing and Scheduling for Engineering Management

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

Engineering ›› 2024, Vol. 36 ›› Issue (5) : 223-239.

PDF(3393 KB)
PDF(3393 KB)
Engineering ›› 2024, Vol. 36 ›› Issue (5) : 223-239. DOI: 10.1016/j.eng.2023.10.014
Research
Article

Unmanned Aerial Vehicle Inspection Routing and Scheduling for Engineering Management

Author information +
History +

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.

Graphical abstract

Keywords

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

Cite this article

Download citation ▾
Lu Zhen, Zhiyuan Yang, Gilbert Laporte, Wen Yi, Tianyi Fan. Unmanned Aerial Vehicle Inspection Routing and Scheduling for Engineering Management. Engineering, 2024, 36(5): 223‒239 https://doi.org/10.1016/j.eng.2023.10.014

References

[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]
AI Summary AI Mindmap
PDF(3393 KB)

Accesses

Citations

Detail

Sections
Recommended

/