IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v190y2024ics019126152400211x.html
   My bibliography  Save this article

An iterative method for integrated hump sequencing, train makeup, and classification track assignment in railway shunting yard

Author

Listed:
  • Zhang, Bojian
  • Zhao, Jun
  • D’Ariano, Andrea
  • Zhang, Yongxiang
  • Feng, Tao
  • Peng, Qiyuan

Abstract

In a railway shunting yard, the transformation of inbound trains into properly composed outbound trains is a complex task because it involves decisions of multiple operations processes. This study addresses the integrated optimization of hump sequencing, train makeup, and classification track assignment problem in a railway shunting yard. Several key practical yard operation constraints are considered, including train formulation constraints, hump sequencing constraints, and limitations of the maximum number and capacity of classification tracks. By introducing a new representation of block flow, the integrated problem, which adopts the extended single-stage strategy and the train-to-track policy, is formulated as a unified 0-1 integer linear programming model. The objective of the proposed model is to minimize the weighted-sum of the total dwell time of all railcars and the formulation deviation penalties of all outbound trains. Then, an iterative two-phase decomposition approach is developed to reduce the complexity of solving the integrated problem. The first phase aims to explore all feasible humping sequences using a Branch-and-Bound (B&B) algorithm. Each time a new humping sequence is generated in the first phase, the second phase containing a Branch-and-Price (B&P) algorithm is applied to solve the integrated train makeup and classification track assignment problem with the known humping sequence found in the first phase. In addition, greedy heuristics and lower bounding techniques are designed in both phases to improve computational efficiency. Comprehensive experiments are investigated based on a set of real-life instances. The results show that exact approaches provide optimal solutions, whereas heuristic approaches yield satisfactory solutions within a shorter computation time. Moreover, sensitivity analyses on the number of classification tracks and the effects of different deviation penalties are also performed to gain more managerial insights.

Suggested Citation

  • 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).
    • Handle: RePEc:eee:transb:v:190:y:2024:i:c:s019126152400211x
    DOI: 10.1016/j.trb.2024.103087
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S019126152400211X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2024.103087?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 search for a different version of it.

    References listed on IDEAS

    as
    1. Chai, Simin & Yin, Jiateng & D’Ariano, Andrea & Liu, Ronghui & Yang, Lixing & Tang, Tao, 2024. "A branch-and-cut algorithm for scheduling train platoons in urban rail networks," Transportation Research Part B: Methodological, Elsevier, vol. 181(C).
    2. 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.
    3. Wang, Dian & D’Ariano, Andrea & Zhao, Jun & Zhong, Qingwei & Peng, Qiyuan, 2022. "Integrated rolling stock deadhead routing and timetabling in urban rail transit lines," European Journal of Operational Research, Elsevier, vol. 298(2), pages 526-559.
    4. Kraft, Edwin R., 2002. "Priority-Based Classification for Improving Connection Reliability in Railroad Yards - Part I: Integration With Car Scheduling," Journal of the Transportation Research Forum, Transportation Research Forum, vol. 41(01).
    5. Jaehn, Florian & Rieder, Johannes & Wiehl, Andreas, 2015. "Single-stage shunting minimizing weighted departure times," Omega, Elsevier, vol. 52(C), pages 133-141.
    6. Mascis, Alessandro & Pacciarelli, Dario, 2002. "Job-shop scheduling with blocking and no-wait constraints," European Journal of Operational Research, Elsevier, vol. 143(3), pages 498-517, December.
    7. Lusby, Richard M. & Haahr, Jørgen Thorlund & Larsen, Jesper & Pisinger, David, 2017. "A Branch-and-Price algorithm for railway rolling stock rescheduling," Transportation Research Part B: Methodological, Elsevier, vol. 99(C), pages 228-250.
    8. 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.
    9. Li, Siqiao & Zhu, Xiaoning & Shang, Pan & Li, Tianqi & Liu, Wenqian, 2023. "Optimizing a shared freight and passenger high-speed railway system: A multi-commodity flow formulation with Benders decomposition solution approach," Transportation Research Part B: Methodological, Elsevier, vol. 172(C), pages 1-31.
    10. 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.
    11. 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.
    12. Yvonne Bontekoning & Hugo Priemus, 2004. "Breakthrough innovations in intermodal freight transport," Transportation Planning and Technology, Taylor & Francis Journals, vol. 27(5), pages 335-345, October.
    13. D'Ariano, Andrea & Pacciarelli, Dario & Pranzo, Marco, 2007. "A branch and bound algorithm for scheduling trains in a railway network," European Journal of Operational Research, Elsevier, vol. 183(2), pages 643-657, December.
    14. Zhou, Xuesong & Zhong, Ming, 2007. "Single-track train timetabling with guaranteed optimality: Branch-and-bound algorithms with enhanced lower bounds," Transportation Research Part B: Methodological, Elsevier, vol. 41(3), pages 320-341, March.
    15. Lin, Zhiyuan & Kwan, Raymond S.K., 2016. "A branch-and-price approach for solving the train unit scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 97-120.
    16. Kraft, Edwin R., 2002. "Priority-Based Classification for Improving Connection Reliability in Railroad Yards - Part II: Dynamic Block to Track Assignment," Journal of the Transportation Research Forum, Transportation Research Forum, vol. 41(01).
    17. Cacchiani, Valentina & Caprara, Alberto & Toth, Paolo, 2010. "Scheduling extra freight trains on railway networks," Transportation Research Part B: Methodological, Elsevier, vol. 44(2), pages 215-231, February.
    18. 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).
    19. Chen, Chongshuang & Dollevoet, Twan & Zhao, Jun, 2018. "One-block train formation in large-scale railway networks: An exact model and a tree-based decomposition algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 118(C), pages 1-30.
    20. Kulkarni, Sarang & Krishnamoorthy, Mohan & Ranade, Abhiram & Ernst, Andreas T. & Patil, Rahul, 2018. "A new formulation and a column generation-based heuristic for the multiple depot vehicle scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 118(C), pages 457-487.
    21. Yin, Jiateng & Pu, Fan & Yang, Lixing & D’Ariano, Andrea & Wang, Zhouhong, 2023. "Integrated optimization of rolling stock allocation and train timetables for urban rail transit networks: A benders decomposition approach," Transportation Research Part B: Methodological, Elsevier, vol. 176(C).
    22. Gao, Yuan & Xia, Jun & D’Ariano, Andrea & Yang, Lixing, 2022. "Weekly rolling stock planning in Chinese high-speed rail networks," Transportation Research Part B: Methodological, Elsevier, vol. 158(C), pages 295-322.
    23. Feng, Tao & Lusby, Richard M. & Zhang, Yongxiang & Peng, Qiyuan, 2024. "Integrating train service route design with passenger flow allocation for an urban rail transit line," European Journal of Operational Research, Elsevier, vol. 313(1), pages 146-170.
    24. Feng, Tao & Lusby, Richard M. & Zhang, Yongxiang & Tao, Siyu & Zhang, Bojian & Peng, Qiyuan, 2024. "A branch-and-price algorithm for integrating urban rail crew scheduling and rostering problems," Transportation Research Part B: Methodological, Elsevier, vol. 183(C).
    25. 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.
    26. 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.
    27. Mo, Pengli & D’Ariano, Andrea & Yang, Lixing & Veelenturf, Lucas P. & Gao, Ziyou, 2021. "An exact method for the integrated optimization of subway lines operation strategies with asymmetric passenger demand and operating costs," Transportation Research Part B: Methodological, Elsevier, vol. 149(C), pages 283-321.
    28. 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.
    29. Liu, Mengyang & Luo, Zhixing & Lim, Andrew, 2015. "A branch-and-cut algorithm for a realistic dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 267-288.
    30. 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.
    31. Kraft, Edwin R., 2000. "A Hump Sequencing Algorithm for Real Time Management of Train Connection Reliability," Journal of the Transportation Research Forum, Transportation Research Forum, vol. 39(4).
    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. 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).
    3. Chai, Simin & Yin, Jiateng & D’Ariano, Andrea & Liu, Ronghui & Yang, Lixing & Tang, Tao, 2024. "A branch-and-cut algorithm for scheduling train platoons in urban rail networks," Transportation Research Part B: Methodological, Elsevier, vol. 181(C).
    4. Bettinelli, Andrea & Santini, Alberto & Vigo, Daniele, 2017. "A real-time conflict solution algorithm for the train rescheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 237-265.
    5. Xu, Xiaoming & Li, Keping & Yang, Lixing, 2015. "Scheduling heterogeneous train traffic on double tracks with efficient dispatching rules," Transportation Research Part B: Methodological, Elsevier, vol. 78(C), pages 364-384.
    6. Wang, Entai & Yang, Lixing & Yin, Jiateng & Zhang, Jinlei & Gao, Ziyou, 2024. "Passenger-oriented rolling stock scheduling in the metro system with multiple depots: Network flow based approaches," Transportation Research Part B: Methodological, Elsevier, vol. 180(C).
    7. Xiaoming Xu & Keping Li & Lixing Yang & Ziyou Gao, 2019. "An efficient train scheduling algorithm on a single-track railway system," Journal of Scheduling, Springer, vol. 22(1), pages 85-105, February.
    8. Julia Lange & Frank Werner, 2018. "Approaches to modeling train scheduling problems as job-shop problems with blocking constraints," Journal of Scheduling, Springer, vol. 21(2), pages 191-207, April.
    9. Yuan, Yin & Li, Shukai & Yang, Lixing & Gao, Ziyou, 2022. "Real-time optimization of train regulation and passenger flow control for urban rail transit network under frequent disturbances," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 168(C).
    10. 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.
    11. Wang, Dian & D’Ariano, Andrea & Zhao, Jun & Zhan, Shuguang & Peng, Qiyuan, 2024. "Joint rolling stock rotation planning and depot deadhead scheduling in complicated urban rail transit lines," European Journal of Operational Research, Elsevier, vol. 314(2), pages 665-684.
    12. Zhang, Chuntian & Gao, Yuan & Yang, Lixing & Gao, Ziyou & Qi, Jianguo, 2020. "Joint optimization of train scheduling and maintenance planning in a railway network: A heuristic algorithm using Lagrangian relaxation," Transportation Research Part B: Methodological, Elsevier, vol. 134(C), pages 64-92.
    13. Cacchiani, Valentina & Furini, Fabio & Kidd, Martin Philip, 2016. "Approaches to a real-world Train Timetabling Problem in a railway node," Omega, Elsevier, vol. 58(C), pages 97-110.
    14. Yin, Jiateng & Yang, Lixing & Tang, Tao & Gao, Ziyou & Ran, Bin, 2017. "Dynamic passenger demand oriented metro train scheduling with energy-efficiency and waiting time minimization: Mixed-integer linear programming approaches," Transportation Research Part B: Methodological, Elsevier, vol. 97(C), pages 182-213.
    15. 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.
    16. 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.
    17. 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.
    18. Zhang, Qin & Lusby, Richard Martin & Shang, Pan & Zhu, Xiaoning, 2022. "A heuristic approach to integrate train timetabling, platforming, and railway network maintenance scheduling decisions," Transportation Research Part B: Methodological, Elsevier, vol. 158(C), pages 210-238.
    19. Yin, Jiateng & Pu, Fan & Yang, Lixing & D’Ariano, Andrea & Wang, Zhouhong, 2023. "Integrated optimization of rolling stock allocation and train timetables for urban rail transit networks: A benders decomposition approach," Transportation Research Part B: Methodological, Elsevier, vol. 176(C).
    20. Yang, Lin & Gao, Yuan & D’Ariano, Andrea & Xu, Suxiu, 2024. "Integrated optimization of train timetable and train unit circulation for a Y-type urban rail transit system with flexible train composition mode," Omega, Elsevier, vol. 122(C).

    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:190:y:2024:i:c:s019126152400211x. 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.