A headway and order scheme based mixed integer goal programming model for railway rescheduling / Zuraida Alwadood

Service disruptions in rail transport services often lead to trains cancelations and delays. The disruptions can create conflicts in the use of tracks and platforms and further propagate the disruptions throughout the railway system. The challenge in rescheduling trains is to quickly find the solution to the problem by synchronising resources to minimise the effect of the disruption. Railway rescheduling involves real-time alteration of train schedules in a railway network which is highly interconnected. Mathematical modeling for trains rescheduling has always been considered as a difficult and heavily constrained combinatorial optimisation problem that involves a large number of hard (operational) constraints and soft (desirability) constraints and the complexity of problem increases with the number of decision variables and constraints. Modelling and solving railway rescheduling problem is thus considered a highly complex task and categorised as an NP-hard class problem. This study is concerned with solving the railway rescheduling problem when disruption occurs on a track segment of the railway. Among the objectives of the study are to analyse the causes of railway disruptions and delay problems and to develop the visual railway network topology for the local Komuter rail system. The main contribution of the study is the formulation of a Mixed Integer Goal Programming (MIGP) model that determines a rescheduled timetable, generated based on trains priority rules, which are outlined according to the types of trains. The model aims at achieving two goals, where the first objective function is to minimise the total delay time of all trains in the network, while the second objective function is to maximise the train service reliability. A novel heuristic algorithm named as Headway and Order Scheme (HOS) is introduced to solve the rescheduling model. The approach considers the headway restriction and the sequence order of conflicting trains as its main feature. The headway restriction is formulated based on a new concept of blockoriented headway, whereas the sequence order is formulated based on the priority of conflicting trains. The model is solved by means of preemptive goal programming technique, using MATLAB r2014a, which automatically generates the optimal solution to the problem. Experimental analysis with incident scenarios based on different train priorities on Malaysian double track railway is examined to evaluate the performance of the proposed model and solution approach. It focuses on Komuter trains services and disruption incidences, which are mainly caused by signaling switches problem that takes a duration of five to fifteen minutes of time. The computational results show that the model is able to produce the provisional timetable in short computing time of 36 seconds. In addition to this, the total delay time and service reliability generated are strongly influenced by the setting of the train priorities. The solution generated successfully satisfies the restrictions posed by the rail operator and subsequently enables the goals of the model to be achieved. The verification of model was done by comparing the analytical solution generated in terms of the specification made by the new sets of constraint of the proposed model, while model validation was carried out by means of sensitivity analysis and face validation techniques. Besides the MIGP model and solution approach, the study has also developed a user interface for Komuter trains rescheduling support system.