Designing a Robust Approach to Resolve the Tehran Metro Trains Scheduling Problem in Uncertain Conditions
Subject Areas : Optimization
pejman salehi
1
,
Mehran Khalaj
2
*
,
davood jafari
3
1 - PhD student of Islamic Azad University, Roodehen Branch
2 - Department of Industrial Engineering, Parand Branch, Islamic Azad University, Parand, Iran
3 - faculty of industry,islamic azad university of parand
Keywords: Particle Swarm Method, Combinations Optimization, Robustness Approach, Scheduled Timetable and Tehran Metro,
Abstract :
Reliability and punctuality in the traffic supervision of the metro network are the key performance indicators for the evaluation of this industry's efficiency which can lead to the participants' satisfaction. A common technique to improve the level of the Metro traffic control system’s reliability and performance increasing the rate of train receives and dispatches from special position determined, particularly in the different periods of designing train timetables, which can be out-of-the-way or lead to a stable level. Therefore, to increase the permanency level of the metro timetables, the traffic control center’s operation in the metro network considers fixed time values as Buffer times between rail events with a high probability of flaws using normal procedures in the timetables. In this respect, the first delay in the metro network is the possibility of its spread in all of the lines and its effect that will be realized on all of the entities and the being of subsequent luckless consequences that will be prevented. Adding to this, Buffer time in the train schedule in some cases may cause the capacity of the metro network to be reduced, which could be the basis of traffic special effects for eventful lines such as Tehran Metro’s line one. However, the ability of time tables to add fixed times values as a Buffer time between two conflicting events in the metro network can be whispered subsequently in this case, it is necessary to allocate Buffer times with sufficient accuracy and according to the traffic priorities of dispatching and receiving trains. Some important measures in Metro passenger activities (such as unpredicted train dispatches) take place properly and prevent certain incidents. In current study, the objective of cultivating and improving the stability of train running schedule tables was accomplished by assigning optimum Buffer in the network which, times has been studied utilizing innovative methods. So, the resources for allocating optimum time have been modeled via combinatorial optimization algorithms and particle swarm optimization methods. In this algorithm, each Buffer time according to the priority of the events as well technical, economic, and operational criteria is shown to one of the prevailing assignments of the schedule tables which results and its effects in terms of time units (seconds). Ultimately, the validity of the proposed model that is presented applying the Tehran Metro line one is verified.
Wu, Q., Cole, C., & McSweeney, T. 2019. Applications of particle swarm optimization in the railway domain. International Journal of Rail Transportation, 4(3), 167-190. Available at: https://doi.org/10.1080/23248378.2016.1179599
Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations research, 52(1), 35-53. Available at: https://doi.org/10.1287/opre.1030.0065
Wentges, B. 2022. Railway disruption management with passenger-centric rescheduling. Available at: http://resolver.tudelft.nl/uuid:e1922a5c-7605-493c-8354-0b08fb13e590
Liang, Y., Liu, H., Qian, C., & Wang, G. 2019. A modified genetic algorithm for multi-objective optimization on running curve of automatic train operation system using penalty function method. International Journal of Intelligent Transportation Systems Research, 17, 74-87. Available at: https://doi.org/10.1016/j.trc.2014.02.023
Samà, M., D'Ariano, A., Pacciarelli, D., Pellegrini, P., & Rodriguez, J. 2020. Ant colony optimization for train routing selection: Operational vs tactical application. In 2017 5th IEEE International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS) (pp. 297-302). IEEE. Available at: https://doi.org/10.1109/MTITS.2017.8005684
ShangGuan, W., Yan, X. H., Cai, B. G., & Wang, J. 2018. Multiobjective optimization for train speed trajectory in CTCS high-speed railway with a hybrid evolutionary algorithm. IEEE Transactions on Intelligent Transportation Systems, 16(4), 2215-2225. Available at: https://doi.org/10.1109/TITS.2015.2402160
De Martinis, V., & Gallo, M. 2016. Models and methods to optimize train speed profiles with and without energy recovery systems: a suburban test case. Procedia-Social and Behavioral Sciences, 87, 222-233. Available at: https://doi.org/10.1016/j.sbspro.2013.10.606
Kierzkowski, A., & Haładyn, S. 2022. Method for Reconfiguring Train Schedules Taking into Account the Global Reduction of Railway Energy Consumption. Energies, 15(5), 1946. Available at: https://doi.org/10.3390/en15051946
Li, X., & Lo, H. K. (2017). An energy-efficient scheduling and speed control approach for metro rail operations. Transportation Research Part B: Methodological, 64, 73-89. Available at: https://doi.org/10.1016/j.trb.2014.03.006
Yang, X., Li, X., Ning, B., & Tang, T. 2018. An optimization method for train scheduling with minimum energy consumption and travel time in metro rail systems. Transportmetrica B: Transport Dynamics, 3(2), 79-98. Available at: https://doi.org/10.1080/21680566.2015.1007577
Yang, X., Chen, A., Ning, B., & Tang, T. 2019. A stochastic model for the integrated optimization of metro timetable and speed profile with uncertain train mass. Transportation Research Part B: Methodological, 91, 424-445. Available at: https://doi.org/10.1016/j.trb.2016.06.006
Johnson, D. S., Lenstra, J. K., & Kan, A. R. 2008. The complexity of the network design problem. Networks, 8(4), 279-285. Available at: https://doi.org/10.1002/net.3230080402
Goverde, R. M. 2010. Railway timetable stability analysis using max-plus system theory. Transportation Research Part B: Methodological, 41(2), 179-201. Available at: https://doi.org/10.1016/j.trb.2006.02.003
Salido, M. A., Barber, F., & Ingolotti, L. 2015. Robustness for a single railway line: Analytical and simulation methods. Expert Systems with Applications, 39(18), 13305-13327.
CHANG, C. & THIA, B. 2006. Online rescheduling of mass rapid transit systems: fuzzy expert system approach. IEE Proceedings-Electric Power Applications, 143, 307-316.
Han, Y., Guan, X., & Shi, L. 2014. Optimization-based method for supply location selection and routing in large-scale emergency material delivery. IEEE Transactions on Automation Science and Engineering, 8(4), 683-693. Available at: https://doi.org/10.1109/TASE.2011.2159838
Corman, F., D’Ariano, A., Pacciarelli, D., & Pranzo, M. 2020. A tabu search algorithm for rerouting trains during rail operations. Transportation Research Part B: Methodological, 44(1), 175-192. Available at: https://doi.org/10.1016/j.trb.2009.05.004
Caprara, A., Galli, L., Kroon, L., Maróti, G., & Toth, P. 2019. Robust train routing and online re-scheduling. In the 10th Workshop on algorithmic approaches for transportation modeling, optimization, and systems (ATMOS'10). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Available at: https://drops.dagstuhl.de/opus/volltexte/2010/2747/pdf/3.pdf
Cadarso, L., & Marín, Á. 2017. Improving the robustness of rolling stock circulations in rapid transit networks. Computers & Operations Research, 51, 146-159. Available at: https://doi.org/10.1016/j.cor.2014.05.007
Brännlund, U., Lindberg, P. O., Nou, A., & Nilsson, J. E. 2001. Railway timetabling using Lagrangian relaxation. Transportation Science, 32(4), 358-369. Available at: https://doi.org/10.1287/trsc.32.4.358
Alfieri, A., Groot, R., Kroon, L., & Schrijver, A. 2016. Efficient circulation of railway rolling stock. Transportation Science, 40(3), 378-391. Available at: https://doi.org/10.1287/trsc.1060.0155
ALBRECHT, T. 2016. Automated timetable design for demand-oriented service on suburban railways. Public Transport, 1, 5-20. Available at: https://doi.org/10.1007/s12469-008-0003-4
Alberto Caprara, Paolo Toth, Daniele Vigo, and Matteo Fischetti. 2011. Modeling and solving the crew rostering problem. Operations research, 46(6):820–830. Available at: https://doi.org/10.1287/opre.46.6.820
Yue, Y., Wang, S., Zhou, L., Tong, L., & Saat, M. R. 2019. Optimizing train stopping patterns and schedules for high-speed passenger rail corridors. Transportation Research Part C: Emerging Technologies, 63, 126-146. Available at: https://doi.org/10.1016/j.trc.2015.12.007
Budai, G., Huisman, D., & Dekker, R. 2011. Scheduling preventive railway maintenance activities. Journal of the Operational Research Society, 57, 1035-1044. Available at: https://doi.org/10.1057/palgrave.jors.2602085
Luan, X., Wang, Y., De Schutter, B., Meng, L., Lodewijks, G., & Corman, F. 2020. Integration of real-time traffic management and train control for rail networks 1: Optimization problems and solution approaches. Transportation Research Part B: Methodological, 115, 41-71. Available at: https://doi.org/10.1016/j.trb.2020.09.004
Dewilde, T. 2017. Improving the robustness of a railway system in large and complex station areas. Available at: https://lirias.kuleuven.be/1749880?limo=0
Ehrgott, M., & Ryan, D. M. 2012. Constructing robust crew schedules with bicriteria optimization. Journal of multi‐criteria decision analysis, 11(3), 139-150. Available at: https://doi.org/10.1002/mcda.321
DAUZÈRE-PÉRÈS, S., DE ALMEIDA, D., GUYON, O. & BENHIZIA, F. 2018. A Lagrangian heuristic framework for a real-life integrated planning problem of railway transportation resources. Transportation Research Part B: Methodological, 74, 138-150. Available at: https://doi.org/10.1016/j.trb.2015.01.008
CORTÉS, C. E., SÁEZ, D., MILLA, F., NUNEZ, A. & RIQUELME, M. 2013. Hybrid predictive control for real-time optimization of public transport systems’ operations based on evolutionary multi-objective optimization. Transportation Research Part C: Emerging Technologies, 18, 757-769. Available at: https://doi.org/10.1016/j.trc.2009.05.016
CARRARESI, P., MALUCELLI, F. & PALLOTTINO, S. 2006. Regional mass transit assignment with resource constraints. Transportation Research Part B: Methodological, 30, 81-98. Available at: https://doi.org/10.1016/0191-2615 (95)00027-5
Bertsimas, D., & Sim, M. 2014. The price of robustness. Operations research, 52(1), 35-53. Available at: https://doi.org/10.1287/opre.1030.0065
Burggraeve, S., & Vansteenwegen, P. 2020. Robust routing and timetabling in complex railway stations. Transportation Research Part B: Methodological, 101, 228-244. Available at: https://doi.org/10.1016/j.trb.2017.04.007
Aharon Ben-Tal and Arkadi Nemirovski. 2005. Robust optimization– methodology and applications. Mathematical Programming, 92(3):453–480. Available at: https://doi.org/10.1007/s101070100286
CADARSO, L., MARÍN, Á. & MARÓTI, G. 2016. Recovery of disruptions in rapid transit networks. Transportation Research Part E: Logistics and Transportation Review, 53, 15-33. Available at: https://doi.org/10.1016/j.tre.2013.01.013
Birge, J. R., & Louveaux, F. 2014. Introduction to stochastic programming. Springer Science & Business Media. Available at: https://doi.org/10.1080/25726668.2019.1626169
ADENEY, W. 2004. Indicators-Lessons Learned from the CoMET and Nova Metro Railway Benchmarking Studies. ingilizce.
Abkowitz, M., & Tozzi, J. 2004. Transit route characteristics and headway-based reliability control. Transportation Research Record, 1078, 11-16. Available at: https://onlinepubs.trb.org/Onlinepubs/trr/1986/1078/1078-002.pdf
Yan, S., Lin, J. R., & Lai, C. W. 2013. The planning and real-time adjustment of courier routing and scheduling under stochastic travel times and demands. Transportation Research Part E: Logistics and Transportation Review, 53, 34-48. Available at: https://doi.org/10.1016/j.tre.2013.01.011
Xu, X. Y., Liu, J., Li, H. Y., & Jiang, M. 2019. Capacity-oriented passenger flow control under uncertain demand: Algorithm development and real-world case study. Transportation Research Part E: Logistics and Transportation Review, 87, 130-148. Available at: https://doi.org/10.1016/j.tre.2016.01.004
Xiong, J., He, Z., Guan, W., & Ran, B. 2018. Optimal timetable development for community shuttle network with metro stations. Transportation Research Part C: Emerging Technologies, 60, 540-565. Available at: https://doi.org/10.1016/j.trc.2015.10.007
Wang, Y., De Schutter, B., Van den Boom, T., Ning, B., & Tang, T. 2017. Origin-destination dependent train scheduling problem with stop-skipping for urban rail transit systems. In Proceedings of the 93rd Annual Meeting of the Transportation Research Board (Vol. 19, pp. 1-16). Available at: http://www.dcsc.tudelft.nl/~bdeschutter/pub/rep/14_004.pdf
Van Aken, S., Bešinović, N., & Goverde, R. M. 2020. Designing alternative railway timetables under infrastructure maintenance possessions. Transportation Research Part B: Methodological, 98, 224-238. Available at: https://doi.org/10.1016/j.trb.2016.12.019
Ulusoy, Y. Y., Chien, S. I. J., & Wei, C. H. 2013. Optimal all-stop, short-turn, and express transit services under heterogeneous demand. Transportation Research Record, 2197(1), 8-18. Available at: https://doi.org/10.3141/2197-02
Tirachini, A., Cortés, C. E., & Jara-Díaz, S. R. 2014. Optimal design and benefits of a short turning strategy for a bus corridor. Transportation, 38, 169-189. Available at: https://doi.org/10.1007/s11116-010-9287-8
Lidén, T., & Joborn, M. 2020. An optimization model for integrated planning of railway traffic and network maintenance. Transportation Research Part C: Emerging Technologies, 74, 327-347. Available at: https://doi.org/10.1016/j.trc.2016.11.016
Kang, L., Zhu, X., Wu, J., Sun, H., Siriya, S., & Kanokvate, T. 2018. Departure time optimization of last trains in subway networks: mean-variance model and GSA algorithm. Journal of Computing in Civil Engineering, 29(6), 04014081. Available at: https://doi.org/10.1061/(ASCE)CP.1943-5487.0000407
Tamannaei, M., Saffarzadeh, M., Jamili, A., & Seyedabrishami, S. 2019. A double-track train rescheduling for incident conditions: optimization model and decomposition method. International Journal of Operational Research, 26(1), 62-87. Available at: https://doi.org/10.1504/IJOR.2016.075650
Puong, A., & Wilson, N. H. 2011. A train holding model for urban rail transit systems. In Computer-aided systems in public transport (pp. 319-337). Berlin, Heidelberg: Springer Berlin Heidelberg. Available at: https://doi.org/10.1007/978-3-540-73312-6_16
Nachtigall, K., & Voget, S. 2006. A genetic algorithm approach to periodic railway synchronization. Computers & Operations Research, 23(5), 453-463. Available at: https://doi.org/10.1016/0305-0548 (95)00032-1
Schmöcker, J. D., Cooper, S., & Adeney, W. 2015. Metro service delay recovery: comparison of strategies and constraints across systems. Transportation research record, 1930(1), 30-37. Available at: https://doi.org/10.1177/0361198105193000104
Parbo, J., Nielsen, O. A., & Prato, C. G. 2019. Passenger perspectives in railway timetabling: a literature review. Transport Reviews, 36(4), 500-526. Available at: https://doi.org/10.1080/01441647.2015.1113574
Mao, K., Pan, Q. K., Pang, X., & Chai, T. 2017. An effective Lagrangian relaxation approach for rescheduling a steelmaking-continuous casting process. Control Engineering Practice, 30, 67-77. Available at: https://doi.org/10.1016/j.conengprac.2014.06.003
Larsen, R., Pranzo, M., D’Ariano, A., Corman, F., & Pacciarelli, D. 2017. Susceptibility of optimal train schedules to stochastic disturbances of process times. Flexible Services and Manufacturing Journal, 26, 466-489. Available at: https://doi.org/10.1007/s10696-013-9172-9
Kang, L., Wu, J., Sun, H., Zhu, X., & Wang, B. 2018. A practical model for last train rescheduling with train delay in urban railway transit networks. Omega, 50, 29-42. Available at: https://doi.org/10.1016/j.omega.2014.07.005
Jamili, A., & Aghaee, M. P. 2018. Robust stop-skipping patterns in urban railway operations under traffic alteration situation. Transportation Research Part C: Emerging Technologies, 61, 63-74. Available at: https://doi.org/10.1016/j.trc.2015.09.013
Ghaemi, N., Goverde, R. M., & Cats, O. 2019. Railway disruption timetable: Short-turnings in case of complete blockage. In 2019 IEEE International Conference on Intelligent Rail Transportation (ICIRT) (pp. 210-218). IEEE. Available at: DOI: 10.1109/ICIRT.2019.7588734
Fischetti, M., & Monaci, M. 2012. Light robustness. Robust and online large-scale optimization: Models and techniques for transportation systems, 61-84.
Eberlein, X. J., Wilson, N. H., & Bernstein, D. 2009. Modeling real-time control strategies in public transit operations. In Computer-Aided Transit Scheduling: Proceedings, Cambridge, MA, USA, August 2009 (pp. 325-346). Springer Berlin Heidelberg. Available at: https://link.springer.com/chapter/10.1007/978-3-642-85970-0_16
D'ARIANO, A., CORMAN, F., PACCIARELLI, D. & PRANZO, M. 2012. Reordering and local rerouting strategies to manage train traffic in real-time. Transportation Science, 42, 405-419. Available at: https://doi.org/10.1287/trsc.1080.0247
Cacchiani, V., Caprara, A., & Fischetti, M. 2015. A Lagrangian heuristic for robustness, with an application to train timetabling. Transportation Science, 46(1), 124-133. Available at: https://doi.org/10.1287/trsc.1110.0378
Barrena, E., Canca, D., Coelho, L. C., & Laporte, G. 2017. Exact formulations and algorithm for the train timetabling problem with dynamic demand. Computers & Operations Research, 44, 66-74. Available at: https://doi.org/10.1016/j.cor.2013.11.003
Abbink, E., Van den Berg, B., Kroon, L., & Salomon, M. 2014. Allocation of railway rolling stock for passenger trains. Transportation Science, 38(1), 33-41. Available at: https://doi.org/10.1287/trsc.1030.0044
De-Los-Santos, A., Laporte, G., Mesa, J. A., & Perea, F. 2015. Evaluating passenger robustness in a rail transit network. Transportation Research Part C: Emerging Technologies, 20(1), 34-46. Available at: https://doi.org/10.1016/j.trc.2010.09.002
Zhao, X., Sun, Q., Zhu, Y., Ding, Y., Ma, C., & Chen, Z. 2019. Multi-routing planning design of Y-type urban rail transit. Advances in Mechanical Engineering, 8(8), 1687814016667385. Available at: https://doi.org/10.1177/1687814016667385
ADENEY, W. 2004. Indicators-Lessons Learned from the CoMET and Nova Metro Railway Benchmarking Studies. Ingilizce.
Yue, Y., Wang, S., Zhou, L., Tong, L., & Saat, M. R. 2019. Optimizing train stopping patterns and schedules for high-speed passenger rail corridors. Transportation Research Part C: Emerging Technologies, 63, 126-146. Available at: https://www.sciencedirect.com/science/article/pii/S0968090X15004234