ROBUST VEHICLE PATH PLANNING FOR MARITIME MONITORING UNDER TRAVEL TIME UNCERTAINTY

In this study, we explore the routing and scheduling for an integrated system of unmanned aerial vehicles (UAVs) and unmanned surface vehicles (USVs) in maritime surveillance. The uncertainty in the air and maritime conditions can cause delays for monitoring tasks (might even expose unmanned vehicles to danger). We introduce a robust coordinated path planning approach for the integrated UAV-USV system that aims to optimize operational efficiency while accounting for the travel time unreliability. In particular, we propose a novel robust compact formulation for the coordinated path planning problem of UAVs and USVs based on the budgeted uncertainty set. To solve this complicated formulation, we decompose it into a master problem which is a set partitioning problem and a subproblem that deals with robust resource constrained elementary shortest path. Furthermore, we develop a customized branch and price and cut algorithm to efficiently solve the proposed robust path planning problem. Numerical results demonstrate that the solution obtained by the proposed branch and price and cut algorithm is significantly more robust than that when ignoring uncertainty.