Routing a Fleet of Drones from a Base Station for Emission Detection of Moving Ships by Genetic Algorithm

Abstract

A fleet of drones is considered in the routing problems with an offshore drone base station, considering the simultaneous movements of drones and ships. A model, entitled meeting model, between a drone and a moving ship is devised, and an extended model is developed based on the vehicle routing problem model. A genetic algorithm based on a sequential insert heuristic (SIH) is designed to solve the model as a holistic framework with two strategies to determine the sequential assignments of ships to drones, namely, the DroneByDrone, and ShipByShip strategies. The proposed models and solution algorithms are demonstrated and verified by experiments. Numerical studies show that the DroneByDrone strategy can overperform the ShipByShip strategy regarding traveling distances. In addition, when considering the simultaneous movement of the ship and drone, improving the drone flying speeds can reduce the flying time of drones rather than optimizing the ship’s moving speed. The managerial implications and possible extensions are discussed based on modeling and experimental studies.

Keywords

• ship emission estimation
• emission control area
• vehicle routing problem
• drone routing problem
• sequential insert heuristic model