The DOI matches its Crossref record; 8 of the 8 references it cites were found in a registry or an index.
Optimization Approaches for the Traveling Salesman Problem with Drone
Open accessAbstract
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 we call the TSP with drone. In this paper, we model this problem as an integer program and develop several fast route-first, cluster-second heuristics based on local search and dynamic programming. We 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, we apply our 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 .
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Reducibility among Combinatorial Problems
Karp, R. M. (1972) · Complexity of Computer Computations · doi:10.1007/978-1-4684-2001-2_9 · Cited by 11,511
The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery
Murray, C. C., & Chu, A. G. (2015) · Transportation Research Part C: Emerging Technologies · doi:10.1016/j.trc.2015.03.005 · Cited by 1,715
The traveling salesman problem: An overview of exact and approximate algorithms
Laporte, G. (1992) · European Journal of Operational Research · doi:10.1016/0377-2217(92)90138-y · Cited by 971
An Analysis of Several Heuristics for the Traveling Salesman Problem
Rosenkrantz, D. J., Stearns, R. E., & Lewis, II (1977) · SIAM Journal on Computing · doi:10.1137/0206041 · Cited by 837
The vehicle routing problem with drones: several worst-case results
Wang, X., Poikonen, S., & Golden, B. (2017) · Optimization Letters · doi:10.1007/s11590-016-1035-3 · Cited by 551
A tabu search heuristic for the truck and trailer routing problem
Scheuerer, S. (2004) · Computers & Operations Research · doi:10.1016/j.cor.2004.08.002 · Cited by 162
A GRASP with evolutionary path relinking for the truck and trailer routing problem
Villegas, J. G., Prins, C., Prodhon, C., Medaglia, A. L., & Velasco, N. (2010) · Computers & Operations Research · doi:10.1016/j.cor.2010.11.011 · Cited by 112
UAV Applications: Introduction
Valavanis, K. P., & Vachtsevanos, G. (2014) · Springer eBooks · doi:10.1007/978-90-481-9707-1_151 · Cited by 47
Cited by
Otto, A., Agatz, N., Campbell, J., Golden, B., & Pesch, E. (2018) · Networks · doi:10.1002/net.21818 · Cited by 985
Self-citationIndustry 4.0: Opportunities and Challenges for Operations Management
Olsen, T. L., & Tomlin, B. (2020) · Manufacturing & Service Operations Management · doi:10.1287/msom.2019.0796 · Cited by 651
On the min-cost Traveling Salesman Problem with Drone
Ha, Q. M., Deville, Y., Pham, Q. D., & Hà, M. H. (2018) · Transportation Research Part C: Emerging Technologies · doi:10.1016/j.trc.2017.11.015 · Cited by 622
Last-mile delivery concepts: a survey from an operational research perspective
Boysen, N., Fedtke, S., & Schwerdfeger, S. (2021) · OR Spectrum · doi:10.1007/s00291-020-00607-8 · Cited by 621
The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones
Murray, C. C., & Raj, R. (2020) · Transportation Research Part C: Emerging Technologies · doi:10.1016/j.trc.2019.11.003 · Cited by 575
Drone-aided routing: A literature review
Macrina, G., Di Puglia Pugliese, L., Guerriero, F., & Laporte, G. (2020) · Transportation Research Part C: Emerging Technologies · doi:10.1016/j.trc.2020.102762 · Cited by 522
The strategic role of logistics in the industry 4.0 era
Tang, C. S., & Veelenturf, L. P. (2019) · Transportation Research Part E: Logistics and Transportation Review · doi:10.1016/j.tre.2019.06.004 · Cited by 514
Chung, S. H., Sah, B., & Lee, J. (2020) · Computers & Operations Research · doi:10.1016/j.cor.2020.105004 · Cited by 441
Coordinated Logistics with a Truck and a Drone
Carlsson, J. G., & Song, S. (2018) · Management Science · doi:10.1287/mnsc.2017.2824 · Cited by 425
Chiang, W.-C., Li, Y., Shang, J., & Urban, T. L. (2019) · Applied Energy · doi:10.1016/j.apenergy.2019.03.117 · Cited by 391
Applications and Research avenues for drone-based models in logistics: A classification and review
Moshref-Javadi, M., & Winkenbach, M. (2021) · Expert Systems with Applications · doi:10.1016/j.eswa.2021.114854 · Cited by 391
Dynamic programming approaches for the traveling salesman problem with drone
Bouman, P., Agatz, N., & Schmidt, M. (2018) · Networks · doi:10.1002/net.21864 · Cited by 360
Self-citationEnergy consumption models for delivery drones: A comparison and assessment
Zhang, J., Campbell, J. F., Sweeney II, D. C., & Hupman, A. C. (2021) · Transportation Research Part D: Transport and Environment · doi:10.1016/j.trd.2020.102668 · Cited by 342
Two echelon vehicle routing problem with drones in last mile delivery
Kitjacharoenchai, P., Min, B.-C., & Lee, S. (2020) · International Journal of Production Economics · doi:10.1016/j.ijpe.2019.107598 · Cited by 332
Drones for parcel and passenger transportation: A literature review
Kellermann, R., Biehle, T., & Fischer, L. (2020) · Transportation Research Interdisciplinary Perspectives · doi:10.1016/j.trip.2019.100088 · Cited by 319
Multi-visit drone routing problem
Poikonen, S., & Golden, B. (2020) · Computers & Operations Research · doi:10.1016/j.cor.2019.104802 · Cited by 297
The hybrid vehicle-drone routing problem for pick-up and delivery services
Karak, A., & Abdelghany, K. (2019) · Transportation Research Part C: Emerging Technologies · doi:10.1016/j.trc.2019.03.021 · Cited by 294
A matheuristic for the vehicle routing problem with drones and its variants
Schermer, D., Moeini, M., & Wendt, O. (2019) · Transportation Research Part C: Emerging Technologies · doi:10.1016/j.trc.2019.06.016 · Cited by 278
Drone Delivery Models for Healthcare
Scott, J., & Scott, C. (2017) · Proceedings of the Annual Hawaii International Conference on System Sciences · doi:10.24251/hicss.2017.399 · Cited by 271
Schermer, D., Moeini, M., & Wendt, O. (2019) · Computers & Operations Research · doi:10.1016/j.cor.2019.04.021 · Cited by 264
Comparison of energy demands of drone-based and ground-based parcel delivery services
Kirschstein, T. (2020) · Transportation Research Part D: Transport and Environment · doi:10.1016/j.trd.2019.102209 · Cited by 264
Emerging technologies and the use case: A multi‐year study of drone adoption
Maghazei, O., Lewis, M. A., & Netland, T. H. (2022) · Journal of Operations Management · doi:10.1002/joom.1196 · Cited by 117
Jan, R. (2024) · Advances in Educational Technologies and Instructional Design · doi:10.4018/979-8-3693-0884-4.ch014 · Cited by 9
Metadata
- Authors
- Agatz, N., Bouman, P., & Schmidt, M.
- Venue
- Transportation Science
- Published
- 2018-08
- Volume
- 52
- Issue
- 4
- Pages
- 965-981
- ISSN
- 0041-1655 (ISSN-L)
- 1526-5447
- OpenAlex
- W2990601306
- Cited by
- 1,029
- References
- 8
- FWCI
- 60.23
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.