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

Document Type : Scientific - Research

Abstract

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.

Keywords


-جمیلی،  امین و کیانفر،  فریدون (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.