The drone-assisted variable speed asymmetric traveling salesman problem. (February 2023)

• Record Type: Journal Article
• Authors: Campuzano, Giovanni; Lalla-Ruiz, Eduardo; Mes, Martijn
• Is Part Of: Computers & industrial engineering. Volume 176(2023)
• Publication Date: 2023-02
• Subjects: Drones -- Traveling salesman problem -- Last-mile delivery -- Variable speed -- Weather conditions -- Meta-heuristics; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2023.109003
• Languages: English
• ISSNs: 0360-8352

Abstract

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. Highlights: Novel extensions of the Traveling Salesman Problem with Drone (TSP-D). Inclusion of weather conditions and variable drone speeds into the TSP-D. Two metaheuristics approaches to solve the extended problems. Provision of insights into the benefits of the extensions and solution approaches. Design of a new set of benchmark instances.