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

Solution of the Train Platforming Problem

Author

Listed:
  • Alberto Caprara

    (DEIS, University of Bologna, 40136 Bologna, Italy)

  • Laura Galli

    (DEIS, University of Bologna, 40136 Bologna, Italy)

  • Paolo Toth

    (DEIS, University of Bologna, 40136 Bologna, Italy)

Abstract

In this paper we study a general formulation of the train platforming problem, which contains as special cases all the versions previously considered in the literature as well as a case study from Rete Ferroviaria Italiana, the Italian Infrastructure Manager. In particular, motivated by our case study, we consider a general quadratic objective function, and propose a new way to linearize it by using a small number of new variables along with a set of constraints that can be separated efficiently by solving an appropriate linear program. The resulting integer linear programming formulation has a continuous relaxation that leads to strong bounds on the optimal value. For the instances in our case study, the solution approach based on this relaxation produces solutions that are much better than those produced by a simple heuristic method currently in use, and that often turn out to be (nearly) optimal.

Suggested Citation

  • Alberto Caprara & Laura Galli & Paolo Toth, 2011. "Solution of the Train Platforming Problem," Transportation Science, INFORMS, vol. 45(2), pages 246-257, May.
    • Handle: RePEc:inm:ortrsc:v:45:y:2011:i:2:p:246-257
    DOI: 10.1287/trsc.1100.0366
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1100.0366
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1100.0366?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. Bunte, F.H.J. & Maks, J.A.H., 1997. "Contestability and sunk costs: an analysis of product R+D competition," Research Memorandum 015, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    2. Kroon, Leo G. & Edwin Romeijn, H. & Zwaneveld, Peter J., 1997. "Routing trains through railway stations: complexity issues," European Journal of Operational Research, Elsevier, vol. 98(3), pages 485-498, May.
    3. Zwaneveld, Peter J. & Kroon, Leo G. & van Hoesel, Stan P. M., 2001. "Routing trains through a railway station based on a node packing model," European Journal of Operational Research, Elsevier, vol. 128(1), pages 14-33, January.
    4. Carey, Malachy & Carville, Sinead, 2003. "Scheduling and platforming trains at busy complex stations," Transportation Research Part A: Policy and Practice, Elsevier, vol. 37(3), pages 195-224, March.
    5. Peter J. Zwaneveld & Leo G. Kroon & H. Edwin Romeijn & Marc Salomon & Stéphane Dauzère-Pérès & Stan P. M. Van Hoesel & Harrie W. Ambergen, 1996. "Routing Trains Through Railway Stations: Model Formulation and Algorithms," Transportation Science, INFORMS, vol. 30(3), pages 181-194, August.
    6. Alain Billionnet, 2003. "Using Integer Programming to Solve the Train-Platforming Problem," Transportation Science, INFORMS, vol. 37(2), pages 213-222, May.
    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. Roca-Riu, Mireia & Fernández, Elena & Estrada, Miquel, 2015. "Parking slot assignment for urban distribution: Models and formulations," Omega, Elsevier, vol. 57(PB), pages 157-175.
    3. Twan Dollevoet & Dennis Huisman & Leo Kroon & Marie Schmidt & Anita Schöbel, 2015. "Delay Management Including Capacities of Stations," Transportation Science, INFORMS, vol. 49(2), pages 185-203, May.
    4. Xu, Xiaoming & Li, Chung-Lun & Xu, Zhou, 2021. "Train timetabling with stop-skipping, passenger flow, and platform choice considerations," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 52-74.
    5. Rajnish Kumar & Goutam Sen & Samarjit Kar & Manoj Kumar Tiwari, 2018. "Station Dispatching Problem for a Large Terminal: A Constraint Programming Approach," Interfaces, INFORMS, vol. 48(6), pages 510-528, November.
    6. Sels, P. & Dewilde, T. & Cattrysse, D. & Vansteenwegen, P., 2016. "Reducing the passenger travel time in practice by the automated construction of a robust railway timetable," Transportation Research Part B: Methodological, Elsevier, vol. 84(C), pages 124-156.
    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. Vansteenwegen, Pieter & Dewilde, Thijs & Burggraeve, Sofie & Cattrysse, Dirk, 2016. "An iterative approach for reducing the impact of infrastructure maintenance on the performance of railway systems," European Journal of Operational Research, Elsevier, vol. 252(1), pages 39-53.
    9. Yinggui Zhang & Ruihua Hu & Qiongfang Zeng & Yuhang Wang & Ya Liu & Shan Huang, 2023. "Optimal Train Platforming with Shunting Operations for Multidirectional Passenger Stations: A Case Study of Guangzhou Station," Mathematics, MDPI, vol. 11(14), pages 1-19, July.
    10. Sels, P. & Vansteenwegen, P. & Dewilde, T. & Cattrysse, D. & Waquet, B. & Joubert, A., 2014. "The train platforming problem: The infrastructure management company perspective," Transportation Research Part B: Methodological, Elsevier, vol. 61(C), pages 55-72.
    11. Leonardo Lamorgese & Carlo Mannino & Mauro Piacentini, 2016. "Optimal Train Dispatching by Benders’-Like Reformulation," Transportation Science, INFORMS, vol. 50(3), pages 910-925, August.
    12. Alberto Caprara & Laura Galli & Sebastian Stiller & Paolo Toth, 2014. "Delay-Robust Event Scheduling," Operations Research, INFORMS, vol. 62(2), pages 274-283, April.
    13. Dollevoet, T.A.B. & Huisman, D. & Schöbel, A. & Schmidt, M.E., 2012. "Delay Management including Capacities of Stations," Econometric Institute Research Papers EI 2012-22, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    14. Lu, Gongyuan & Nie, Yu(Marco) & Liu, Xiaobo & Li, Denghui, 2019. "Trajectory-based traffic management inside an autonomous vehicle zone," Transportation Research Part B: Methodological, Elsevier, vol. 120(C), pages 76-98.
    15. 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.
    16. San Segundo, Pablo & Furini, Fabio & León, Rafael, 2022. "A new branch-and-filter exact algorithm for binary constraint satisfaction problems," European Journal of Operational Research, Elsevier, vol. 299(2), pages 448-467.
    17. Sparing, Daniel & Goverde, Rob M.P., 2017. "A cycle time optimization model for generating stable periodic railway timetables," Transportation Research Part B: Methodological, Elsevier, vol. 98(C), pages 198-223.
    18. Nils Boysen & Simon Emde & Konrad Stephan & Markus Weiß, 2015. "Synchronization in hub terminals with the circular arrangement problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(6), pages 454-469, September.
    19. 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.
    20. Jingliu Xu & Zhimei Wang & Shangjun Yao & Jiarong Xue, 2022. "Train Operations Organization in High-Speed Railway Station Considering Variable Configuration," Sustainability, MDPI, vol. 14(4), pages 1-17, February.
    21. Lu, Gongyuan & Ning, Jia & Liu, Xiaobo & Nie, Yu (Marco), 2022. "Train platforming and rescheduling with flexible interlocking mechanisms: An aggregate approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 159(C).
    22. 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.
    23. Weiya Chen & Weiting Yang & Guangdong Zhang, 2022. "Track Utilization Optimization Method for Arrival Yard of Marshalling Station Considering Arrival and Break-Up Coordination Operation," Mathematics, MDPI, vol. 10(18), pages 1-12, September.

    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. Richard Lusby & Jesper Larsen & David Ryan & Matthias Ehrgott, 2011. "Routing Trains Through Railway Junctions: A New Set-Packing Approach," Transportation Science, INFORMS, vol. 45(2), pages 228-245, May.
    2. Burdett, R.L. & Kozan, E., 2010. "A disjunctive graph model and framework for constructing new train schedules," European Journal of Operational Research, Elsevier, vol. 200(1), pages 85-98, January.
    3. Lu, Gongyuan & Nie, Yu(Marco) & Liu, Xiaobo & Li, Denghui, 2019. "Trajectory-based traffic management inside an autonomous vehicle zone," Transportation Research Part B: Methodological, Elsevier, vol. 120(C), pages 76-98.
    4. Jingliu Xu & Zhimei Wang & Shangjun Yao & Jiarong Xue, 2022. "Train Operations Organization in High-Speed Railway Station Considering Variable Configuration," Sustainability, MDPI, vol. 14(4), pages 1-17, February.
    5. Nikola Bešinović & Rob M. P. Goverde, 2019. "Stable and robust train routing in station areas with balanced infrastructure capacity occupation," Public Transport, Springer, vol. 11(2), pages 211-236, August.
    6. Sels, P. & Vansteenwegen, P. & Dewilde, T. & Cattrysse, D. & Waquet, B. & Joubert, A., 2014. "The train platforming problem: The infrastructure management company perspective," Transportation Research Part B: Methodological, Elsevier, vol. 61(C), pages 55-72.
    7. G. Caimi & F. Chudak & M. Fuchsberger & M. Laumanns & R. Zenklusen, 2011. "A New Resource-Constrained Multicommodity Flow Model for Conflict-Free Train Routing and Scheduling," Transportation Science, INFORMS, vol. 45(2), pages 212-227, May.
    8. Lu, Gongyuan & Ning, Jia & Liu, Xiaobo & Nie, Yu (Marco), 2022. "Train platforming and rescheduling with flexible interlocking mechanisms: An aggregate approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 159(C).
    9. Flamini, Marta & Pacciarelli, Dario, 2008. "Real time management of a metro rail terminus," European Journal of Operational Research, Elsevier, vol. 189(3), pages 746-761, September.
    10. Yidong Wang & Rui Song & Shiwei He & Zilong Song, 2022. "Train Routing and Track Allocation Optimization Model of Multi-Station High-Speed Railway Hub," Sustainability, MDPI, vol. 14(12), pages 1-21, June.
    11. Andrea D'Ariano & Francesco Corman & Dario Pacciarelli & Marco Pranzo, 2008. "Reordering and Local Rerouting Strategies to Manage Train Traffic in Real Time," Transportation Science, INFORMS, vol. 42(4), pages 405-419, November.
    12. 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.
    13. Zwaneveld, Peter J. & Kroon, Leo G. & van Hoesel, Stan P. M., 2001. "Routing trains through a railway station based on a node packing model," European Journal of Operational Research, Elsevier, vol. 128(1), pages 14-33, January.
    14. Carlo Mannino & Alessandro Mascis, 2009. "Optimal Real-Time Traffic Control in Metro Stations," Operations Research, INFORMS, vol. 57(4), pages 1026-1039, August.
    15. Lee, Yusin & Chen, Chuen-Yih, 2009. "A heuristic for the train pathing and timetabling problem," Transportation Research Part B: Methodological, Elsevier, vol. 43(8-9), pages 837-851, September.
    16. Jurjen S. Hooghiemstra & Leo G. Kroon & Michiel A. Odijk & Marc Salomon & Peter J. Zwaneveld, 1999. "Decision Support Systems Support the Search for Win-Win Solutions in Railway Network Design," Interfaces, INFORMS, vol. 29(2), pages 15-32, April.
    17. Yinggui Zhang & Ruihua Hu & Qiongfang Zeng & Yuhang Wang & Ya Liu & Shan Huang, 2023. "Optimal Train Platforming with Shunting Operations for Multidirectional Passenger Stations: A Case Study of Guangzhou Station," Mathematics, MDPI, vol. 11(14), pages 1-19, July.
    18. Lu Yang & Leishan Zhou & Hanxiao Zhou & Chang Han & Wenqiang Zhao, 2023. "A Lagrangian Method for Calculation of Passing Capacity on a Railway Hub Station," Mathematics, MDPI, vol. 11(6), pages 1-20, March.
    19. Carey, Malachy & Crawford, Ivan, 2007. "Scheduling trains on a network of busy complex stations," Transportation Research Part B: Methodological, Elsevier, vol. 41(2), pages 159-178, February.
    20. Twan Dollevoet & Dennis Huisman & Leo Kroon & Marie Schmidt & Anita Schöbel, 2015. "Delay Management Including Capacities of Stations," Transportation Science, INFORMS, vol. 49(2), pages 185-203, May.

    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:246-257. 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.