Drone station location and routing optimization for infrastructure inspection

Recent advancements in drone technology have expanded drone applications in logistics, humanitarian aid, and infrastructure surveillance. Motivated by the demand for drone-based infrastructure inspection and the emerging design of drone battery swapping stations, this paper introduces the location routing problem with heterogeneous stations and drones (LRPHSD). In the problem, two types of stations are considered: one that supports a single drone, and another that accommodates two heterogeneous drones with different battery capacities. The objective is to determine the locations and types of stations, along with the multi-trip routes of drones, to minimize the total cost. We formulate the LRPHSD as a mixed-integer linear programming model and develop a two-stage adaptive large neighborhood search algorithm (TSALNS) for resolution. Numerical results show that for large-sized LRPHSD instances, TSALNS can efficiently find solutions comparable to or better than those obtained by Gurobi within a 3600-second time limit. For classical location routing problem instances, TSALNS provides solutions with optimality gaps of around 3% for instances with over 150 nodes in under two minutes. The results based on simulated data and a real-world case study collectively demonstrate that a heterogeneous station-drone configuration can achieve a better balance between cost and task completion time compared to various homogeneous configurations.