{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T21:26:34Z","timestamp":1783027594690,"version":"3.54.6"},"reference-count":50,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["INFORMS Journal on Computing"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:p>Unexpected disruptions in urban rail transit systems cause the infeasibility of the initial train schedule and delays or cancelations of a lot of trains. Even though some recent studies begun to address the rolling stock and timetable optimization problem (RSTO), there is still a large gap between theoretical models and practical applications due to the real-time requirements of train rescheduling decisions. In this work, we first model RSTO using a path-based formulation, in which each path refers to a spatial-temporal trajectory of a rescheduled train in the considered network. The optimal set of paths can minimize the expected cost of train cancelation and train delay time. Our formulation also considers a series of operational constraints, such as train headway constraints, short-turning constraints and rolling stock constraints. We develop an efficient branch-and-price framework that decomposes the problem into a restricted master problem and a set of pricing subproblems, where we iteratively generate promising paths with negative reduce costs. We show that each subproblem is a resource-constrained shortest path problem and can be solved efficiently by an improved label setting algorithm by proving its optimality conditions. We compare the tightness of our new path-based formulation with state-of-art formulations and test our branch-and-price approach on real-world instances from Beijing rail transit. The results show that our approach can generate near-optimal solutions in less than three minutes with small duality gap, which evidently outperforms existing formulations and fulfills the requirement of rail managers in practical applications.<\/jats:p>\n                  <jats:p>History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods &amp; Analysis.<\/jats:p>\n                  <jats:p>Funding: This work was supported by the National Natural Science Foundation of China [Grants 72288101 and 72322022].<\/jats:p>\n                  <jats:p>Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https:\/\/pubsonline.informs.org\/doi\/suppl\/10.1287\/ijoc.2023.0391 ) as well as from the IJOC GitHub software repository ( https:\/\/github.com\/INFORMSJoC\/2023.0391 ). The complete IJOC Software and Data Repository is available at https:\/\/informsjoc.github.io\/ .<\/jats:p>","DOI":"10.1287\/ijoc.2023.0391","type":"journal-article","created":{"date-parts":[[2025,4,18]],"date-time":"2025-04-18T12:01:06Z","timestamp":1744977666000},"page":"507-530","source":"Crossref","is-referenced-by-count":4,"title":["Real-Time Rolling Stock and Timetable Rescheduling in Urban Rail Transit Systems"],"prefix":"10.1287","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2725-3919","authenticated-orcid":false,"given":"Jiateng","family":"Yin","sequence":"first","affiliation":[{"name":"School of Systems Science, Beijing Jiaotong University, Beijing 100044, China; and Hebei Key Laboratory of Future Urban Intelligent Traffic Management, Beijing Jiaotong University, Beijing 100044, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1628-5015","authenticated-orcid":false,"given":"Lixing","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Systems Science, Beijing Jiaotong University, Beijing 100044, China; and Hebei Key Laboratory of Future Urban Intelligent Traffic Management, Beijing Jiaotong University, Beijing 100044, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5774-2791","authenticated-orcid":false,"given":"Zhe","family":"Liang","sequence":"additional","affiliation":[{"name":"School of Economics and Management, Tongji University, Shanghai 200092, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrea","family":"D\u2019Ariano","sequence":"additional","affiliation":[{"name":"Department of Civil, Computer Science and Aeronautical Technologies Engineering, Rome Tre University, 00154 Rome, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ziyou","family":"Gao","sequence":"additional","affiliation":[{"name":"School of Systems Science, Beijing Jiaotong University, Beijing 100044, China; and Hebei Key Laboratory of Future Urban Intelligent Traffic Management, Beijing Jiaotong University, Beijing 100044, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1060.0155"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.46.3.316"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-011-0978-0"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tre.2013.01.013"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1016\/j.tre.2017.10.018"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1007\/s10288-007-0037-5"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1110.0388"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2014.01.009"},{"key":"B10","unstructured":"Corman F (2010) Real-time railway traffic management: Dispatching in complex, large and busy railway networks. PhD thesis, Technische Universiteit, Delft, Germany."},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2022.2283"},{"key":"B12","doi-asserted-by":"crossref","first-page":"646","DOI":"10.1016\/j.ejor.2006.10.034","volume":"183","author":"D\u2019Ariano A","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.34.3.312.12298"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2013.0506"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.24.2.145"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2020.1002"},{"issue":"6","key":"B17","first-page":"1627","volume":"57","author":"Gemander P","year":"2023","journal-title":"Transportation Sci."},{"key":"B18","unstructured":"Haahr J, Lusby R, Larsen J, Pisinger D (2014) A branch-and-price framework for railway rolling stock rescheduling during disruptions. Technical report, DTU Management Engineering, Delhi."},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2019.0891"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2021.1084"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2019.0968"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2019.12.005"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199805)31:3<193::AID-NET6>3.0.CO;2-A"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2013.0502"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1080\/21680566.2017.1358678"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2014.1327"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2018.1837"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2015.0605"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2013.0480"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2013.12.020"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2017.0772"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2017.03.003"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1080.0642"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2021.04.041"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2013.0489"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2017.0807"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1002\/net.20212"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1287\/opre.45.6.831"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2021.1118"},{"key":"B41","doi-asserted-by":"publisher","DOI":"10.1007\/s12469-023-00339-2"},{"key":"B42","doi-asserted-by":"publisher","DOI":"10.1177\/0361198105193000104"},{"key":"B43","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2020.1024"},{"key":"B44","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2015.0618"},{"key":"B45","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2018.10.006"},{"key":"B46","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2018.0867"},{"key":"B47","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2021.02.059"},{"key":"B49","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2022.1233"},{"key":"B48","doi-asserted-by":"crossref","unstructured":"Yin J, Yang L, Liang Z, D\u2019Ariano A, Gao Z (2025) Real-time rolling stock and timetable rescheduling in urban rail transit systems. 10.1287\/ijoc.2023.0391.cd, https:\/\/github.com\/INFORMSJoC\/2023.0391.","DOI":"10.1287\/ijoc.2023.0391.cd"},{"key":"B50","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2019.02.015"},{"key":"B51","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2021.103080"},{"key":"B52","doi-asserted-by":"publisher","DOI":"10.1080\/23249935.2023.2181024"}],"container-title":["INFORMS Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/ijoc.2023.0391","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T08:19:53Z","timestamp":1776068393000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/ijoc.2023.0391"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["10.1287\/ijoc.2023.0391"],"URL":"https:\/\/doi.org\/10.1287\/ijoc.2023.0391","relation":{},"ISSN":["1091-9856","1526-5528"],"issn-type":[{"value":"1091-9856","type":"print"},{"value":"1526-5528","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3]]}}}