IDEAS home Printed from https://ideas.repec.org/a/eee/oprepe/v15y2025ics2214716025000405.html

Reinforcement learning for solving the pricing problem in column generation for routing

Author

Listed:
  • Abouelrous, Abdo
  • Bliek, Laurens
  • Gabor, Adriana F.
  • Wu, Yaoxin
  • Zhang, Yingqian

Abstract

In this paper, we address the problem of Column Generation (CG) for routing problems using Reinforcement Learning (RL). Specifically, we use a RL model based on the attention-mechanism architecture to find the columns with most negative reduced cost in the Pricing Problem (PP). Unlike previous Machine Learning (ML) applications for CG, our model deploys an end-to-end mechanism that independently solves the pricing problem without the help of any heuristic. We consider a variant of Vehicle Routing Problem (VRP) as a case study for our method. Through a series of experiments comparing our approach with a Dynamic Programming (DP)-based heuristic for solving the PP, we demonstrate that the proposed method obtains solutions for the linear relaxation up to a reasonable objective gap and significantly faster than the DP-based heuristic for the PP.

Suggested Citation

  • Abouelrous, Abdo & Bliek, Laurens & Gabor, Adriana F. & Wu, Yaoxin & Zhang, Yingqian, 2025. "Reinforcement learning for solving the pricing problem in column generation for routing," Operations Research Perspectives, Elsevier, vol. 15(C).
    • Handle: RePEc:eee:oprepe:v:15:y:2025:i:c:s2214716025000405
    DOI: 10.1016/j.orp.2025.100364
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S2214716025000405
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.orp.2025.100364?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Leonardo Lozano & Daniel Duque & Andrés L. Medaglia, 2016. "An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints," Transportation Science, INFORMS, vol. 50(1), pages 348-357, February.
    2. Mouad Morabit & Guy Desaulniers & Andrea Lodi, 2021. "Machine-Learning–Based Column Selection for Column Generation," Transportation Science, INFORMS, vol. 55(4), pages 815-831, July.
    3. Nadia Giuffrida & Jenny Fajardo-Calderin & Antonio D. Masegosa & Frank Werner & Margarete Steudter & Francesco Pilla, 2022. "Optimization and Machine Learning Applied to Last-Mile Logistics: A Review," Sustainability, MDPI, vol. 14(9), pages 1-16, April.
    4. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    5. Kadyrov, Shirali & Azamov, Azamkhon & Abdumajitov, Yelbek & Turan, Cemil, 2025. "Deep reinforcement learning for dynamic vehicle routing with demand and traffic uncertainty," Operations Research Perspectives, Elsevier, vol. 15(C).
    6. Václavík, Roman & Novák, Antonín & Šůcha, Přemysl & Hanzálek, Zdeněk, 2018. "Accelerating the Branch-and-Price Algorithm Using Machine Learning," European Journal of Operational Research, Elsevier, vol. 271(3), pages 1055-1069.
    7. Guan, Qingshu & Cao, Hui & Tan, Junkai & Jia, Lixin & Yan, Dapeng & Chen, Badong, 2025. "Token-specific deep reinforcement learning for energy-efficient capacitated electric vehicle routing problems," Applied Energy, Elsevier, vol. 396(C).
    8. repec:inm:orijoo:v:5:y:2023:i:2:p:191-210 is not listed on IDEAS
    9. Martin Desrochers & Jacques Desrosiers & Marius Solomon, 1992. "A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows," Operations Research, INFORMS, vol. 40(2), pages 342-354, April.
    10. Moshe Dror, 1994. "Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW," Operations Research, INFORMS, vol. 42(5), pages 977-978, October.
    11. Bengio, Yoshua & Lodi, Andrea & Prouvost, Antoine, 2021. "Machine learning for combinatorial optimization: A methodological tour d’horizon," European Journal of Operational Research, Elsevier, vol. 290(2), pages 405-421.
    12. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    13. Emilie Danna & Claude Pape, 2005. "Branch-and-Price Heuristics: A Case Study on the Vehicle Routing Problem with Time Windows," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 99-129, Springer.
    14. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    15. Santini, Alberto & Plum, Christian E.M. & Ropke, Stefan, 2018. "A branch-and-price approach to the feeder network design problem," European Journal of Operational Research, Elsevier, vol. 264(2), pages 607-622.
    16. Ang Li & Jianping Chen & Qiming Fu & Hongjie Wu & Yunzhe Wang & You Lu, 2022. "A Novel Deep Reinforcement Learning Based Framework for Gait Adjustment," Mathematics, MDPI, vol. 11(1), pages 1-18, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mads Jepsen & Bjørn Petersen & Simon Spoorendonk & David Pisinger, 2008. "Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows," Operations Research, INFORMS, vol. 56(2), pages 497-511, April.
    2. Emilio Zamorano & Annika Becker & Raik Stolletz, 2018. "Task assignment with start time-dependent processing times for personnel at check-in counters," Journal of Scheduling, Springer, vol. 21(1), pages 93-109, February.
    3. Theodore Athanasopoulos & Ioannis Minis, 2013. "Efficient techniques for the multi-period vehicle routing problem with time windows within a branch and price framework," Annals of Operations Research, Springer, vol. 206(1), pages 1-22, July.
    4. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    5. Stefan Irnich & Guy Desaulniers & Jacques Desrosiers & Ahmed Hadjar, 2010. "Path-Reduced Costs for Eliminating Arcs in Routing and Scheduling," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 297-313, May.
    6. Diego Pecin & Claudio Contardo & Guy Desaulniers & Eduardo Uchoa, 2017. "New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 489-502, August.
    7. Guy Desaulniers & François Lessard & Ahmed Hadjar, 2008. "Tabu Search, Partial Elementarity, and Generalized k -Path Inequalities for the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 42(3), pages 387-404, August.
    8. Koutecká, Pavlína & Šůcha, Přemysl & Hůla, Jan & Maenhout, Broos, 2025. "A machine learning approach to rank pricing problems in branch-and-price," European Journal of Operational Research, Elsevier, vol. 320(2), pages 328-342.
    9. Shen, Yunzhuang & Sun, Yuan & Li, Xiaodong & Eberhard, Andrew & Ernst, Andreas, 2023. "Adaptive solution prediction for combinatorial optimization," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1392-1408.
    10. Guy Desaulniers & Diego Pecin & Claudio Contardo, 2019. "Selective pricing in branch-price-and-cut algorithms for vehicle routing," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(2), pages 147-168, June.
    11. Matteo Petris & Claudia Archetti & Diego Cattaruzza & Maxime Ogier & Frédéric Semet, 2025. "A tutorial on Branch-Price-and-Cut algorithms," 4OR, Springer, vol. 23(1), pages 1-52, March.
    12. Gondzio, Jacek & González-Brevis, Pablo & Munari, Pedro, 2013. "New developments in the primal–dual column generation technique," European Journal of Operational Research, Elsevier, vol. 224(1), pages 41-51.
    13. Shyam S. G. Perumal & Jesper Larsen & Richard M. Lusby & Morten Riis & Tue R. L. Christensen, 2022. "A column generation approach for the driver scheduling problem with staff cars," Public Transport, Springer, vol. 14(3), pages 705-738, October.
    14. Asvin Goel & Stefan Irnich, 2017. "An Exact Method for Vehicle Routing and Truck Driver Scheduling Problems," Transportation Science, INFORMS, vol. 51(2), pages 737-754, May.
    15. Qinxiao Yu & Chun Cheng & Ning Zhu, 2022. "Robust Team Orienteering Problem with Decreasing Profits," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3215-3233, November.
    16. Bohan Hu & Feng-Jang Hwang, 2026. "Supermarket-chain grocery delivery optimization through courier coordination," Annals of Operations Research, Springer, vol. 359(3), pages 2829-2868, April.
    17. Ricardo Fukasawa & Qie He & Fernando Santos & Yongjia Song, 2018. "A Joint Vehicle Routing and Speed Optimization Problem," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 694-709, November.
    18. Stefan Irnich & Daniel Villeneuve, 2006. "The Shortest-Path Problem with Resource Constraints and k -Cycle Elimination for k (ge) 3," INFORMS Journal on Computing, INFORMS, vol. 18(3), pages 391-406, August.
    19. Ermağan, Umut & Yıldız, Barış & Salman, F. Sibel, 2024. "Express shipments with autonomous robots and public transportation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 192(C).
    20. Arpan Rijal & Marco Bijvank & Asvin Goel & René de Koster, 2021. "Workforce Scheduling with Order-Picking Assignments in Distribution Facilities," Transportation Science, INFORMS, vol. 55(3), pages 725-746, May.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:oprepe:v:15:y:2025:i:c:s2214716025000405. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/operations-research-perspectives .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.