Planning of train movements in single track railways

Railway is known to be the best mode of land transport in terms of energy consumption and land use per passenger-km or ton-km transported; and also in terms of economic efficiency for freight transportation. It is also known to be superior to air transport in terms energy consumption per passenger-km up to some specific distance of travel. Thus, it is of crucial importance to increase the market share of rail transport for economic and environmental sustainability. Customer satisfaction through better punctuality is one of the possible strategies towards this purpose. In reality, most of the railways operate according to a timetable, within which, all trains have predetermined departure times from, arrival times at and / or passing times without stopping through all the reference points (stations, sidings) in their routes. In daily operation, some of the trains may get delayed for various reasons. This creates a knock-on effect, spreading the delay to other trains. Thus, the timetable becomes invalid, and rescheduling of the traffic becomes necessary. Efficient rescheduling helps the railway system be more punctual. In practice, rescheduling is done by human operators (called dispatchers) by manual methods. Human brain has a limited computational ability. This puts an upper limit on the effectiveness of rescheduling solutions produced manually by humans. Fortunately, the computational power of today's modern computers can provide significant improvement. In this thesis, first, a mixed integer programming model for solving the rescheduling problem on a single track railway line to optimality is developed. The model considers most of the real constraints in a real railway operation like deadlock prevention and capacities of stations/sidings and aims to minimize the total weighted delay of the trains. Train scheduling is a strongly NP-Complete problem. This nature of the problem was clearly observed even in the small sized problems, like 4 eastbound trains and 3 westbound trains. This is a big drawback in a rescheduling problem, because rescheduling has to be done in a dynamic environment. Trains are xv moving and they can get some additional delays during the computation process, if it takes too long. This would make the solution produced worthless. To be specific, any algorithm for train rescheduling has to finish its job in at most 5 minutes, but, preferably, in 3 minutes. Therefore, a plan mixed-integer programming proved to be inadequate for rescheduling. It has to be supported with some additional procedures. We call these procedures as "speed-up routines". In this thesis, three different speed-up routines were used. The first was using the "lazy constraint" attribute of AIMMS. This attribute enables the user to mark the constraints that are unlikely to be binding. Then, the solver excludes them when computing the linear programming relaxation of the model and checks to solution of the linear programming relaxation against the constraints marked as "lazy". If it finds that one of the lazy constraints is violated, it adds the violated constraint into the constraint pool and re-solves the linear programming relaxation. In the model, most of the station / siding capacity constraints were marked as lazy. The second speed-up routine was a heuristic solution space restriction algorithm. The algorithm first produces a solution by implementing a greedy algorithm. This algorithm neglects the station / siding capacity constraints and deadlock prevention. Then, it restricts the solution to be not much different from the outcome of the greedy heuristic. This eliminates hundreds of binary variables and thousands of constraints from the model and provides a radical increase in the model's computational speed. However, the optimality of the solution is no longer guaranteed, although the model produces good solutions. The third speed-up routine was adopting a multiobjective approach. The objective of the main model is to minimize the total weighted delay of all trains. In the multiobjective approach, first, a problem with the same variables, parameters and feasible region, but a different objective function is defined. The objective function is minimizing the maximum weighted delay of all trains. Then, the optimal solution from this model is used as an initial feasible solution for the main problem. Also, in the main problem, weighted delay of each train is constrained not to exceed the maximum weighted delay computed in the first problem. This routine also provided a speed-up. The final model was tested on a hypothetical single track railway line with 18 stations. In the worst cases, the final model with all the speed up routines managed to solve the problems with 6 eastbound trains and 5 westbound trains in less than three minutes.