An exact solution method for the TSP with Drone based on decomposition. (March 2021)

• Record Type: Journal Article
• Authors: Vásquez, Sebastián A.; Angulo, Gustavo; Klapp, Mathias A.
• Is Part Of: Computers & operations research. Volume 127(2021)
• Publication Date: 2021-03
• Subjects: Traveling salesman -- Vehicle routing -- Drones -- Benders' decomposition; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2020.105127
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: This paper presents a two-stage formulation and decomposition for the TSP-D.. We present properties used to implement an extension of the Integer L-shaped Method. In particular, we obtain strong lower bounds and improved optimality cuts. Our computational study shows the efficiency of the approach. Abstract: The Traveling Salesman Problem with Drone (TSP-D) is a routing model in which a given set of customer locations must be visited in the least amount of time, either by a truck route starting and ending at a depot or by a drone dispatched from the truck en route. We study the TSP-D model and propose a mixed–integer programming formulation which exploits the model's structure and decomposes it into two natural decision stages: (1) selecting and sequencing a subset of customers served by the truck and (2) planning where to execute drone direct dispatches from the truck to each of the remaining customer locations. We design a Benders–type decomposition algorithm, strengthened by valid inequalities arising from structural properties of optimal solutions, and improved optimality cuts stemming from the notions of t –shortcut and t –reduction, which might be of independent interest. Finally, our solution approach is empirically tested over an extensive family of randomly generated instances, which show its effectiveness.