An Exact Solution Method for the TSP with Drone Based on DecompositionRevista : Computers & Operations Research
Volumen : 127
Páginas : 105127
Tipo de publicación : ISI Ir a publicación
The Traveling Salesperson Problem with Drone (TSPD) 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 TSPD model and propose a mixedinteger programming formulation which exploits the models 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 Benderstype decomposition algorithm, strengthened by valid inequalities arising from structural properties of optimal solutions, and improved optimality cuts stemming from the notions of tshortcut and treduction, 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.