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

Train scheduling for minimizing passenger waiting time with time-dependent demand and skip-stop patterns: Nonlinear integer programming models with linear constraints

Author

Listed:
  • Niu, Huimin
  • Zhou, Xuesong
  • Gao, Ruhu

Abstract

This paper focuses on how to minimize the total passenger waiting time at stations by computing and adjusting train timetables for a rail corridor with given time-varying origin-to-destination passenger demand matrices. Given predetermined train skip-stop patterns, a unified quadratic integer programming model with linear constraints is developed to jointly synchronize effective passenger loading time windows and train arrival and departure times at each station. A set of quadratic and quasi-quadratic objective functions are proposed to precisely formulate the total waiting time under both minute-dependent demand and hour-dependent demand volumes from different origin–destination pairs. We construct mathematically rigorous and algorithmically tractable nonlinear mixed integer programming models for both real-time scheduling and medium-term planning applications. The proposed models are implemented using general purpose high-level optimization solvers, and the model effectiveness is further examined through numerical experiments of real-world rail train timetabling test cases.

Suggested Citation

  • Niu, Huimin & Zhou, Xuesong & Gao, Ruhu, 2015. "Train scheduling for minimizing passenger waiting time with time-dependent demand and skip-stop patterns: Nonlinear integer programming models with linear constraints," Transportation Research Part B: Methodological, Elsevier, vol. 76(C), pages 117-135.
    • Handle: RePEc:eee:transb:v:76:y:2015:i:c:p:117-135
    DOI: 10.1016/j.trb.2015.03.004
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261515000478
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2015.03.004?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. G. F. Newell, 1971. "Dispatching Policies for a Transportation Route," Transportation Science, INFORMS, vol. 5(1), pages 91-105, February.
    2. 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.
    3. Carey, Malachy, 1994. "A model and strategy for train pathing with choice of lines, platforms, and routes," Transportation Research Part B: Methodological, Elsevier, vol. 28(5), pages 333-353, October.
    4. Rachel C. W. Wong & Tony W. Y. Yuen & Kwok Wah Fung & Janny M. Y. Leung, 2008. "Optimizing Timetable Synchronization for Rail Mass Transit," Transportation Science, INFORMS, vol. 42(1), pages 57-69, February.
    5. Cordone, Roberto & Redaelli, Francesco, 2011. "Optimizing the demand captured by a railway system with a regular timetable," Transportation Research Part B: Methodological, Elsevier, vol. 45(2), pages 430-446, February.
    6. Kroon, Leo & Maróti, Gábor & Helmrich, Mathijn Retel & Vromans, Michiel & Dekker, Rommert, 2008. "Stochastic improvement of cyclic railway timetables," Transportation Research Part B: Methodological, Elsevier, vol. 42(6), pages 553-570, July.
    7. Ghoneim, N. S. A. & Wirasinghe, S. C., 1986. "Optimum zone structure during peak periods for existing urban rail lines," Transportation Research Part B: Methodological, Elsevier, vol. 20(1), pages 7-18, February.
    8. Goverde, Rob M.P., 2007. "Railway timetable stability analysis using max-plus system theory," Transportation Research Part B: Methodological, Elsevier, vol. 41(2), pages 179-201, February.
    9. Christian Liebchen, 2008. "The First Optimized Railway Timetable in Practice," Transportation Science, INFORMS, vol. 42(4), pages 420-435, November.
    10. Bhat, Chandra R., 1995. "A heteroscedastic extreme value model of intercity travel mode choice," Transportation Research Part B: Methodological, Elsevier, vol. 29(6), pages 471-483, December.
    11. 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.
    12. Nachtigall, Karl & Voget, Stefan, 1997. "Minimizing waiting times in integrated fixed interval timetables by upgrading railway tracks," European Journal of Operational Research, Elsevier, vol. 103(3), pages 610-627, December.
    13. 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.
    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. Tian, Xiaopeng & Niu, Huimin, 2020. "Optimization of demand-oriented train timetables under overtaking operations: A surrogate-dual-variable column generation for eliminating indivisibility," Transportation Research Part B: Methodological, Elsevier, vol. 142(C), pages 143-173.
    2. 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.
    3. 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.
    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. 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.
    6. 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.
    7. Wang, Chao & Meng, Xin & Guo, Mingxue & Li, Hao & Hou, Zhiqiang, 2022. "An integrated energy-efficient and transfer-accessible model for the last train timetabling problem," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 588(C).
    8. Cacchiani, Valentina & Qi, Jianguo & Yang, Lixing, 2020. "Robust optimization models for integrated train stop planning and timetabling with passenger demand uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 136(C), pages 1-29.
    9. Kang, Liujiang & Zhu, Xiaoning & Sun, Huijun & Puchinger, Jakob & Ruthmair, Mario & Hu, Bin, 2016. "Modeling the first train timetabling problem with minimal missed trains and synchronization time differences in subway networks," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 17-36.
    10. Kang, Liujiang & Wu, Jianjun & Sun, Huijun & Zhu, Xiaoning & Gao, Ziyou, 2015. "A case study on the coordination of last trains for the Beijing subway network," Transportation Research Part B: Methodological, Elsevier, vol. 72(C), pages 112-127.
    11. Liu, Renming & Li, Shukai & Yang, Lixing, 2020. "Collaborative optimization for metro train scheduling and train connections combined with passenger flow control strategy," Omega, Elsevier, vol. 90(C).
    12. 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.
    13. 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.
    14. Yan, Fei & Goverde, Rob M.P., 2019. "Combined line planning and train timetabling for strongly heterogeneous railway lines with direct connections," Transportation Research Part B: Methodological, Elsevier, vol. 127(C), pages 20-46.
    15. 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).
    16. Burdett, R.L. & Kozan, E., 2009. "Techniques for inserting additional trains into existing timetables," Transportation Research Part B: Methodological, Elsevier, vol. 43(8-9), pages 821-836, September.
    17. Talebian, Ahmadreza & Zou, Bo, 2015. "Integrated modeling of high performance passenger and freight train planning on shared-use corridors in the US," Transportation Research Part B: Methodological, Elsevier, vol. 82(C), pages 114-140.
    18. Zhang, Quan & Li, Xuan & Yan, Tao & Lu, Lili & Shi, Yang, 2022. "Last train timetabling optimization for minimizing passenger transfer failures in urban rail transit networks: A time period based approach," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 605(C).
    19. Wenliang Zhou & Wenzhuang Fan & Xiaorong You & Lianbo Deng, 2019. "Demand-Oriented Train Timetabling Integrated with Passenger Train-Booking Decisions," Sustainability, MDPI, vol. 11(18), pages 1-34, September.
    20. Pan Shang & Yu Yao & Liya Yang & Lingyun Meng & Pengli Mo, 2021. "Integrated Model for Timetabling and Circulation Planning on an Urban Rail Transit Line: a Coupled Network-Based Flow Formulation," Networks and Spatial Economics, Springer, vol. 21(2), pages 331-364, June.

    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:76:y:2015:i:c:p:117-135. 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.