Abstract: In response to global maritime greenhouse gas emission reductions, many countries have strengthened the monitoring and management of vessel emissions in recent years. With the rapid development of drone and remote sensing technologies, drones are gradually becoming an important platform for ship emission monitoring due to their advantages such as high resolution and flexibility. The drone routing problem needs to consider factors such as the movement of vessels, the impact of weather conditions on cruising time, coordination of multiple types of payloads, and the heterogeneity of drones. This paper investigates a time-dependent drone routing problem for vessel monitoring (TDDRPVM). A modeling framework based on time-expanded networks is developed to characterize the position changes of vessels within the scheduling horizon, and a time-dependent drone cruising time function considering wind speed is proposed. A mixed-integer linear programming model is formulated. A variable neighborhood search algorithm with beam pruning and progressive disturbance (VNS-BPPD) is proposed, which includes a dynamic programming algorithm based on the beam pruning strategy and a path combination evaluation strategy as the decoding procedure. A neighborhood search structure with four neighborhood operators is designed, and a progressive disturbance strategy is introduced to gradually increase the disturbance intensity. Numerical experiments are conducted. The effectiveness of the TDDRPVM model and VNS-BPPD is verified based on datasets of different scales, and compared with Gurobi and customized genetic algorithm. The effects of different scheduling periods on the total reward are analyzed. Ablation experiments further quantify the effectiveness of the operators of VNS-BPPD. The sensitivity experiments analyze the impact of variations in vessel speed and wind speed on the total reward. The study provides decision support for optimizing drone deployment and monitoring routes under dynamic vessel positions and time-varying wind conditions.

Key words: routing problem, time-dependent cruising time, variable neighborhood search algorithm, drone, vessel emission monitoring