Decremental State-Space Relaxations for the Basic Traveling Salesman Problem with a Drone

Marcos Blufstein (), Gonzalo Lera-Romero () and Francisco J. Soulignac ()
Additional contact information
Marcos Blufstein: Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires C1428EGA, Argentina
Gonzalo Lera-Romero: Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires C1428EGA, Argentina
Francisco J. Soulignac: Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires C1428EGA, Argentina; Instituto de Investigación en Ciencias de la Computación (ICC), CONICET-Universidad de Buenos Aires, Buenos Aires C1428EGA, Argentina

INFORMS Journal on Computing, 2024, vol. 36, issue 4, 1064-1083

Abstract: Truck-and-drone routing problems have become an important research topic in the last decade because of their applications for last-mile deliveries. Despite the many publications in this area, the most efficient exact algorithms designed thus far struggle to solve the benchmark instances with 39 or more customers. This fact holds even for one of the simplest variants involving one truck and one drone whose routes must synchronize at customers’ locations: the basic traveling salesman problem with a drone (TSP-D). In this article, we devise a new algorithm for the TSP-D that solves every benchmark instance with up to 59 customers, and it scales up to 99 customers when the drone is much faster than the truck. The core of our method is a dynamic programming algorithm that is applied for column generation and variable fixing within tailored decremental state-space relaxation strategies.

Keywords: traveling salesman problem with a drone; column generation; decremental state-space relaxation; dynamic programming; completion bounds; variable fixing (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0390 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:36:y:2024:i:4:p:1064-1083

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().