Exact Methods for the Traveling Salesman Problem with Drone

Roberto Roberti () and Mario Ruthmair ()
Additional contact information
Roberto Roberti: Department of Supply Chain Analytics, Vrije Universiteit Amsterdam, 1081HV Amsterdam, Netherlands
Mario Ruthmair: Department of Supply Chain Analytics, Vrije Universiteit Amsterdam, 1081HV Amsterdam, Netherlands; Department of Statistics and Operations Research, University of Vienna, 1090 Vienna, Austria

Transportation Science, 2021, vol. 55, issue 2, 315-335

Abstract: Efficiently handling last-mile deliveries becomes more and more important nowadays. Using drones to support classical vehicles allows improving delivery schedules as long as efficient solution methods to plan last-mile deliveries with drones are available. We study exact solution approaches for some variants of the traveling salesman problem with drone (TSP-D) in which a truck and a drone are teamed up to serve a set of customers. This combination of truck and drone can exploit the benefits of both vehicle types: the truck has a large capacity but usually low travel speed in urban areas; the drone is faster and not restricted to street networks, but its range and carrying capacity are limited. We propose a compact mixed-integer linear program (MILP) for several TSP-D variants that is based on timely synchronizing truck and drone flows; such an MILP is easy to implement but nevertheless leads to competitive results compared with the state-of-the-art MILPs. Furthermore, we introduce dynamic programming recursions to model several TSP-D variants. We show how these dynamic programming recursions can be exploited in an exact branch-and-price approach based on a set partitioning formulation using ng -route relaxation and a three-level hierarchical branching. The proposed branch-and-price can solve instances with up to 39 customers to optimality outperforming the state-of-the-art by more than doubling the manageable instance size. Finally, we analyze different scenarios and show that even a single drone can significantly reduce a route’s completion time when the drone is sufficiently fast.

Keywords: traveling salesman problem; drones; mixed-integer linear programming; compact formulation; dynamic programming; set partitioning; branch-and-price (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (25)

Downloads: (external link)
https://doi.org/10.1287/trsc.2020.1017 (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:ortrsc:v:55:y:2021:i:2:p:315-335

Access Statistics for this article

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