A Branch-and-Price-and-Cut Algorithm for the Vehicle Routing Problem with Two-Dimensional Loading Constraints

References

• Achterberg T, Koch T, Martin A (2005) Branching rules revisited. Oper. Res. Lett. 33(1):42–54.Crossref, Google Scholar
• Alinaghian M, Zamanlou K, Sabbagh MS (2017) A bi-objective mathematical model for two-dimensional loading time-dependent vehicle routing problem. J. Oper. Res. Soc. 68(11):1422–1441.Crossref, Google Scholar
• Annouch A, Bellabdaoui A, Minkhar J (2016) Split delivery and pickup vehicle routing problem with two-dimensional loading constraints. Proc. 11th Internat. Conf. on Intelligent Systems: Theories and Applications (IEEE, New York), 1–6.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
• Brass P (2008) Advanced Data Structures, vol. 193 (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Burke EK, Kendall G, Whitwell G (2004) A new placement heuristic for the orthogonal stock-cutting problem. Oper. Res. 52(4):655–671.Link, Google Scholar
• Costa L, Contardo C, Desaulniers G (2019) Exact branch-price-and-cut algorithms for vehicle routing. Transportation Sci. 53(4):946–985.Link, Google Scholar
• Côté JF, Dell’Amico M, Iori M (2014a) Combinatorial benders’ cuts for the strip packing problem. Oper. Res. 62(3):643–661.Link, Google Scholar
• Côté JF, Gendreau M, Potvin JY (2014b) An exact algorithm for the two-dimensional orthogonal packing problem with unloading constraints. Oper. Res. 62(5):1126–1141.Link, Google Scholar
• Côté JF, Gendreau M, Potvin JY (2020) The vehicle routing problem with stochastic two-dimensional items. Transportation Sci. 54(2):453–469.Link, Google Scholar
• Desaulniers G, Desrosiers J, Solomon MM (2006) Column Generation, vol. 5 (Springer Science & Business Media, New York).Google Scholar
• Desaulniers G, Desrosiers J, Spoorendonk S (2011) Cutting planes for branch-and-price algorithms. Networks 58(4):301–310.Crossref, Google Scholar
• Desaulniers G, Lessard F, Hadjar A (2008) Tabu search, partial elementarity, and generalized k-path inequalities for the vehicle routing problem with time windows. Transportation Sci. 42(3):387–404.Link, 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
• Dominguez O, Guimarans D, Juan AA, de la Nuez I (2016a) A biased-randomised large neighbourhood search for the two-dimensional vehicle routing problem with backhauls. Eur. J. Oper. Res. 255(2):442–462.Crossref, Google Scholar
• Dominguez O, Juan AA, Barrios B, Faulin J, Agustin A (2016b) Using biased randomization for solving the two-dimensional loading vehicle routing problem with heterogeneous fleet. Ann. Oper. Res. 236(2):383–404.Crossref, Google Scholar
• Feillet D, Gendreau M, Rousseau LM (2007) New refinements for the solution of vehicle routing problems with branch and price. Inform. Systems Oper. Res. 45(4):239–256.Crossref, 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
• Fischetti M, González JJS, Toth P (1995) Experiments with a multi-commodity formulation for the symmetric capacitated vehicle routing problem. Proc. 3rd Meeting of the EURO Working Group on Transportation (Citeseer), 169–173.Google Scholar
• Fuellerer G, Doerner KF, Hartl RF, Iori M (2009) Ant colony optimization for the two-dimensional loading vehicle routing problem. Comput. Oper. Res. 36(3):655–673.Crossref, Google Scholar
• Gendreau M, Iori M, Laporte G, Martello S (2006) A tabu search algorithm for a routing and container loading problem. Transportation Sci. 40(3):342–350.Link, Google Scholar
• Gendreau M, Iori M, Laporte G, Martello S (2008) A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints. Networks 51(1):4–18.Crossref, Google Scholar
• Guimarans D, Dominguez O, Panadero J, Juan AA (2018) A simheuristic approach for the two-dimensional vehicle routing problem with stochastic travel times. Simulations Modeling Practical Theory 89:1–14.Crossref, Google Scholar
• Hokama P, Miyazawa FK, Xavier EC (2016) A branch-and-cut approach for the vehicle routing problem with loading constraints. Expert Systems Appl. 47:1–13.Crossref, Google Scholar
• Hong S, Zhang D, Lau HC, Zeng X, Si YW (2014) A hybrid heuristic algorithm for the 2d variable-sized bin packing problem. Eur. J. Oper. Res. 238(1):95–103.Crossref, Google Scholar
• Iori M, Salazar-González JJ, Vigo D (2007) An exact approach for the vehicle routing problem with two-dimensional loading constraints. Transportation Sci. 41(2):253–264.Link, Google Scholar
• Kang J, Park S (2003) Algorithms for the variable sized bin packing problem. Eur. J. Oper. Res. 147(2):365–372.Crossref, Google Scholar
• Khebbache-Hadji S, Prins C, Yalaoui A, Reghioui M (2013) Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows. Central Eur. J. Oper. Res. 21(2):307–336.Crossref, Google Scholar
• Leung SC, Zhou X, Zhang D, Zheng J (2011) Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem. Comput. Oper. Res. 38(1):205–215.Crossref, Google Scholar
• Lysgaard J, Letchford AN, Eglese RW (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Programming 100(2):423–445.Crossref, Google Scholar
• Mahvash B, Awasthi A, Chauhan S (2017) A column generation based heuristic for the capacitated vehicle routing problem with three-dimensional loading constraints. Internat. J. Production Res. 55(6):1730–1747.Crossref, Google Scholar
• Martello S, Vigo D (1998) Exact solution of the two-dimensional finite bin packing problem. Management Sci. 44(3):388–399.Link, Google Scholar
• Martinelli R, Pecin D, Poggi M (2014) Efficient elementary and restricted non-elementary route pricing. Eur. J. Oper. Res. 239(1):102–111.Crossref, Google Scholar
• Pinto T, Alves C, de Carvalho JV (2015) Variable neighborhood search for the elementary shortest path problem with loading constraints. Proc. Internat. Conf. on Comput. Sci. and Its Appl. (Springer, Berlin), 474–489.Google Scholar
• Pinto T, Alves C, de Carvalho JV (2016) A branch-and-price algorithm for the vehicle routing problem with 2-dimensional loading constraints. Proc. Internat. Conf. on Comput. Logist. (Springer, Berlin), 321–336.Google Scholar
• Pisinger D, Sigurd M (2005) The two-dimensional bin packing problem with variable bin sizes and costs. Discrete Optim. 2(2):154–167.Crossref, Google Scholar
• Pollaris H, Braekers K, Caris A, Janssens GK, Limbourg S (2015) Vehicle routing problems with loading constraints: State-of-the-art and future directions. OR Spectrum 37(2):297–330.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
• Song X, Jones D, Asgari N, Pigden T (2019) Multi-objective vehicle routing and loading with time window constraints: A real-life application. Ann. Oper. Res. 291(1):799–825. Crossref, Google Scholar
• Tarantilis CD, Zachariadis EE, Kiranoudis CT (2009) A hybrid metaheuristic algorithm for the integrated vehicle routing and three-dimensional container-loading problem. IEEE Trans. Intelligent Transportation Systems 10(2):255–271.Crossref, Google Scholar
• Wei L, Zhang Z, Zhang D, Leung SC (2018) A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints. Eur. J. Oper. Res. 265(3):843–859.Crossref, Google Scholar
• Zachariadis EE, Tarantilis CD, Kiranoudis CT (2009) A guided tabu search for the vehicle routing problem with two-dimensional loading constraints. Eur. J. Oper. Res. 195(3):729–743.Crossref, Google Scholar
• Zhang X, Chen L, Gendreau M, Langevin A (2021) Learning-based branch-and-price algorithms for the vehicle routing problem with time windows and two-dimensional loading constraints. INFORMS J. Comput., ePub ahead of print December 29, 2021, https://doi.org/10.12878/ijoc.2021.1110.Google Scholar
• Zhang X, Chen L, Gendreau M, Langevin A (2022) A branch-and-cut algorithm for the vehicle routing problem with two-dimensional loading constraints. Eur. J. Oper. Res., ePub ahead of print January 7, 2022, http://doi.org/10.1016/j.ejor.2021/12/050.Google Scholar