The Mothership and Drone Routing Problem

Stefan Poikonen () and Bruce Golden ()
Additional contact information
Stefan Poikonen: Business School, University of Colorado Denver, Denver, Colorado 80202
Bruce Golden: H. Smith School of Business, University of Maryland, College Park, Maryland 20742

INFORMS Journal on Computing, 2020, vol. 32, issue 2, 249-262

Abstract: The mothership and drone routing problem (MDRP) considers the routing of a two-vehicle tandem. The larger vehicle, which may be a ship or an airplane, is called the mothership ; the smaller vehicle, which may be a small boat or unmanned aerial vehicle, is called the drone . We assume that there exists a set of target locations T . For each t in T , the drone must launch from the mothership, visit t , and then return to the mothership to refuel. The drone has a limited range of R time units. In the MDRP, we assume that both mothership and drone operate in the “open seas” (i.e., using the Euclidean metric). We also introduce the mothership and infinite-capacity drone routing problem (MDRP-IC), where a drone launches from the mothership and visits one or more targets consecutively before returning to the mothership. Our exact approach uses branch and bound, where each node of the branch-and-bound tree corresponds to a potential subsequence of the order of target visits. A lower bound at each node is given by solving a second-order cone program, which optimally chooses a launch point and landing point for each target in the subsequence. A set of heuristics that also uses a second-order cone program as an embedded procedure is presented. We show that our schemes are flexible to accommodate a variety of additional constraints and/or objective functions. Computational results and interesting variants of the MDRP and MDRP-IC are also presented.

Keywords: drone; vehicle routing; traveling salesman; ship; logistics (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0879 (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:32:y:2020:i:2:p:249-262

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 ().