Heterogeneous multi-drone and helicopter routing problem for reconnaissance

Abstract: Helicopters and drones are widely used in military and post-disaster reconnaissance. But less attention has been paid to collaborative reconnaissance between the two, especially when drones can be launched and retrieved multiple times. We propose a synchronous routing problem of helicopter and heterogeneous multi-drone for reconnaissance, which is a new variant of the orienteering problem (OP), where the drones can visit multiple mission nodes and can reconnoiter the retrieval nodes in a single trip, with the goal of maximizing the information collected. The problem is formulated as a mixed integer linear programming (MILP) model, and then an adaptive simulated annealing algorithm (A-SA) is designed to solve the problem. Specifically, a universal high-efficiency heuristics solution evaluation method based on segment sorting is proposed. The time complexity of this method is O(n). The numerical experiments illustrate the accuracy and efficiency of the algorithm. The results also show that allowing the drones to conduct reconnaissance on the retrieval nodes can positively impact the solution.

How to cite this paper

 Zhao, P., Zeng, X & Du, C. (2024). Heterogeneous multi-drone and helicopter routing problem for reconnaissance.International Journal of Industrial Engineering Computations , 15(1), 255-276.

Refrences

Agatz, N., Bouman, P., & Schmidt, M. (2018). Optimization Approaches for the Traveling Salesman Problem with Drone. Transportation Science, 52(4), 965-981. https://doi.org/10.1287/trsc.2017.0791
Avi, A., Frisco, N., Giurato, M., Lovera, M., Masarati, P., Panza, S., ... & Quaranta, G. (2022). Scout Drone: a Drone-Helicopter Collaboration to Support HEMS Missions. In 48th European Rotorcraft Forum (ERF 2022) (pp. 1-8).
Cavani, S., Iori, M., & Roberti, R. (2021). Exact Methods for the Traveling Salesman Problem with Multiple Drones. Transportation Research Part C: Emerging Technologies, 130, 103280. https://doi.org/10.1016/j.trc.2021.103280
Chung, S. H., Sah, B., & Lee, J. (2020). Optimization for Drone and Drone-Truck Combined Operations: A Review of the State of the Art and Future Directions. Computers & Operations Research, 123, 105004. https://doi.org/10.1016/j.cor.2020.105004
Demir, E., Bektas, T., & Laporte, G. (2012). An Adaptive Large Neighborhood Search Heuristic for the Pollution-Routing Problem. European Journal of Operational Research, 223(2), 346-359. https://doi.org/10.1016/j.ejor.2012.06.044
Golden, B. L., Levy, L., & Vohra, R. (1987). The Orienteering Problem. Naval Research Logistics, 34(3), 307-318. https://doi.org/10.1002/1520-6750(198706)34:33.0.CO;2-D
Gonzalez-R, P. L., Canca, D., Andrade-Pineda, J. L., Calle, M., & Leon-Blanco, J. M. (2020). Truck-Drone Team Logistics: A Heuristic Approach to Multi-Drop Route Planning. Transportation Research Part C: Emerging Technologies, 114, 657-680. https://doi.org/10.1016/j.trc.2020.02.030
Gu, R., Poon, M., Luo, Z., Liu, Y., & Liu, Z. (2022). A Hierarchical Solution Evaluation Method and a Hybrid Algorithm for the Vehicle Routing Problem with Drones and Multiple Visits. Transportation Research Part C: Emerging Technologies, 141, 103733. https://doi.org/10.1016/j.trc.2022.103733
Gunawan, A., Lau, H. C., & Vansteenwegen, P. (2016). Orienteering Problem: A Survey of Recent Variants, Solution Approaches and Applications. European Journal of Operational Research, 255(2), 315-332. https://doi.org/10.1016/j.ejor.2016.04.059.
Optimization, G. (2020). Gurobi Optimizer Reference Manual.
Kim, H., Kim, B. I., & Noh, D. J. (2020). The Multi-Profit Orienteering Problem. Computers & Industrial Engineering, 149, 106808. https://doi.org/10.1016/j.cie.2020.106808
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science 220(4598), 671-680. https://doi.org/10.1126/science.220.4598.671
Kitjacharoenchai, P., Min, B.-C., & Lee, S. (2020). Two Echelon Vehicle Routing Problem with Drones in Last Mile Delivery. International Journal of Production Economics, 225, 107598. https://doi.org/10.1016/j.ijpe.2019.107598
Kitjacharoenchai, P., Ventresca, M., Moshref-Javadi, M., Lee, S., Tanchoco, J. M. A., & Brunese, P. A. (2019). Multiple Traveling Salesman Problem with Drones: Mathematical Model and Heuristic Approach. Computers & Industrial Engineering, 129, 14-30. https://doi.org/10.1016/j.cie.2019.01.020
Kobeaga, G., Merino, M., & Lozano, J. A. (2018). An Efficient Evolutionary Algorithm for the Orienteering Problem. Computers & Operations Research, 90, 42-59. https://doi.org/10.1016/j.cor.2017.09.003
Liu, Y., Qi, N., Yao, W., Zhao, J., & Xu, S. (2020). Cooperative Path Planning for Aerial Recovery of a Uav Swarm Using Genetic Algorithm and Homotopic Approach. Applied Sciences, 10(12), 4154. https://doi.org/10.3390/app10124154
Luo, Q., Wu, G., Ji, B., Wang, L., & Suganthan, P. N. (2022). Hybrid Multi-Objective Optimization Approach with Pareto Local Search for Collaborative Truck-Drone Routing Problems Considering Flexible Time Windows. IEEE Transactions on Intelligent Transportation Systems, 23(8), 13011-13025. https://doi.org/10.1109/tits.2021.3119080
Luo, Z., Poon, M., Zhang, Z., Liu, Z., & Lim, A. (2021). The Multi-Visit Traveling Salesman Problem with Multi-Drones. Transportation Research Part C: Emerging Technologies, 128, 103172. https://doi.org/10.1016/j.trc.2021.103172
Losey, S. (2021). DARPA nabs Gremlin drone in midair for first time.
Macrina, G., Di Puglia Pugliese, L., Guerriero, F., & Laporte, G. (2020). Drone-Aided Routing: A Literature Review. Transportation Research Part C: Emerging Technologies, 120, 102762. https://doi.org/10.1016/j.trc.2020.102762
Mahmoudi, B., & Eshghi, K. (2022). Energy-Constrained Multi-Visit Tsp with Multiple Drones Considering Non-Customer Rendezvous Locations. Expert Systems with Applications, 210, 118479. https://doi.org/10.1016/j.eswa.2022.118479
Masmoudi, M. A., Hosny, M., Braekers, K., & Dammak, A. (2016). Three Effective Metaheuristics to Solve the Multi-Depot Multi-Trip Heterogeneous Dial-a-Ride Problem. Transportation Research Part E: Logistics and Transportation Review, 96, 60-80. https://doi.org/10.1016/j.tre.2016.10.002
Moshref-Javadi, M., Hemmati, A., & Winkenbach, M. (2020). A Truck and Drones Model for Last-Mile Delivery: A Mathematical Model and Heuristic Approach. Applied Mathematical Modelling, 80, 290-318. https://doi.org/10.1016/j.apm.2019.11.020
Moshref-Javadi, M., & Winkenbach, M. (2021). Applications and Research Avenues for Drone-Based Models in Logistics: A Classification and Review. Expert Systems with Applications, 177, 114854. https://doi.org/10.1016/j.eswa.2021.114854
Murray, C. C., & Chu, A. G. (2015). The Flying Sidekick Traveling Salesman Problem: Optimization of Drone-Assisted Parcel Delivery. Transportation Research Part C: Emerging Technologies, 54, 86-109. https://doi.org/10.1016/j.trc.2015.03.005
Murray, C. C., & Raj, R. (2020). The Multiple Flying Sidekicks Traveling Salesman Problem: Parcel Delivery with Multiple Drones. Transportation Research Part C: Emerging Technologies, 110, 368-398. https://doi.org/10.1016/j.trc.2019.11.003
Mizokami, K. (2020). Black Hawk Helicopters Can Now Launch Drones From Midair.
Masmoudi, M. A., Mancini, S., Baldacci, R., & Kuo, Y. H. (2022). Vehicle Routing Problems with Drones Equipped with Multi-Package Payload Compartments. Transportation Research Part E: Logistics and Transportation Review, 164, 102757. https://doi.org/10.1016/j.tre.2022.102757
Matijević, L. (2023). General variable neighborhood search for electric vehicle routing problem with time-dependent speeds and soft time windows.International Journal of Industrial Engineering Computations, 14(2), 275-275. https://doi.org/10.5267/j.ijiec.2023.2.001
Morandi, N., Leus, R., Matuschke, J., & Yaman, H. (2023). The Traveling Salesman Problem with Drones: The Benefits of Retraversing the Arcs. Transportation Science. https://doi.org/10.1287/trsc.2022.0230
Poikonen, S., & Golden, B. (2020). The Mothership and Drone Routing Problem. INFORMS Journal on Computing, 32(2), 249-262. https://doi.org/10.1287/ijoc.2018.0879
Ponza, A. (2016). Optimization of drone-assisted parcel delivery. https://doi.org/10.13140/RG.2.2.24444.56962
Ropke, S., & Pisinger, D. (2006). An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows. Transportation Science, 40(4), 455-472. https://doi.org/10.1287/trsc.1050.0135
Salama, M. R., & Srinivas, S. (2022). Collaborative Truck Multi-Drone Routing and Scheduling Problem: Package Delivery with Flexible Launch and Recovery Sites. Transportation Research Part E: Logistics and Transportation Review, 164, 102788. https://doi.org/10.1016/j.tre.2022.102788
Schermer, D., Moeini, M., & Wendt, O. (2019). A Matheuristic for the Vehicle Routing Problem with Drones and Its Variants. Transportation Research Part C: Emerging Technologies, 106, 166-204. https://doi.org/10.1016/j.trc.2019.06.016
Tamke, F., & Buscher, U. (2021). A Branch-and-Cut Algorithm for the Vehicle Routing Problem with Drones. Transportation Research Part B Methodological, 144, 174-203. https://doi.org/10.1016/j.trb.2020.11.011
Tu, P. A., Dat, N. T., & Dung, P. Q. (2018, December). Traveling salesman problem with multiple drones. In Proceedings of the 9th International Symposium on Information and Communication Technology (pp. 46-53).
Vansteenwegen, P., Souffriau, W., & Van Oudheusden, D. (2011). The Orienteering Problem: A Survey. European Journal of Operational Research, 209(1), 1-10. https://doi.org/10.1016/j.ejor.2010.03.045
Wang, K., Pesch, E., Kress, D., Fridman, I., & Boysen, N. (2022). The Piggyback Transportation Problem: Transporting Drones Launched from a Flying Warehouse. European Journal of Operational Research, 296(2), 504-519. https://doi.org/10.1016/j.ejor.2021.03.064
Wang, X., Poikonen, S., & Golden, B. (2016). The Vehicle Routing Problem with Drones: Several Worst-Case Results. Optimization Letters, 11(4), 679-697. https://doi.org/10.1007/s11590-016-1035-3
Wang, Z., & Sheu, J.-B. (2019). Vehicle Routing Problem with Drones. Transportation Research Part B Methodological, 122, 350-364. https://doi.org/10.1016/j.trb.2019.03.005.
Wen, X., & Wu, G. (2022). Heterogeneous Multi-Drone Routing Problem for Parcel Delivery. Transportation Research Part C: Emerging Technologies, 141, 103763. https://doi.org/10.1016/j.trc.2022.103763
Yoon, J. J. (2018). The traveling salesman problem with multiple drones: an optimization model for last-mile delivery (Doctoral dissertation, Massachusetts Institute of Technology).
Zhao, L., Bi, X., Li, G., Dong, Z., Xiao, N., & Zhao, A. (2022). Robust Traveling Salesman Problem with Multiple Drones: Parcel Delivery under Uncertain Navigation Environments. Transportation Research Part E: Logistics and Transportation Review, 168, 102967. https://doi.org/10.1016/j.tre.2022.102967