After a major disaster, it is very likely that access to some areas can be extremely difficult due to the damage caused by the disaster itself, road congestion or blockages, or even the contamination of dangerous products. This was the case of the Beirut port explosion in Lebanon in 2020 that caused several causalities, more than 7000 injured people, and left about 30,000 homeless [1]. In this context, an alternative strategy to circumvent the aforementioned accessibility difficulties is to use drones to perform tasks such as the distribution of drugs and food, the detection of ground conditions, and to search for victims. They can also quickly access hard-to-reach areas. An extensive study in [2] demonstrates the capabilities, performance outcomes and barriers of using drones in the context of humanitarian logistics.

In such a context, the search for victims is a crucial operation and must be well-planned and carried out with extreme efficiency to save lives. The search for victims can be supported by the use of drones. Moreover, the search can be boosted by using a fleet of drones equipped with optical and thermal cameras, flying in a coordinate swarm. This allows them to share updated information about the area, to be more efficient in scanning the area, and also to save energy using a special flight organization. As shown in [3], energy consumption can be reduced by applying a V-shaped formation with leader replacements, which is inspired by bird flight.

The search for victims using drone swarms involves not only solving a path planning problem [4], but also solving an optimization problem for finding the route that minimizes/maximizes a given criterion, which is the main focus of this study. More specifically, this study proposes the Drone Swarms Routing Problem (DSRP) and consists of defining routes for drone swarms in order to maximize the number of victims identified. The novelties of the DSRP are the consideration of the cooperative and decentralized flight of drone swarms, where they decide on the fly if they scan a location together or not. The interest of using such a strategy is to cover faster an area and to save energy, by means of an appropriate swarm organization. Civil drones still have low autonomy, which makes scanning large areas difficult. Moreover, the hydrogen technology for drones is not yet operational. This study extends the work of [5], in which, drones fly independently of each other with routes predefined by a control center.

A computational model to solve the DSRP, using the concept of Multi-Agents Systems (MAS), where drones are agents able to analyze information about the post-disaster area, and smartly select the next search location to perform the search for victims. For such a purpose, a Drone Swarm Heuristic (DSH) is applied to carry out the decision step of the drones. The proposed method is tested over a case study inspired by the Beirut port explosion in 2020. Numerical experiments considering offline and online versions of the method are presented. In the former, the input data are predefined, while in the latter, data changes during the execution of the model. The DSRP solutions produced by the proposed method are also observed in the robot simulator CoppeliaSim [6] to simulate their execution step-by-step.

2. Optimization Surveys

In the scientific literature, there is growing interest in the use of drones, as can be noticed by the number of surveys published and the number of papers they analyze. From 2001 to 2017 more than 200 papers with optimization approaches for civil applications of drones were reviewed in ^[7][8], such as area coverage, search operations, routing, data gathering, networks of drones, communication linking and computing power to mobile devices. In ^[8][9], the authors classified 79 relevant publications from 2005 to 2019 that address Drone Routing Problems (DRP) modeled as a VRP. Survey ^[9][10] reviewed 63 papers, from 2015 to 2020, related to routing problems for four main problem classes: (1) the traveling salesman problem with drones; (2) the vehicle routing problem with drones; (3) the drone delivery problem and (4) the carrier-vehicle problem with drones. A survey and a framework for classifying drone-based delivery systems is presented in ^[10][11] and this framework was used to classify 101 related papers according to their objectives, methods, applications and constraints. The authors in ^[11][12] did an extensive analysis of articles published from January 2005 to June 2022, identifying 135 articles that explore various aspects of VRP problems. These surveys are very interesting entry points for researchers looking for the state-of-the-art on a wide range of topics involving optimization problems involving drones, like exact and heuristic solution methods, novel problem variants like drone routing, and emerging research areas such as green routing.

3. Offline and Centralized DRP Approaches

Some studies investigate variants of DRPs in the post-disaster context, proposing both methods and case studies. The DRPs can be addressed by adopting an offline or online approach. Offline computation is very often used for static and centralized approaches when there is enough time for decision-making. On the other hand, online computation is commonly used for dynamic and decentralized approaches, when the time for decision-making is a hard constraint, being taken in almost “real time”. All the works cited in this section consider offline computation with a centralized approach. The authors in ^[12][13] address a DRP to recognize a post-earthquake area, where the objective is to find the shortest path to visit each site affected by the earthquake and to check the state of building damage. A simulated annealing was proposed and was applied to instances generated from the city of Acireale (Italy), finding good solutions with two drones. Another DRP to assess post-disaster areas using drones and motorcycles is studied in ^[13][14], where a bi-objective mathematical model for maximizing the total importance of population centers (nodes) and road segments (arcs) is presented. The bi-objectives are optimized by means of an 𝜖-constraint method, together with a heuristic to solve the problem on instances based on Istanbul’s Kartal district (Turkey). The results show that a high-quality approximation of the Pareto front can be found using the proposed methodology. Study ^[14][15] presents a DRP that uses gliders to collect useful information for assessing the extent of the disaster’s consequences by visiting the post-disaster locations as fast as possible. They also propose a solution to this problem by linearizing a Mixed-Integer Nonlinear Programming (MINLP) formulation that optimizes the routes and the trajectories along these routes. The MINLP formulation is tested on random instances and on instances based on flooding-prone cities of the United Kingdom (UK). These instances are divided into small and medium ranges and they contain up to 10 waypoints, 2 landing zones and 3 gliders. The strategy is able to prove optimal solutions for some test cases, contrary to large test cases with more waypoints and a medium to large size. A heterogeneous fixed fleet DRP is considered in ^[15][16] with the objective of minimizing the inspection cost of a post-disaster area. In order to solve it, the authors propose a Mixed-Integer Linear Programming (MILP) model and two heuristics, an Adaptive Large Neighborhood Search (ALNS) algorithm and a Modified Backtracking Adaptive Threshold Accepting (MBATA) one. The algorithms were tested on instances generated over Hancock county from Mississippi State (USA) and produced high-quality solutions in a reasonable time.

4. Online and Decentralized MRTA Approaches

Considering the field of multi-agent systems (MAS), the Multi-Robot Task Allocation (MRTA) is a problem commonly found problem (see ^[16][17] for more information on MRTA). The MRTA is an analogous problem to the VRP in which tasks are defined in terms of location. Furthermore, the MRTA problems can be also solved by adopting offline or online approaches. Several studies consider MAS with an online approach to solve different MRTA problems, but there is a lack of studies that address MRTA in post-disaster areas. The authors in ^[17][18] present a MRTA in which robots (drones) with limited range and payload must accomplish tasks with deadlines that are generated during the search. The MRTA goal is to deliver survival kits to spatially distributed victims after a flood disaster. An Integer Linear Programming (ILP) formulation is presented to solve the offline version of the problem as well as an online method, named BiG-MRTA, that combines a bipartite graph construction with a model that assigns edge weights to the graph, and allocates tasks, by solving a maximum weighted matching problem. Each task can be allocated to only one agent and task selection is performed in a myopic way, i.e., at each iteration, an agent selects the next task to undertake considering an acquisition function that balances exploitation and exploration. The algorithms were run on instances generated from South Hilo district, Hawaii. The results show that the BiG-MRTA is more than 10³ times efficient than the ILP, and it can also offer up to 46% higher task completion when compared to a random walk baseline in problems with 1000 tasks.

5. V-Shaped Formation

Another inspiration for theour work comes from [3], in which the authors study the energy conservation of V-shaped swarming flight for fixed-wing drones. The study has shown that the V-shaped formation drones can save up to 70% of their energy, and that adopting leader replacements during the flight, a further 21% of their energy is saved, consequently, increasing the flight time and the distance travelled.