A bi-objective optimisation model for the drone scheduling problem in island delivery

Drone-assisted parcel delivery to remote islands is increasingly replacing traditional methods, offering improved efficiency and enhanced service reliability. This paper addresses the drone scheduling problem in island delivery (DSP-ID) by optimising drone delivery routes. In particular, we first introduce a bi-objective mixed-integer linear programming model that concurrently optimises delivery time and energy consumption. To address the model, both a heuristic non-dominated sorting genetic algorithm II (NSGA-II) and an exact augmented epsilon-constraint method are developed. The efficacy and robustness of the proposed model and algorithms are evaluated through experiments across various scales. Results indicate that both algorithms yield high-quality solutions for DSP-ID in small-scale scenarios. However, as the problem size expands, the performance of the augmented epsilon-constraint method wanes under time constraints, whereas the NSGA-II consistently delivers high-quality solutions. Additionally, we provide decision-makers with actionable insights for selecting the most effective drone delivery routes.