The DOI matches its Crossref record; 19 of the 19 references it cites were found in a registry or an index.
On the min-cost Traveling Salesman Problem with Drone
Open accessAbstract
Over the past few years, unmanned aerial vehicles (UAV), also known as drones, have been adopted as part of a new logistic method in the commercial sector called “last-mile delivery”. In this novel approach, they are deployed alongside trucks to deliver goods to customers to improve the quality of service and reduce the transportation cost. This approach gives rise to a new variant of the traveling salesman problem (TSP), called TSP with drone (TSP-D). A variant of this problem that aims to minimize the time at which truck and drone finish the service (or, in other words, to maximize the quality of service) was studied in the work of Murray and Chu (2015). In contrast, this paper considers a new variant of TSP-D in which the objective is to minimize operational costs including total transportation cost and one created by waste time a vehicle has to wait for the other. The problem is first formulated mathematically. Then, two algorithms are proposed for the solution. The first algorithm (TSP-LS) was adapted from the approach proposed by Murray and Chu (2015), in which an optimal TSP solution is converted to a feasible TSP-D solution by local searches. The second algorithm, a Greedy Randomized Adaptive Search Procedure (GRASP), is based on a new split procedure that optimally splits any TSP tour into a TSP-D solution. After a TSP-D solution has been generated, it is then improved through local search operators. Numerical results obtained on various instances of both objective functions with different sizes and characteristics are presented. The results show that GRASP outperforms TSP-LS in terms of solution quality under an acceptable running time.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
(2003) · International Series in Operations Research & Management Science · doi:10.1007/b101874 · Cited by 3,430
TSPLIB—A Traveling Salesman Problem Library
Reinelt, G. (1991) · ORSA Journal on Computing · doi:10.1287/ijoc.3.4.376 · Cited by 2,616
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
(2010) · International Series in Operations Research & Management Science · doi:10.1007/978-1-4419-1665-5 · Cited by 1,642
The Traveling Salesman Problem and Its Variations
(2007) · Combinatorial Optimization · doi:10.1007/b101971 · Cited by 1,392
A simple and effective evolutionary algorithm for the vehicle routing problem
Prins, C. (2004) · Computers & Operations Research · doi:10.1016/s0305-0548(03)00158-8 · Cited by 1,058
Optimization Approaches for the Traveling Salesman Problem with Drone
Agatz, N., Bouman, P., & Schmidt, M. (2018) · Transportation Science · doi:10.1287/trsc.2017.0791 · Cited by 1,029
Vidal, T., Crainic, T. G., Gendreau, M., et al. (2012) · Computers & Operations Research · doi:10.1016/j.cor.2012.07.018 · Cited by 560
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
How not to lie with statistics: the correct way to summarize benchmark results
Fleming, P. J., & Wallace, J. J. (1986) · Communications of the ACM · doi:10.1145/5666.5673 · Cited by 446
A unified solution framework for multi-attribute vehicle routing problems
Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2014) · European Journal of Operational Research · doi:10.1016/j.ejor.2013.09.045 · Cited by 433
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
The vehicle routing problem with drones: Extended models and connections
Poikonen, S., Wang, X., & Golden, B. (2017) · Networks · doi:10.1002/net.21746 · Cited by 342
Planning Paths for Package Delivery in Heterogeneous Multirobot Teams
Mathew, N., Smith, S. L., & Waslander, S. L. (2015) · IEEE Transactions on Automation Science and Engineering · doi:10.1109/tase.2015.2461213 · Cited by 301
Ant colony optimization for real-world vehicle routing problems: From theory to applications
Rizzoli, A. E., Montemanni, R., Lucibello, E., & Gambardella, L. M. (2007) · Swarm Intelligence · doi:10.1007/s11721-007-0005-x · Cited by 202
A memetic algorithm for the Multi Trip Vehicle Routing Problem
Cattaruzza, D., Absi, N., Feillet, D., & Vidal, T. (2014) · European Journal of Operational Research · doi:10.1016/j.ejor.2013.06.012 · Cited by 178
A GRASP × Evolutionary Local Search Hybrid for the Vehicle Routing Problem
Prins, C. (2008) · Studies in computational intelligence · doi:10.1007/978-3-540-85152-3_2 · Cited by 173
Optimization Approaches for the Traveling Salesman Problem with DronePreprint
Agatz, N. A. H., Bouman, P., & Schmidt, M. (2015) · SSRN Electronic Journal · doi:10.2139/ssrn.2639672 · Cited by 105
Ant colony optimization for real-world vehicle routing problems
Coltorti, D., & Rizzoli, A. E. (2007) · ACM SIGEVOlution · doi:10.1145/1329465.1329466 · Cited by 30
Cited by
Otto, A., Agatz, N., Campbell, J., Golden, B., & Pesch, E. (2018) · Networks · doi:10.1002/net.21818 · Cited by 985
“[106] formulate the TSP with a drone, or a flying sidekick TSP.”
BackgroundMethodLast-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
An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones
Sacramento, D., Pisinger, D., & Ropke, S. (2019) · Transportation Research Part C: Emerging Technologies · doi:10.1016/j.trc.2019.02.018 · Cited by 563
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
Metadata
- Authors
- Ha, Q. M., Deville, Y., Pham, Q. D., & Hà, M. H.
- Venue
- Transportation Research Part C: Emerging Technologies
- Publisher
- Elsevier BV
- Published
- 2018-01
- Volume
- 86
- Pages
- 597-621
- ISSN
- 0968-090X (ISSN-L)
- OpenAlex
- W2245682929
- Cited by
- 622
- References
- 19
- FWCI
- 40.19
- 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.