IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v200y2025ics0191261525001559.html

Integrated optimization of train makeup problem and resource scheduling in railway marshalling yards: A hybrid MILP-CP approach with Logic-based Benders decomposition

Author

Listed:
  • Han, Peiran
  • Meng, Lingyun
  • Luan, Xiaojie
  • Bešinović, Nikola
  • Miao, Jianrui
  • Wang, Yihui
  • Liao, Zhengwen

Abstract

In the marshalling yard, various complex operations occur, leading to inefficiencies in railcar connections. Therefore, designing an effective operational research methodology is essential for the marshalling yard, and even for the local rail freight network. This paper addresses the integrated Train Makeup and Resource Scheduling (TMRS) problem. A Mixed-Integer Linear Programming (MILP) model is developed, where the train makeup problem is formulated as an assignment problem, guiding the overall operations. Additionally, a series of hybrid flow shop scheduling tasks are established to coordinate the operations of trains, blocks, and railcars. Due to the complexity of TMRS, the integrated problem is reformulated as a hybrid mixed-integer linear programming (MILP) and constraint programming (CP) model. Logic-based benders decomposition (LBBD) is used to partition the TMRS problem, with lower bounds designed and integrated into the solving procedure to accelerate the convergence. We propose feasibility cuts, optimality cuts, and symmetry cuts based on the structure of the subproblem, which are dynamically added to the master problem. Two numerical examples are designed to demonstrate the effectiveness of the proposed hybrid modelling approach, lower bounds, and cuts. Finally, the proposed approach and algorithm are tested on a series of artificial instances and real-scale examples, demonstrating their practical effectiveness and ability to achieve high-quality solutions.

Suggested Citation

  • Han, Peiran & Meng, Lingyun & Luan, Xiaojie & Bešinović, Nikola & Miao, Jianrui & Wang, Yihui & Liao, Zhengwen, 2025. "Integrated optimization of train makeup problem and resource scheduling in railway marshalling yards: A hybrid MILP-CP approach with Logic-based Benders decomposition," Transportation Research Part B: Methodological, Elsevier, vol. 200(C).
    • Handle: RePEc:eee:transb:v:200:y:2025:i:c:s0191261525001559
    DOI: 10.1016/j.trb.2025.103306
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261525001559
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2025.103306?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. Luan, Xiaojie & De Schutter, Bart & Meng, Lingyun & Corman, Francesco, 2020. "Decomposition and distributed optimization of real-time traffic management for large-scale railway networks," Transportation Research Part B: Methodological, Elsevier, vol. 141(C), pages 72-97.
    2. Ruf, Moritz & Cordeau, Jean-François, 2021. "Adaptive large neighborhood search for integrated planning in railroad classification yards," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 26-51.
    3. Boysen, Nils & Fliedner, Malte & Jaehn, Florian & Pesch, Erwin, 2012. "Shunting yard operations: Theoretical aspects and applications," European Journal of Operational Research, Elsevier, vol. 220(1), pages 1-14.
    4. E. R. Petersen, 1977. "Railyard Modeling: Part I. Prediction of Put-Through Time," Transportation Science, INFORMS, vol. 11(1), pages 37-49, February.
    5. Meng, Lingyun & Zhou, Xuesong, 2014. "Simultaneous train rerouting and rescheduling on an N-track network: A model reformulation with network-based cumulative flow variables," Transportation Research Part B: Methodological, Elsevier, vol. 67(C), pages 208-234.
    6. Zhu, Xuedong & Son, Junbo & Zhang, Xi & Wu, Jianguo, 2023. "Constraint programming and logic-based Benders decomposition for the integrated process planning and scheduling problem," Omega, Elsevier, vol. 117(C).
    7. Mark A. Turnquist & Mark S. Daskin, 1982. "Queuing Models of Classification and Connection Delay in Railyards," Transportation Science, INFORMS, vol. 16(2), pages 207-230, May.
    8. Leutwiler, Florin & Corman, Francesco, 2022. "A logic-based Benders decomposition for microscopic railway timetable planning," European Journal of Operational Research, Elsevier, vol. 303(2), pages 525-540.
    9. Shi, Tie & Zhou, Xuesong, 2015. "A mixed integer programming model for optimizing multi-level operations process in railroad yards," Transportation Research Part B: Methodological, Elsevier, vol. 80(C), pages 19-39.
    10. Aliakbari, Mina & Geunes, Joseph & Ghahari, Amir & Prince, Mike, 2024. "Freight railcar-to-train assignment and departure scheduling in a railyard," European Journal of Operational Research, Elsevier, vol. 314(3), pages 950-962.
    11. J. N. Hooker, 2007. "Planning and Scheduling by Logic-Based Benders Decomposition," Operations Research, INFORMS, vol. 55(3), pages 588-602, June.
    12. Naderi, Bahman & Begen, Mehmet A. & Zaric, Gregory S. & Roshanaei, Vahid, 2023. "A novel and efficient exact technique for integrated staffing, assignment, routing, and scheduling of home care services under uncertainty," Omega, Elsevier, vol. 116(C).
    13. Endong Zhu & Teodor Gabriel Crainic & Michel Gendreau, 2014. "Scheduled Service Network Design for Freight Rail Transportation," Operations Research, INFORMS, vol. 62(2), pages 383-400, April.
    14. Scheffler, Martin & Neufeld, Janis S. & Hölscher, Michael, 2020. "An MIP-based heuristic solution approach for the locomotive assignment problem focussing on (dis-)connecting processes," Transportation Research Part B: Methodological, Elsevier, vol. 139(C), pages 64-80.
    15. Ruiz, Rubén & Vázquez-Rodríguez, José Antonio, 2010. "The hybrid flow shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 205(1), pages 1-18, August.
    16. Boysen, Nils & Fliedner, Malte & Kellner, Michael, 2010. "Determining fixed crane areas in rail-rail transshipment yards," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(6), pages 1005-1016, November.
    17. Wang, Dian & Yao, Ling & D’Ariano, Andrea & Zhan, Shuguang & Wang, Lisha, 2025. "Rolling stock shunt operation planning in urban rail transit depots with maintenance consideration," Transportation Research Part B: Methodological, Elsevier, vol. 199(C).
    18. Ravindra K. Ahuja & Jian Liu & James B. Orlin & Dushyant Sharma & Larry A. Shughart, 2005. "Solving Real-Life Locomotive-Scheduling Problems," Transportation Science, INFORMS, vol. 39(4), pages 503-517, November.
    19. John N. Hooker, 2019. "Logic-Based Benders Decomposition for Large-Scale Optimization," Springer Optimization and Its Applications, in: Jesús M. Velásquez-Bermúdez & Marzieh Khakifirooz & Mahdi Fathi (ed.), Large Scale Optimization in Supply Chains and Smart Manufacturing, pages 1-26, Springer.
    20. Markus Bohlin & Sara Gestrelius & Florian Dahms & Matúš Mihalák & Holger Flier, 2016. "Optimization Methods for Multistage Freight Train Formation," Transportation Science, INFORMS, vol. 50(3), pages 823-840, August.
    21. He, Shiwei & Song, Rui & Chaudhry, Sohail S., 2000. "Fuzzy dispatching model and genetic algorithms for railyards operations," European Journal of Operational Research, Elsevier, vol. 124(2), pages 307-331, July.
    22. Yantong Li & Jean-François Côté & Leandro Callegari-Coelho & Peng Wu, 2022. "Novel Formulations and Logic-Based Benders Decomposition for the Integrated Parallel Machine Scheduling and Location Problem," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 1048-1069, March.
    23. Boysen, Nils & Emde, Simon & Fliedner, Malte, 2016. "The basic train makeup problem in shunting yards," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 79432, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    24. Bahman Naderi & Rubén Ruiz & Vahid Roshanaei, 2023. "Mixed-Integer Programming vs. Constraint Programming for Shop Scheduling Problems: New Results and Outlook," INFORMS Journal on Computing, INFORMS, vol. 35(4), pages 817-843, July.
    25. Bruck, Bruno P. & Cordeau, Jean-François & Frejinger, Emma, 2021. "Integrated inbound train split and load planning in an intermodal railway terminal," Transportation Research Part B: Methodological, Elsevier, vol. 145(C), pages 270-289.
    26. Zhang, Yongxiang & Peng, Qiyuan & Yao, Yu & Zhang, Xin & Zhou, Xuesong, 2019. "Solving cyclic train timetabling problem through model reformulation: Extended time-space network construct and Alternating Direction Method of Multipliers methods," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 344-379.
    27. Nils Boysen & Simon Emde & Malte Fliedner, 2016. "The basic train makeup problem in shunting yards," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(1), pages 207-233, January.
    28. Jean-François Cordeau & Paolo Toth & Daniele Vigo, 1998. "A Survey of Optimization Models for Train Routing and Scheduling," Transportation Science, INFORMS, vol. 32(4), pages 380-404, November.
    29. Santos, D. L. & Hunsucker, J. L. & Deal, D. E., 1995. "Global lower bounds for flow shops with multiple processors," European Journal of Operational Research, Elsevier, vol. 80(1), pages 112-120, January.
    30. Zhang, Bojian & Zhao, Jun & D’Ariano, Andrea & Zhang, Yongxiang & Feng, Tao & Peng, Qiyuan, 2024. "An iterative method for integrated hump sequencing, train makeup, and classification track assignment in railway shunting yard," Transportation Research Part B: Methodological, Elsevier, vol. 190(C).
    31. Li, Shengdong & Zuo, Dajie & Li, Wenqing & Zhang, Yongxiang & Shi, Li, 2024. "Freight train line planning for large-scale high-speed rail network: An integer Benders decomposition-based branch-and-cut algorithm," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 192(C).
    32. Szymula, Christopher & Bešinović, Nikola, 2020. "Passenger-centered vulnerability assessment of railway networks," Transportation Research Part B: Methodological, Elsevier, vol. 136(C), pages 30-61.
    33. Carl D. Martland, 1982. "PMAKE Analysis: Predicting Rail Yard Time Distributions Using Probabilistic Train Connection Standards," Transportation Science, INFORMS, vol. 16(4), pages 476-506, November.
    34. Wang, Dian & Zhao, Jun & Peng, Qiyuan, 2022. "Optimizing the loaded train combination problem at a heavy-haul marshalling station," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 162(C).
    35. Rodriguez, Joaquín, 2007. "A constraint programming model for real-time train scheduling at junctions," Transportation Research Part B: Methodological, Elsevier, vol. 41(2), pages 231-245, February.
    36. Carlier, Jacques, 1987. "Scheduling jobs with release dates and tails on identical machines to minimize the makespan," European Journal of Operational Research, Elsevier, vol. 29(3), pages 298-306, June.
    37. Ruhollah Heydari & Emanuel Melachrinoudis, 2017. "A path-based capacitated network flow model for empty railcar distribution," Annals of Operations Research, Springer, vol. 253(2), pages 773-798, June.
    38. Markus Bohlin & Ronny Hansmann & Uwe T. Zimmermann, 2018. "Optimization of Railway Freight Shunting," International Series in Operations Research & Management Science, in: Ralf Borndörfer & Torsten Klug & Leonardo Lamorgese & Carlo Mannino & Markus Reuther & Thomas Schlec (ed.), Handbook of Optimization in the Railway Industry, chapter 0, pages 181-212, Springer.
    39. Roshanaei, Vahid & Naderi, Bahman, 2021. "Solving integrated operating room planning and scheduling: Logic-based Benders decomposition versus Branch-Price-and-Cut," European Journal of Operational Research, Elsevier, vol. 293(1), pages 65-78.
    40. Haahr, Jørgen Thorlund & Lusby, Richard M. & Wagenaar, Joris Camiel, 2017. "Optimization methods for the Train Unit Shunting Problem," European Journal of Operational Research, Elsevier, vol. 262(3), pages 981-995.
    41. Zhu, Jia Hui & Dollevoet, Twan & Huisman, Dennis, 2025. "An exact and heuristic framework for rolling stock rescheduling with railway infrastructure availability constraints," Transportation Research Part B: Methodological, Elsevier, vol. 195(C).
    42. Gianni Codato & Matteo Fischetti, 2006. "Combinatorial Benders' Cuts for Mixed-Integer Linear Programming," Operations Research, INFORMS, vol. 54(4), pages 756-766, August.
    43. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    44. Roel van den Broek & Han Hoogeveen & Marjan van den Akker & Bob Huisman, 2022. "A Local Search Algorithm for Train Unit Shunting with Service Scheduling," Transportation Science, INFORMS, vol. 56(1), pages 141-161, January.
    45. E. R. Petersen, 1977. "Railyard Modeling: Part II. The Effect of Yard Facilities on Congestion," Transportation Science, INFORMS, vol. 11(1), pages 50-59, February.
    46. repec:inm:orijoo:v:4:y:2022:i:1:p:1-28 is not listed on IDEAS
    47. Alena Otto & Xiyu Li & Erwin Pesch, 2017. "Two-Way Bounded Dynamic Programming Approach for Operations Planning in Transshipment Yards," Transportation Science, INFORMS, vol. 51(1), pages 325-342, February.
    48. Leonardo Lamorgese & Carlo Mannino, 2015. "An Exact Decomposition Approach for the Real-Time Train Dispatching Problem," Operations Research, INFORMS, vol. 63(1), pages 48-64, February.
    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. Ruf, Moritz & Cordeau, Jean-François, 2021. "Adaptive large neighborhood search for integrated planning in railroad classification yards," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 26-51.
    2. Zhang, Bojian & Zhao, Jun & D’Ariano, Andrea & Zhang, Yongxiang & Feng, Tao & Peng, Qiyuan, 2024. "An iterative method for integrated hump sequencing, train makeup, and classification track assignment in railway shunting yard," Transportation Research Part B: Methodological, Elsevier, vol. 190(C).
    3. Wang, Dian & Yao, Ling & D’Ariano, Andrea & Zhan, Shuguang & Wang, Lisha, 2025. "Rolling stock shunt operation planning in urban rail transit depots with maintenance consideration," Transportation Research Part B: Methodological, Elsevier, vol. 199(C).
    4. Wang, Dian & Zhao, Jun & Peng, Qiyuan, 2022. "Optimizing the loaded train combination problem at a heavy-haul marshalling station," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 162(C).
    5. Guo, Penghui & Zhu, Jianjun, 2023. "Capacity reservation for humanitarian relief: A logic-based Benders decomposition method with subgradient cut," European Journal of Operational Research, Elsevier, vol. 311(3), pages 942-970.
    6. Zhang, Qin & Lusby, Richard Martin & Shang, Pan & Liu, Chang & Liu, Wenqian, 2025. "Solving a multi-resolution model of the train platforming problem using Lagrangian Relaxation with dynamic multiplier aggregation," European Journal of Operational Research, Elsevier, vol. 324(3), pages 981-1001.
    7. Boysen, Nils & Fliedner, Malte & Jaehn, Florian & Pesch, Erwin, 2012. "Shunting yard operations: Theoretical aspects and applications," European Journal of Operational Research, Elsevier, vol. 220(1), pages 1-14.
    8. Shi, Tie & Zhou, Xuesong, 2015. "A mixed integer programming model for optimizing multi-level operations process in railroad yards," Transportation Research Part B: Methodological, Elsevier, vol. 80(C), pages 19-39.
    9. Hu, Linyuan & Zhang, Yuli & Wen, Muyang & Leus, Roel & Zhang, Ningwei, 2025. "Robust parallel machine selection and scheduling with uncertain release times," European Journal of Operational Research, Elsevier, vol. 327(3), pages 838-856.
    10. Xiong, Fuli & Liu, Hengchong, 2026. "Logic-based benders decomposition methods for the distributed flexible job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 329(3), pages 778-797.
    11. Wang, Lin & Zhang, Ziqing & Wang, Sirui, 2026. "Grain drying capacity planning and scheduling under yield uncertainty: Minimizing post-harvest losses and operational costs," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 205(C).
    12. Leutwiler, Florin & Corman, Francesco, 2022. "A logic-based Benders decomposition for microscopic railway timetable planning," European Journal of Operational Research, Elsevier, vol. 303(2), pages 525-540.
    13. Lin, Bo-Liang & Wang, Zhi-Mei & Ji, Li-Jun & Tian, Ya-Ming & Zhou, Guo-Qing, 2012. "Optimizing the freight train connection service network of a large-scale rail system," Transportation Research Part B: Methodological, Elsevier, vol. 46(5), pages 649-667.
    14. Zhang, Yongxiang & D'Ariano, Andrea & He, Bisheng & Peng, Qiyuan, 2019. "Microscopic optimization model and algorithm for integrating train timetabling and track maintenance task scheduling," Transportation Research Part B: Methodological, Elsevier, vol. 127(C), pages 237-278.
    15. Roy, Debjit & van Ommeren, Jan-Kees & de Koster, René & Gharehgozli, Amir, 2022. "Modeling landside container terminal queues: Exact analysis and approximations," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 73-102.
    16. Scheffler, Martin & Neufeld, Janis S. & Hölscher, Michael, 2020. "An MIP-based heuristic solution approach for the locomotive assignment problem focussing on (dis-)connecting processes," Transportation Research Part B: Methodological, Elsevier, vol. 139(C), pages 64-80.
    17. Avgerinos, Ioannis & Mourtos, Ioannis & Vatikiotis, Stavros & Zois, Georgios, 2025. "One Benders cut to rule all schedules in the neighbourhood," European Journal of Operational Research, Elsevier, vol. 323(1), pages 62-85.
    18. Mao, Zhaofang & Fu, Enyuan & Huang, Dian & Fang, Kan & Chen, Lin, 2024. "Combinatorial Benders decomposition for single machine scheduling in additive manufacturing with two-dimensional packing constraints," European Journal of Operational Research, Elsevier, vol. 317(3), pages 890-905.
    19. Xiu, Cong & Pan, Jinyi & D’Ariano, Andrea & Zhan, Shuguang & Tessitore, Marta Leonina & Peng, Qiyuan, 2025. "Integrated train rescheduling and passenger reassignment for disrupted high-speed railway networks: A hierarchical Benders decomposition and column generation approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 200(C).
    20. Xu, Xiaoming & Li, Chung-Lun & Xu, Zhou, 2018. "Integrated train timetabling and locomotive assignment," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 573-593.

    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:transb:v:200:y:2025:i:c:s0191261525001559. 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.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    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.