IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v37y2009i3p555-565.html
   My bibliography  Save this article

A hybrid genetic algorithm for train sequencing in the Korean railway

Author

Listed:
  • Chung, Ji-Won
  • Oh, Seog-Moon
  • Choi, In-Chan

Abstract

This article addresses the train-sequencing problem encountered in the Korean railway. It first presents a mixed integer programming model for the problem, in which the mileage must be balanced for each train route, while various field constraints must be satisfied, including overnight stay capacity and maintenance allocation restrictions. Then, it proposes a hybrid genetic algorithm as a solution approach to the problem. The proposed algorithm utilizes a modified elite group technique along with two heuristic procedures based on the mixed integer programming model. Finally, the proposed solution approach is tested with real-world data from the Korean railway. Numerical experiments under different conditions indicate that the proposed solution approach to the train-sequencing problem is promising.

Suggested Citation

  • Chung, Ji-Won & Oh, Seog-Moon & Choi, In-Chan, 2009. "A hybrid genetic algorithm for train sequencing in the Korean railway," Omega, Elsevier, vol. 37(3), pages 555-565, June.
    • Handle: RePEc:eee:jomega:v:37:y:2009:i:3:p:555-565
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305-0483(07)00124-7
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Lee, Sang M. & Asllani, Arben A., 2004. "Job scheduling with dual criteria and sequence-dependent setups: mathematical versus genetic programming," Omega, Elsevier, vol. 32(2), pages 145-153, April.
    2. Moudani, Walid El & Mora-Camino, Félix, 2000. "A dynamic approach for aircraft assignment and maintenance scheduling by airlines," Journal of Air Transport Management, Elsevier, vol. 6(4), pages 233-237.
    3. Yan, Shangyao & Tang, Ching-Hui & Lee, Ming-Chei, 2007. "A flight scheduling model for Taiwan airlines under market competitions," Omega, Elsevier, vol. 35(1), pages 61-74, February.
    4. Gomes da Silva, Carlos & Figueira, José & Lisboa, João & Barman, Samir, 2006. "An interactive decision support system for an aggregate production planning model based on multiple criteria mixed integer linear programming," Omega, Elsevier, vol. 34(2), pages 167-177, April.
    5. Ruiz, Rubén & Maroto, Concepciøn & Alcaraz, Javier, 2006. "Two new robust genetic algorithms for the flowshop scheduling problem," Omega, Elsevier, vol. 34(5), pages 461-476, October.
    6. Kuo, Ching-Chung & Nicholls, Gillian M., 2007. "A mathematical modeling approach to improving locomotive utilization at a freight railroad," Omega, Elsevier, vol. 35(5), pages 472-485, October.
    7. L. W. Clarke & C. A. Hane & E. L. Johnson & G. L. Nemhauser, 1996. "Maintenance and Crew Considerations in Fleet Assignment," Transportation Science, INFORMS, vol. 30(3), pages 249-260, August.
    8. Koorush Ziarati & François Soumis & Jacques Desrosiers & Marius M. Solomon, 1999. "A Branch-First, Cut-Second Approach for Locomotive Assignment," Management Science, INFORMS, vol. 45(8), pages 1156-1168, August.
    9. Marco E. Lübbecke & Uwe T. Zimmermann, 2003. "Engine Routing and Scheduling at Industrial In-Plant Railroads," Transportation Science, INFORMS, vol. 37(2), pages 183-197, May.
    10. Ziarati, Koorush & Soumis, Francois & Desrosiers, Jacques & Gelinas, Sylvie & Saintonge, Andre, 1997. "Locomotive assignment with heterogeneous consists at CN North America," European Journal of Operational Research, Elsevier, vol. 97(2), pages 281-292, March.
    11. Jean-François Cordeau & François Soumis & Jacques Desrosiers, 2001. "Simultaneous Assignment of Locomotives and Cars to Passenger Trains," Operations Research, INFORMS, vol. 49(4), pages 531-548, 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. Matthew E. H. Petering & Mojtaba Heydar & Dietrich R. Bergmann, 2016. "Mixed-Integer Programming for Railway Capacity Analysis and Cyclic, Combined Train Timetabling and Platforming," Transportation Science, INFORMS, vol. 50(3), pages 892-909, August.
    2. Jaehn, Florian & Rieder, Johannes & Wiehl, Andreas, 2015. "Single-stage shunting minimizing weighted departure times," Omega, Elsevier, vol. 52(C), pages 133-141.
    3. Kang, Liujiang & Zhu, Xiaoning & Sun, Huijun & Wu, Jianjun & Gao, Ziyou & Hu, Bin, 2019. "Last train timetabling optimization and bus bridging service management in urban railway transit networks," Omega, Elsevier, vol. 84(C), pages 31-44.
    4. Barrena, Eva & Canca, David & Coelho, Leandro C. & Laporte, Gilbert, 2014. "Single-line rail rapid transit timetabling under dynamic passenger demand," Transportation Research Part B: Methodological, Elsevier, vol. 70(C), pages 134-150.
    5. Prashant Premkumar & P. N. Ram Kumar, 2019. "Literature Review of Locomotive Assignment Problem from Service Operations Perspective: The Case of Indian Railways," IIM Kozhikode Society & Management Review, , vol. 8(1), pages 74-86, January.
    6. Yang, Lixing & Li, Keping & Gao, Ziyou & Li, Xiang, 2012. "Optimizing trains movement on a railway network," Omega, Elsevier, vol. 40(5), pages 619-633.
    7. Canca, David & Barrena, Eva, 2018. "The integrated rolling stock circulation and depot location problem in railway rapid transit systems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 115-138.
    8. Salazar-González, Juan-José, 2014. "Approaches to solve the fleet-assignment, aircraft-routing, crew-pairing and crew-rostering problems of a regional carrier," Omega, Elsevier, vol. 43(C), pages 71-82.
    9. Jiahao Zhao & Xiaoning Zhu & Li Wang, 2020. "Study on Scheme of Outbound Railway Container Organization in Rail-Water Intermodal Transportation," Sustainability, MDPI, vol. 12(4), pages 1-18, February.
    10. Blanco, Víctor & Puerto, Justo & Ramos, Ana B., 2011. "Expanding the Spanish high-speed railway network," Omega, Elsevier, vol. 39(2), pages 138-150, April.
    11. Dali Jiang & Haitao Li & Tinghong Yang & De Li, 2016. "Genetic algorithm for inventory positioning problem with general acyclic supply chain networks," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 10(3), pages 367-384.
    12. Yiting Xing & Ling Li & Zhuming Bi & Marzena Wilamowska‐Korsak & Li Zhang, 2013. "Operations Research (OR) in Service Industries: A Comprehensive Review," Systems Research and Behavioral Science, Wiley Blackwell, vol. 30(3), pages 300-353, May.
    13. E. Ursavas & Stuart X. Zhu, 2018. "Integrated Passenger and Freight Train Planning on Shared-Use Corridors," Service Science, INFORMS, vol. 52(6), pages 1376-1390, December.
    14. Guo, Xin & Wu, Jianjun & Sun, Huijun & Yang, Xin & Jin, Jian Gang & Wang, David Z.W., 2020. "Scheduling synchronization in urban rail transit networks: Trade-offs between transfer passenger and last train operation," Transportation Research Part A: Policy and Practice, Elsevier, vol. 138(C), pages 463-490.
    15. Souffriau, Wouter & Vansteenwegen, Pieter & Vanden Berghe, Greet & Van Oudheusden, Dirk, 2011. "The planning of cycle trips in the province of East Flanders," Omega, Elsevier, vol. 39(2), pages 209-213, April.
    16. Shi Qiang Liu & Erhan Kozan, 2011. "Scheduling Trains with Priorities: A No-Wait Blocking Parallel-Machine Job-Shop Scheduling Model," Transportation Science, INFORMS, vol. 45(2), pages 175-198, May.
    17. Redondo, Juana L. & Fernández, José & Arrondo, Aránzazu G. & García, Inmaculada & Ortigosa, Pilar M., 2012. "Fixed or variable demand? Does it matter when locating a facility?," Omega, Elsevier, vol. 40(1), pages 9-20, January.
    18. Boctor, Fayez F. & Renaud, Jacques & Cornillier, Fabien, 2011. "Trip packing in petrol stations replenishment," Omega, Elsevier, vol. 39(1), pages 86-98, January.
    19. Kang, Liujiang & Wu, Jianjun & Sun, Huijun & Zhu, Xiaoning & Wang, Bo, 2015. "A practical model for last train rescheduling with train delay in urban railway transit networks," Omega, Elsevier, vol. 50(C), pages 29-42.
    20. Bing Bu & Guoying Qin & Ling Li & Guojie Li, 2018. "An Energy Efficient Train Dispatch and Control Integrated Method in Urban Rail Transit," Energies, MDPI, vol. 11(5), pages 1-23, May.
    21. Yang, Lixing & Zhou, Xuesong & Gao, Ziyou, 2014. "Credibility-based rescheduling model in a double-track railway network: a fuzzy reliable optimization approach," Omega, Elsevier, vol. 48(C), pages 75-93.

    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. Prashant Premkumar & P. N. Ram Kumar, 2022. "Locomotive assignment problem: integrating the strategic, tactical and operational level aspects," Annals of Operations Research, Springer, vol. 315(2), pages 867-898, August.
    2. 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.
    3. Rouillon, Stéphane & Desaulniers, Guy & Soumis, François, 2006. "An extended branch-and-bound method for locomotive assignment," Transportation Research Part B: Methodological, Elsevier, vol. 40(5), pages 404-423, June.
    4. Lin, Boliang & Zhao, Yinan, 2021. "Synchronized optimization of EMU train assignment and second-level preventive maintenance scheduling," Reliability Engineering and System Safety, Elsevier, vol. 215(C).
    5. Camilo Ortiz-Astorquiza & Jean-François Cordeau & Emma Frejinger, 2021. "The Locomotive Assignment Problem with Distributed Power at the Canadian National Railway Company," Transportation Science, INFORMS, vol. 55(2), pages 510-531, March.
    6. Piu, F. & Prem Kumar, V. & Bierlaire, M. & Speranza, M.G., 2015. "Introducing a preliminary consists selection in the locomotive assignment problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 82(C), pages 217-237.
    7. Belgacem Bouzaiene-Ayari & Clark Cheng & Sourav Das & Ricardo Fiorillo & Warren B. Powell, 2016. "From Single Commodity to Multiattribute Models for Locomotive Optimization: A Comparison of Optimal Integer Programming and Approximate Dynamic Programming," Transportation Science, INFORMS, vol. 50(2), pages 366-389, May.
    8. Prashant Premkumar & P. N. Ram Kumar, 2019. "Literature Review of Locomotive Assignment Problem from Service Operations Perspective: The Case of Indian Railways," IIM Kozhikode Society & Management Review, , vol. 8(1), pages 74-86, January.
    9. Warren B. Powell & Belgacem Bouzaiene-Ayari & Coleman Lawrence & Clark Cheng & Sourav Das & Ricardo Fiorillo, 2014. "Locomotive Planning at Norfolk Southern: An Optimizing Simulator Using Approximate Dynamic Programming," Interfaces, INFORMS, vol. 44(6), pages 567-578, December.
    10. Oliver Faust & Jochen Gönsch & Robert Klein, 2017. "Demand-Oriented Integrated Scheduling for Point-to-Point Airlines," Transportation Science, INFORMS, vol. 51(1), pages 196-213, February.
    11. Canca, David & Barrena, Eva, 2018. "The integrated rolling stock circulation and depot location problem in railway rapid transit systems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 115-138.
    12. Sciau, Jean-Baptiste & Goyon, Agathe & Sarazin, Alexandre & Bascans, Jérémy & Prud’homme, Charles & Lorca, Xavier, 2024. "Using constraint programming to address the operational aircraft line maintenance scheduling problem," Journal of Air Transport Management, Elsevier, vol. 115(C).
    13. 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.
    14. Vaidyanathan, Balachandran & Ahuja, Ravindra K. & Liu, Jian & Shughart, Larry A., 2008. "Real-life locomotive planning: New formulations and computational results," Transportation Research Part B: Methodological, Elsevier, vol. 42(2), pages 147-168, February.
    15. Hong, Sung-Pil & Kim, Kyung Min & Lee, Kyungsik & Hwan Park, Bum, 2009. "A pragmatic algorithm for the train-set routing: The case of Korea high-speed railway," Omega, Elsevier, vol. 37(3), pages 637-645, June.
    16. Balachandran Vaidyanathan & Ravindra K. Ahuja & James B. Orlin, 2008. "The Locomotive Routing Problem," Transportation Science, INFORMS, vol. 42(4), pages 492-507, November.
    17. Zhong, Qingwei & Lusby, Richard M. & Larsen, Jesper & Zhang, Yongxiang & Peng, Qiyuan, 2019. "Rolling stock scheduling with maintenance requirements at the Chinese High-Speed Railway," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 24-44.
    18. Zhiyuan Lin & Raymond S. K. Kwan, 2016. "Local convex hulls for a special class of integer multicommodity flow problems," Computational Optimization and Applications, Springer, vol. 64(3), pages 881-919, July.
    19. 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.
    20. 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.

    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:jomega:v:37:y:2009:i:3:p:555-565. 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/375/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.