Train Platforming Problem Solving

Abstract

This dissertation addresses train platforming problem in busy complex stations at peak times which poses a great challenge for railway network controllers. The aim of the dissertation is to propose decision-making tool for an assignment plan of one-day timetable without conflicts. In this context, a special version of train platforming problem is described in detailed way. The characteristics of problem belongs to Prague main railway station. For the purpose of overcome the problem, two solution methods are applied: a mixed integer programming model and a matheuristic algorithm. The objective is to minimize total weighted delays in which weight is synonymous with importance level of each train. Train platforming problem can be solved easily for small railway stations with very few trains and platform tracks. By the help of mixed integer mathematical model that is called M1 in this context, it can be reached optimal solutions for these kind of railway stations. However, M1 model is not capable for large railway stations due to the Np-hard nature of problem. So, a matheuristic algorithm is presented and it consists of three stages: (i) platform track assignment algorithm, (ii) calculation of total weighted delay, (iii) improvement algorithm. In the proposed matheuristic, the algorithms and the sub-problem (M2) work cooperatively. Platform track assignment algorithm for allocation of track for each train. M2 model that is reduced version of M1 calculates all decision variables. Finally, improvement algorithm is enhancing the quality of solutions in each step. The mixed integer model and matheuristic algorithm have been implemented in GAMS/Cplex solver and validated using real-world data from Prague main railway station. One day timetable for a weekday in 2016/2017 year is divided into the time intervals. There are approximately 700 arriving and departing trains from/to the station for one day. In each interval, assignments of 36 trains are determined and allocation of the trains which are in intersection time for two consecutive intervals are transferred to next interval. Based on these rules, computational results are presented and solution of two methods are compared.