Drone routing problem for shore-to-ship delivery services considering non-linear energy consumption

This study investigates the emerging application of unmanned aerial vehicles (UAVs), or drones, for shore-to-ship delivery services between onshore and offshore locations. However, deploying drones for shore-to-ship delivery can encounter unique operational challenges, including constantly moving target vessels and non-linear drone energy consumption. To address these issues, we propose a novel and practical drone routing problem for shore-to-ship delivery services (DRP-SSDS) considering the non-linear energy consumption related to payload, flight phase, and flight time. The proposed DRP-SSDS is formulated as a mixed-integer second-order cone programming (MISOCP) model that integrates continuous decisions on both time and location to realistically capture vessel movements within port waters. We then develop a tailored branch-and-price algorithm that can solve DRP-SSDS exactly and efficiently for medium-scale instances. Additionally, we design an effective heuristic method that can provide high-quality solutions in a reasonable time limit for large-scale instances. Extensive numerical experiments demonstrate the superiority of the proposed solution methods over the off-the-shelf optimization solver and a benchmark method across all tested instances.