## 4 Numerical Tests and Results
### Trains
#### 4.2.1 Orders and Frequency of Trains  
The order in which trains entered the line had a great effect on the actual difficulty of the instance. When a faster (higher priority) train entered the line before a slower (lower priority) train in the same direction, no overtaking was allowed between those two trains. Thus, all binary variables related to the following and overtaking of these two trains could be either fixed or omitted from the model (see Section 3.2.2). Furthermore, because the distance between these two trains could be safely assumed to grow, virtually all headway constraints between these two trains would be guaranteed to be nonbinding. Given these facts, one can indeed easily \"cheat\" by selecting the problem instances properly, i.e., sending the faster trains first and then the slower trains. This was not the case for this study. In all instances, trains entered the line from the slowest to the fastest. In Table 8, the entrance time orders are given. The order is from the left to the right. Different instances are defined by the entrance times of the trains plus the entrance delays. However, the entrance time orders do not differ. All of them follow the same scheme. In the table, \"s\" stands for \"slow\", \"s-f\" stands for \"semi-fast\" and \"f\" stands for \"fast\". Furthermore, the headways between the entrances of the trains would produce an effect. If the trains are too infrequent, most (if not all) of the following- and overtaking-related constraints would be nonbinding. Because this will make respective binary variables useless, a solution space restriction algorithm will fix or eliminate most of them. Table 9 illustrates how the entrance time order can affect problem complexity. Because the solution space restriction algorithm does not eliminate any continuous variables, no difference in the number of them would be observed. The reduction is in the number of constraints and binary variables. It can be clearly seen that, with the same number of trains, it would be possible to create instances that are much easier to solve. However, we did not adopt this approach. Instead, in these instances, trains were introduced into the system in small headways and from the slowest to the fastest. Readers can think our approach as a \"worst-case scenario\" approach. To further demonstrate the effect of train order and frequency on problem difficulty (or complexity), a special instance with eight eastbound and eight westbound trains was prepared. In this instance, trains were introduced into the system from the fastest to the slowest. In addition, the headways between train entrances were each one hour. The unsolved state (infeasible schedule) of this special instance is given in Figure 3. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Train Number** & **Direction** & **Train Type** & **Weight** \\ \hline
1 & Eastbound & Fast & 6 \\
2 & Westbound & Fast & 6 \\
3 & Eastbound & Fast & 6 \\
4 & Westbound & Semi-fast & 4 \\
5 & Eastbound & Semi-fast & 4 \\
6 & Westbound & Semi-fast & 4 \\
7 & Eastbound & Semi-fast & 4 \\
8 & Westbound & Slow & 3 \\
9 & Eastbound & Slow & 3 \\
10 & Westbound & Slow & 3 \\
11 & Eastbound & Slow & 3 \\ \hline \hline \end{tabular}
\end{table} 
Table 7: Trains in the problem instances. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline Eastbound & 9 (s) & 11 (s) & 5 (s-f) & 7 (s-f) & 1 (f) & 3 (f) \\ Westbound & 8 (s) & 10 (s) & 4 (s-f) & 6 (s-f) & 2 (f) & - \\ \hline \hline \end{tabular}
\end{table} 
Table 8: Train entrance time orders. Even from the unsolved state, one can observe the simplicity of this instance. Because fast trains entered the line before slow trains, no trailing train could catch up to the train in front. Even in their smallest form, the headways between two trains in the same direction at any point were at least 60 min. This implies that no overtaking constraints and no following constraints were active. Moreover, station capacity constraints will not be active at all.