Location and routing optimization problem for detecting multi-drone ship emissions based on a bi-stage algorithm

A stochastic programming model is devised for the multi-base, multi-drone location and routing problem, considering the simultaneous movements of drones and ships as well as ship movement uncertainty. A decoding algorithm is developed to divide a sequence into sub-routes using ship-based and drone-based strategies. Furthermore, a bi-stage heuristic algorithm is proposed, combining a genetic algorithm and Tabu search. In the bi-stage algorithm, the first stage addresses ship movement uncertainty and employs Tabu search to solve the drone base station location problem. The second stage uses the genetic algorithm to route the drones for detection based on the location results. Numerical experiment results show that, in the same application scenario, the drone-based（D） strategy can optimize flying distance by 7% while reducing computing time by 50% compared to the ship-based（S） strategy. Considering ship movement uncertainty can reduce flying distance by 10% for the drone base station location solution. Flying distance is sensitive to the number of available drones. For example, in a scenario with two base stations and 3-5 drones, adding one drone may increase flying distance by 15%. Speeding up the drones by 5% may reduce flying distance by 5%. This method can effectively generate multi-UAV inspection paths that meet the requirements of moving ships, providing technical support for maritime supervision.