Transporting Blood Using Unmanned Aerial Vehicles: History
View Latest Version
Please note this is an old version of this entry, which may differ significantly from the current revision.
Contributor:
Sumayah Al-Rabiaah
,
Manar Hosny
,
Sarab AlMuhaideb

Unmanned Aerial Vehicles (UAVs) play crucial roles in numerous applications, such as healthcare services. For example, UAVs can help in disaster relief and rescue missions, such as by delivering blood samples and medical supplies.

  • UAV-based Capacitated Vehicle Routing Problem
  • routing and scheduling
  • heuristics
  • healthcare
  • transporting blood

1. Introduction

Natural disasters—such as earthquakes, volcanoes, avalanches, tornadoes, forest fires, and floods—rank among the greatest threats to humanity and the environment. They have a tragic impact on lives, where they leave behind critical injuries and change and affect the terrain. Patients in emergency or post-disaster situations often encounter difficulties obtaining medical help and supplies (especially blood) in a timely manner. Sending blood supplies to injured patients in inaccessible locations can prove indispensable in saving human lives. The greatest challenge in sending blood to patients is the difficulty or impossibility (in most cases) of using land transportation due to post-disaster environmental conditions and transportation infrastructures (e.g., roads might become obstructed, and bridges might be cracked [1]). Moreover, the blood temperature may change during transportation.
To transcend these challenges, it is crucial to design and implement an efficient algorithm to assist patients in emergency or post-disaster situations using transport that is not hampered by transportation infrastructure and is not much more expensive than land transportation. This aim can be accomplished by utilizing Unmanned Aerial Vehicles (UAVs). UAVs have proven suitable in various applications when used in harsh conditions, such as agriculture, transport, aerial photography, and data collection [2]. In addition, UAVs have been utilized in healthcare applications (Figure 1). For example, UAVs were used to deliver medicines and temperature-sensitive COVID-19 vaccines in Malawi [3], Zipline UAVs were used to transport vaccines and blood [4], UAVs were used to track malaria outbreaks in Africa [5], and Shenzhen Smart UAVs were used to spray chemical substances to reduce the prevalence of COVID-19 in China [6].
Electronics 11 03399 g001
Figure 1. Example of using drones to transport blood. Reprinted with permission from ref. [7]. Copyright 2022 Shutterstock, Inc.
However, healthcare applications require distinct considerations related to their circumstances and how to maximize their services. For example, blood should be delivered to patients quickly while guaranteeing the blood’s viability [8]. In such instances, the compliance of healthcare applications with these considerations proves critical [8][9].
In light of the above points, the problems in emergency situations that healthcare workers may face—namely, the delivery of viable blood to patients using the smallest number of UAVs and the shortest routing distance [10]. In the literature, this problem is known as the UAV-based Capacitated Vehicle Routing Problem (UCVRP) [10], which is concerned with finding the optimal or a near-optimal solution for the UAV-based Capacitated Vehicle Routing Problem for delivering blood to patients in emergency situations. The UCVRP is a variant of the well-known Capacitated Vehicle Routing Problem (CVRP). The CVRP is a typical NP-hard combinatorial optimization problem [11]. Typically, NP-hard problems are solved by heuristic or metaheuristic algorithms [12][13][14], which can obtain optimal or near-optimal solutions in a fast time with a low computational cost compared to exact methods. In addition, large problem sizes cannot be solved to optimality using exact methods. Thus, since the problem size of the UCVRP is large and the optimal solution is not known, the most common approach in the literature is to use approximate methods (i.e., heuristics and metaheuristics) and compare the new obtained solutions with the best known solutions [11].
A novel heuristic that solves the UCVRP, referred to as the Greedy Battery—Distance Optimizing Heuristic (GBDOH). The innovative aspects of the GBDOH are as follows: (1) dealing with the problem as a single-objective problem to simplify the solution approach, (2) considering the lowest battery consumption as a factor in assigning patients to UAVs in order to minimize the number of UAVs used, and (3) reordering the patients of each UAV (considering the amount of water needed to keep the blood viable) in order to minimize the total routing distance.
Being an approximate method, the GBDOH does not guarantee the optimal solution, but it strives to provide a tradeoff between the quality of the current best solution and the computational time. When compared with the MOEA/D-N-UVRP (multi-objective evolutionary algorithm based on decomposition using a local search with random nearest neighbors to solve unmanned vehicle routing problems) method used in [10] to deliver valid blood samples to patients from a single depot, the GBDOH could solve the UCVRP with fewer UAVs within a short travel distance. In fact, when comparing greedy heuristics with iterative algorithms, complexity is typically lower for the former [11].
In summary, the principal idea of the GBDOH is to first assign patients to UAVs based on the lowest battery consumption while considering the UAV’s capacity constraint, in order to serve as many patients as possible with a single UAV. This approach, in turn, minimizes the number of UAVs used. After that, researchers can rearrange the patients of each UAV to minimize the fleet’s total routing distance.

2. Items Delivery Blood Using Unmanned Aerial Vehicles

In reality, the CVRP using UAVs has crucial applications—especially for healthcare, in post-disaster scenarios, or when attempting to reach difficult-to-reach regions. However, many factors require consideration, including the UAV’s capacity, battery life, flying range, and other variables [15]. Minimizing the number of UAVs used and the total routing distance reduces operational costs and enhances the use of resources. Moreover, the short routing distance from the healthcare provider (depot) to patients proves crucial in responding swiftly to medical emergencies.
The UAV-based Capacitated Vehicle Routing Problem (UCVRP) was introduced by Wen et al. [10] and is the problem that researchers study in this research. The authors addressed the Capacitated Vehicle Routing Problem of delivering blood to patients using UAVs. They implemented a multi-objective evolutionary algorithm based on decomposition using a local search with a random nearest neighbor to solve the unmanned vehicle routing problem (MOEA/D-N-UVRP). The aim was to minimize the routing distance between the depot and patients, as well as the number of UAVs used. The authors applied a multi-objective evolutionary algorithm with a local search method on a CVRP public benchmark dataset. What distinguishes this research is that the authors studied blood temperature and considered appending heating or cooling objects to keep the blood suitable for use. However, dealing with the problem as a multi-objective optimization problem can cause difficulties as compared to splitting the objectives and dealing with each separately. In addition, evolutionary algorithms and local search need time to provide viable results, which does not prove suitable for emergency situations in healthcare, where the response time to patients constitutes a critical factor.
Wikarek et al. [16] used a binary integer linear programming model for solving the CVRP using drones. The model tries to minimize the distance between customers and the depot, which is a truck that moves. Kitjacharoenchaia et al. [17] solved the CVRP using trucks and drones with mixed integer programming. This approach sought to minimize the total traveling time. Both [16][17] used exact methods that limit the size of the instances tackled.
Other works addressed problems related to the CVRP using UAVs with different objectives, or did not rely on UAVs alone, i.e., they used a combination of trucks and drones. In [18], Ozkan studied the transfer of blood products from distribution centers (i.e., multiple depots) to hospitals in cities using UAVs. The problem involved two objectives: minimizing the number of UAVs, and minimizing the total traveling distances under the UAVs’ constraints. Ozkan attempted to solve this problem by implementing a Multi-Objective Integer Programming (MOIP) model and three multi-objective metaheuristics: the first relied on simulated annealing, the second relied on local search, and the last depended on genetic algorithms. The metaheuristic methods obtained better results than MOIP because of the nature of the dataset. In [8], the study dealt with optimal path planning for emergency medical deliveries using UAVs and vehicles with a single depot, using four distinct metaheuristic algorithms. However, in both [8][18], the metaheuristic methods required a long time to obtain suitable results since they tested numerous neighborhood moves, increasing the response time and proving inappropriate for emergency situations. Dorling et al. [19] investigated vehicle routing problems using UAVs; they considered the UAVs’ limited capacity and the effect of the weight of the drone on battery consumption. They found that if two UAVs with different weights travel the same distance, the heavier drone consumes more battery than the lighter one. Jiang et al. [20] studied vehicle routing problems with time windows for UAV task assignment considering a limited payload. They compared the proposed method (i.e., an improved particle swarm optimization algorithm) with a genetic algorithm and found that the proposed method proved suitable to solve the UAV task assignment problem. Chase and Ritwik [21] designed a new model for the multiple flying sidekicks traveling salesman problem, which was intended to minimize the time needed to deliver all parcels by drone and return to the depot. In [22], Wusheng Liu et al. proposed a delivery method to minimize the total delivery distance in mountain cities using a truck with UAVs. In [23], Mustapha Ouiss et al. attempted to solve the routing problem using drones to deliver medicine from multiple depots. The goal was to find optimal drone routes using genetic algorithms. Minh Nguyen et al. [24] invented a new optimization problem known as the min-cost Parallel Drone Scheduling Vehicle Routing Problem (PDSVRP) that attempted to minimize the package transporting costs using multiple trucks and drones, i.e., total traveling costs. Xinwei Chen et al. [25] built a deep Q-learning model to deliver packages to customers using drones and trucks. They assigned a customer to a truck and a drone to an order, aiming to maximize the number of served customers. Khin Thida San et al. [26] attempted to solve a drone routing problem in which the drones had different specifications and the flight served one location; the objective was to minimize the total time required.
UAV routing has become a burgeoning field of study. However, the healthcare domain—in comparison to other applications, such as parcel delivery—has received insufficient attention. Thus, the literature features few studies of using UAVs in healthcare, despite their importance in preserving human lives and easing the strain on healthcare facilities and individual patients. With the ongoing COVID-19 pandemic, the scarcity of studies in this field has become even more apparent, because UAV applications have made it simpler to supply services to remote and difficult-to-reach places while also being cheaper, safer, and faster than traditional methods of transportation. Another key finding of this review is that exact approaches lack suitability for solving huge datasets of the UCVRP and its variants. Since the UCVRP is an NP-hard problem [10][11], exact methods require extensive processing time to generate solutions. Therefore, existing research tends to use heuristics and metaheuristics to find near-optimal solutions (in terms of quality) with a reasonable processing time for real-world and healthcare emergency applications with enormous datasets.

This entry is adapted from the peer-reviewed paper 10.3390/electronics11203399

References

  1. Fukubayashi, Y.; Kimura, M. Improvement of rural access roads in developing countries with initiative for self-reliance of communities. Soils Found. 2014, 54, 23–35.
  2. Otto, A.; Agatz, N.; Campbell, J.; Golden, B. Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey. Networks 2018, 72, 411–458.
  3. Crumley, B. Swoop Aero drones deliver Pfizer COVID-19 vaccines in Malawi—DroneDJ. Available online: https://dronedj.com/2022/03/02/swoop-aero-drones-deliver-ultra-cold-pfizer-covid-19-vaccines-in-malawi/ (accessed on 8 June 2022).
  4. Dickson, I. Flying pharmacy: Why Medical Drones Will Take Off in 2022. Available online: https://360.here.com/medical-drones (accessed on 8 June 2022).
  5. Harrisberg, K.; Pensulo, C. From drones to data: New Innovations Are Supporting Africa’s Health Systems. Available online: https://www.weforum.org/agenda/2022/05/drones-to-data-africans-turn-to-healthtech/ (accessed on 8 June 2022).
  6. Liu, Y. China adapts Surveying, Mapping, Delivery Drones To Enforce World’s Biggest Quarantine And Contain Coronavirus Outbreak | South China Morning Post. Available online: https://www.scmp.com/business/china-business/article/3064986/china-adapts-surveying-mapping-delivery-drones-task (accessed on 27 September 2022).
  7. Drone First Aid Kit On Blue Stock Illustration 1633656133 | Shutterstock. Available online: https://www.shutterstock.com/image-illustration/drone-first-aid-kit-on-blue-1633656133 (accessed on 30 August 2022).
  8. Khan, S.I.; Qadir, Z.; Munawar, H.S.; Nayak, S.R.; Budati, A.K.; Verma, K.D.; Prakash, D. UAVs path planning architecture for effective medical emergency response in future networks. Phys. Commun. 2021, 47, 101337.
  9. Chung, S.H.; Sah, B.; Lee, J. Optimization for drone and drone-truck combined operations: A review of the state of the art and future directions. Comput. Oper. Res. 2020, 123, 105004.
  10. Wen, T.; Zhang, Z.; Wong, K.K.L. Multi-objective algorithm for blood supply via unmanned aerial vehicles to the wounded in an emergency situation. PLoS ONE 2016, 11, e0155176.
  11. El-Ghazali, T. Metaheuristics: From Design to Implementation, 2nd ed.; John Wiley & Sons: Hoboken, NJ, USA, 2009; ISBN 9780470278581.
  12. Sajid, M.; Singh, J.; Haidri, R.A.; Prasad, M.; Varadarajan, V.; Kotecha, K.; Garg, D. A Novel Algorithm for Capacitated Vehicle Routing Problem for Smart Cities. Symmetry 2021, 13, 1923.
  13. Accorsi, L.; Vigo, D. A Fast and Scalable Heuristic for the Solution of Large-Scale Capacitated Vehicle Routing Problems. Transp. Sci. 2021, 55, 832–856.
  14. Thibbotuwawa, A.; Bocewicz, G.; Nielsen, P.; Banaszak, Z. Unmanned Aerial Vehicle Routing Problems: A Literature Review. Appl. Sci. 2020, 10, 4504.
  15. Al-rabiaah, S.; Hosny, M.; Almuhaideb, S. An Efficient Greedy Randomized Heuristic for the Maximum Coverage Facility Location Problem with Drones in Healthcare. Appl. Sci. 2022, 12, 1403.
  16. Wikarek, J.; Sitek, P.; Zawarczyński, Ł. An integer programming model for the capacitated vehicle routing problem with drones. In Proceedings of the ICCCI 2019: International Conference on Computational Collective Intelligence, Hendaye, France, 4–6 September 2019; Volume 11683, pp. 511–520.
  17. Kitjacharoenchai, P.; Lee, S. Vehicle routing problem with drones for last mile delivery. In Procedia Manufacturing, Proceedings of the 25th International Conference on Production Research Manufacturing Innovation: Cyber Physical Manufacturing, Chicago, IL, USA, 9–14 August 2019; Elsevier: Amsterdam, The Netherlands, 2019; Volume 39, pp. 314–324.
  18. Ozkan, O. Multi-objective optimization of transporting blood products by routing UAVs: The case of Istanbul. Int. Trans. Oper. Res. 2022, 30, 302–327.
  19. Dorling, K.; Member, S.; Heinrichs, J.; Messier, G.G.; Magierowski, S. Vehicle Routing Problems for Drone Delivery. IEEE Trans. Syst. Man, Cybern. Syst. 2017, 47, 70–85.
  20. Jiang, X.; Zhou, Q.; Ye, Y. Method of Task Assignment for UAV Based on Particle Swarm Optimization in logistics. In Proceedings of the The 2017 International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence, Association for Computing Machinery, New York, NY, USA, 25 March 2017; pp. 113–117.
  21. Murray, C.C.; Raj, R. The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones. Transp. Res. Part C Emerg. Technol. 2020, 110, 368–398.
  22. Liu, W.; Li, W.; Zhou, Q.; Die, Q.; Yang, Y. The optimization of the “UAV-vehicle” joint delivery route considering mountainous cities. PLoS ONE 2022, 17, e0265518.
  23. Ouiss, M.; Ettaoufik, A.; Marzak, A.; Tragha, A. A Parallel Genetic Algorithm for Solving the Vehicle Routing Problem with Drone Medication Delivery; Springer: Singapore, 2022; pp. 225–233.
  24. Nguyen, M.A.; Dang, G.T.H.; Hà, M.H.; Pham, M.T. The min-cost parallel drone scheduling vehicle routing problem. Eur. J. Oper. Res. 2022, 299, 910–930.
  25. Chen, X.; Ulmer, M.W.; Thomas, B.W. Deep Q-learning for same-day delivery with vehicles and drones. Eur. J. Oper. Res. 2022, 298, 939–952.
  26. Thida San, K.; Chang, Y.S. Drone-based delivery: A concurrent heuristic approach using a genetic algorithm. Aircr. Eng. Aerosp. Technol. 2022, 94, 1312–1326.
More
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.
This entry is offline, you can click here to edit this entry!
Video Production Service
Feedback