Drone scheduling optimization for continuous sea area monitoring

Drones equipped with industrial sensors offer a promising solution for environmental surveillance. This paper studies a new drone scheduling problem for sea area emission surveillance, where drones are utilized to monitor vessel emissions across a continuous sea area for a given planning horizon. The challenges of this optimization problem stem from the varying monitoring requirements within a continuous area due to vessel dynamics and the operational issues of drone deployment, such as multi-trip operations. To address these issues, we discretize the continuous sea area using hexagonal grids and represent the problem through a time-expanded network, resulting in a mixed-integer linear programming formulation for its optimization. To solve large-scale instances, we propose a Lagrangian relaxation-based approach enhanced with a customized lower bounding heuristic. Numerical experiments demonstrate that our approach is very effective and efficient in obtaining high-quality solutions. We conduct a real-world case study based on the Gulf of Mexico’s AIS data to examine the practical implementation of the proposed optimization tool. Furthermore, we investigate how the drone’s operational factors, including the sensor range, endurance, and operational flexibility, affect the monitoring performance.