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

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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="normal">D</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">n</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">B</mi><mi mathvariant="normal">y</mi><mi mathvariant="normal">D</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">n</mi><mi mathvariant="normal">e</mi><mo>,</mo></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="normal">S</mi><mi mathvariant="normal">h</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">p</mi><mi mathvariant="normal">B</mi><mi mathvariant="normal">y</mi><mi mathvariant="normal">S</mi><mi mathvariant="normal">h</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">p</mi></mrow></semantics></math></inline-formula> strategies. The proposed models and solution algorithms are demonstrated and verified by experiments. Numerical studies show that the <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="normal">D</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">n</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">B</mi><mi mathvariant="normal">y</mi><mi mathvariant="normal">D</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">n</mi><mi mathvariant="normal">e</mi></mrow></semantics></math></inline-formula> strategy can overperform the <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="normal">S</mi><mi mathvariant="normal">h</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">p</mi><mi mathvariant="normal">B</mi><mi mathvariant="normal">y</mi><mi mathvariant="normal">S</mi><mi mathvariant="normal">h</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">p</mi></mrow></semantics></math></inline-formula> 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.