Unmanned Aerial Vehicle Routing Problems: A Literature Review
Source abstract
Abstract
Unmanned aerial vehicle (UAV) routing is transitioning from an emerging topic to a growing research area as the 3D flexible utilization of airspace, promogulated by UAVs, is a potential game changer in solving the urban air mobility challenge by allowing to reshape transportation and logistics in the future. This has revealed a need to classify different types of research and examine the general characteristics of the research area. This research aims to assist in identifying the main topics and emerging research streams and provides a published overview of the current state and contributions to the area of the UAV routing problem (UAVRP) and a general categorization of the vehicle routing problem (VRP) followed by a UAVRP classification with a graphical taxonomy based on the analysis of UAVRP current status. To achieve this, an analysis of the existing research contributions promulgated in this domain is conducted. This analysis is used to identify the current state of UAVRP and the gaps related to the UAVs’ flight dynamics and weather conditions, which significantly influence the fuel consumption of the UAV when modeling the UAVRP.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: UAV Applications and Optimization · Robotic Path Planning Algorithms · Vehicle Routing Optimization Methods
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Transport and Logistics Management, Faculty of Engineering, University of Moratuwa, Moratuwa 10400, Sri Lanka
Faculty of Electronics and Computer Science, Koszalin University of Technology, 75-453 Koszalin, Poland
Department of Materials and Production, Aalborg University, 9220 Aalborg, Denmark
References (100+)
Show source-provided references
1. Solving location and routing problem for UAVs10.1016/j.cie.2016.10.029 ↗
2. Herrera-Viedma, E., Vale, Z., Nielsen, P., Del Rey, A.M., and Vara, R.C. (2019, January 26–28). UAV Mission Planning Subject to Weather Forecast Constraints. Proceedings of the International Symposium on Distributed Computing and Artificial Intelligence, Ávila, Spain.
3. Planning deliveries with UAV routing under weather forecast and energy consumption constraints10.1016/j.ifacol.2019.11.231 ↗
4. A system of UAV application in indoor environment
5. Aerial remote sensing in agriculture: A practical approach to area coverage and path planning for fleets of mini aerial robots10.1002/rob.20403 ↗
6. Zhang, M., Su, C., Liu, Y., Hu, M., and Zhu, Y. (2016). Unmanned Aerial Vehicle Route Planning in the Presence of a Threat Environment Based on a Virtual Globe Platform. ISPRS Int. J. Geo-Inf., 5.10.3390/ijgi5100184 ↗
7. Flight safety measurements of UAVs in congested airspace10.1016/j.cja.2016.08.017 ↗
8. Fused Deposition Modeling for Unmanned Aerial Vehicles (UAVs): A Review10.1002/adem.201700552 ↗
9. Popper, B. (2017, April 11). Drones could make Amazon’s dream of free delivery profitable—The Verge. Available online: http://www.theverge.com/33.
10. UAVs flight routes optimization in changing weather conditions—Constraint programming approach10.35784/acs-2019-17 ↗
11. Bocewicz, G., Nielsen, P., Banaszak, Z., and Thibbotuwawa, A. (2019). A Declarative Modelling Framework for Routing of Multiple UAVs in a System with Mobile Battery Swapping Stations. International Conference on Intelligent Systems in Production Engineering and Maintenance, Springer.10.1007/978-3-319-97490-3_42 ↗
12. Aasen, H., and Gnyp, M.L. (2013, January 9–10). Spectral comparison of low-weight and UAV- based hyperspectral frame cameras with portable spectroradiometers measurements. Proceedings of the Work UAV-Based Remote Sensing Methods for Monitoring Vegetation, Cologne, Germany.
13. Modeling and Solving the Capacitated Vehicle Routing Problem on Trees
14. Thibbotuwawa, A. (2020). Unmanned Aerial Vehicle Fleet Mission Planning Subject to Changing Weather Conditions. [Ph.D. Thesis, Og Naturvidenskabelige Fakultet, Aalborg Universitet].10.3390/app9193972 ↗
15. Zoning a Service Area of Unmanned Aerial Vehicles for Package Delivery Services10.1007/s10846-019-01045-7 ↗
16. The vehicle routing problem: A taxonomic review10.1016/j.cie.2009.05.009 ↗
17. Vehicle Routing Problems for Drone Delivery10.1109/TSMC.2016.2582745 ↗
18. The vehicle routing problem: State of the art classification and review10.1016/j.cie.2015.12.007 ↗
19. Toro, E.M., Escobar, A.H., and Granada, E.M. (2015). Literature Review on the Vehicle Routing Problem in the Green Transportation Context. Luna Azul, 362–387.10.17151/luaz.2016.42.21 ↗
20. Drone-Aided Healthcare Services for Patients with Chronic Diseases in Rural Areas10.1007/s10846-017-0548-z ↗
21. Dynamic vehicle routing: Status and prospects10.1007/BF02098286 ↗
22. Some applications of the generalized vehicle routing problem10.1057/jors.2009.51 ↗
23. Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies10.1016/S0377-2217(02)00915-3 ↗
24. Le Ny, J., Dahleh, M., and Feron, E. (2008, January 11–13). Multi-UAV dynamic routing with partial observations using restless bandit allocation indices. Proceedings of the 2008 American Control Conference, Seattle, WA, USA.10.1109/ACC.2008.4587156 ↗
25. Computational intelligence in control of AGV multimodal systems10.1016/j.ifacol.2018.08.315 ↗
26. Scheduling a single mobile robot for part-feeding tasks of production lines10.1007/s10845-013-0729-y ↗
27. Bocewicz, G., Nielsen, P., Banaszak, Z., and Thibbotuwawa, A. (2018, January 20–22). Routing and Scheduling of Unmanned Aerial Vehicles Subject to Cyclic Production Flow Constraints. Proceedings of the 15th International Conference Distributed Computing and Artificial Intelligence, Toledo, Spain.10.1007/978-3-319-99608-0_9 ↗
28. A methodology for implementation of mobile robot in adaptive manufacturing environments10.1007/s10845-015-1072-2 ↗
29. Simultaneous scheduling of machines and mobile robots
30. Assignment rules in robotic mobile fulfilment systems for online retailers10.1080/00207543.2017.1331050 ↗
31. Determination of robotic melon harvesting efficiency: A probabilistic approach10.1080/00207543.2015.1081428 ↗
32. Extended range tactility in material handling10.1080/00207540050205145 ↗
33. Sequencing of robot activities and parts in two-machine robotic cells10.1080/00207549608905099 ↗
34. Modelling the performance of a mobile robot with RTM10.1080/00207549108930113 ↗
35. An unmanned aerial vehicle-based system for large scale metrology applications10.1080/00207540902896220 ↗
36. Toth, P., and Vigo, D. (2002). The Vehicle Routing Problem, Society for Industrial and Applied Mathematics.10.1137/1.9780898718515 ↗
37. Sonmezocak, E., and Kurt, S. (2010). Optimum Route Planning and Scheduling for Unmanned Aerial Vehicles, Navel Postgraduate School.
38. Toth, P., and Tramontani, A. (2008). An Integer Linear Programming Local Search for Capacitated Vehicle Routing Problems. The Vehicle Routing Problem: Latest Advances and New Challenges, Springer.
39. Models, relaxations and exact approaches for the capacitated vehicle routing problem10.1016/S0166-218X(01)00351-1 ↗
40. A general heuristic for vehicle routing problems10.1016/j.cor.2005.09.012 ↗
41. A literature review on the vehicle routing problem with multiple depots10.1016/j.cie.2014.10.029 ↗
42. The Split Delivery Vehicle Routing Problem: A Survey
43. Stochastic vehicle routing10.1016/0377-2217(95)00050-X ↗
44. A review of dynamic vehicle routing problems10.1016/j.ejor.2012.08.015 ↗
45. Time-dependent vehicle routing problem with path flexibility10.1016/j.trb.2016.10.013 ↗
46. Drexl, M. (2014). A Generic Heuristic for Vehicle Routing Problems with Multiple Synchronization Constraints, Gutenberg School of Management and Economics–Discussion Paper Series.
47. The vehicle routing problem with profits and consistency constraints10.1016/j.ejor.2018.09.046 ↗
48. Archetti, C., Speranza, M.G., and Vigo, D. (2014). Vehicle routing problems with profits. Vehicle Routing: Problems, Methods, and Applications, Society for Industrial and Applied Mathematics. [2nd ed.].10.1137/1.9781611973594.ch10 ↗
49. Planning, operation, and control of bus transport systems: A literature review10.1016/j.trb.2015.03.002 ↗
50. The Green Ship Routing and Scheduling Problem (GSRSP): A conceptual approach10.1016/j.trd.2014.05.014 ↗
51. Wang, X. (2015). Operational Transportation Planning of Modern Freight Forwarding Companies: Vehicle Routing under Consideration of Subcontracting and Request Exchange, Springer Nature.10.1007/978-3-658-06869-1 ↗
52. Industrial aspects and literature survey: Fleet composition and routing10.1016/j.cor.2010.03.015 ↗
53. Kjeldsen, K.H., Ergun, O., Lysgaard, J., and Erera, A. (2011). Rescheduling ships and cargo in liner shipping in the event of disruptions. Liner Shipp, 105–133.
54. Twenty-Five Years of Hub Location Research10.1287/trsc.1120.0410 ↗
55. Holden, J., and Goel, N. (2016). Fast-Forwarding to A Future of On-Demand Urban Air Transportation, Uber Elevate. Available online: https://www.uber.com/info/elevate.
56. Esa, J., Poikonen, E., and Hyvönen, M. (2016). Remote and Autonomous Ships: The Next Steps, Rolls Royce plc. AAWA Position Paper.
57. Zheng, F., Wang, F., Wu, J., and Zheng, X. (2015, January 19–21). A methodology of UAV route planning for fast image mosaicking. Proceedings of the 2015 23rd International Conference on Geoinformatics, Wuhan, China.
58. (2019, May 11). Drones: High-Profile and Niche. Deloitte Touche Tohmatsu Ltd, London, UK. Available online: https://www2.deloitte.com/content/dam/Deloitte/global/Documents.
59. A network flow based heuristic approach for optimising AGV movements10.1007/s10845-011-0612-7 ↗
60. Simultaneous scheduling of machines and automated guided vehicles10.1080/00207549308956904 ↗
61. Dynamic conflict-free routing of automated guided vehicles10.1080/002075499190888 ↗
62. Scheduling and routing algorithms for AGVs: A survey10.1080/00207540110091712 ↗
63. Towards the assessment of potential impact of unmanned vessels on maritime transportation safety10.1016/j.ress.2017.03.029 ↗
64. A multi-objective green UAV routing problem10.1016/j.cor.2017.04.011 ↗
65. Enright, J.J., Frazzoli, E., Pavone, M., and Ketan, S. (2015). Selection of Appropriate Class UAS/Sensors to Support Fire Monitoring: Experiences in the United States, Springer Nature. Handbook of UAVs.
66. A survey of motion planning algorithms from the perspective of autonomous UAV guidance10.1007/s10846-009-9383-1 ↗
67. UAV Control on the Basis of 3D Landmark Bearing-Only Observations10.3390/s151229768 ↗
68. A multi-objective approach for unmanned aerial vehicle routing problem with soft time windows constraints10.1016/j.apm.2013.07.002 ↗
69. Sundar, K., Venkatachalam, S., and Rathinam, S. (2016). An Exact Algorithm for a Fuel-Constrained Autonomous Vehicle Path Planning Problem. arXiv Preprint.
70. Rojas-Viloria, D., Solano-Charris, E.L., Muñoz-Villamizar, A., and Montoya-Torres, J.R. (2020). Unmanned aerial vehicles/drones in vehicle routing problems: A literature review. Int. Trans. Oper. Res.10.1111/itor.12783 ↗
71. The human factor in supply chain forecasting: A systematic review10.1016/j.ejor.2018.10.028 ↗
72. Reactive tabu search in unmanned aerial reconnaissance simulations
73. Visibility Constrained Routing of Unmanned Aerial Vehicles. Signal Processing, Sensor Fusion, and Target Recognition
74. The Vehicle Routing Problem: An overview of exact and approximate algorithms10.1016/0377-2217(92)90138-Y ↗
75. UAV path planning for structure inspection in windy environments10.1007/s10846-012-9778-2 ↗
76. Efficient route planning for an unmanned air vehicle deployed on a moving carrier10.1007/s00500-015-1970-4 ↗
77. Lawler, E.L. (1985). The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley-Interscience Series in Discrete Mathematics.
78. A UAV Allocation Method for Traffic Surveillance in Sparse Road Network
79. Geyer, C., Dey, D., and Singh, S. (2009). Prototype Sense-and-Avoid Sstemy for UAVs, Robotics Institute, Carnegie Mellon University. Report 2009 Tech. Report, CMU-RI-TR-09-09.
80. Fu, Y. (2016). New Development on Sense and Avoid Strategies for Unmanned Aerial Vehicles. [Master’s Thesis, Concordia University].
81. Imanberdiyev, N., Fu, C., Kayacan, E., and Chen, I.M. (2016, January 13–15). Autonomous navigation of UAV by using real-time model-based reinforcement learning. Proceedings of the 2016 14th International Conference on Control, Automation, Robotics and Vision (ICARCV), Phuket, Thailand.10.1109/ICARCV.2016.7838739 ↗
82. Priority-based assignment and routing of a fleet of unmanned combat aerial vehicles10.1016/j.cor.2006.09.013 ↗
83. The vehicle routing problem with drones: Several worst-case results10.1007/s11590-016-1035-3 ↗
84. Algorithms for routing an unmanned aerial vehicle in the presence of refueling depots10.1109/TASE.2013.2279544 ↗
85. Column generation for a UAV assignment problemwith precedence constraints David10.1002/rnc.1722 ↗
86. Karaman, S., and Frazzoli, E. (2006, January 13–15). Vehicle Routing Problem with Metric Temporal Logic Specifications. Proceedings of the IEEE Conf Decis Control, San Diego, CA, USA.
87. Localization with sparse acoustic sensor network using UAVs as information-seeking data mules10.1145/2480730.2480733 ↗
88. Efficient routing of multiple vehicles with no explicit communications10.1002/rnc.1258 ↗
89. The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery10.1016/j.trc.2015.03.005 ↗
90. Devising a quick-running heuristic for an unmanned aerial vehicle (UAV) routing system10.1057/palgrave.jors.2601867 ↗
91. Multi-objective algorithm for blood supply via unmanned aerial vehicles to the wounded in an emergency situation10.1371/journal.pone.0155176 ↗
92. A Branch-and-Bound-Based Solution Approach for Dynamic Rerouting of Airborne Platforms10.1002/nav.21526 ↗
93. Lamont, G.B., Slear, J.N., and Melendez, K. (2007, January 1–5). UAV swarm mission planning and routing using multi-objective evolutionary algorithms. Proceedings of the 2007 IEEE Symposium on Computational Intelligence in Multi-Criteria Decision-Making, Honolulu, HI, USA.10.1109/MCDM.2007.369410 ↗
94. Employing multiple unmanned aerial vehicles for co-operative path planning10.5772/56286 ↗
95. Oberlin, P., Rathinam, S., and Darbha, S. (2003). A Transformation for a Heterogenous, Multiple Depot, Multiple Traveling Salesman Problem. Transformation, 1292–1297.
96. Curvature-constrained traveling salesman tours for aerial surveillance in scenarios with obstacles10.1016/j.ejor.2017.03.067 ↗
97. GPS Denied UAV Routing with Communication Constraints10.1007/s10846-016-0343-2 ↗
98. The Time Dependent Traveling Salesman Planning Problem in Controlled Airspace10.1016/j.trb.2016.04.009 ↗
99. UAV Routing in a Stochastic, Time-Varying Environment
100. Sisson, M.R. (1997). Applying Tabu Heuristic to Wind Influenced, Minimum Risk and Maximum Expected Coverage Routes. Air Force Inst of Tech Wright-Patterson of School of Engineering. [Master’s Thesis, Air Force Institute of Technology].