زمانبندی حرکت قطارهای مسافری با رویکرد بهینه‌سازی بر پایه شبیه‌سازی گسسته-پیشامد

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

نویسندگان

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

2 استادیار، پژوهشگاه علوم و فناوری اطلاعات ایران (ایرانداک)‌، تهران، ایران

3 دانشجوی دکتری برنامه ریزی شهری، دانشکده ارتباطات، معماری، هنر و فناوری اطلاعات، دانشگاه لوسوفونا، لیسبون - پرتغال

4 دانش آموخته کارشناسی ارشد، دانشکده مهندسی صنایع، دانشگاه آزاد قزوین، ایران

چکیده

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

کلیدواژه‌ها

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

A Discrete Event Simulation-Based Optimization Approach for Train Timetabling Problem

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

  • E. Hassannayebi 1
  • A. Sajedinejad 2
  • S. Mardani 3
  • S. R. Hosseini 4
1 Assistant Professor, Industrial Engineering Department, Islamic Azad University (Central Tehran Branch), Tehran, Iran
2 Assistant Professor, Iranian Research Institute for Information Science and Technology (IRANDOC), Tehran, Iran.
3 Ph.D. student of Urban Planning, School of Communication, Architecture, Arts and Information Technologies, Lusofona University, Lisboa - Portugal
4 M.Sc., Grad., Department of Industrial Engineering, Azad University, Iran
چکیده [English]

In this paper, a simulation-based optimization approach is proposed to solve train scheduling problem in single-line and double-track rail networks. In the proposed approach, the simulation model is used to generate feasible train timetable. The simulation model is designed in an object software environment called Enterprise Dynamics (ED). The input data of the problem includes the type of blocks, the order and location of the stations, the number of lines and platform inside the stations, the station facilities (dewatering, refueling, and prayer room), maintenance intervals and praying intervals. The decision variable is the departure time of trains from the origin and the objective of the problem is to minimize the total weighted non-planned stopping times of trains. To find a near-optimal timetable, a simulation-based optimization method based on the evolutionary path relinking algorithm is designed. To evaluate the efficiency of the proposed algorithm, the scheduling of passenger trains in the Tehran-Razi route has been performed. The results of the research show that the implementation of the proposed model has led to significant improvement in non-planned train stopping times as against to the current schedule of the Iranian railways. The proposed algorithm is also able to generate a train timetable in a reasonable time according to the intervals allowed for prayer.
 
 

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

  • Train scheduling
  • Simulation-based optimization
  • Object oriented model
  • evolutionary path re-linking

مراجع

-          جمیلی، الف. و کیانفر، ف. (1388)، "زمانبندی حرکت قطارها به کمک روش فوق ابتکاری عملیات حرارتی شبیه‌سازی شده". نشریه پژوهشنامه حمل ونقل، سال ششم، شماره یک، ص. 13-27.
 
-          جمیلی، الف. (1390)، "زمانبندی دوره­ای استوار در برابر اغتشاش حرکت قطارها و تعیین ظرفیت زیرساخت­های خطوط ریلی"، پایان نامه دکتری، دانشکده مهندسی صنایع، دانشگاه علم و صنعت.
 
-          حسن نایبی، ع. (1390)، "تعیین توالی اعزام و برنامه توقف قطارها در مسیرهای ریلی دوخطه به کمک الگوریتم­های جستجوی تصادفیِ تطابقیِ حریصانه و جستجوی همسایگی متغیر". پایان نامه کارشناسی ارشد، دانشکده مهندسی صنایع، دانشگاه صنعتی شریف، تهران.
 
 
-          خادم ثامنی، م. (1386)، "زمانبندی حرکت قطارها در مسیرهای دوخطه". پایان­نامه کارشناسی ارشد، دانشکده مهندسی صنایع، دانشگاه تربیت مدرس، تهران.
 
-          سپهری، م. م. و پورسید آقایی، م. (1378)، "برنامه­ریزی حرکت قطارها در خطوط یک خطه"، نشریه دانشکده فنی، جلد 33، شماره 2، ص. 87-97.
 
-          شفاهی، ی. و عابدینی، ای. (1383)، "زمانبندی حرکت قطارها با استفاده از یک روش ابتکاری جستجوی مبتنی بر منع­"، هفتمین همایش حمل و نقل ریلی، تهران، دانشگاه صنعتی شریف.
 
-          شفاهی، ی. و عزیزخانی، ع.ر. (1383)، "زمانبندی حرکت قطارها با روشی ابتکاری مبتنی بر الگوریتم ژنتیک­"، هفتمین همایش حمل و نقل ریلی، تهران، دانشگاه صنعتی شریف.
 
-          شفاهی، ی. و صادقی، ن. (1383)­،"یک مدل شبیه‌سازی برای زمانبندی حرکت قطارها با هدف افزایش قابلیت اطمینان برنامه زمانبندی­"، هفتمین همایش حمل و نقل ریلی، تهران، دانشگاه صنعتی شریف.
 
-          قاسم پور، ش. و رادفر، الف. (1388)، "شبیه‌سازی حرکت قطار با استفاده از شبکه­های پیشرفته­تری و مدلهای بهینه‌سازی"، دومین کنفرانس بین المللی پیشرفتهای اخیر در مهندسی راه آهن، تهران.
 
-          قصیری، ک. و مرشد سلوک، ف. (1384)، "ارایه یک مدل ابتکاری مبتنی بر سیستم اجتماع مورچه­ها برای حل مسئله زمانبندی حرکت قطارها"، پژوهشنامه حمل ونقل، سال دوم، شماره چهار، ص. 257 تا 270.
 
-          یقینی، م. و محمدزاده، ع. (1390)، "یک مدل زمانبندی حرکت قطارها با در نظر گرفتن زمانهای توقف برای نماز". نشریه تخصصی مهندسی صنایع، دوره 45 ، شماره 1­، ص. 103 تا 116.
 
-          یقینی، م. و نیکو، ن. (1390)، "ارایه مدل بهینه‌سازی برای تولید جدول زمانبندی فشرده حرکت قطارها و محاسبه ظرفیت برای راه آهن­های شهری و برون­شهری"­. یازدهمین کنفرانس بین المللی حمل ونقل و ترافیک.
 
-   Andrade, D.V. and Resende, M.G.C. (2007), "GRASP with evolutionary path re-linking", Proc. of Seventh Meta-heuristics International Conference (MIC).
 
 
 
-       Andradottir, S. (1998), "Simulation optimization, Handbooks of Simulation: Principles, Methodology, Advances, Applications, and Practice", chapter 9. John Wiley & Sons, New York.
 
-       Cacchiani, V. and Toth, P. (2012), " Nominal and robust train timetabling problems", European Journal of Operational Research 219,
pp.727–737.
 
-       Caprara, A., Fischetti, M. and Toth, P. (2002), "Modeling and solving the timetabling problem", Operations Research, Vol. 50, No. 5. pp. 851-861.
 
-       Castilloa, E., Gallegob, I., Ureñab, J.M. and Coronadob, J.M. (2011), "Timetabling optimization of a mixed double- and single-tracked railway network", Applied Mathematical Modeling, Vol. 35 (2),
pp. 859-878.
 
 
-       Cui, Y. (2010), "Simulation-Based Hybrid Model for a Partially-Automatic Dispatching of Railway Operation", Institut für Eisenbahn- und Verkehrswesen der Universität Stuttgart.
 
-       Cheng, Y. (1998), "Hybrid Simulation for Resolving Resource Conflicts in Train Traffic Rescheduling", Computers in Industry 35(3): pp.233–246.
 
-       Dessouky, M. M., and Leachman, R. (1995), "A Simulation Modeling Methodology for Analyzing Large Complex Rail Networks", Simulation 65(2): pp.131–142.
 
 
-       Fu, M. (2002), "Optimization for simulation: Theory vs. practice", INFORMS Journal on Computing, 14(3): pp.192–215.
 
-       Glover, F. (1999), "Scatter Search and Path Re-linking", New ideas in optimization, McGraw-Hill Ltd., UK Maidenhead, UK, England.
 
-      Gély, L., Feillée, D. and Dessagne, G. (2009),
"A cooperative framework between optimization and simulation to address on-line re-scheduling problems", SNCF - Innovation and Research Department.
-       Higgins, A. and Kozan, E. (1997), "Heuristic techniques for single line train scheduling", Journal of Heuristics, Vol. 3, pp. 43-62.
 
 
-      Hofman, M., Madsen, L. F., Groth, J. J., Clausen, J. and Larsen, J. (2006), "Robustness and recovery in train scheduling a simulation study from dsb s–tog a/s. In ATMOS Informatics and Mathematical Modelling, Technical University of Denmark, DTU, IMM–Technical Report.
 
-     Li, F., Gao, Z. Li, K. and Yang, L. (2008), "Efficient Scheduling of Railway Traffic Based on Global Information of Train", Transportation Research Part B 42: pp.1008–1030.
 
-       Marinov, M. and Viegas, J. A. (2010), "mesoscopic simulation modeling methodology for analyzing and evaluating freight train operations in a rail network", International journal of simulation modeling practice and theory.
 
-       Mills, G. and Pudney, P. (2003), "The Effects of Deadlock Avoidance on Rail Network Capacity and Performance", Proceedings of the Mathematics-in-Industry Study Group.
 
-       Middelkoop, D. and Bouwman, M. (2001), "Simone: Large scale train network simulations", In Proceeding of the 2001 Winter Simulation Conference, volume 2,
pp. 1042–1047.
 
-        Petersen, E. R. and Taylor, A. J. (1982), "A Structured Model for Rail Line Simulation and Optimization," Transportation Science, Vol. 16, pp. 192-206.
 
-       Petersen, E. R. and Taylor, A. J. (1983), "Line Block Prevention in Rail Line Dispatch", In: INFOR Journal 2, No. 1, pp. 46-51.
 
-       Resende, M. G. C., Martí, R., Gallego, M., Duarte, A. (2010), "GRASP and path re-linking for the max-min diversity problem", Computers & OR 37(3): pp.498-508.
 
-       Ribeiro, C. C. and Resende, M. G. C. (2012), "Path re-linking intensification methods for stochastic local search algorithms", Journal of Heuristics 18(2): pp.193-214.
 
-     Valkenaers, P.; Van Brussel, H. (2003), "Deadlock avoidance in flexible flow shops with loops", Journal of Intelligent
 
-     Welch, N. and Gussow, J. (1986), "Expansion of Canadian National Railway’s line capacity". Interfaces 16(1) pp.51–64.
 
 
-      Yalçinkaya, Ö, and Bayhan, G. M. (2012), "A feasible timetable generator simulation modeling framework for train scheduling problem", Simulation Modeling Practice and Theory 20(1), pp.124-141.
 
-      Zhou, X. and Zhong, M. (2007), "Single-track train timetabling with guaranteed optimality: Branch-and-bound algorithms with enhanced lower bounds", Transportation Research Part B, Vol. 41, pp. 320–341.
 
 

فایل ها

هم رسانی

ارجاع به این مقاله

آمار