A Greedy Randomized Adaptive Search Procedure to Solve the Train Sequencing and Stop Scheduling Problem in Double Track Railway Lines

Optimizing the railway capacity is one of the most important goals in the train scheduling field, and literature shows that optimizing the use of the existing railway capacity is a more cost-effective solution than capital investment on upgrading or installing new railway infrastructure. The sequence of dispatching trains and stopping schedules are the main factors that can affect the railway capacity on double track lines, and in this thesis, a train sequencing and stop scheduling problem is studied in order to maximize the use of existing railway capacity. The main decision variables are the sequence of dispatches from the origin station and the selection of the best station for the scheduled stops in order to minimize the makespan. This research proposes a flexible flow shop scheduling formulation, which considers block section and station as single and parallel machines. In addition, an integer programming model is presented for solving the train sequencing problem in double track railway lines by considering the station infrastructure and stopping schedule policies in Iran’s railway systems. The problem is of very high complexity, and therefore a greedy randomized adaptive search procedure (GRASP) is used for finding the near optimal solution. Three meta-heuristic algorithms based on GRASP are developed and tested on randomly generated test problems, and the output results show the effectiveness of the proposed meta-heuristic algorithm in solving real-sized problems.