Collaborative path optimization of ship and multiple drones for maritime search

Maritime accidents are frequent, making efficient search and rescue operations critical. Traditional rescue ship often encounter challenges such as poor maneuverability and limited visibility. In response, maritime authorities are exploring the use of drones to quickly locate survivors. While drones offer excellent maneuverability, their limited endurance constrains their effectiveness in large-scale maritime searches. To address these challenges, this paper proposes a novel maritime search strategy that combines the sustained operational capabilities of the ship with the agility of drones. Specifically, we formulate a mixed integer linear programming (MILP) model to optimize the collaborated paths of ship and drones, as well as the battery-swapping plans for drones, with the goal of minimizing search time. The model fully accounts for practical factors, including irregular maritime areas, wind and ocean current effects, drone endurance limits, and variable drone and ship speeds. Given the complexity of the MILP model, we developed an adaptive two-stage iterative algorithm (ATIA) to solve the problem. Various experiments were conducted to evaluate ATIA’s performance: for small-scale instances, ATIA’s results deviated from Gurobi’s optimal solutions by no more than 0.3 %; for medium-scale instances, ATIA outperformed Gurobi in both solution quality and computation time. We also derived the problem’s lower bounds under the specified scenario; comparing ATIA’s results with these bounds further validated its effectiveness for large-scale instances. Additionally, numerical experiments showed the number of drones and endurance significantly impact search efficiency-this insight helps determine optimal drone configurations to enhance search performance.