Optimization of train positioning in railway stations

Abstract: Today’s society keeps trying to improve efficiency in production and general reliability in systems. This is true for all types of companies that are driven to use optimization techniques in their work. One major field impacted by these studies is transport. Railway companies set the example and make optimization a priority in order to handle train flows the best way possible. That is why the French National Railway Company imagined an informatic tool to decide how trains are to be parked optimally. The thesis exposed in this report has been proposed for treating the modeling and programming parts of the project. Modeling the station has been done in association with railway experts who bring their knowledge about the station infrastructure. They are also a reference for determining the constraints a train must obey when arriving at the station, parking and leaving. Only useful aspects of the station must be taken into account. That is why a compromise has been chosen in the level of detail modeled. Then, a mathematical formulation of the problem has been proposed. The decision variables are for each train its arrival path, parking track and departure path. There are lots of possibilities and the choice can be difficult. The constraints are quite numerous as well. Thus, it has been decided to divide the constraints in two parts: hard and soft constraints. The general idea is to find a solution that obeys all hard constraints and minimizes the number of soft constraints not respected.  The project consisted also in choosing a language to code the model and a solver. The mathematical model has been written with the modeling language OPL that calls the solver Cplex. This software is one of the best to solve large scale problems that may arise for complex stations. Since the problem was a Mixed Integer Programming; the solver uses the Branch & Cut algorithm that is a combination between different techniques. It consists in applying the Branch & Bound algorithm while cutting the feasibility region. Heuristics techniques are also used by the algorithm in order to provide quickly a feasible solution. After running the program, we get a solution which is optimal according to the approach discussed earlier on. More precisely, it would determine for each train an arrival path, a parking track and a departure path.   The program developed during this thesis is proposed to the stations. It would help them in deciding how trains are parked on one day. This decision is made in a conception phase happening several months before the actual day treated. Several major stations have tested the optimization tool. Thanks to a regularity coefficient, they are able to judge the quality of the solution. Since this score has been increased, the solution is judged as rather good. Furthermore, they will use it for the year 2016. A significant advantage is also the time for making the decision. When the modeling phase is done, a few minutes are enough to produce a solution for a given train set, whereas it can take several weeks of work by hand.