Optimization Approaches for the Traveling Salesman Problem with Drone
The fast and cost-efficient home delivery of goods ordered online is logistically challenging. Many companies are looking for new ways to cross the last mile to their customers. One technology-enabled opportunity that recently has received much attention is the use of drones to support deliveries. An innovative last-mile delivery concept in which a truck collaborates with a drone to make deliveries gives rise to a new variant of the traveling salesman problem (TSP) that the authors call the TSP with drone. In this paper, they model this problem as an integer program and develop several fast route-first, cluster-second heuristics based on local search and dynamic programming. The authors prove worst-case approximation ratios for the heuristics and test their performance by comparing the solutions to the optimal solutions for small instances. In addition, the authors apply their heuristics to several artificial instances with different characteristics and sizes. Our experiments show that substantial savings are possible with this concept compared to truck-only delivery. The online appendix is available at https://doi.org/10.1287/trsc.2017.0791.
- Record URL:
-
Availability:
- Find a library where document is available. Order URL: http://worldcat.org/oclc/1767714
-
Supplemental Notes:
- Abstracts reprinted with permission of INFORMS (Institute for Operations Research and the Management Sciences, http://www.informs.org).
-
Authors:
- Agatz, Niels
- Bouman, Paul
- Schmidt, Marie
- Publication Date: 2018-7
Language
- English
Media Info
- Media Type: Web
- Features: References;
- Pagination: 965-981
-
Serial:
- Transportation Science
- Volume: 52
- Issue Number: 4
- Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
- ISSN: 0041-1655
- Serial URL: http://transci.journal.informs.org/
Subject/Index Terms
- TRT Terms: Delivery service; Delivery vehicles; Drones; Dynamic programming; Integer programming; Multimodal transportation; Optimization; Traveling salesman problem
- Subject Areas: Aviation; Freight Transportation; Motor Carriers; Operations and Traffic Management; Planning and Forecasting;
Filing Info
- Accession Number: 01680803
- Record Type: Publication
- Files: TRIS
- Created Date: Sep 19 2018 11:06AM