Unmanned aerial vehicles (UAVs), or drones, are recognized for their potential to improve efficiency in last-mile delivery. Unlike the vehicle routing problem, drone route design is challenging due to several operational signatures, such as speed optimization, multi-trip operation, and energy consumption estimation. Drone energy consumption is a nonlinear function of both speed and payload. Moreover, the high speed of drones can significantly curtail the drone range, thereby limiting the efficiency of drone delivery systems. This paper addresses the trade-off between speed and flight range in a multi-trip drone routing problem with variable flight speeds (DRP–VFS). We propose a new model to specifically consider energy constraints using a nonlinear energy consumption model and treat drone speeds as decision variables. The DRP–VFS is initially formulated using mixed-integer linear programming (MILP) to minimize energy consumption. To solve large-scale instances, we propose a three-phase adaptive large neighborhood search (ALNS) algorithm and compare its performance with a commercial MIP solver. The experimental results demonstrate that the proposed method is capable of effectively identifying suboptimal solutions in practical scenarios. Furthermore, results indicate that operating drones at variable speeds leads to about 21% energy savings compared to fixed speeds, with advantages in cost savings and range extension.

Unmanned aerial vehicle (UAV), or drone is recognized for its potential to improve efficiency and address last-mile delivery issues. As a result, there has been a lot of activity in recent years in the field of drone scheduling and routing. Unlike the vehicle routing problem, drone route design is difficult due to several operational characteristics, such as speed optimization, multitrip operation, and energy consumption estimation. On the one hand, drone energy consumption is a complex nonlinear function of both speed and payload in practice. On the other hand, the high operating speed of drones can significantly curtail the drone range, thereby limiting the efficiency of drone delivery systems. Most of the existing drone delivery models either assume constant drone speed or do not consider the effect of drone speed and parcel weight on energy consumption, leading to costly or energy-infeasible routes. This paper addresses the trade-off between speed and flight range in a multi-trip drone routing problem with variable flight speeds (DRP-VFS), in which a team of homogeneous drones is employed for delivery services. We propose a new model to particularly consider energy constraints using a nonlinear energy consumption model and treat drone speeds as decision variables so that various drone speeds can be adopted in applications. The DRP-VFS is initially formulated as mixed-integer linear programming (MILP) to minimize total energy consumption. To solve large-scale instances, we propose a three-phase adaptive large neighborhood search (ALNS) algorithm. The experimental results demonstrate that suboptimal solutions can be found effectively in practical scenarios using the proposed method. Furthermore, results indicate that operating drones at variable speeds leads to about 21% of energy savings compared to fixed speeds, boasting advantages in cost-savings and range extensions.