A Branch-and-Bound Approach to the Traveling Salesman Problem with a Drone
Stefan Poikonen, Bruce Golden, Edward A. Wasil
INFORMS Journal on Computing · 2019 · Volume 31 · Issue 2
Abstract
The Traveling Salesman Problem with a Drone (TSP-D) is a hybrid truck and drone model of delivery, in which the drone rides on the truck and launches from the truck to deliver packages. Our approach to the TSP-D uses branch and bound, whereby each node of the branch-and-bound tree corresponds with a potential order to deliver a subset of packages. An approximate lower bound at each node is given by solving a dynamic program. We provide additional variants of our heuristic approach and compare solution quality and computation times. Consideration is given to various input parameters and distance metrics. The online supplement is available at https://doi.org/10.1287/ijoc.2018.0826 .
Keywords
970 transportation, vehicle routing, 490 networks-graphs, traveling salesman, 630 programming, integer, algorithms, branch and bound
Enable JavaScript for citation tools and additional paper interactions.