A relax-and-fix-based heuristic for the problem of locating facilities with maximum coverage and drone deliveries

The growth in urban demand for fast deliveries drives the use of drones in last-mile logistics. This paper addresses the Maximum Coverage Capacitated Facility Location Problem with Drones (MCFLPD), which seeks to define the opening of bases and the allocation of customers to maximize coverage, subject to energy and capacity constraints. Due to the intractability of exact methods for this NP-Hard problem, the literature presents heuristics and metaheuristics. As an alternative in balancing quality and computational time, this work proposes a constructive relax and fix based matheuristic. The approach decomposes the original problem into three integrated phases: infrastructure selection, progressive demand allocation based on an energy radius, and fleet allocation. Experiments have shown that the method achieves coverage levels close to those of the exact approach, with significantly shorter times, and competitive performance compared to heuristics in the literature, with an advantage in resource-limited scenarios.