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

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.