زمان‏بندی حرکت قطارها با استفاده از الگوریتم شاخه و حد و الگوریتم ابتکاری جستجوی پرتو- مطالعه موردی: مسیرهای دوخطه ریلی ایران

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

چکیده

هدف از این پژوهش، ارایه روشهای دقیق و تقریبی جهت حل مسئله زمان‏بندی حرکت قطارها در مسیرهای دوخطه ریلی است. به منظور حل دقیق و یافتن جواب بهینه مسئله زمان‏بندی حرکت قطارها، از بسته نرم‏افزاری CPLEX11 و نیز الگوریتم شاخه وحد زمان‏بندی حرکت قطارها استفاده می‏شود. مدل ریاضی زمان‏بندی حرکت قطارها در مسیر دوخطه و نیز الگوریتم شاخه و حد پیشنهادی در نرم‏افزار جاوا پیاده‏سازی شدند و مسائلی با ابعاد مختلف در مسیرهای ریلی بافق-سیرجان و تهران-مشهد مورد آزمایش قرار گرفتند. مقایسه نتایج حاصل، نشان از برتری عملکرد الگوریتم شاخه و حد پیشنهادی نسبت به CPLEX بویژه در مواجهه با مسائل زمان‏بندی با ابعاد بزرگ دارد. نتایج نشان می‏دهند که CPLEX ، مسائل بزرگ را در زمانهای بسیار طولانی حل می‏کند؛ در حالی که الگوریتم شاخه و حد می تواند جواب بهینه این‏گونه مسائل را در زمانهایی منطقی و بسیار کمتر از زمان حل CPLEX به دست آورد. همچنین در این پژوهش، از پنج روش تقریبی حل مبتنی بر الگوریتم جستجوی پرتو استفاده شد. نتایج بررسی روشهای تقریبی برای مسائل با ابعاد مختلف در مسیر تهران-مشهد حاکی از عملکرد مناسب‏تر روشهای ابداع‏شده پژوهش حاضر، در مقایسه با روشهای قبلی، به ویژه در مواجهه با مسائل با ابعاد بزرگ است؛ به طوری که بسته به میزان اهمیت پارامتر دقت و سرعت در شرایط مختلف، روشهای جستجوی پرتو جدید می توانند جداول زمان‏بندی نزدیک به بهینه را در زمانهای منطقی و با اشغال کنترل‏شده فضای حافظه ارایه کنند. با استفاده از نتایج این پژوهش، امکان تهیه جداول زمانی حرکت قطارها در زمانهای مناسب برای مسیرهای دوخطه به ویژه مسیرهای طولانی با تعداد زیاد قطار فراهم می‏شود.

کلیدواژه‌ها


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

Train Timetabling Problem: Branch and Bound Algorithm and Heuristic Beam Search Algorithms, Case Study: Double Track Railways in Iran

چکیده [English]

The aim of this study is to develop the algorithms for solving train timetabling problems in the double-track railways. To find the optimal solution of the problems, the common software package CPLEX 11 was used in addition to a method based on branch and bound algorithm. Both the mathematical model and branch and bound algorithm were implemented in Java Software and some large-scale real problems were investigated. The problems are based on Bafgh-Sirjan and Tehran-Mashhad railways. Comparison of results show more efficient performance of the algorithm rather than CPLEX. The criterion to compare the performances was the solving time. Five methods were then used based on beam search algorithm to find near-optimal solutions in a rational amount of time. Three of these methods are considered as the innovations of the present research. The results of applying beam search methods demonstrate more impressive proficiency of the heuristic methods innovated compared to methods suggested in previous works especially when facing large-scale problems. Depending on the importance of accuracy and time in different conditions, the excogitated methods can generate the train timetable schedules. By using the results of the research, it is possible to prepare the optimal and near-optimal time-tables especially for the long railways with the large amount of trains.

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

  • train time tabling
  • Heuristic methods
  • Branch and bound
  • beam search algorithm
  • optimal solution
-جمیلی،  امین و کیانفر،  فریدون (1388) "زمان‏بندی حرکت قطارها به کمک روش فوق ابتکاری عملیات حرارتی شبیه سازی شده"، پژوهشنامه حمل و نقل، سال ششم، شماره اول.

-خادم ثامنی، ملودی (1386) "زمان‏بندی حرکت قطارها در مسیرهای دوخطه"، رساله کارشناسی ارشد، دانشکده مهندسی صنایع، دانشگاه تربیت مدرس، تهران.

-شفاهی، یوسف و صادقی، نازنین (1383) «کاربرد یک مدل شبیه سازی برای تعیین اثر سیاستهای عملیاتی مختلف بر روی قابلیت اطمینان برنامه زمان‏بندی حرکت قطارها»، اولین کنگره ملی مهندسی عمران، دانشگاه شریف.

-یقینی، مسعود و انجمن علمی دانشکده مهندسی راه آهن (1389) "زمان‏بندی و سیر و حرکت در راه آهن"،  ترجمه مسعود یقینی، تهران، انتشارات پیشرو فنآوری قائد.

-یقینی، مسعود و محمدزاده، علی (1390) "یک مدل زمان‏بندی حرکت قطارها با در نظر گرفتن زمانهای توقف برای نماز"، نشریه تخصصی مهندسی صنایع، دوره 45، شماره 1، فروردین ماه 1390، از صفحه 103 تا 116.

-یقینی، مسعود و لسان، جواد (1389) " برنامه ریزی عملیات حمل و نقل ریلی"، ایران: انتشارات دانشگاه علم و صنعت ایران.

- Burdett, R. L. and Kozan, E. (2010) “A disjunctive graph model and framework for constructing new train schedules”, European Journal of Operational Research, Vol. 200, pp.85-98.

- Cacchiani, V., Caprara, A. and Toth, P. (2008) “A column generation approach to train timetabling on a corridor,” 4OR, vol. 6, no. 2, pp. 125–142.

- Caprara, A., Monaci, M., Toth, P. and Guida, P. L. (2006) “A Lagrangian heuristic algorithm for a real-world train timetabling problem,” Discrete Appl. Math., vol. 154, no. 5, pp. 738–753.

- Corman, F., D’Ariano, A., Pacciarelli, D. and Pranzo, M. (2009) “A tabu search algorithm for rerouting trains during rail operations”, Transportation Research Part B, 44 (1), pp.175–192.

-D’Ariano, A., Pacciarelli, D. and Pranzo, M. (2007) “A branch and bound algorithm for scheduling trains in a railway network”, European Journal of Operational Research, 183 (2), 643–657.

-Ghoseiri, K.; Szidarovszky, F. and Asgharpour, M. J. (2004) “A multi-objective train scheduling model and solution”, Transportation Research Part B, vol. 38, no. 10, pp. 927-952.

-Higgins, A., Kozan, E. and Ferreira, L. (1996) “Optimal scheduling of trains on a single line track”, Transportation Research Part B: Methodological, vol.30, PP. 147-161.

-Mu, Shi and Dessouky, Maged (2011) “Scheduling freight trains traveling on complex networks”, Transportation Research Part B 45, pp.1103–1123.

-Pinedo, M. (2002) “Scheduling theory, algorithms and systems”, Prentice Hall, Upper Saddle River, NJ.2002.

- Shafia, Mohammad Ali, Pourseyedaghaee, Mohsen, Sadjadi, Seyed Jafar and Jamili, Amin (2012) “Robust train timetabling problem: Mathematical model and branch and bound algorithm”, IEEE Transactions On Intelligent Transportation Systems, Vol. 13, No. 1.

-Szpigel, B. (1973) “Optimal train scheduling on a single track railway”, Operational Research 72, M. Ross (ed.), North-Holland, Amsterdam, pp. 343-352.

-Tornquist, J. and Persson, J. A. (2007) “N-tracked railway traffic re-scheduling during disturbances”, Transportation Research Part B, Volume 41, Issue 3, pp. 342–362.

-Walker, C. G., Snowdon, J. N. and Ryan, D. M. (2005) “Simultaneous disturbance recovery of a train timetable and crew roster in real time,” Computers & Operations Research, Vol. 32(8), pp. 2077-2094.

-Zhou, X., Zhong, M. (2005) “Bi-criteria train scheduling for high-speed passenger railroad planning applications,” Eur. J. Oper. Res., Vol. 167, no. 3, pp. 752–771.

-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.