Decremental State-Space Relaxations for the Basic Traveling Salesman Problem with a Drone

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
• Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283.Link, Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2012) New state-space relaxations for solving the traveling salesman problem with time windows. INFORMS J. Comput. 24(3):356–371.Link, 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. Proc. 52:51–58.Crossref, Google Scholar
• Boland N, Dethridge J, Dumitrescu I (2006) Accelerated label setting algorithms for the elementary resource constrained shortest path problem. Oper. Res. Lett. 34(1):58–68.Crossref, 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
• Christofides N, Mingozzi A, Toth P (1981) State-space relaxation procedures for the computation of bounds to routing problems. Networks 11(2):145–164.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
• 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) Benchmark instances and optimal solutions for the traveling salesman problem with drone. Preprint, submitted July 28, https://arxiv.org/abs/2107.13275.Google Scholar
• Dell’Amico M, Montemanni R, Novellani S (2021c) 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 (2022) Exact models for the flying sidekick traveling salesman problem. Internat. Trans. Oper. Res. 29(3):1360–1393.Crossref, Google Scholar
• Drexl M (2012) Synchronization in vehicle routing-a survey of VRPs with multiple synchronization constraints. Transportation Sci. 46(3):297–316.Link, Google Scholar
• Gambella C, Lodi A, Vigo D (2018) Exact solutions for the carrier-vehicle traveling salesman problem. Transportation Sci. 52(2):320–330.Link, Google Scholar
• Ha QM, Deville Y, Pham QD, Hà MH (2018) On the min-cost traveling salesman problem with drone. Transportation Res. Part C Emerging Tech. 86:597–621.Crossref, Google Scholar
• Irnich S, Desaulniers G, Desrosiers J, Hadjar A (2010) Path-reduced costs for eliminating arcs in routing and scheduling. INFORMS J. Comput. 22(2):297–313.Link, 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
• Lera-Romero G, Miranda Bront JJ, Soulignac FJ (2020) Linear edge costs and labeling algorithms: The case of the time-dependent vehicle routing problem with time windows. Networks 76(1):24–53.Crossref, Google Scholar
• Lera-Romero G, Miranda Bront JJ, Soulignac FJ (2022) Dynamic programming for the time-dependent traveling salesman problem with time windows. INFORMS J. Comput. 34(6):3292–3308.Link, Google Scholar
• Liang YJ, Luo ZX (2022) A survey of truck–drone routing problem: Literature review and research prospects. J. Oper. Res. Soc. China 10(2):343–377.Crossref, Google Scholar
• Macrina G, Di Puglia Pugliese L, Guerriero F, Laporte G (2020) Drone-aided routing: A literature review. Transportation Res. Part C Emerging Tech. 120:102762.Crossref, Google Scholar
• Masone A, Poikonen S, Golden BL (2022) The multivisit drone routing problem with edge launches: An iterative approach with discrete and continuous improvements. Networks 80(2):193–215.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
• Poikonen S, Golden B (2020) Multi-visit drone routing problem. Comput. Oper. Res. 113:104802.Crossref, Google Scholar
• Poikonen S, Golden B, Wasil EA (2019) A branch-and-bound approach to the traveling salesman problem with a drone. INFORMS J. Comput. 31(2):335–346.Link, Google Scholar
• Ponza A (2016) Optimization of drone-assisted parcel delivery. Master’s thesis, Universitá Degli Studi di Padova, Padua, Italy. Accessed November 17, 2022, https://thesis.unipd.it/handle/20.500.12608/25563.Google Scholar
• Righini G, Salani M (2006) Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optim. 3(3):255–273.Crossref, Google Scholar
• Righini G, Salani M (2008) New dynamic programming algorithms for the resource constrained elementary shortest path problem. Networks 51(3):155–170.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
• 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
• Tang Z, van Hoeve W-J, 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
• Tilk C, Irnich S (2017) Dynamic programming for the minimum tour duration problem. Transportation Sci. 51(2):549–565.Link, Google Scholar
• van Dijck E, Bouman P (2018) A branch-and-cut algorithm for the traveling salesman problem with drone. Master’s thesis, Erasmus University, Rotterdam, Netherlands. http://hdl.handle.net/2105/44107.Google Scholar
• Vanderbeck F, Wolsey LA (2010) Reformulation and decomposition of integer programs. Jünger M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA, eds. 50 Years of Integer Programming 1958–2008: From the Early Years to the State-of-the-Art (Springer, Berlin), 431–502.Crossref, 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 Z, Sheu JB (2019) Vehicle routing problem with drones. Transportation Res. Part B Methodol. 122:350–364.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