{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T17:52:35Z","timestamp":1762105955302,"version":"build-2065373602"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,8,29]],"date-time":"2024-08-29T00:00:00Z","timestamp":1724889600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,29]],"date-time":"2024-08-29T00:00:00Z","timestamp":1724889600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100018687","name":"Katholische Universit\u00e4t Eichst\u00e4tt-Ingolstadt","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100018687","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["OR Spectrum"],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Aerial drone delivery has great potential to improve package delivery time, as drones can fly autonomously over obstacles at a possibly higher speed than trucks. The benefits of drones in delivery can even be increased in a truck-and-drone tandem where a truck carries multiple drones and releases them at advantageous places, i.e., the traveling salesman problem with multiple drones (TSPmD). We focus on a general version of this problem with makespan minimization, where the drones have two options after serving the customer: they can return to any node the truck visits at a later stage (sidekick) or return to the same node they were launched from (loop)\u00a0\u2014\u00a0even at the depot. We introduce an efficient two-indexed mixed-integer linear program (MILP) for this TSPmD and show how to adapt the MILP to cover two problem variants, namely the multiple flying sidekick traveling salesman problem and the traveling salesman problem with drone. Our MILP formulation is an efficient formulation, as it outperforms eight state-of-the-art MILP formulations for these problem variants in nearly all larger instances. In a numerical study, we provide new optimal solutions with up to 28 nodes for benchmark purposes. Moreover, we analyze the impact of allowing drone loops on makespan minimization in general and at the depot. We find that loops mainly become relevant when drones travel faster than trucks, resulting in average makespan savings of up to 2.7%.<\/jats:p>","DOI":"10.1007\/s00291-024-00785-9","type":"journal-article","created":{"date-parts":[[2024,8,29]],"date-time":"2024-08-29T15:12:14Z","timestamp":1724944334000},"page":"67-104","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Two-indexed formulation of the traveling salesman problem with multiple drones performing sidekicks and loops"],"prefix":"10.1007","volume":"47","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0262-4859","authenticated-orcid":false,"given":"Alexander","family":"Rave","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,8,29]]},"reference":[{"issue":"4","key":"785_CR1","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1287\/trsc.2017.0791","volume":"52","author":"N Agatz","year":"2018","unstructured":"Agatz N, Bouman P, Schmidt M (2018) Optimization approaches for the traveling salesman problem with drone. Transp Sci 52(4):965\u2013981. https:\/\/doi.org\/10.1287\/trsc.2017.0791","journal-title":"Transp Sci"},{"issue":"3","key":"785_CR2","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1002\/net.22172","volume":"82","author":"M Boccia","year":"2023","unstructured":"Boccia M, Mancuso A, Masone A, Sterle C (2023) A new MILP formulation for the flying sidekick traveling salesman problem. Networks 82(3):254\u2013276. https:\/\/doi.org\/10.1002\/net.22172","journal-title":"Networks"},{"issue":"1","key":"785_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00291-020-00607-8","volume":"43","author":"N Boysen","year":"2021","unstructured":"Boysen N, Fedtke S, Schwerdfeger S (2021) Last-mile delivery concepts: a survey from an operational research perspective. OR Spectrum 43(1):1\u201358. https:\/\/doi.org\/10.1007\/s00291-020-00607-8","journal-title":"OR Spectrum"},{"key":"785_CR4","unstructured":"Bouman, P., Agatz, N., Schmidt, M.: Instances for the TSP with Drone (and some solutions) (v1.2). Zenodo (2018). Last access: 14 Feb 2023"},{"key":"785_CR5","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2021.103280","volume":"130","author":"S Cavani","year":"2021","unstructured":"Cavani S, Iori M, Roberti R (2021) Exact methods for the traveling salesman problem with multiple drones. Transp Res Part C Emerg Technol 130:103280. https:\/\/doi.org\/10.1016\/j.trc.2021.103280","journal-title":"Transp Res Part C Emerg Technol"},{"key":"785_CR6","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/j.eswa.2018.03.032","volume":"104","author":"YS Chang","year":"2018","unstructured":"Chang YS, Lee HJ (2018) Optimal delivery routing with wider drone-delivery areas along a shorter truck-route. Expert Syst Appl 104:307\u2013317. https:\/\/doi.org\/10.1016\/j.eswa.2018.03.032","journal-title":"Expert Syst Appl"},{"key":"785_CR7","doi-asserted-by":"publisher","first-page":"1617","DOI":"10.1007\/s11590-019-01492-z","volume":"15","author":"M Dell\u2019Amico","year":"2021","unstructured":"Dell\u2019Amico M, Montemanni R, Novellani S (2021) Drone-assisted deliveries: new formulations for the flying sidekick traveling salesman problem. Optim Lett 15:1617\u20131648. https:\/\/doi.org\/10.1007\/s11590-019-01492-z","journal-title":"Optim Lett"},{"issue":"3","key":"785_CR8","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1002\/net.22022","volume":"78","author":"M Dell\u2019Amico","year":"2021","unstructured":"Dell\u2019Amico M, Montemanni R, Novellani S (2021) Modeling the flying sidekick traveling salesman problem with multiple drones. Networks 78(3):303\u2013327. https:\/\/doi.org\/10.1002\/net.22022","journal-title":"Networks"},{"key":"785_CR9","unstructured":"Dell\u2019Amico, M., Montemanni, R., Novellani, S.: Benchmark instances and optimal solutions for the traveling salesman problem with drone. arXiv preprint arXiv:2107.13275 (2021)"},{"issue":"3","key":"785_CR10","doi-asserted-by":"publisher","first-page":"1360","DOI":"10.1111\/itor.13030","volume":"29","author":"M Dell\u2019Amico","year":"2022","unstructured":"Dell\u2019Amico M, Montemanni R, Novellani S (2022) Exact models for the flying sidekick traveling salesman problem. Int Trans Oper Res 29(3):1360\u20131393. https:\/\/doi.org\/10.1111\/itor.13030","journal-title":"Int Trans Oper Res"},{"issue":"2","key":"785_CR11","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1080\/01605682.2019.1671156","volume":"72","author":"AM El-Adle","year":"2021","unstructured":"El-Adle AM, Ghoniem A, Haouari M (2021) Parcel delivery by vehicle and drone. J Oper Res Soc 72(2):398\u2013416. https:\/\/doi.org\/10.1080\/01605682.2019.1671156","journal-title":"J Oper Res Soc"},{"key":"785_CR12","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejtl.2022.100094","volume":"12","author":"JC Freitas","year":"2023","unstructured":"Freitas JC, Penna PHV, Toffolo TAM (2023) Exact and heuristic approaches to truck-drone delivery problems. EURO J Transp Logist 12:100094. https:\/\/doi.org\/10.1016\/j.ejtl.2022.100094","journal-title":"EURO J Transp Logist"},{"key":"785_CR13","unstructured":"Gartner, J.: JD.com\u2019s Drone delivery program takes flight in Rural China. World Wide Web (2016). Last Access 17 May 2022"},{"key":"785_CR14","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1016\/j.trc.2017.11.015","volume":"86","author":"QM Ha","year":"2018","unstructured":"Ha QM, Deville Y, Pham QD, H\u00e0 MH (2018) On the min-cost traveling salesman problem with drone. Transp Res Part C Emerg Technol 86:597\u2013621. https:\/\/doi.org\/10.1016\/j.trc.2017.11.015","journal-title":"Transp Res Part C Emerg Technol"},{"key":"785_CR15","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2023.106390","volume":"160","author":"B \u0130bro\u015fka","year":"2023","unstructured":"\u0130bro\u015fka B, \u00d6zpeynirci S (2023) \u00d6zpeynirci: multiple traveling salesperson problem with drones: General variable neighborhood search approach. Comput Oper Res 160:106390. https:\/\/doi.org\/10.1016\/j.cor.2023.106390","journal-title":"Comput Oper Res"},{"key":"785_CR16","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1016\/j.trc.2019.03.021","volume":"102","author":"A Karak","year":"2019","unstructured":"Karak A, Abdelghany K (2019) The hybrid vehicle-drone routing problem for pick-up and delivery services. Transp Res Part C Emerg Technol 102:427\u2013449. https:\/\/doi.org\/10.1016\/j.trc.2019.03.021","journal-title":"Transp Res Part C Emerg Technol"},{"key":"785_CR17","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.cie.2019.01.020","volume":"129","author":"P Kitjacharoenchai","year":"2019","unstructured":"Kitjacharoenchai P, Ventresca M, Moshref-Javadi M, Lee S, Tanchoco JMA, Brunese PA (2019) Multiple traveling salesman problem with drones: mathematical model and heuristic approach. Comput Indus Eng 129:14\u201330. https:\/\/doi.org\/10.1016\/j.cie.2019.01.020","journal-title":"Comput Indus Eng"},{"issue":"4","key":"785_CR18","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1145\/321043.321046","volume":"7","author":"CE Miller","year":"1960","unstructured":"Miller CE, Tucker AW, Zemlin RA (1960) Integer programming formulation of traveling salesman problem. J ACM 7(4):326\u2013329. https:\/\/doi.org\/10.1145\/321043.321046","journal-title":"J ACM"},{"issue":"5","key":"785_CR19","doi-asserted-by":"publisher","first-page":"1340","DOI":"10.1287\/trsc.2022.0230","volume":"57","author":"N Morandi","year":"2023","unstructured":"Morandi N, Leus R, Matuschke J, Yaman H (2023) The traveling salesman problem with drones: the benefits of retraversing the arcs. Transp Sci 57(5):1340\u20131358. https:\/\/doi.org\/10.1287\/trsc.2022.0230","journal-title":"Transp Sci"},{"key":"785_CR20","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1016\/j.apm.2019.11.020","volume":"80","author":"M Moshref-Javadi","year":"2020","unstructured":"Moshref-Javadi M, Hemmati A, Winkenbach M (2020) A truck and drones model for last-mile delivery: a mathematical model and heuristic approach. Appl Math Model 80:290\u2013318. https:\/\/doi.org\/10.1016\/j.apm.2019.11.020","journal-title":"Appl Math Model"},{"key":"785_CR21","doi-asserted-by":"publisher","DOI":"10.1016\/j.tre.2020.101887","volume":"136","author":"M Moshref-Javadi","year":"2020","unstructured":"Moshref-Javadi M, Lee S, Winkenbach M (2020) Design and evaluation of a multi-trip delivery model with truck and drones. Transp Res Part E Logist Transp Rev 136:101887. https:\/\/doi.org\/10.1016\/j.tre.2020.101887","journal-title":"Transp Res Part E Logist Transp Rev"},{"key":"785_CR22","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.trc.2015.03.005","volume":"54","author":"CC Murray","year":"2015","unstructured":"Murray CC, Chu AG (2015) The flying sidekick traveling salesman problem: optimization of drone-assisted parcel delivery. Transp Res Part C Emerg Technol 54:86\u2013109. https:\/\/doi.org\/10.1016\/j.trc.2015.03.005","journal-title":"Transp Res Part C Emerg Technol"},{"key":"785_CR23","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1016\/j.trc.2019.11.003","volume":"110","author":"CC Murray","year":"2020","unstructured":"Murray CC, Raj R (2020) The multiple flying sidekicks traveling salesman problem: parcel delivery with multiple drones. Transp Res Part C Emerg Technol 110:368\u2013398. https:\/\/doi.org\/10.1016\/j.trc.2019.11.003","journal-title":"Transp Res Part C Emerg Technol"},{"issue":"4","key":"785_CR24","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1002\/net.21818","volume":"72","author":"A Otto","year":"2018","unstructured":"Otto A, Agatz N, Campbell J, Golden B, Pesch E (2018) Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: a survey. Networks 72(4):411\u2013458. https:\/\/doi.org\/10.1002\/net.21818","journal-title":"Networks"},{"key":"785_CR25","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2019.104802","volume":"113","author":"S Poikonen","year":"2020","unstructured":"Poikonen S, Golden B (2020) Multi-visit drone routing problem. Comput Oper Res 113:104802. https:\/\/doi.org\/10.1016\/j.cor.2019.104802","journal-title":"Comput Oper Res"},{"issue":"1","key":"785_CR26","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/j.ejor.2022.10.015","volume":"308","author":"A Rave","year":"2023","unstructured":"Rave A, Fontaine P, Kuhn H (2023) Drone location and vehicle fleet planning with trucks and aerial drones. Eur J Oper Res 308(1):113\u2013130. https:\/\/doi.org\/10.1016\/j.ejor.2022.10.015","journal-title":"Eur J Oper Res"},{"issue":"2","key":"785_CR27","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1287\/trsc.2020.1017","volume":"55","author":"R Roberti","year":"2021","unstructured":"Roberti R, Ruthmair M (2021) Exact methods for the traveling salesman problem with drone. Transp Sci 55(2):315\u2013335. https:\/\/doi.org\/10.1287\/trsc.2020.1017","journal-title":"Transp Sci"},{"key":"785_CR28","doi-asserted-by":"crossref","unstructured":"Rave A, Fontaine P, Kuhn H (2023) Drone network design for emergency resupply of pharmacies and ambulances. Available at SSRN 4569199","DOI":"10.2139\/ssrn.4569199"},{"key":"785_CR29","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/j.trc.2019.02.018","volume":"102","author":"D Sacramento","year":"2019","unstructured":"Sacramento D, Pisinger D, R\u00f8pke S (2019) An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones. Transp Res Part C Emerg Technol 102:289\u2013315. https:\/\/doi.org\/10.1016\/j.trc.2019.02.018","journal-title":"Transp Res Part C Emerg Technol"},{"key":"785_CR30","doi-asserted-by":"publisher","first-page":"620","DOI":"10.1016\/j.trc.2020.01.019","volume":"114","author":"M Salama","year":"2020","unstructured":"Salama M, Srinivas S (2020) Joint optimization of customer location clustering and drone-based routing for last-mile deliveries. Transp Res Part C Emerging Technol 114:620\u2013642. https:\/\/doi.org\/10.1016\/j.trc.2020.01.019","journal-title":"Transp Res Part C Emerging Technol"},{"key":"785_CR31","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.trc.2019.06.016","volume":"106","author":"D Schermer","year":"2019","unstructured":"Schermer D, Moeini M, Wendt O (2019) A matheuristic for the vehicle routing problem with drones and its variants. Transp Res Part C Emerg Technol 106:166\u2013204. https:\/\/doi.org\/10.1016\/j.trc.2019.06.016","journal-title":"Transp Res Part C Emerg Technol"},{"issue":"2","key":"785_CR32","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1002\/net.21958","volume":"76","author":"D Schermer","year":"2020","unstructured":"Schermer D, Moeini M, Wendt O (2020) A branch-and-cut approach and alternative formulations for the traveling salesman problem with drone. Networks 76(2):164\u2013186. https:\/\/doi.org\/10.1002\/net.21958","journal-title":"Networks"},{"key":"785_CR33","doi-asserted-by":"crossref","unstructured":"Seifried, K.: The traveling salesman problem with one truck and multiple drones. Available at SSRN 3389306 (2019)","DOI":"10.2139\/ssrn.3389306"},{"key":"785_CR34","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.trb.2020.11.011","volume":"144","author":"F Tamke","year":"2021","unstructured":"Tamke F, Buscher U (2021) A branch-and-cut algorithm for the vehicle routing problem with drones. Transp Res Part B Methodol 144:174\u2013203. https:\/\/doi.org\/10.1016\/j.trb.2020.11.011","journal-title":"Transp Res Part B Methodol"},{"key":"785_CR35","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/j.trb.2022.12.007","volume":"168","author":"GO Tini\u00e7","year":"2023","unstructured":"Tini\u00e7 GO, Karasan OE, Kara BY, Campbell JF, Ozel A (2023) Exact solution approaches for the minimum total cost traveling salesman problem with multiple drones. Transp Res Part B Methodol 168:81\u2013123. https:\/\/doi.org\/10.1016\/j.trb.2022.12.007","journal-title":"Transp Res Part B Methodol"},{"issue":"4","key":"785_CR36","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1007\/s11590-016-1035-3","volume":"11","author":"X Wang","year":"2017","unstructured":"Wang X, Poikonen S, Golden B (2017) The vehicle routing problem with drones: several worst-case results. Optim Lett 11(4):679\u2013697. https:\/\/doi.org\/10.1007\/s11590-016-1035-3","journal-title":"Optim Lett"},{"issue":"20","key":"785_CR37","doi-asserted-by":"publisher","first-page":"4305","DOI":"10.3390\/math11204305","volume":"11","author":"VF Yu","year":"2023","unstructured":"Yu VF, Lin S-W, Jodiawan P, Lai Y-C (2023) Solving the flying sidekick traveling salesman problem by a simulated annealing heuristic. Mathematics 11(20):4305","journal-title":"Mathematics"}],"container-title":["OR Spectrum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00291-024-00785-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00291-024-00785-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00291-024-00785-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,12]],"date-time":"2025-03-12T09:22:18Z","timestamp":1741771338000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00291-024-00785-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,29]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["785"],"URL":"https:\/\/doi.org\/10.1007\/s00291-024-00785-9","relation":{},"ISSN":["0171-6468","1436-6304"],"issn-type":[{"type":"print","value":"0171-6468"},{"type":"electronic","value":"1436-6304"}],"subject":[],"published":{"date-parts":[[2024,8,29]]},"assertion":[{"value":"31 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 August 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}