Decremental state-space relaxations for the traveling salesman problem with a drone
Keywords:
problema de viajante de comercio con un drone, generaci´on de columnas, relajaciones decrementales del espacio de estados, programaci´on din´amica, cotas de compleci´on, fijado de variablesAbstract
Research into vehicle routing problems combining trucks and drones has grown significantly in the last decade due to their applications in last-mile logistics. Despite the vast literature on the subject, the most efficient exact algorithms designed to date can only solve a few instances with up to 39 customers. This is true even for the simplest variants of the problem involving only a truck and a drone whose routes are synchronized at customer locations: the traveling salesman problem with a drone (TSP-D). In this work, we design a new exact algorithm for TSP-D that solves all benchmark instances with up to 59 customers, and is capable of solving instances with up to 99 customers in cases where the drone is faster than the truck. Our method is based on a dynamic programming algorithm that is executed to generate columns and set variables within a novel algorithm that applies different decremental strategies to relax the state space.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Marcos Blufstein, Gonzalo Lera-Romero, Francisco J. Soulignac
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Acorde a estos términos, el material se puede compartir (copiar y redistribuir en cualquier medio o formato) y adaptar (remezclar, transformar y crear a partir del material otra obra), siempre que a) se cite la autoría y la fuente original de su publicación (revista y URL de la obra), b) no se use para fines comerciales y c) se mantengan los mismos términos de la licencia.
