×

Integrated model for timetabling and circulation planning on an urban rail transit line: a coupled network-based flow formulation. (English) Zbl 1514.90091

Summary: The recent development of advanced communication and data collection technologies enables a wide range of possibilities for systematic planning, operation, and control of urban rail transit systems in many megacities. While traditional methods consider tactical transit timetabling and operational circulation planning as two independent stages, this study aims to propose an optimization model and solution scheme to fully integrate these two supply-side stages in response to passenger demand dynamics. We first construct a new formulation through two coupled space-time network representations, namely, the transit space-time network and passenger space-time network, with many embedded constraints. In detail, the transit space-time network covers constraints involving train fleet size, deadheading and holding operations, headway requirements, and running and dwell times; meanwhile, the passenger space-time network is used to represent passenger traveling processes and the resulting trajectories. A coupled network-based flow optimization model is accordingly established to minimize passenger total travel time with a fixed train fleet size. To handle large-scale problem instances, we first adopt a constraint splitting technique to form two subsets of Lagrangian multipliers corresponding to individual passenger decision constraints and train capacity constraints. A dual decomposition scheme is then developed to iteratively coordinate the adjustment of Lagrangian multipliers and solve the related two subproblems. Specifically, the passenger subproblem is solved by a passenger loading algorithm, and the train subproblem is decomposed and solved by the alternating direction method of multipliers. The effectiveness of the proposed model and solution approach is evaluated on a real-world case study based on the Batong Line in the Beijing subway network.

MSC:

90B20 Traffic problems in operations research
90B35 Deterministic scheduling theory in operations research
Full Text: DOI

References:

[1] Alfieri, A.; Groot, R.; Kroon, L.; Schrijver, A., Efficient circulation of railway rolling stock, Transp Sci, 40, 3, 378-391 (2006)
[2] Auffrey, C.; Fu, X.; Wang, X.; McClearnon, AW, Enhancing Beijing’s resilience by improving Tongzhou’s access to high-speed rail transportation, Urban Rail Transit, 3, 1, 23-33 (2017)
[3] Banks, JH, Optimal headways for multiroute transit systems, J Adv Transp, 24, 2, 127-155 (1990)
[4] Bao, X., Urban rail transit present situation and future development trends in China: overall analysis based on national policies and strategic plans in 2016-2020, Urban Rail Transit, 4, 1, 1-12 (2018)
[5] Barrena, E.; Canca, D.; Coelho, LC; Laporte, G., Exact formulations and algorithm for the train timetabling problem with dynamic demand, Comput Oper Res, 44, 66-74 (2014) · Zbl 1307.90067
[6] Barrena, E.; Canca, D.; Coelho, LC; Laporte, G., Single-line rail rapid transit timetabling under dynamic passenger demand, Transp Res B Methodol, 70, 134-150 (2014)
[7] Binder, S.; Maknoon, Y.; Bierlaire, M., Exogenous priority rules for the capacitated passenger assignment problem, Transp Res B Methodol, 105, 19-42 (2017)
[8] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations Trends Machine Learning, 3, 1, 1-122 (2011) · Zbl 1229.90122
[9] Cadarso, L.; Marín, Á., Integration of timetable planning and rolling stock in rapid transit networks, Ann Oper Res, 199, 1, 113-135 (2012) · Zbl 1251.90082
[10] Cadarso, L.; Marín, Á.; Maróti, G., Recovery of disruptions in rapid transit networks, Transport Res Part E: Logistics Transportation Rev, 53, 15-33 (2013)
[11] Caimi, G.; Burkolter, D.; Herrmann, T.; Chudak, F.; Laumanns, M., Design of a railway scheduling model for dense services, Netw Spat Econ, 9, 1, 25-46 (2009) · Zbl 1162.90447
[12] Canca, D.; Barrena, E., The integrated rolling stock circulation and depot location problem in railway rapid transit systems, Transportation Research Part E Logistics Transportation Rev, 109, 115-138 (2018)
[13] Carey M, Crawford I (2007) Scheduling trains on a network of busy complex stations. Transportation Research Part B: Methodological 41(2):159-178
[14] Ceder, A., Optimal multi-vehicle type transit timetabling and vehicle scheduling, Procedia Soc Behav Sci, 20, 19-30 (2011)
[15] Ceder, A.; Golany, B.; Tal, O., Creating bus timetables with maximal synchronization, Transp Res A Policy Pract, 35, 10, 913-928 (2001)
[16] Douglas, J.; Rachford, HH, On the numerical solution of heat conduction problems in two and three space variables, Trans Am Math Soc, 82, 2, 421-439 (1956) · Zbl 0070.35401
[17] Feizollahi, MJ; Costley, M.; Ahmed, S.; Grijalva, S., Large-scale decentralized unit commitment, Int J Electr Power Energy Syst, 73, 97-106 (2015)
[18] Frangioni, A.; Gendron, B., 0-1 reformulations of the multicommodity capacitated network design problem, Discret Appl Math, 157, 6, 1229-1241 (2009) · Zbl 1168.90002
[19] Ghoneim, N.; Wirasinghe, S., Optimum zone structure during peak periods for existing urban rail lines, Transp Res B Methodol, 20, 1, 7-18 (1986)
[20] Guihaire, V.; Hao, J-K, Transit network design and scheduling: a global review, Transp Res A Policy Pract, 42, 10, 1251-1273 (2008)
[21] Guihaire, V.; Hao, J-K, Transit network timetabling and vehicle assignment for regulating authorities, Comput Ind Eng, 59, 1, 16-23 (2010)
[22] Hamdouch, Y.; Szeto, W.; Jiang, Y., A new schedule-based transit assignment model with travel strategies and supply uncertainties, Transp Res B Methodol, 67, 35-67 (2014)
[23] Ibarra-Rojas, O.; Delgado, F.; Giesen, R.; Muñoz, J., Planning, operation, and control of bus transport systems: a literature review, Transp Res B Methodol, 77, 38-75 (2015)
[24] Ibarra-Rojas, OJ; Giesen, R.; Rios-Solis, YA, An integrated approach for timetabling and vehicle scheduling problems to analyze the trade-off between level of service and operating costs of transit networks, Transp Res B Methodol, 70, 35-46 (2014)
[25] Jara-Diaz S, Friesz TL Measuring the Benefits Derived From a Transportation Investment. Trans Res B Methodol 16(1):57-77
[26] Jiang, Z.; Gu, J.; Fan, W.; Liu, W.; Zhu, B., Q-learning approach to coordinated optimization of passenger inflow control with train skip-stopping on a urban rail transit line, Comput Ind Eng, 127, 1131-1142 (2019)
[27] Kang, L.; Sun, H.; Wu, J.; Gao, Z., Last train station-skipping, transfer-accessible and energy-efficient scheduling in subway networks, Energy, 206, 118127 (2020)
[28] Kang, L.; Zhu, X.; Sun, H.; Wu, J.; Gao, Z.; Hu, B., Last train timetabling optimization and bus bridging service management in urban railway transit networks, Omega, 84, 31-44 (2019)
[29] Kliewer, N.; Mellouli, T.; Suhl, L., A time-space network based exact optimization model for multi-depot bus scheduling, Eur J Oper Res, 175, 3, 1616-1627 (2006) · Zbl 1142.90354
[30] Krasemann, JT, Design of an effective algorithm for fast response to the re-scheduling of railway traffic during disturbances, Transportation Res Part C Emerg Technol, 20, 1, 62-78 (2012)
[31] Liebchen, C.; Möhring, RH, The modeling power of the periodic event scheduling problem: railway timetables — and beyond, 3-40 (2007), Berlin Heidelberg: Springer, Berlin Heidelberg
[32] Liu, J.; Zhou, X., Capacitated transit service network design with boundedly rational agents, Transp Res B Methodol, 93, 225-250 (2016)
[33] Long, S.; Meng, L.; Miao, J.; Hong, X.; Corman, F., Synchronizing last Trains of Urban Rail Transit System to better serve passengers from late night Trains of High-Speed Railway Lines, Netw Spat Econ, 20, 2, 599-633 (2020) · Zbl 1514.90078
[34] Lu, K.; Han, B.; Zhou, X., Smart urban transit systems: from integrated framework to interdisciplinary perspective, Urban Rail Transit, 4, 2, 49-67 (2018)
[35] Meng, L.; Luan, X.; Zhou, X., A train dispatching model under a stochastic environment: stable train routing constraints and reformulation, Netw Spat Econ, 16, 3, 791-820 (2016) · Zbl 1364.90074
[36] Michaelis, M.; Schöbel, A., Integrating line planning, timetabling, and vehicle scheduling: a customer-oriented heuristic, Public Transport, 1, 3, 211 (2009)
[37] Niu, H.; Zhou, X., Optimizing urban rail timetable under time-dependent demand and oversaturated conditions, Transportation Res Part C: Emerg Technol, 36, 212-230 (2013)
[38] Niu, H.; Zhou, X.; Gao, R., Train scheduling for minimizing passenger waiting time with time-dependent demand and skip-stop patterns: nonlinear integer programming models with linear constraints, Transp Res B Methodol, 76, 117-135 (2015)
[39] Niu, H.; Zhou, X.; Tian, X., Coordinating assignment and routing decisions in transit vehicle schedules: a variable-splitting Lagrangian decomposition approach for solution symmetry breaking, Transp Res B Methodol, 107, 70-101 (2018)
[40] Nuzzolo, A.; Crisalli, U.; Rosati, L., A schedule-based assignment model with explicit capacity constraints for congested transit networks, Transportation Res Part C: Emerg Technol, 20, 1, 16-33 (2012)
[41] Peeters, M.; Kroon, L., Circulation of railway rolling stock: a branch-and-price approach, Comput Ind Eng, 35, 2, 538-556 (2008) · Zbl 1141.90009
[42] Pelletier, M-P; Trépanier, M.; Morency, C., Smart card data use in public transit: A literature review, Transportation Research Part C: Emerging Technologies, 19, 4, 557-568 (2011)
[43] Petersen, HL; Larsen, A.; Madsen, OBG; Petersen, B.; Ropke, S., The simultaneous vehicle scheduling and passenger service problem, Transp Sci, 47, 4, 603-616 (2013)
[44] Schöbel, A., An eigenmodel for iterative line planning, timetabling and vehicle scheduling in public transportation, Transportation Res Part C: Emerg Technol, 74, 348-365 (2017)
[45] Shafahi, Y.; Khani, A., A practical model for transfer optimization in a transit network: model formulations and solutions, Transp Res A Policy Pract, 44, 6, 377-389 (2010)
[46] Shang, P.; Li, R.; Guo, J.; Xian, K.; Zhou, X., Integrating Lagrangian and Eulerian observations for passenger flow state estimation in an urban rail transit network: a space-time-state hyper network-based assignment approach, Transp Res B Methodol, 121, 135-167 (2019)
[47] Shang, P.; Li, R.; Liu, Z.; Xian, K.; Guo, J., Timetable synchronization and optimization considering time-dependent passenger demand in an urban Subway network, Transp Res Rec, 2672, 8, 243-254 (2018)
[48] Shang, P.; Li, R.; Liu, Z.; Yang, L.; Wang, Y., Equity-oriented skip-stopping schedule optimization in an oversaturated urban rail transit network, Transportation Res Part C Emerg Technol, 89, 321-343 (2018)
[49] Shang, P.; Li, R.; Yang, L., Demand-driven timetable and stop pattern cooperative optimization on an urban rail transit line, Transp Plan Technol, 43, 1, 78-100 (2020)
[50] Shi, J.; Yang, L.; Yang, J.; Gao, Z., Service-oriented train timetabling with collaborative passenger flow control on an oversaturated metro line: an integer linear optimization approach, Transp Res B Methodol, 110, 26-59 (2018)
[51] Steinzen, I.; Gintner, V.; Suhl, L.; Kliewer, N., A time-space network approach for the integrated vehicle-and crew-scheduling problem with multiple depots, Transp Sci, 44, 3, 367-382 (2010)
[52] Sun, H.; Wu, J.; Wu, L.; Yan, X.; Gao, Z., Estimating the influence of common disruptions on urban rail transit networks, Transp Res A Policy Pract, 94, 62-75 (2016)
[53] Sun, L.; Jin, JG; Lee, D-H; Axhausen, KW; Erath, A., Demand-driven timetable design for metro services, Transportation Research Part C: Emerg Technol, 46, 284-299 (2014)
[54] Szeto, WY; Jiang, Y., Transit assignment: approach-based formulation, extragradient method, and paradox, Transp Res B Methodol, 62, 51-76 (2014)
[55] Teng, J.; Liu, W-R, Development of a behavior-based passenger flow assignment model for urban rail transit in section interruption circumstance, Urban Rail Transit, 1, 1, 35-46 (2015)
[56] Tian, X.; Niu, H., A bi-objective model with sequential search algorithm for optimizing network-wide train timetables, Comput Ind Eng, 127, 1259-1272 (2019)
[57] Wang, Y.; D’Ariano, A.; Yin, J.; Meng, L.; Tang, T.; Ning, B., Passenger demand oriented train scheduling and rolling stock circulation planning for an urban rail transit line, Transp Res B Methodol, 118, 193-227 (2018)
[58] Wang, Y.; Tang, T.; Ning, B.; Meng, L., Integrated optimization of regular train schedule and train circulation plan for urban rail transit lines, Transportation Res Part E: Logistics Transportation Rev, 105, 83-104 (2017)
[59] Wang, Y.; Tang, T.; Ning, B.; van den Boom, TJJ; De Schutter, B., Passenger-demands-oriented train scheduling for an urban rail transit network, Transportation Research Part C: Emerg Technol, 60, 1-23 (2015)
[60] Wong, RCW; Yuen, TWY; Fung, KW; Leung, JMY, Optimizing timetable synchronization for rail mass transit, Transp Sci, 42, 1, 57-69 (2008)
[61] Wu, J.; Liu, M.; Sun, H.; Li, T.; Gao, Z.; Wang, DZW, Equity-based timetable synchronization optimization in urban subway network, Transportation Research Part C Emerg Technol, 51, 1-18 (2015)
[62] Yang, L., Yao, Y., Shi, H., Shang, P., 2020a. Dynamic passenger demand-oriented train scheduling optimization considering flexible short-turning strategy. J Oper Res Soc, 1-19. doi:doi:10.1080/01605682.2020.1806745
[63] Yang, S.; Ning, L.; Shang, P.; Tong, LC, Augmented Lagrangian relaxation approach for logistics vehicle routing problem with mixed backhauls and time windows, Transportation Res Part E Logistics Transportation Rev, 135, 101891 (2020)
[64] Yao, Y.; Zhu, X.; Dong, H.; Wu, S.; Wu, H.; Carol Tong, L.; Zhou, X., ADMM-based problem decomposition scheme for vehicle routing problem with time windows, Transp Res B Methodol, 129, 156-174 (2019)
[65] Yin, J.; Tang, T.; Yang, L.; Gao, Z.; Ran, B., Energy-efficient metro train rescheduling with uncertain time-variant passenger demands: an approximate dynamic programming approach, Transp Res B Methodol, 91, 178-210 (2016)
[66] Yin, J.; Yang, L.; Tang, T.; Gao, Z.; Ran, B., Dynamic passenger demand oriented metro train scheduling with energy-efficiency and waiting time minimization: mixed-integer linear programming approaches, Transp Res B Methodol, 97, 182-213 (2017)
[67] Yue, Y.; Han, J.; Wang, S.; Liu, X., Integrated train timetabling and rolling stock scheduling model based on time-dependent demand for urban rail transit, Comput Aided Civil Infrastructure Eng, 32, 10, 856-873 (2017)
[68] Zeng, Z.; Li, T., Analyzing congestion propagation on urban rail transit oversaturated conditions: a framework based on SIR epidemic model, Urban Rail Transit, 4, 3, 130-140 (2018)
[69] Zhang, Y.; Peng, Q.; Yao, Y.; Zhang, X.; Zhou, X., Solving cyclic train timetabling problem through model reformulation: extended time-space network construct and alternating direction method of multipliers methods, Transp Res B Methodol, 128, 344-379 (2019)
[70] Zhou, X.; Tong, L.; Mahmoudi, M.; Zhuge, L.; Yao, Y.; Zhang, Y.; Shang, P.; Liu, J.; Shi, T., Open-source VRPLite package for vehicle routing with pickup and delivery: a path finding engine for scheduled transportation systems, Urban Rail Transit, 4, 2, 68-85 (2018)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.