A Branch-and-Price Algorithm for Robust Drone-Vehicle Routing Problem with Time Windows

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
• Agra A, Christiansen M, Figueiredo R, Hvattum LM, Poss M, Requejo C (2013) The robust vehicle routing problem with time windows. Comput. Oper. Res. 40(3):856–866.Crossref, Google Scholar
• Bertsimas D, Sim M (2004) The price of robustness. Oper. Res. 52(1):35–53.Link, Google Scholar
• Boysen N, Briskorn D, Fedtke S, Schwerdfeger S (2018) Drone delivery from trucks: Drone scheduling for given truck routes. Networks 72(4):506–527.Crossref, Google Scholar
• Chabrier A (2006) Vehicle routing problem with elementary shortest path based column generation. Comput. Oper. Res. 33(10):2972–2990.Crossref, Google Scholar
• De La Vega J, Munari P, Morabito R (2020) Exact approaches to the robust vehicle routing problem with time windows and multiple deliverymen. Comput. Oper. Res. 124:105062.Crossref, Google Scholar
• Dell’Amico M, Martello S (2005) A note on exact algorithms for the identical parallel machine scheduling problem. Eur. J. Oper. Res. 160(2):576–578.Crossref, Google Scholar
• Dell’Amico M, Montemanni R, Novellani S (2020) Matheuristic algorithms for the parallel drone scheduling traveling salesman problem. Ann. Oper. Res. 289(2):211–226.Crossref, Google Scholar
• Desaulniers G, Desrosiers J, Ioachim I, Solomon MM, Soumis F, Villeneuve D (1998) A unified framework for deterministic time constrained vehicle routing and crew scheduling problems. Crainic TG, Laporte G, eds. Fleet Management and Logistics (Springer, Boston), 57–93.Crossref, Google Scholar
• Desrochers M, Desrosiers J, Solomon M (1992) A new optimization algorithm for the vehicle routing problem with time windows. Oper. Res. 40(2):342–354.Link, Google Scholar
• Deutsche Post (2014) DHL parcelcopter launches initial operations for research purposes. Accessed February 15, 2025, https://www.theguardian.com/technology/2014/sep/25/german-dhl-launches-first-commercial-drone-delivery-service.Google Scholar
• Dohn A, Mason A (2013) Branch-and-price for staff rostering: An efficient implementation using generic programming and nested column generation. Eur. J. Oper. Res. 230(1):157–169.Crossref, Google Scholar
• Drexl M, Schneider M (2015) A survey of variants and extensions of the location-routing problem. Eur. J. Oper. Res. 241(2):283–308.Crossref, Google Scholar
• Du B, Sun D, Manyam SG, Casbeer DW (2020) Cooperative air-ground vehicle routing using chance-constrained optimization. 2020 Amer. Control Conf. ACC (IEEE, Piscataway, NJ), 392–397.Google Scholar
• FedEx (2019) Wing drone deliveries take flight in first-of-its-kind trial with FedEx. Accessed February 15, 2025, https://newsroom.fedex.com/newsroom/global-english/wing-drone-deliveries-take-flight-in-first-of-its-kind-trial-with-fedex.Google Scholar
• Feillet D, Dejax P, Gendreau M, Gueguen C (2004) An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks 44(3):216–229.Crossref, Google Scholar
• Gary MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (WH Freeman and Company, New York).Google Scholar
• Gérard M, Clautiaux F, Sadykov R (2016) Column generation based approaches for a tour scheduling problem with a multi-skill heterogeneous workforce. Eur. J. Oper. Res. 252(3):1019–1030.Crossref, Google Scholar
• Ha QM, Deville Y, Pham QD, Ha MH (2018) On the min-cost traveling salesman problem with drone. Transportation Res. Part C Emerging Tech. 86:597–621.Crossref, Google Scholar
• Ham AM (2018) Integrated scheduling of m-truck, m-drone, and m-depot constrained by time-window, drop-pickup, and m-visit using constraint programming. Transportation Res. Part C Emerging Tech. 91:1–14.Crossref, Google Scholar
• Irnich S (2008) Resource extension functions: Properties, inversion, and generalization to segments. OR Spectrum 30(1):113–148.Crossref, Google Scholar
• Joo J, Lee C (2025) A branch-and-price algorithm for robust drone-vehicle routing problem with time windows. http://dx.doi.org/10.1287/ijoc.2023.0484.cd, https://github.com/INFORMSJoC/2023.0484.Google Scholar
• Kang M, Lee C (2021) An exact algorithm for heterogeneous drone-truck routing problem. Transportation Sci. 55(5):1088–1112.Link, Google Scholar
• Kim S, Moon I (2019) Traveling salesman problem with a drone station. IEEE Trans. Systems Man Cybernetics Systems 49(1):42–52.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
• Klein T, Becker P (2021) Exact separation algorithms for the parallel drone scheduling traveling salesman problem. Comput. Logistics 12th Internat. Conf. ICCL 2021, Lecture Notes in Computer Science (Springer, Cham, Switzerland), 377–392.Google Scholar
• Kuo R, Lu SH, Lai P, Mara STW (2022) Vehicle routing problem with drones considering time windows. Expert Systems Appl. 191:116264.Crossref, Google Scholar
• Lee C, Lee K, Park S (2012) Robust vehicle routing problem with deadlines and travel time/demand uncertainty. J. Oper. Res. Soc. 63(9):1294–1306.Crossref, Google Scholar
• Munari P, Moreno A, Vega JDL, Alem D, Gondzio J, Morabito R (2019) The robust vehicle routing problem with time windows: Compact formulation and branch-price-and-cut method. Transportation Sci. 53(4):1043–1066.Link, 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
• Nguyen MA, Luong HL, Hà MH, Ban HB (2021) An efficient branch-and-cut algorithm for the parallel drone scheduling traveling salesman problem. Preprint, submitted November 9, https://arxiv.org/abs/2111.11307.Google Scholar
• Poikonen S, Golden B (2019) Multi-visit drone routing problem. Comput. Oper. Res. 113:104802.Crossref, Google Scholar
• Popper B (2015) Drones could make Amazon’s dream of free delivery profitable. Accessed February 15, 2025, http://www.theverge.com/2015/6/3/8719659/amazon-prime-air-drone-delivery-profit-free-shipping-small-items.Google Scholar
• Pugliese LDP, Guerriero F (2017) Last-mile deliveries by using drones and classical vehicles. Sforza A, Sterle C, eds. Optimization and Decision Science: Methodologies and Applications ODS, Springer Proceedings in Mathematics & Statistics (Springer, Cham, Switzerland), 557–565.Google Scholar
• Sacramento D, Pisinger D, Ropke S (2019) An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones. Transportation Res. Part C Emerging Tech. 102:289–315.Crossref, Google Scholar
• Schermer D, Moeini M, Wendt O (2019) The traveling salesman drone station location problem. Le Thi H, Le H, Pham Dinh T, eds. Optim. Complex Systems Theory Models Algorithms Applications (Springer, Cham, Switzerland), 1129–1138.Google Scholar
• Shi G, Karapetyan N, Asghar AB, Reddinger JP, Dotterweich J, Humann J, Tokekar P (2022) Risk-aware UAV-UGV rendezvous with chance-constrained Markov decision process. Preprint, submitted April 10, https://arxiv.org/abs/2204.04767.Google Scholar
• Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35(2):254–265.Link, Google Scholar
• Toth P, Vigo D, eds. (2014) Vehicle Routing: Problems, Methods, and Applications, 2nd ed. (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• UPS (2019) UPS and CVS make first residential drone deliveries of prescription medicines. Accessed February 15, 2025, https://www.reuters.com/article/technology/ups-drone-makes-first-home-prescription-deliveries-for-cvs-idUSKBN1XF2JC/.Google Scholar
• Vásquez SA, Angulo G, Klapp MA (2020) 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 Methodological 122:350–364.Crossref, Google Scholar
• Yang Y, Yan C, Cao Y, Roberti R (2023) Planning robust drone-truck delivery routes under road traffic uncertainty. Eur. J. Oper. Res. 309(3):1145–1160.Crossref, Google Scholar
• Yin F, Zhao Y (2022) Distributionally robust equilibrious hybrid vehicle routing problem under twofold uncertainty. Inform. Sci. 609:1239–1255.Crossref, Google Scholar
• Yu Q, Cheng C, Zhu N (2022) Robust team orienteering problem with decreasing profits. INFORMS J. Comput. 34(6):3215–3233.Link, Google Scholar
• Zhang D, Li D, Sun H, Hou L (2021) A vehicle routing problem with distribution uncertainty in deadlines. Eur. J. Oper. Res. 292(1):311–326.Crossref, Google Scholar