A Greedy randomized adaptive search procedure for train sequencing and stop scheduling problem in double track railway lines

Optimizing the railway capacity is one of the most important goals in train scheduling phase. Optimizing the use of existing railway capacity is a more cost-effective solution than capital investment on upgrading railway infrastructure. The sequence of dispatching trains and stopping schedule are the main factors that can affect railway capacity on double track lines. In this thesis, a train sequencing and stop scheduling problem is studied in order to maximize the use of railway capacity. The main decision variables are the sequence of dispatches from origin station and the selection of the best station for scheduled stop 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. Also 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 railway. Because of the complexity of the problem, a greedy randomized adaptive search procedure (GRASP) is used for finding near optimal solution. Three meta-heuristic algorithms based on GRASP is developed and tested on randomly generated test problems. The output results show the effectiveness of the proposed meta-heuristic in solving the real sized problems.