طراحی مدلی پایدار برای مساله زمان‌بندی قطارهای متروی تهران با رویکرد بهینه‌سازی استوار

نوع مقاله : مقاله پژوهشی

نویسندگان

دانشکده مهندسی صنایع، دانشگاه آزاد اسلامی، واحد پرند، تهران، ایران.

چکیده

در این تحقیق، هدف ارائه یک الگوی بهینه‌ برای مساله زمان‌بندی سیر و حرکت قطارهای حمل‌ونقل ریلی درون شهری در مطالعه موردی متروی تهران است، لذا کوشیده شده است یک رهیافت جدید بر مبنای اصول و مفاهیم استواری برای حل مساله جداول زمان‌بندی قطارهای متروی تهران در شرایط عدم قطعیت و بروز اعوجاج با استفاده از رهیافت‌های شبیه‌سازی از طریق لحاظ نمودن زمان‌های بافر و حداقل سرفاصله زمانی حرکت قطارها ارائه گردد. بنابراین به دست آوردن سرفاصله‌های بهینه از طریق استقرار زمان‌های بافر در جداول زمان‌بندی خطوط متروی تهران در رویکرد برنامه‌ریزی خطی طوری دنبال گردیده که بتوان میانگین مدت زمان انتظار در سکوهای مسافری و سرفاصله زمانی قطارها را در مسیر ریلی حداقل نموده و نرخ تردد قطارها در خطوط ریلی را حداکثر کرد. در تحقیق حاضر با استفاده از مدل عمومی برنامه‌ریزی خطی پس از تعیین تابع هدف و محدودیت‌های مرتبط از قبیل زمان‌های توقف قطارها در ایستگاه‌ها (گره‌ها) و طول مسیر (یال‌ها)، ظرفیت ایستگاه‌های مترو و رعایت حاشیه‌های ایمنی با توجه به شرایط کلی شبکه ریلی، از طریق لحاظ کردن زمان بافر و رویکردهای شبیه‌سازی در مورد کاوی ایستگاه متروی شاهد کوشیده نقاط بهینه شناسایی و در طراحی تابلوی نهایی زمان‌بندی مورد استفاده قرار گیرد. در این تحقیق همچنین فرض بر آن بود که متغیرهای مدل تصمیم‌گیری نظیر نرخ ورود مسافری به ایستگاه‌ها و زمان طی قطعات توسط ناوگان قطارها غیرقطعی باشد. در پایان نیز اعتبار مدل پیشنهادی از طریق داده‌های به دست آمده از نیمه جنوبی خط یک متروی تهران مورد ارزیابی قرار گرفته و نتایج به دست آمده از آن ارائه شده است.

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

Designing a stable model for the Tehran subway train scheduling problem with a robust optimization approach

نویسندگان [English]

  • Davood Jafari
  • Mehran Khalaj
  • Pejman Salehi
Faculty of Industrial Engineering, Islamic Azad University, Parand Branch, Tehran, Iran.
چکیده [English]

This study aims to present a robust optimization model for scheduling intra-city rail transport trains (metro) in Tehran. We present a new approach based on robust principles and concepts to tackle the challenge of timetable planning for Tehran's subway trains under uncertainty and disturbances. To this end, a simulation method is employed, considering buffer times and minimum train movement intervals. Therefore, this paper follows a linear programming framework to determine the optimal headway distances for Tehran's subway lines, with the goal of minimizing average waiting times at station platforms and enhancing train flow according to passenger demand. Using a general linear programming model, after defining the objective function and constraints—such as train stopping times at stations (nodes), route lengths (edges), station capacities, and safety margins in line with the overall rail network conditions—optimal points are identified through buffer times and simulation approaches, exemplified at Shahed station, and incorporated into the final timetable design. Additionally, this work assumes that parameters related to capacity and timing of train units are non-deterministic. At the end, the validity of the proposed model is evaluated using data from the southern part of line one of Tehran's subway, and the results are presented.

کلیدواژه‌ها [English]

  • Robust optimization
  • Timetabling problem
  • Trains
  • Tehran metro
[1] L. Zhang, P. Hou, and D. Qiang, “Transit-Oriented Development in New Towns: Identifying Its Association with Urban Function in Shanghai, China,” Buildings, vol. 12, no. 9, p. 1394, 2022, doi: 10.3390/buildings12091394.
[2] G. Caimi, L.G. Kroon, and C. Liebchen, “Models for railway timetable optimization: Applicability and applications in practice,” J. Rail Transp. Plan. Manag., vol. 6, no. 4, pp. 285-312, 2017, doi: 10.1016/j.jrtpm.2016.11.002.
[3] M. Tamnai, “Rescheduling of train movement in two-track rail routes,” PhD thesis, Faculty of Civil and Environmental Engineering, Tarbiat Modares University, 2013 [In Persian].
[4] T. Albrecht, “Automated timetable design for demand-oriented service on suburban railways,” Public Transp., vol. 1, no. 1, pp. 5-20, 2009, doi: 10.1007/s12469-008-0003-4.
[5] P.-A. Andersson and G.-P. Scalia-Tomba, “A mathematical model of an urban bus route,” Transp. Res. Part B: Methodol., vol. 15, no. 4, pp. 249-266, 1981, doi: 10.1016/0191-2615(81)90011-4.
[6] S. Zhan, S.C. Wong, Q. Peng, and S.M. Lo, “Passenger-oriented Railway Timetable Rescheduling in a Complete Blockage,” in 14th Int. Conf. Adv. Syst. Public Transp. (CASPT), Brisbane Convention Centre, Brisbane, Australia, 2018, pp. 1-20.
[7] N. Ahmadi Asl, R. Effatnejad, M. Hedayati, and P. Hajihosseini, “Introducing a new scheme for demand response of a smart residential community with a variety of demand response models,” Karafan J., vol. 20, no. 3, pp. 311-339, 2023, doi: 10.48301/KSSA.2021.287832.1547 [In Persian].
[8] M. Goerigk and A. Schobel, Algorithm engineering in robust optimization, in Algorithm Enginerring, pp. 245-279, 2016,  doi: 10.1007/978-3-319-49487-6_8.
[9] M.R. Amin-Naseri and V. Baradaran, “Accurate Estimation of Average Waiting Time in Public Transportation Systems,” Transp. Sci., vol. 49, no. 2, pp. 213-222, 2015, doi: 10.1287/trsc.2013.0514.
[10] Y. Yue, S. Wang, L. Zhou, L. Tong, and M.R. Saat, “Optimizing train stopping patterns and schedules for high-speed passenger rail corridors,” Transp. Res. Part C: Emerg. Technol., vol 63, pp. 126-146, 2016, doi: 10.1016/j.trc.2018.12.007.
[11] H. Gong, X. Chen, L. Yu, and L. Wu, “An application-oriented model of passenger waiting time based on bus departure time intervals,” Transp. Plan. Technol., vol. 39, no. 4, pp. 424-37, 2016, doi: 10.1080/03081060.2016.1160583.
[12] G. Laporte, J.A. Mesa, and F. Perea, “A game theoretic framework for the robust railway transit network design problem,” Transp. Res. Part B Methodol., vol. 44, no. 4, pp. 447-459, 2010, doi: 10.1016/j.trb.2009.08.004.
[13] M.S. Visentini, D. Borenstein, L.Q. Li, and P.B. Mirchandani, “Review of real-time vehicle schedule recovery methods in transportation services,” J. Sched., vol. 17, no. 6, pp. 541-567, 2014, doi: 10.1007/s10951-013-0339-8.
[14] N. Ghaemi, R.M. Goverde, and O. Cats, “Railway disruption timetable: Short-turnings in case of complete blockage,” in IEEE Int. Conf. Intell. Rail Transp. (ICIRT), Birmingham, UK, 2016, pp. 210-218, doi: 10.1109/ICIRT.2016.7588734.
[15] S. Shen and N.H. Wilson, “An Optimal Integrated Real-time Disruption Control Model for Rail Transit Systems,” In Computer-Aided Scheduling of Public Transport. Lecture Notes in Economics and Mathematical Systems, vol 505, Springer, Berlin, Heidelberg, doi: 10.1007/978-3-642-56423-9_19.
[16] J.D. Schmocker, S. Cooper, and W. Adeney, “Metro service delay recovery: comparison of strategies and constraints across systems,” Transp. Res. Record J., vol. 1930, no. 1, pp. 30-37, 2005, doi: 10.3141/1930-04.
[17] J. Brimberg, E. Korach, M. Eben‐Chaim, and A. Mehrez, “The Capacitated p‐facility Location Problem on the Real Line,” Int. Trans. Oper. Res., vol. 8, no. 6, pp. 727-738, 2002, doi: 10.1111/1475-3995.t01-1-00334.
[18] N. Askari and M.H. Taheri, “Numerical Investigation of a MHD Natural Convection Heat Transfer Flow in a Square Enclosure with Two Heaters on the Bottom Wall,” Karafan J., vol. 17, no. 1, pp. 97-114, 2020, doi: 10.48301/kssa.2020.112759.
[19] K. Yang, Y. Lu, L. Yang, and Z. Gao, “Distributionally robust last-train coordination planning problem with dwell time adjustment strategy,” Appl. Math. Model., vol. 91, pp. 1154-1174, 2021, doi: 10.1016/j.apm.2020.10.035.
[20] A. D’Ariano, F. Corman, D. Pacciarelli, and M. Pranzo, “Reordering and local rerouting strategies to manage train traffic in real time,” Transp. Sci., vol. 42, no. 4, pp. 405-419, 2008, doi: 10.1287/trsc.1080.0247.
[21] F. Corman, A. D’Ariano, D. Pacciarelli, and M. Pranzo, “Dispatching and coordination in multi-area railway traffic management,” Comput. Oper. Res., vol. 44, pp. 146-160, 2014, doi: 10.1016/j.cor.2013.11.011.
[22] X.J. Eberlein, N.H.M. Wilson, and D. Bernstein, “Modeling Real-Time Control Strategies In Public Transit Operations,” in Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, vol 471, Springer, Berlin, Heidelberg, 1999, doi: 10.1007/978-3-642-85970-0_16.
[23] M. Clerc and J. Kennedy, “The particle swarm-explosion, stability, and convergence in a multidimensional complex space,” IEEE Trans. Evol. Comput., vol. 6, no. 1, pp. 58-73, 2002, doi: 10.1109/4235.985692.
[24] B. De Schutter, T. van den Boom, and A. Hegyi, “Model predictive control approach for recovery from delays in railway systems,” Transp. Res. Record, vol. 1793, no. 1, pp. 15-20, 2002, doi: 10.3141/1793-03.
[25] M. Hasanzadeh and R. Bashizade, “Optimizing University Course Timetable Using Local Search Methods,” Soft Comput. J., vol. 1, no. 1, pp. 24-31, 2012, dor: 20.1001.1.23223707.1391.1.1.111.8 [In Persian].
[26] P.D. Site and F. Filippi, “Service optimization for bus corridors with short-turn strategies and variable vehicle size,” Transp. Res. Part A Policy Practice, vol. 32, no. 1, pp. 19-38, 1998, doi: 10.1016/S0965-8564(97)00016-5.
[27] N. Daneshpour, “Optimizing Process of Data Extraction, Transformation and Load in Data Warehouse Based on Parallel Processing,” Soft Comput. J., vol. 4, no. 2, pp.18-31, 2016, dor: 20.1001.1.23223707.1394.4.2.55.5 [In Persian].
[28] X. Luo, T. Tang, J. Yin, and H. Liu, “A robust mpc approach with controller tuning for close following operation of virtually coupled train set,” Transp. Res. Part C Emerg. Technol., vol. 151, p. 104116, 2023, doi: 10.1016/j.trc.2023.104116.
[29] X. Luo, Y. Jiang, Z. Yao, Y. Tang, and Y. Liu, “Designing Limited-Stop Transit Service with Fixed Fleet Size in Peak Hours by Exploiting Transit Data,” Transp. Res. Record, vol. 2647, no. 1, pp. 134-141, 2017, doi: 10.3141/2647-16.
[30] D. Potthoff, D. Huisman, and G. Desaulniers, “Column generation with dynamic duty selection for railway crew rescheduling,” Transp. Sci., vol. 44, no. 4, pp. 493-505, 2010, doi: 10.1287/trsc.1100.0322.
[31] Y. Lu, L. Yang, H. Yang, H. Zhou, and Z. Gao, “Robust collaborative passenger flow control on a congested metro line: A joint optimization with train timetabling,” Transp. Res. Part B Methodol., vol. 168, pp. 27-55, 2023, doi: 10.1016/j.trb.2022.12.008.
[32] A. Brochard, W. Pasillas-Lepine, and B. Demaya, “Cascaded Train Speed Regulation: Robustness to Feedback Delay and Measurement Filtering,” IFAC-PapersOnLine, vol. 55, no. 34, pp. 126-131, 2022, doi: 10.1016/j.ifacol.2022.11.319.
[33] Y. Wang, J. Chen, Y. Qin, and X. Yang, “Timetable rescheduling of metro network during the last train period,” Tunn. Underground Space Technol., vol. 139, p. 105226, 2023, doi: 10.1016/j.tust.2023.105226.
[34] V. Cacchiani, J. Qi, and L. Yang, “Robust optimization models for integrated train stop planning and timetabling with passenger demand uncertainty,” Transp. Res. Part B Methodol., vol. 136, pp. 1-29, 2020, doi: 10.1016/j.trb.2020.03.009.
[35] C.E. Cortes, D. Saez, F. Milla, A. Nunez, and M. Riquelme, “Hybrid predictive control for real-time optimization of public transport systems’ operations based on evolutionary multi-objective optimization,” Transp. Res. Part C Emerg. Technol., vol. 18, no. 5, pp. 757-769, 2010, doi: 10.1016/j.trc.2009.05.016.
[36] Y. Wang, B. De Schutter, T.J.J. van den Boom, B. Ning, and T. Tang, “Efficient bilevel approach for urban rail transit operation with stop-skipping,” IEEE Trans. Intell. Transp. Syst., vol. 15, no. 6, pp. 2658-2670, 2014,  doi: 10.1109/TITS.2014.2323116.
[37] R.A. Chapman, H.E. Gault, and L.A. Jenkins, Factors affecting the operation of urban bus routes, Newcastle-Upon-Tyne University, England, 1981, issn: 0306-3402. 
[38] A. Caprara, M. Monaci, P. Toth, and P.L. Guida, “A Lagrangian heuristic algorithm for a real-world train timetabling problem,” Discret. Appl. Math. Vol. 154, no. 5, pp. 738-753, 2006, doi: 10.1016/j.dam.2005.05.026.
[39] Z. Cao, Z. Yuan, and D. Li, “Estimation method for a skip-stop operation strategy for urban rail transit in China,” J. Mod. Transp., vol. 22, pp. 174-182, 2014, doi: 10.1007/s40534-014-0059-6.
[40] D. Canca, E. Barrena, E. Algaba, and A. Zarzo, “Design and analysis of demand‐adapted railway timetables,” J. Adv. Transp., vol. 48, no. 2, pp. 119-137, 2014, doi: 10.1002/atr.126.
[41] L. Cadarso, A. Marin, and G. Maroti, “Recovery of disruptions in rapid transit networks,” Transp. Res. Part E Logist. Transp. Rev., vol. 53, pp. 15-33, 2013, doi: 10.1016/j.tre.2013.01.013.
[42] E. Barrena, D. Canca, L.C. Coelho, and G. Laporte, “Exact formulations and algorithm for the train timetabling problem with dynamic demand,” Comput. Oper. Res., vol. 44, pp. 66-74, 2014, doi: 10.1016/j.cor.2013.11.003.
[43] R.L. Burdett and E. Kozan, “A disjunctive graph model and framework for constructing new train schedules,” Eur. J. Oper. Res., vol. 200, no. 1, pp. 85-98, 2010, doi: 10.1016/j.ejor.2008.12.005.
[44] G. Maroti, “A branch-and-bound approach for robust railway timetabling,” Public Transp., vol. 9, no. 1-2, pp. 73-94, 2017, doi: 10.1007/s12469-016-0143-x.
[45] M. Mohammadpour, B. Minaei, and H. Parvin, “Introducing a new meta-heuristic algorithm based on See-See Partridge Chicks Optimization to solve dynamic optimization problems,” Soft Comput. J., vol. 8, no. 2, pp. 38-65, 2020, doi: 10.22052/8.2.38 [In Persian].