# An Evaluation Framework and Algorithms for Train Rescheduling
## 5 Framework Part II: Key Aspects for a Systematic Evaluation of Algorithm Performance  
This section presents the second part of the framework, which suggests a selection of key aspects to be used in systematic performance evaluation and benchmarking of algorithms. During train rescheduling, the objective(s) of an algorithm refer to the aspects that are to be minimized and/or maximized in the solutions [5]. A train rescheduling algorithm may produce one or more rescheduling solutions. The objectives that drive the computation of solutions indicate the quality aspects that are important to be considered by the algorithm. However, there may also be other properties of the produced solution(s) that affect their relevance and acceptability, of which some properties may be difficult to incorporate explicitly in the computations of good rescheduling solutions. For example, an IM may want to assess the robustness of the timetables produced by the algorithm. This property is typically easier to define and compute once the solutions are generated, but less suitable to formalize as a constraint or penalty. Having a standard set of quality indicators allows comparison of solutions computed by different algorithms, irrespective of the objectives of the specific algorithms. A quality indicator may be comprised of one metric or a set of metrics. These metrics can be used to compare algorithms and to reveal their strengths and weaknesses. These can also be used to monitor the search process of an algorithm and explicitly guide the search for improved solutions [30]. Table 4 lists the seven quality indicators and their corresponding metrics that are considered in the proposed evaluation framework. 1. _Train punctuality:_ The percentage of trains that arrive at their final destination within a given threshold of \(t\) minutes represents train punctuality. This metric is frequently used by railway organizations and in rail literature, with various threshold values, e.g., 0 min [16], 3 min [20; 29], 5 min [21]. For this reason, we use the percentage of early, on-time and delayed trains (for different threshold values) as metrics for train punctuality. \begin{table}
\begin{tabular}{l l} \hline \hline
**Indicator** & **Employed Metrics** \\ \hline \multirow{2}{*}{Train punctuality} & (i) The percentage of early and on-time trains, (ii) the percentage of delayed trains for various thresholds. \\ \hline \multirow{2}{*}{Train delays} & The total final and accumulated delays in minutes with a threshold value of three minutes, i.e., \(\text{FTD}_{3}\), \(\text{TAD}_{3}\), and their closeness to the hypothetical, ideal point. \\ \hline \multirow{2}{*}{Delay propagation} & The number of trains with secondary delays, considering a threshold value of three minutes. That is, the number of trains with secondary delays \(\leq\) 3 min and \(>\)3 min. \\ \hline \multirow{4}{*}{Freight train performance} & (i) Deviations in departure times of freight trains at their yards (in min), (ii) increase in freight train travel times (in min), (iii) number of unplanned stops for freight trains, (iv) the percentage of freight trains that arrive earlier than a threshold value (of 15 min) at their arrival yards. \\ \hline \multirow{2}{*}{Passenger delays} & Total passenger delay (in minutes) exceeding a threshold of three minutes, i.e., \(\text{TPD}_{3}\), and its closeness to the optimal value. \\ \hline \multirow{2}{*}{Track reassignments} & The number of rescheduled track allocations for passenger and freight trains, at stations and line sections. \\ \hline \multirow{2}{*}{Computation time} & The wall-clock time taken by the algorithm to obtain the \\  & rescheduled timetable. \\ \hline \hline \end{tabular}
\end{table} 
Table 4: A description of the chosen quality indicators. 2. _Train delays:_ Tardiness of a train at a relevant point in the network, e.g., a station, is its delay in arriving at the point [16], within a chosen \(t\) min threshold.