The Traveling Salesman Problem with Drones: The Benefits of Retraversing the Arcs

References

• Agatz N, Bouman P, Schmidt M (2018) Optimization approaches for the traveling salesman problem with drone. Transportation Sci. 52(4):965–981.Link, Google Scholar
• Bakir I, Tiniç GÖ (2020) Optimizing drone-assisted last-mile deliveries: The vehicle routing problem with flexible drones. Optimization Online. Accessed February 5, 2023, http://www.optimization-online.org/DB_FILE/2020/04/7737.pdf.Google Scholar
• Boccia M, Masone A, Sforza A, Sterle C (2021a) A column-and-row generation approach for the flying sidekick travelling salesman problem. Transportation Res. Part C Emerging Tech. 124:102913.Crossref, Google Scholar
• Boccia M, Masone A, Sforza A, Sterle C (2021b) An exact approach for a variant of the FS-TSP. Transportation Res. Procedia 52:51–58.Google Scholar
• Bouman P, Agatz N, Schmidt M (2018) Dynamic programming approaches for the traveling salesman problem with drone. Networks 72(4):528–542.Crossref, Google Scholar
• Boysen N, Fedtke S, Schwerdfeger S (2021) Last-mile delivery concepts: A survey from an operational research perspective. OR Spectrum 43(1):1–58.Crossref, Google Scholar
• Cavani S, Iori M, Roberti R (2021) Exact methods for the traveling salesman problem with multiple drones. Transportation Res. Part C Emerging Tech. 130:103280.Crossref, Google Scholar
• Chung SH, Sah B, Lee J (2020) Optimization for drone and drone-truck combined operations: A review of the state of the art and future directions. Comput. Oper. Res. 123:105004.Crossref, Google Scholar
• CNBC News (2020) Amazon wins FAA approval for Prime Air drone delivery fleet. (August 31), https://www.cnbc.com/2020/08/31/amazon-prime-now-drone-delivery-fleet-gets-faa-approval.html.Google Scholar
• Coutinho WP, Battarra M, Fliege J (2018) The unmanned aerial vehicle routing and trajectory optimisation problem, a taxonomic review. Comput. Indust. Engrg. 120:116–128.Crossref, Google Scholar
• Dell’Amico M, Montemanni R, Novellani S (2021a) Algorithms based on branch and bound for the flying sidekick traveling salesman problem. Omega 104:102493.Crossref, Google Scholar
• Dell’Amico M, Montemanni R, Novellani S (2021b) Drone-assisted deliveries: New formulations for the flying sidekick traveling salesman problem. Optim. Lett. 15(5):1617–1648.Crossref, Google Scholar
• Dell’Amico M, Montemanni R, Novellani S (2021c) Modeling the flying sidekick traveling salesman problem with multiple drones. Networks 78(3):303–327.Crossref, Google Scholar
• Dell’Amico M, Montemanni R, Novellani S (2022) Exact models for the flying sidekick traveling salesman problem. Internat. Trans. Oper. Res. 29(3):1360–1393.Crossref, Google Scholar
• Ding Y, Xin B, Chen J (2021) A review of recent advances in coordination between unmanned aerial and ground vehicles. Unmanned Systems 9(02):97–117.Crossref, Google Scholar
• Dinur I, Steurer D (2014) Analytical approach to parallel repetition. Proc. 46th Annual ACM Sympos. Theory Comput. (STOC ’14) (Association for Computing Machinery, New York), 624–633.Google Scholar
• El-Adle AM, Ghoniem A, Haouari M (2021) Parcel delivery by vehicle and drone. J. Oper. Res. Soc. 72(2):398–416.Crossref, Google Scholar
• European Council (2019) Drones: Reform of EU aviation safety. Accessed February 5, 2023, https://www.consilium.europa.eu/en/policies/drones/.Google Scholar
• Freitas JC, Penna PHV, Toffolo TA (2021) Exact and heuristic approaches to drone delivery problems. Preprint, submitted July 29, https://arxiv.org/abs/2108.01996.Google Scholar
• González-R PL, Canca D, Andrade-Pineda JL, Calle M, León-Blanco JM (2020) Truck-drone team logistics: A heuristic approach to multi-drop route planning. Transportation Res. Part C Emerging Tech. 114:657–680.Crossref, Google Scholar
• Ha QM, Vu DM, Le XT, Hoang MH (2021) The traveling salesman problem with multi-visit drone. J. Comput. Sci. Cybernetics 37(4):465–493.Crossref, Google Scholar
• Jeon A, Kang J, Choi B, Kim N, Eun J, Cheong T (2021) Unmanned aerial vehicle last-mile delivery considering backhauls. IEEE Access 9:85017–85033.Crossref, Google Scholar
• Jeong HY, Lee S (2019) Optimization of vehicle-carrier routing: Mathematical model and comparison with related routing models. Procedia Manufacturing 39:307–313.Crossref, Google Scholar
• Jeong HY, Song BD, Lee S (2019) Truck-drone hybrid delivery routing: Payload-energy dependency and no-fly zones. Internat. J. Production Econom. 214:220–233.Crossref, Google Scholar
• Khoufi I, Laouiti A, Adjih C (2019) A survey of recent extended variants of the traveling salesman and vehicle routing problems for unmanned aerial vehicles. Drones 3(3):66.Crossref, Google Scholar
• Kitjacharoenchai P, Ventresca M, Moshref-Javadi M, Lee S, Tanchoco JM, Brunese PA (2019) Multiple traveling salesman problem with drones: Mathematical model and heuristic approach. Comput. Indust. Engrg. 129:14–30.Crossref, Google Scholar
• Li H, Chen J, Wang F, Bai M (2021) Ground-vehicle and unmanned-aerial-vehicle routing problems from two-echelon scheme perspective: A review. Eur. J. Oper. Res. 294(3):1078–1095.Crossref, Google Scholar
• Luo H, Zhang P, Wang J, Wang G, Meng F (2019) Traffic patrolling routing problem with drones in an urban road system. Sensors 19(23):5164.Crossref, Google Scholar
• Luo Z, Poon M, Zhang Z, Liu Z, Lim A (2021) The multi-visit traveling salesman problem with multi-drones. Transportation Res. Part C Emerging Tech. 128:103172.Crossref, Google Scholar
• Macrina G, Pugliese LDP, Guerriero F (2020) The green-vehicle routing problem: A survey. Derbel H, Jarboui B, Siarry P, eds. Modeling and Optimization in Green Logistics (Springer International Publishing, Cham, Switzerland), 1–26.Crossref, Google Scholar
• Macrina G, Pugliese LDP, Guerriero F, Laporte G (2020) Drone-aided routing: A literature review. Transportation Res. Part C Emerging Tech. 120:102762.Crossref, Google Scholar
• Merkert R, Bushell J (2020) Managing the drone revolution: A systematic literature review into the current use of airborne drones and future strategic directions for their effective control. J. Air Transportation Management 89:101929.Crossref, Google Scholar
• Moshref-Javadi M, Winkenbach M (2021) Applications and research avenues for drone-based models in logistics: A classification and review. Expert Systems Appl. 177:114854.Crossref, Google Scholar
• Murray CC, Chu AG (2015) The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Res. Part C Emerging Tech. 54:86–109.Crossref, Google Scholar
• Murray CC, Raj R (2020) The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones. Transportation Res. Part C Emerging Tech. 110:368–398.Crossref, Google Scholar
• 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–458.Crossref, Google Scholar
• Persson E (2021) A systematic literature review on drones’ application in last-mile delivery. Accessed February 5, 2023, http://urn.kb.se/resolve?urn=urn:nbn:se:hig:diva-36733.Google Scholar
• Picard JC, Queyranne M (1978) The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling. Oper. Res. 26(1):86–110.Link, Google Scholar
• Poikonen S, Campbell JF (2021) Future directions in drone routing research. Networks 77(1):116–126.Crossref, Google Scholar
• Roberti R, Ruthmair M (2021) Exact methods for the traveling salesman problem with drone. Transportation Sci. 55(2):315–335.Link, Google Scholar
• Roca-Riu M, Menendez M (2019) Logistic deliveries with drones: State of the art of practice and research. 19th Swiss Transport Res. Conf. (STRC, Ascona, Switzerland). https://www.research-collection.ethz.ch/handle/20.500.11850/342823.Google Scholar
• Rojas Viloria D, Solano-Charris EL, Muñoz-Villamizar A, Montoya-Torres JR (2021) Unmanned aerial vehicles/drones in vehicle routing problems: A literature review. Internat. Trans. Oper. Res. 28(4):1626–1657.Crossref, Google Scholar
• 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–186.Crossref, Google Scholar
• Seifried K (2019) The traveling salesman problem with one truck and multiple drones. Preprint, submitted May 1, http://dx.doi.org/10.2139/ssrn.3389306.Google Scholar
• Tamke F, Buscher U (2021) A branch-and-cut algorithm for the vehicle routing problem with drones. Transportation Res. Part B Methodological 144:174–203.Crossref, Google Scholar
• Tang Z, van Hoeve WJ, Shaw P (2019) A study on the traveling salesman problem with a drone. Rousseau LM, Stergiou K, eds. Integration of Constraint Programming, Artificial Intelligence, and Operations Research (Springer International Publishing, Cham, Switzerland), 557–564.Crossref, Google Scholar
• The Washington Post (2021) German start-up creates a delivery drone capable of toting three separate packages. (April 28), https://www.washingtonpost.com/technology/2021/04/28/drone-delivery-triple-drop/.Google Scholar
• Vásquez SA, Angulo G, Klapp MA (2021) An exact solution method for the TSP with drone based on decomposition. Comput. Oper. Res. 127:105127.Crossref, Google Scholar
• Wang X, Poikonen S, Golden B (2017) The vehicle routing problem with drones: Several worst-case results. Optim. Lett. 11(4):679–697.Crossref, Google Scholar
• Yurek EE, Ozmutlu HC (2018) A decomposition-based iterative optimization algorithm for traveling salesman problem with drone. Transportation Res. Part C Emerging Tech. 91:249–262.Crossref, Google Scholar
• Zhou H, Qin H, Cheng C, Rousseau LM (2022) A branch-and-price algorithm for the vehicle routing problem with drones. Optimization Online. Accessed July 6, 2022, http://www.optimization-Online.org/DB_FILE/2022/02/8801.pdf.Google Scholar
• Zhu T, Boyles SD, Unnikrishnan A (2022) Electric vehicle traveling salesman problem with drone. Preprint, submitted April 29, https://arxiv.org/abs/2201.07992.Google Scholar