The drone scheduling problem in shore-to-ship delivery : a time discretization-based model with an exact solving approach

Abstract

Amid growing interest in the integration of drones into maritime logistics, this paper addresses the drone scheduling problem in shore-to-ship delivery (DSP-SSD), which is both significant and challenging. We introduce a mixed-integer programming model with time discretization that incorporates drone-related constraints, moving targets, and the need for multiple drone trips. While commercial solvers can handle this model in small-scale scenarios, we propose a tailored branch-and-price-and-cut (BPC) algorithm for larger and more complex cases. This algorithm integrates a drone-specific backward labeling algorithm, cutting planes, and acceleration methods to boost its effectiveness. Experiments show that the BPC algorithm substantially outperforms the commercial solvers in terms of solution quality and computational efficiency and that the inclusion of acceleration strategies in the algorithm enhances its performance. We also provide detailed sensitivity analyses of critical parameters of the model, such as the time discretization parameter and the number of ships, to gain insights into how our approach could be applied in real-world DSP-SSD operations.