CANCELLED: Exact Methods for the Traveling Salesman Problem with Drone

Roberto Roberti (VU Amsterdam)
Start date

Friday, 20 Mar 2020, 12:00

End date

Friday, 20 Mar 2020, 13:00

Sanders Building
Campus Woudestein
Spoken Language

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 present 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 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.

It is joint work with Mario Ruthmair, University of Vienna and VU Amsterdam.

Registration is required for availability of lunch.


dr. (Krzysztof) KS Postek
More information

Secretariat Econometric Institute

Room: ET-21/ET-22
Phone: 010-4081259/1264