The drone-assisted vehicle routing problem with robot stations

André Morim*, Giovanni Campuzano, Pedro Amorim, Martijn Mes, Eduardo Lalla-Ruiz

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
1 Downloads (Pure)

Abstract

Following the widespread interest of both the scientific community and companies in using autonomous vehicles to perform deliveries, we propose the ‘Drone-Assisted Vehicle Routing Problem with Robot Stations’ (VRPD-RS), a problem that combines two concepts studied in the autonomous vehicles literature: truck-drone tandems and robot stations. We model the VRPD-RS as a mixed-integer linear program (MILP) for two different objectives, the makespan and operational costs, and analyze the impact of adding trucks, drones, and robots to the delivery fleet. Given the computational complexity of the problem, we propose a General Variable Neighborhood Search (GVNS) metaheuristic to solve more realistic instances within reasonable computational times. Results show that, for small instances of 10 customers, where the solver obtains optimal solutions for almost all cases, the GVNS presents solutions with gaps of 0.7% to the solver for the makespan objective and gaps of 0.0% for the operational costs variant. For instances of up to 50 customers, the GVNS presents improvements of 21.5% for the makespan objective and 8.0% for the operational costs variant. Furthermore, we compare the GVNS with a Simulated Annealing (SA) metaheuristic, showing that the GVNS outperforms the SA for the whole set of instances and in more efficient computational times. Accordingly, the results highlight that including an additional drone in a truck-drone tandem increases delivery speed alongside a reduction in operational costs. Moreover, robot stations proved to be a useful delivery element as they were activated in almost every studied scenario.

Original languageEnglish
Article number121741
Number of pages22
JournalExpert systems with applications
Volume238
Early online date24 Sept 2023
DOIs
Publication statusPublished - 15 Mar 2024

Keywords

  • Drones
  • Last-mile logistics
  • Multi-modality
  • Robot stations
  • Vehicle routing
  • 2023 OA procedure

Fingerprint

Dive into the research topics of 'The drone-assisted vehicle routing problem with robot stations'. Together they form a unique fingerprint.

Cite this