Integrated speed optimization and multivisit drone routing: a mathematical programming approach

Abstract This paper considers a last‐mile delivery system in which drones are used to deliver parcels to customers within a predefined delivery‐time limit, while drones can perform multiple multivisit trips. The effects of both drone speed and load weight are considered on energy consumption in all flight phases, including takeoff, cruise, hovering, and landing phases, using a realistic nonconvex formula. The problem determines the routes of the drones and their speeds during the cruise flight phases, with the aim of minimizing the total consumed energy. The paper initially examines the problem for the discrete case where the speeds are selected from a finite list of options. The initial formulation of the problem is a mixed‐integer nonlinear program that cannot be solved efficiently. Using a novel approach that changes the problem's input space, a mixed‐integer linear program is proposed and enhanced by valid inequalities. Utilizing an efficient preprocessing algorithm, the proposed linear formulation is able to solve problem instances with up to 100 customers. Next, the paper studies the problem for the continuous case in which the speeds can take values from a specified interval. It is first demonstrated how the continuous case can be solved optimally when no delivery‐time limit is imposed. Then, it is shown that the continuous case can be solved approximately using the discrete case. A method for computing the approximation error is also presented, which can be used to determine an appropriate level of discretization.