A Hybrid Lagrangian-Relaxation Framework for Drone-Based Facility Location Decisions

Strategic drone-delivery planning couples field locations with drone assignments and customer allocations under field capacity, cumulative payload, and round-trip energy constraints. We formulate this problem as a mixed-integer linear program and derive a Lagrangian primal heuristic with capacity-aware recovery and facility-exchange search. We show that the Lagrangian dual equals the linear-programming relaxation of the original model. For divisible demand, integer drone counts yield an exact reformulation that removes interchangeable drone labels; type-specific allocation flows extend the result to heterogeneous fleets. Experiments on 45 synthetic instances assess feasible solution quality against independent bounds. A same-machine comparison shows that the count formulation solves all 15 instances with 30 customers to optimality, while the Lagrangian heuristic has a mean objective excess of 0.72%. The count formulation also supplies incumbents and bounds for all 60- and 100-customer instances. Resource experiments distinguish changes in optimal planning cost from variation in heuristic solutions: payload tightening leaves the optimum unchanged over the tested ample fleet range, whereas a restrictive battery budget increases cost in a designated random-layout instance. The computational results favor the compact formulation for the tested divisible-demand model and identify the conditions under which the Lagrangian search improves feasible plans.