Optimization Online


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

Sebastián A. Vásquez(savasquez***at***uc.cl)
Gustavo Angulo(gangulo***at***ing.puc.cl)
Mathias A. Klapp(maklapp***at***ing.puc.cl)

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 computationally simulated instances, which show its effectiveness.

Keywords: traveling salesman problem, vehicle routing, drones, Benders' decomposition

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Applications -- OR and Management Sciences (Production and Logistics )

Citation: School of Engineering, Pontificia Universidad Católica de Chile, Santiago, Chile

Download: [PDF]

Entry Submitted: 04/02/2020
Entry Accepted: 04/03/2020
Entry Last Modified: 04/02/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society