## 4 Numerical Tests and Results
### Results of the Test Runs  
The constructed instances were run on a computer with an Intel Core i5-2400 processor with 3.1 GHz processor speed and 6.0 GB RAM. In Figure 5, the initial state of Instance 1 is given. The figure shows trains' free paths with their minimum running times. Please note that the instance shown in Figure 5 is much more difficult to solve than that in Figure 3 because of the unfavorable entrance time orders and close entrance times. As seen in Figure 6, all conflicts are resolved. In this instance, there was a congested area between stations 7 and 10. None of the station or siding capacities were violated in the  
\begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline  & **Train 1** & **Train 2** & **Train 3** & **Train 4** & **Train 5** & **Train 6** & **Train 7** & **Train 8** & **Train 9** & **Train 10** & **Train 11** \\ \hline Instance 1 & 79 & 60 & 95 & 39 & 40 & 49 & 59 & 6 & 9 & 23 & 26 \\ Instance 2 & 82 & 57 & 92 & 42 & 43 & 46 & 5  
final solution. In Figure 7, the congested area in Figure 6 is zoomed in to better visualize the conflict resolutions and station track occupations. In Figure 7, the numbers of secondary lines (abbreviated as SL) in the stations are also given. As seen in this figure, no station capacity was violated in the rescheduling. In Figure 6, the final solution generated with the algorithm is presented. In Table 13, the summary of the solution of Instance 1 is given. The results of all ten instances (together with Instance 1) are summarized in Table 14. Despite the numbers of eastbound and westbound trains being the same in every instance, there are slight differences observed in the number of binary variables created with the solution space restriction algorithm (described in Section 3.2.2). Once a decision variable is fixed, the solver treats that variable as a parameter and does not count it in the total number of variables. Lastly, the number of constraints seem to be relatively high, but very few of these constraints were actually binding at any iteration of the algorithm. Most of them were lazy constraints as defined in Section 3.2.1. They were explicitly considered only if they were violated in the LP relaxation. Figure 6: Final solution of Instance 1. Figure 7: Congested area of Instance 1 is zoomed in. The instance was run using the same hardware and software as the previous instances and adopting four different approaches: no speed-up (Base), using only the lazy constraint attribute (Lazy), using the lazy constraint attribute with the solution space restriction algorithm (Lazy + Restr) and finally the multiobjective added onto the top of them (Lazy + Restr + Multi). At every minute, the optimality gaps were recorded; the results are shown in Figure 8. Figure 8 clearly displays the performance differences of the approaches. In Table 17, it can be seen what happens if the solution were not interrupted until the end (optimal solution). This table also demonstrates the effects of the speed-up routines on the problem tractability. In addition, for this instance, it can be seen that the solution restriction algorithm found the optimal solution. Given the development of the approaches in line with the railway operation practices, we concluded that this algorithm will find the optimal solution most of the time. In Table 18, the arrival time and delay data of trains in the final solution are given. The models with and without the solution space restriction algorithm produced exactly the same solution as each other. The last one naturally  
constraints by enumeration. The train scheduling problem is an NP-complete problem with a structure similar to an extremely difficult version of the job-shop scheduling problem. The combinatorial structure of this problem dominated all of the trial runs. Without any heuristic improvement, the solver could solve only small instances, e.g., a 3 + 3 train problem (three eastbound plus three westbound trains). However, all of the heuristic improvements helped to increase this number to, for now, 6 + 5 trains.