Optimization Online


Exact Methods for the Traveling Salesman Problem with Drone

Roberto Roberti (r.roberti***at***vu.nl)
Mario Ruthmair (mario.ruthmair***at***univie.ac.at)

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 a MILP is easy to implement but nevertheless leads to competitive results compared to 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 and using ng-route relaxation, dual variable stabilization, 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.

Keywords: traveling salesman problem, drone, vehicle routing, mixed integer linear programming, branch-and-price

Category 1: Applications -- OR and Management Sciences (Transportation )

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

Category 3: Other Topics (Dynamic Programming )

Citation: Vrije Universiteit Amsterdam, 11/2019

Download: [PDF]

Entry Submitted: 11/03/2019
Entry Accepted: 11/03/2019
Entry Last Modified: 08/26/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