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.
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 
). 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 
. 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 
, Zipline UAVs were used to transport vaccines and blood 
, UAVs were used to track malaria outbreaks in Africa 
, and Shenzhen Smart UAVs were used to spray chemical substances to reduce the prevalence of COVID-19 in China 
Example of using drones to transport blood. Reprinted with permission from ref. 
. 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 
. In such instances, the compliance of healthcare applications with these considerations proves critical 
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 
. In the literature, this problem is known as the UAV-based Capacitated Vehicle Routing Problem (UCVRP) 
, 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 
. Typically, NP-hard problems are solved by heuristic or metaheuristic algorithms 
, 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 
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 
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 
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 
. 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. 
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. 
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. 
solved the CVRP using trucks and drones with mixed integer programming. This approach sought to minimize the total traveling time. Both 
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 
, 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 
, 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 
, 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. 
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. 
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 
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 
, Wusheng Liu et al. proposed a delivery method to minimize the total delivery distance in mountain cities using a truck with UAVs. In 
, 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. 
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. 
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. 
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 is that exact approaches lack suitability for solving huge datasets of the UCVRP and its variants. Since the UCVRP is an NP-hard problem 
, 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.