The drone-assisted variable speed asymmetric traveling salesman problem
Giovanni Campuzano, Eduardo Lalla‐Ruiz, Martijn Mes
Abstract
We introduce and solve the Drone-Assisted Variable Speed Asymmetric Traveling Salesman Problem, which considers different flight times for the drone depending on the selected speed level and weather conditions, as a result of the natural asymmetry intrinsically involved in the delivery operations. Moreover, we provide an extension that introduces an additional decision regarding the speed of the drone influencing energy consumption. We formulate mixed-integer linear programming models (MILP) and develop two metaheuristic approaches: a variable neighborhood descent (VND) and a multi-neighborhood tabu search (MTS) algorithm. To assess their performance, a set of instances based on existing benchmarks are proposed. Results point out that delivery systems are strongly sensitive to the features considered in this research, showing that the symmetric approach is not able to find feasible solutions when incorporating operational aspects, such as wind conditions and energy consumption. Furthermore, we demonstrate that the option to fly at lower speeds results in a decreasing makespan due to the increased use of the drone. Finally, we show that for all larger instances, the heuristics VND and MTS outperform the MILP solutions by at least 48% and 53%, respectively.