The drone-assisted variable speed asymmetric traveling salesman problem

Giovanni Campuzano*, Eduardo Lalla-Ruiz, Martijn Mes

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)
191 Downloads (Pure)

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.

Original languageEnglish
Article number109003
JournalComputers & industrial engineering
Volume176
DOIs
Publication statusPublished - Feb 2023

Keywords

  • Drones
  • Last-mile delivery
  • Meta-heuristics
  • Traveling salesman problem
  • Variable speed
  • Weather conditions
  • UT-Hybrid-D

Fingerprint

Dive into the research topics of 'The drone-assisted variable speed asymmetric traveling salesman problem'. Together they form a unique fingerprint.

Cite this