An Exact Solution Method for the TSP with Drone Based on Decomposition

Abstract

The Traveling Salesperson 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.