Drone scheduling to monitor vessels in emission control areas

The use of drones to monitor the emissions of vessels has recently attracted wide attention because of its great potentials for enforcing regulations in emission control areas (ECAs). Motivated by this potential application, we study how drones can be scheduled to monitor the sailing vessels in ECAs, which is defined as a drone scheduling problem (DSP) in this paper. The objective of the DSP is to design a group of flight tours for drones, including the inspection sequence and timings for the vessels, such that as many vessels as possible can be inspected during a given time period while prioritizing highly weighted vessels for inspection. We show that the DSP can be regarded as a generalized team orienteering problem, which is known to be NP-hard, and deriving solutions for this problem can be more difficult because additional complicated features, such as time-dependent locations, multiple trips for a drone, and multiple stations (or depots), are addressed simultaneously. To overcome these difficulties, we model the dynamics of each sailing vessel using a real-time location function in a deterministic fashion. This approach allows us to approximately represent the problem on a time-expanded network, based on which a network flow-based formulation can be formally developed. To solve this proposed formulation, we further develop a Lagrangian relaxation-based method that can obtain near-optimal solutions for large-scale instances of the problem. Numerical experiments based on practically generated instances with 300 time points and up to 100 vessels are conducted to validate the effectiveness and efficiency of the proposed method. Results show that our method derives tight upper bounds on optimal solutions, and can quickly return good feasible solutions for the tested instances. We also conduct experiments based on realistic tracking data to demonstrate the usefulness of our solutions, including those for the cases considering the uncertainty of vessel locations.