Machine-Learning–Based Arc Selection for Constrained Shortest Path Problems in Column Generation

References

• Alvarez A, Louveaux Q, Wehenkel L (2017) A machine learning-based approximation of strong branching. INFORMS J. Comput. 29:185–195.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
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1996) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46:316–329.Link, Google Scholar
• Bengio Y, Lodi A, Prouvost A (2021) Machine learning for combinatorial optimization: A methodological tour d’horizon. Eur. J. Oper. Res. 290(2):405–421.Google Scholar
• Contardo C, Desaulniers G, Lessard F (2015) Reaching the elementary lower bound in the vehicle routing problem with time windows. Networks 65(1):88–99.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
• Desaulniers G, Desrosiers J, Solomon MM (2005) Column Generation (Springer, New York).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
• Desaulniers G, Madsen OBG, Ropke S (2014) The vehicle routing problem with time windows. Toth P, Vigo D, eds. Vehicle Routing: Problems, Methods and Applications, 2nd ed. (SIAM, Philadelphia), 119–159.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 (Springer, Boston).Google Scholar
• Desrochers M, Soumis F (1988) A generalized permanent labeling algorithm for the shortest path problem with time windows. Inform. Systems Oper. Res. 26(3):191–212.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
• 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.Google Scholar
• Freling R, Wagelmans APM, Paixão JMP (1999) An overview of models and techniques for integrating vehicle and crew scheduling. Wilson NHM, ed. Computer-Aided Transit Scheduling (Springer, Berlin), 441–460.Google Scholar
• Fukasawa R, Lysgaard J, Poggi de Aragão M, Reis M, Uchoa E, Werneck RF (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming 106:491–511.Google Scholar
• Gamache M, Soumis F, Marquis G, Desrosiers J (1999) A column generation approach for large-scale aircrew rostering problems. Oper. Res. 47(2):247–263.Link, Google Scholar
• Gasse M, Chételat D, Ferroni N, Charlin L, Lodi A (2019) Exact combinatorial optimization with graph convolutional neural networks. Wallach H, et al. eds. Advances in Neural Information Processing Systems, vol. 32 (NIPS 2019) (Curran Associates, Inc., Red Hook, NY), 15554–15566.Google Scholar
• Haase K, Desaulniers G, Desrosiers J (2001) Simultaneous vehicle and crew scheduling in urban mass transit systems. Transportation Sci. 35(3):286–303.Link, Google Scholar
• Homberger J, Gehring H (2005) A two-phase hybrid metaheuristic for the vehicle routing problem with time windows. Eur. J. Oper. Res. 162(1):220–238.Google Scholar
• Irnich S (2008) Resource extension functions: properties, inversion, and generalization to segments. OR Spectrum 30(1):113–148.Google Scholar
• Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation (Springer, Boston, MA), 33–65.Google Scholar
• Irnich S, Villeneuve D (2006) The shortest-path problem with resource constraints and k-cycle elimination for k ¿= 3. INFORMS J. Comput. 18(3):391–406.Link, Google Scholar
• Khalil EB, Bodic PL, Song L, Nemhauser G, Dilkina B (2016) Learning to branch in mixed integer programming. Proc. 30th AAAI Conf. on Artificial Intelligence (AAAI Press, Palo Alto, CA), 724–731.Google Scholar
• Lodi A, Zarpellon G (2017) On learning and branching: a survey. TOP 25(2):207–236.Google Scholar
• Morabit M, Desaulniers G, Lodi A (2021) Machine-learning-based column selection for column generation. Transportation Sci. 55(4):815–831.Link, 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.Google Scholar
• Václavík R, Novák A, Šůcha P, Hanzálek Z (2018) Accelerating the branch-and-price algorithm using machine learning. Eur. J. Oper. Res. 271(3):1055–1069.Google Scholar