## 4 Numerical Tests and Results
### Results of the Test Runs
The algorithm could solve a 6 + 5 train problem within a duration of less than three minutes. This is a considerable improvement. In real operations, rescheduling problems have to be solved in a very short time because they have to be solved in a dynamic environment. The model treats the trains as static entities, but in reality, they would be moving. Note that the instances were chosen carefully to be as difficult as possible. Normally, railway authorities tend to \"speed-fleet\" the trains in timetabling. That means trains in the same direction enter the line segment in the order of decreasing speed, thus minimizing the number of potential following and overtaking conflicts. However, in our instances, the scheme is just the opposite. Trains were introduced into the line in the order of increasing speed, thus maximizing the potential following and overtaking conflicts. Trains were introduced into the system with headways from 10 to 20 min/train/direction, which is indeed an unrealistically high train frequency for such a long (18 stations, approximately 160 km) single-track line. This unrealistically high frequency of trains was, again (like the difficulty created in choosing the order of trains), chosen for observing some kind of worst-case performance [1]. The solution space restriction algorithm shortened the solution time of the model quite radically. Indeed, in its presolve stage, CPLEX applies its own algorithms to eliminate some of the constraints and variables. However, we can be more aggressive in elimination because our algorithm is indeed based on a solution of the problem, albeit a relaxed version (station and siding capacities). Because this algorithm reduces the number of possible meeting locations, it is not possible to provide formal proof of the optimality of the solutions. However, based on our own knowledge and experience in railway operations, we can argue that, in the optimal solution, it is highly unlikely that the meeting will need to be outside the region defined by this restriction algorithm. In the trials, the length of this region was five stations. Carrying the meeting point outside of this region creates an excessive waiting time for one of the trains, and this most probably contradicts with the maximum weighted delay objective. The multiobjective approach provided a surprisingly good boost for solution speed. It provided on the order of 90% improvement in the computation time. In the trial runs, it was observed that most of the time was consumed by the first problem, the minimum-maximum weighted delay. After the solution of the first problem, the second and major problem were indeed very quickly solved in only a few seconds. This was most probably due to the properties and capabilities of CPLEX. Both problems have the same feasibility domains, thus any combination of decision variable values that is feasible for one problem is also feasible for the other. Most probably, CPLEX can improve the solution with simple time shifts and quickly arrive at the optimal solution. Because the problem was solved in a heuristically restricted solution space, it is not possible to present a formal proof of optimality. However, at least the modeling approach was designed towards obtaining a Pareto-optimal solution because the problem was converted into a multiobjective one. However, this is not a very typical multiobjective problem. There is a slight contradiction between the objectives (see Table 2), and additionally, a positive correlation exists. The positive correlation between two objectives may have also helped increase the solution speed. 6 + 5 trains may seem to be a small problem instance, but in reality, it is not. Rescheduling algorithms have to be run in dynamic environments. Trains are moving, and they can always gain additional primary delays. This necessitates the model to be rerun several times. This puts a practical limit to the time horizon of a rescheduling problem. Time horizon is a preset limit to the scope of the rescheduling problem.