Intelligent Drone Swarms to Search for Victims in Post-Disaster Areas.

This study presents the Drone Swarms Routing Problem (DSRP), which consists of identifying the maximum number of victims in post-disaster areas. The post-disaster area is modeled in a complete graph, where each search location is represented by a vertex, and the edges are the shortest paths between destinations, with an associated weight, corresponding to the battery consumption to fly to a location. In addition, in the DSRP addressed here, a set of drones are deployed in a cooperative drone swarms approach to boost the search. In this context, a V-shaped formation is applied with leader replacements, which allows energy saving. We propose a computation model for the DSRP that considers each drone as an agent that selects the next search location to visit through a simple and efficient method, the Drone Swarm Heuristic. In order to evaluate the proposed model, scenarios based on the Beirut port explosion in 2020 are used. Numerical experiments are presented in the offline and online versions of the proposed method. The results from such scenarios showed the efficiency of the proposed approach, attesting not only the coverage capacity of the computational model but also the advantage of adopting the V-shaped formation flight with leader replacements.

Robust min-max regret covering problems.

This article deals with two min-max regret covering problems: the min-max regret Weighted Set Covering Problem (min-max regret WSCP) and the min-max regret Maximum Benefit Set Covering Problem (min-max regret MSCP). These problems are the robust optimization counterparts, respectively, of the Weighted Set Covering Problem and of the Maximum Benefit Set Covering Problem. In both problems, uncertainty in data is modeled by using an interval of continuous values, representing all the infinite values every uncertain parameter can assume. This study has the following major contributions: (i) a proof that MSCP is Σ p 2 -Hard, (ii) a mathematical formulation for the min-max regret MSCP, (iii) exact and (iv) heuristic algorithms for the min-max regret WSCP and the min-max regret MSCP. We reproduce the main exact algorithms for the min-max regret WSCP found in the literature: a Logic-based Benders decomposition, an extended Benders decomposition and a branch-and-cut. In addition, such algorithms have been adapted for the min-max regret MSCP. Moreover, five heuristics are applied for both problems: two scenario-based heuristics, a path relinking, a pilot method and a linear programming-based heuristic. The goal is to analyze the impact of such methods on handling robust covering problems in terms of solution quality and performance.