IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v45y2011i2p199-211.html
   My bibliography  Save this article

Scheduling Freight Trains in Rail-Rail Transshipment Yards

Author

Listed:
  • Nils Boysen

    (Lehrstuhl für Allgemeine Betriebswirtschaftslehre/Operations Management, Friedrich-Schiller-Universität Jena, D-07743 Jena, Germany)

  • Florian Jaehn

    (Institut für Wirtschaftsinformatik, Universität Siegen, D-57068 Siegen, Germany)

  • Erwin Pesch

    (Institut für Wirtschaftsinformatik, Universität Siegen, D-57068 Siegen, Germany)

Abstract

Transshipment yards, where gantry cranes enable the efficient transfer of containers between freight trains, are important entities in modern railway systems. They facilitate a general shift from point-to-point transport to hub-and-spoke railway systems, a shift being driven by concerted efforts within the European Union (EU) to transfer goods traffic from road to rail. Modern rail-rail transshipment yards accelerate container handling so that multiple smaller trains, with identical destinations, can be consolidated onto a reduced number of trains. An important problem attendant upon the daily operations of a transshipment yard is the train-scheduling problem, which involves determining the processing order of trains at parallel railway tracks. The present paper investigates this problem, with a special focus on resolving deadlocks and avoiding multiple crane picks per container move. A mathematical program along with a complexity proof is provided, and two different procedures are described: exact (dynamic programming) and heuristic (beam search).

Suggested Citation

  • Nils Boysen & Florian Jaehn & Erwin Pesch, 2011. "Scheduling Freight Trains in Rail-Rail Transshipment Yards," Transportation Science, INFORMS, vol. 45(2), pages 199-211, May.
    • Handle: RePEc:inm:ortrsc:v:45:y:2011:i:2:p:199-211
    DOI: 10.1287/trsc.1100.0365
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1100.0365
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1100.0365?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
    ---><---

    References listed on IDEAS

    as
    1. Ballis, Athanasios & Golias, John, 2002. "Comparative evaluation of existing and innovative rail-road freight transport terminals," Transportation Research Part A: Policy and Practice, Elsevier, vol. 36(7), pages 593-611, August.
    2. Luigi Moccia & Jean‐François Cordeau & Manlio Gaudioso & Gilbert Laporte, 2006. "A branch‐and‐cut algorithm for the quay crane scheduling problem in a container terminal," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(1), pages 45-59, February.
    3. 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.
    4. Freling, R. & Lentink, R.M. & Kroon, L.G. & Huisman, D., 2002. "Shunting of Passenger Train Units in a Railway Station," ERIM Report Series Research in Management ERS-2002-74-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    5. 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.
    6. Ulrich Blasum & Michael R. Bussieck & Winfried Hochstättler & Christoph Moll & Hans-Helmut Scheel & Thomas Winter, 1999. "Scheduling trams in the morning," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 49(1), pages 137-148, March.
    7. José Ángel González & Eva Ponce & Carlos Mataix & Javier Carrasco, 2008. "The Automatic Generation of Transhipment Plans for a Train--Train Terminal: Application to the Spanish--French Border," Transportation Planning and Technology, Taylor & Francis Journals, vol. 31(5), pages 545-567, May.
    8. Nathalie Bostel & Pierre Dejax, 1998. "Models and Algorithms for Container Allocation Problems on Trains in a Rapid Transshipment Shunting Yard," Transportation Science, INFORMS, vol. 32(4), pages 370-379, November.
    9. Richard Freling & Ramon M. Lentink & Leo G. Kroon & Dennis Huisman, 2005. "Shunting of Passenger Train Units in a Railway Station," Transportation Science, INFORMS, vol. 39(2), pages 261-272, May.
    10. Sabuncuoglu, Ihsan & Gocgun, Yasin & Erel, Erdal, 2008. "Backtracking and exchange of information: Methods to enhance a beam search algorithm for assembly line scheduling," European Journal of Operational Research, Elsevier, vol. 186(3), pages 915-930, May.
    11. Harald Rotter, 2004. "New operating concepts for intermodal transport: The mega hub in Hanover/Lehrte in Germany," Transportation Planning and Technology, Taylor & Francis Journals, vol. 27(5), pages 347-365, October.
    12. Fernando Marín Martínez & Isabel García Gutiérrez & Alberto Ortiz Oliveira & Luis Miguel Arreche Bedia, 2004. "Gantry crane operations to transfer containers between trains: A simulation study of a Spanish terminal," Transportation Planning and Technology, Taylor & Francis Journals, vol. 27(4), pages 261-284, August.
    13. Thomas Winter & Uwe Zimmermann, 2000. "Real-time dispatch of trams in storage yards," Annals of Operations Research, Springer, vol. 96(1), pages 287-315, November.
    14. Macharis, C. & Bontekoning, Y. M., 2004. "Opportunities for OR in intermodal freight transport research: A review," European Journal of Operational Research, Elsevier, vol. 153(2), pages 400-416, March.
    15. Azar, Christian & Lindgren, Kristian & Andersson, Bjorn A., 2003. "Global energy scenarios meeting stringent CO2 constraints--cost-effective fuel choices in the transportation sector," Energy Policy, Elsevier, vol. 31(10), pages 961-976, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. 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.
    2. Albareda-Sambola, Maria & Marín, Alfredo & Rodríguez-Chía, Antonio M., 2019. "Reformulated acyclic partitioning for rail-rail containers transshipment," European Journal of Operational Research, Elsevier, vol. 277(1), pages 153-165.
    3. Konrad Stephan & Nils Boysen, 2017. "Crane scheduling in railway yards: an analysis of computational complexity," Journal of Scheduling, Springer, vol. 20(5), pages 507-526, October.
    4. Stefan Fedtke & Nils Boysen, 2017. "Gantry crane and shuttle car scheduling in modern rail–rail transshipment yards," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(2), pages 473-503, March.
    5. Yan, Baicheng & Jin, Jian Gang & Zhu, Xiaoning & Lee, Der-Horng & Wang, Li & Wang, Hua, 2020. "Integrated planning of train schedule template and container transshipment operation in seaport railway terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 142(C).
    6. Maksim Barketau & Erwin Pesch, 2016. "An approximation algorithm for a special case of the asymmetric travelling salesman problem," International Journal of Production Research, Taylor & Francis Journals, vol. 54(14), pages 4205-4212, July.
    7. Guo, Peng & Weidinger, Felix & Boysen, Nils, 2019. "Parallel machine scheduling with job synchronization to enable efficient material flows in hub terminals," Omega, Elsevier, vol. 89(C), pages 110-121.
    8. Maksim Barketau & Erwin Pesch & Yakov Shafransky, 2016. "Scheduling dedicated jobs with variative processing times," Journal of Combinatorial Optimization, Springer, vol. 31(2), pages 774-785, February.
    9. Rupp, Johannes & Boysen, Nils & Briskorn, Dirk, 2022. "Optimizing consolidation processes in hubs: The hub-arrival-departure problem," European Journal of Operational Research, Elsevier, vol. 298(3), pages 1051-1066.
    10. Wenqian Liu & Xiaoning Zhu & Li Wang, 2019. "Distribution Organization Optimization for Inbound China Railway Express at Alataw Pass Railway Station," Sustainability, MDPI, vol. 11(24), pages 1-19, December.
    11. Amir Gharehgozli & Debjit Roy & Suruchika Saini & Jan-Kees Ommeren, 2023. "Loading and unloading trains at the landside of container terminals," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 25(3), pages 549-575, September.
    12. 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.
    13. Schulz, Arne & Fliedner, Malte & Fiedrich, Benedikt & Pfeiffer, Christian, 2021. "Levelling crane workload in multi-yard rail-road container terminals," European Journal of Operational Research, Elsevier, vol. 293(3), pages 941-954.
    14. Mateusz Cichenski & Florian Jaehn & Grzegorz Pawlak & Erwin Pesch & Gaurav Singh & Jacek Blazewicz, 2017. "An integrated model for the transshipment yard scheduling problem," Journal of Scheduling, Springer, vol. 20(1), pages 57-65, February.
    15. Nils Boysen & Malte Fliedner & Florian Jaehn & Erwin Pesch, 2013. "A Survey on Container Processing in Railway Yards," Transportation Science, INFORMS, vol. 47(3), pages 312-329, August.
    16. 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.
    17. Li, Xinyan & Xie, Chi & Bao, Zhaoyao, 2022. "A multimodal multicommodity network equilibrium model with service capacity and bottleneck congestion for China-Europe containerized freight flows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    18. Dirk Briskorn & Malte Fliedner & Martin Tschöke, 2021. "Vehicle Sequencing at Transshipment Terminals with Handover Relations," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 477-494, May.

    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. 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.
    2. Nils Boysen & Malte Fliedner & Florian Jaehn & Erwin Pesch, 2013. "A Survey on Container Processing in Railway Yards," Transportation Science, INFORMS, vol. 47(3), pages 312-329, August.
    3. Boysen, Nils & Fliedner, Malte, 2010. "Determining crane areas in intermodal transshipment yards: The yard partition problem," European Journal of Operational Research, Elsevier, vol. 204(2), pages 336-342, July.
    4. Kroon, L.G. & Lentink, R.M. & Schrijver, A., 2006. "Shunting of Passenger Train Units: an Integrated Approach," ERIM Report Series Research in Management ERS-2006-068-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    5. Leo G. Kroon & Ramon M. Lentink & Alexander Schrijver, 2008. "Shunting of Passenger Train Units: An Integrated Approach," Transportation Science, INFORMS, vol. 42(4), pages 436-449, November.
    6. Boysen, Nils & Emde, Simon, 2016. "The parallel stack loading problem to minimize blockages," European Journal of Operational Research, Elsevier, vol. 249(2), pages 618-627.
    7. Mateusz Cichenski & Florian Jaehn & Grzegorz Pawlak & Erwin Pesch & Gaurav Singh & Jacek Blazewicz, 2017. "An integrated model for the transshipment yard scheduling problem," Journal of Scheduling, Springer, vol. 20(1), pages 57-65, February.
    8. Mohamed Hamdouni & Guy Desaulniers & Odile Marcotte & François Soumis & Marianne van Putten, 2006. "Dispatching Buses in a Depot Using Block Patterns," Transportation Science, INFORMS, vol. 40(3), pages 364-377, August.
    9. Hamdouni, Mohamed & Soumis, Francois & Desaulniers, Guy, 2007. "Parking buses in a depot with stochastic arrival times," European Journal of Operational Research, Elsevier, vol. 183(2), pages 502-515, December.
    10. Lentink, R.M. & Fioole, P-J. & Kroon, L.G. & van 't Woudt, C., 2003. "Applying Operations Research techniques to planning of train shunting," ERIM Report Series Research in Management ERS-2003-094-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    11. Martin Josef Geiger & Sandra Huber & Sebastian Langton & Marius Leschik & Christian Lindorf & Ulrich Tüshaus, 2018. "Multi-attribute assignment of trains to departures in rolling stock management," Annals of Operations Research, Springer, vol. 271(2), pages 1131-1163, December.
    12. Haahr, Jørgen & Lusby, Richard M., 2017. "Integrating rolling stock scheduling with train unit shunting," European Journal of Operational Research, Elsevier, vol. 259(2), pages 452-468.
    13. Dennis Huisman & Leo G. Kroon & Ramon M. Lentink & Michiel J. C. M. Vromans, 2005. "Operations Research in passenger railway transportation," Statistica Neerlandica, Netherlands Society for Statistics and Operations Research, vol. 59(4), pages 467-497, November.
    14. Christian Artigues & Eric Bourreau & Vincent Jost & Safia Kedad-Sidhoum & François Ramond, 2018. "Trains do not vanish: the ROADEF/EURO challenge 2014," Annals of Operations Research, Springer, vol. 271(2), pages 1091-1105, December.
    15. 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.
    16. Richard Freling & Ramon M. Lentink & Leo G. Kroon & Dennis Huisman, 2005. "Shunting of Passenger Train Units in a Railway Station," Transportation Science, INFORMS, vol. 39(2), pages 261-272, May.
    17. Dirk Briskorn & Florian Jaehn & Andreas Wiehl, 2019. "A generator for test instances of scheduling problems concerning cranes in transshipment terminals," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(1), pages 45-69, March.
    18. Lehnfeld, Jana & Knust, Sigrid, 2014. "Loading, unloading and premarshalling of stacks in storage areas: Survey and classification," European Journal of Operational Research, Elsevier, vol. 239(2), pages 297-312.
    19. 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.
    20. Ballis, Athanasios & Golias, John, 2004. "Towards the improvement of a combined transport chain performance," European Journal of Operational Research, Elsevier, vol. 152(2), pages 420-436, January.

    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:inm:ortrsc:v:45:y:2011:i:2:p:199-211. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.