# An Evaluation Framework and Algorithms for Train Rescheduling
## 4 Framework Part I: Classification of Algorithm Capabilities and Characteristics
_Applicable infrastructures, sections and tracks:_ These three related aspects specify the properties that can be represented by an algorithm's model of the rail infrastructure. For example, an algorithm that is intended to be used for rescheduling trains on a single line may assume that all stations are linked in a sequence and that all trains travel between the stations in a chronological order. A line is here a \"sequence of segments between two major stations with possibly several intermediate stations\", while a railway network is instead comprised of \"one or several junctions of lines\" [15]. In a network, one station can be connected directly with more than two stations [6]. Hence, an algorithm may or may not be able to reschedule trains in a network setting. Furthermore, the segments between the stations and their capacity restrictions may be modelled differently depending on if e.g., only single track is considered or if segments with several alternative tracks can be used to reschedule delayed trains. Whether the algorithm can represent only tracks that permit traffic in only one direction, or in both directions (i.e., bi-directional traffic), is also relevant to capture. For example, in some rail networks, a double-tracked line consists of two parallel, uni-directional tracks where one is dedicated to traffic in one direction and the other to traffic in the reversed direction. Hence, overtaking is then \begin{table}
\begin{tabular}{l l} \hline \hline
**Algorithm Characteristic** & **Values** \\ \hline Infrastructure granularity [9; 11] & Microscopic, Mesoscopic, Macroscopic \\ Time representation [15] & Discrete, Continuous \\  & Train length, train weight, type of train service and its associated \\ Special considerations [15] & preferences, train connections and other operational \\  & dependencies, etc. \\  & Line, Network \\  & Single-tracked, Double-tracked, Multi-tracked \\  & Unidirectional, Bi-directional \\ \hline Rescheduling tactics [6; 25] & Retiming, rerouting, reordering, train cancellations, adding extra \\  & trains, etc. \\  & Optimization objective(s) & Minimize train delays, maximize passenger satisfaction, etc. \\  & Solving strategy & Centralized, Decomposition \\  & Solution space exploration & Full, Partial \\  & MILP solver, lagrangian relaxation method, branch and bound \\  & Solution approach [6] & method using a depth-first search or a parallel tree search, tabu \\  & & \\  & Interpreting the problem as a blocking job-shop scheduling \\  & problem and modelling using graph theory, addressing multiple \\  & objectives in the problem using epsilon constraints, etc. \\  & & Open, Multiple open, Closed \\ \hline Evaluation level [15] & Conceptual approach, Simulated experiments (artificial or real \\  & data), Field experiments, Deployed in practice \\  & Station or Terminal area, Line, Network \\  & Delayed train, infrastructure (e.g., signal) failure, train \\  & malfunction, freight train’s early departure from its yard, etc. \\ \hline \hline \end{tabular}
\end{table} 
Table 2: The characteristics used to classify and describe algorithms and their capabilities. only possible at stations and an algorithm may base its computation on this assumption and enforce associated constraints. In Sweden, basically, all tracks allow bi-directional traffic (i.e., there are signals for trains in either direction). Allowing faster trains to overtake slower trains on the line between stations is a frequently-used measure to enable trains to catch up and to reduce delay propagation. _Solving strategy:_ When the original problem is solved as one instance, it is said to be a centralized approach [15]. A _decomposition_ approach replaces the original problem with a sequence of smaller sub-problems, the solutions to which are computed and then recombined or extended to the original problem.