Template-Type: ReDIF-Paper 1.0
Author-Name: Bouman, P.C.
Author-Name-Last: Bouman
Author-Name-First: Paul
Author-Name: Agatz, N.A.H.
Author-Name-Last: Agatz
Author-Name-First: Niels
Author-Name: Schmidt, M.E.
Author-Name-Last: Schmidt
Author-Name-First: Marie
Title: Dynamic Programming Approaches for the Traveling Salesman Problem with Drone
Abstract: A promising new delivery model involves the use of a delivery truck that collaborates with a drone to make deliveries. Effectively combining a truck and a drone gives rise to a new planning problem that is known as the Traveling Salesman Problem with Drone (TSP-D). This paper presents exact solution approaches for the TSP-D based on dynamic programming and provides an experimental comparison of these approach. Our numerical experiments show that our approach can solve larger problems than the mathematical programming approaches that have been presented in the literature thus far. Moreover, we show that restrictions on the number of locations the truck can visit while the drone is away can help significantly reduce the solution times while having relatively little impact on the overall solution quality.
Length: 24
Creation-Date: 2017-09-11
File-URL: https://repub.eur.nl/pub/101691/ERS-2017-011-LIS_v01.pdf
File-Format: application/pdf
Series: RePEc:ems:eureri
Number: ERS-2017-011-LIS
Keywords: Traveling salesman problem, Vehicle routing, Drones, Dynamic Programming
Handle: RePEc:ems:eureri:101691