A Branch-and-Bound Approach to the Traveling Salesman Problem with a Drone

Stefan Poikonen (), Bruce Golden () and Edward A. Wasil ()
Additional contact information
Stefan Poikonen: Business School, University of Colorado Denver, Denver, Colorado 80202
Bruce Golden: R.H. Smith School of Business, University of Maryland, College Park, Maryland 20742; c Kogod School of Business, American University, Washington, District of Columbia 20016
Edward A. Wasil: Kogod School of Business, American University, Washington, District of Columbia 20016

INFORMS Journal on Computing, 2019, vol. 31, issue 2, 335-346

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.

Keywords: 970 transportation; vehicle routing; 490 networks-graphs; traveling salesman; 630 programming; integer; algorithms; branch and bound (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (41)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0826 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:31:y:2019:i:2:p:335-346

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().