Real-time routing and scheduling of unmanned aerial and surface vehicles for maritime monitoring under travel time and demand uncertainty

Maritime monitoring using unmanned aerial vehicles (UAVs) and unmanned surface vehicles (USVs) has attracted growing attention due to reduced human risk and extended operational coverage. Coordinated routing and scheduling of such fleets, however, are challenged by weather-dependent travel time uncertainty, dynamic task arrivals, and battery endurance constraints. This study develops a dynamic robust optimization framework for coordinated UAV-USV routing and scheduling under these conditions. Using historical travel time data, we construct cluster-wise uncertainty sets that capture context-dependent deviation patterns under different weather conditions. Within a rolling-horizon scheme, routing and scheduling decisions are repeatedly re-optimized based on the most relevant uncertainty cluster, while explicitly accounting for depot-based battery swapping. We formulate a cluster-wise robust optimization (CWRO) model with a global uncertainty budget to prevent excessive conservatism. To solve the problem at scale, we develop a customized branch-and-price-and-cut algorithm for small and medium-sized instances and a column-and-constraint generation based adaptive large neighborhood search for large-scale instances. Numerical experiments based on the Guangdong-Hong Kong-Macau Greater Bay Area show that the proposed methods consistently outperform benchmark implementations based on deterministic, stochastic, and classical robust models, as well as C&CG-based genetic algorithms and commercial solvers, in terms of solution robustness and computational scalability.