# An Evaluation Framework and Algorithms for Train Rescheduling
## 7 Description of the Experiment
### Computation Times
ALG1 is a heuristic algorithm that considers two minimization objectives with equal priority: minimizing \(\text{TFD}_{3}\) and \(\text{TPD}_{3}\). ALG2 is an exact algorithm that has five minimization objectives, with minimizing \(\text{TFD}_{3}\) as the primary objective. A threshold of 3 min is considered for all the delays appearing in the minimization objectives. Based on the carried out evaluation, we analyze the overall strengths and shortcomings of the two train rescheduling algorithms and their application when solving the 30 disturbance scenarios. A strength of ALG1 is that it is good at quickly finding solutions with small passenger delays. Weaknesses of ALG1 are apparent when it is solving disturbances due to an infrastructure failure. The solutions obtained for these scenarios have significant delay propagation, unsatisfactory freight train performance and many track reassignments. The strength of ALG2 is its ability to reschedule during infrastructure failures. In the studied scenarios, these failures are of rather modest size. When solving these disturbances, ALG2 is certainly the better choice, since it obtained significantly better solutions and is always within 30 seconds. The main weakness of ALG2 is its speed, particularly while solving disturbances 1-20. Typically, ALG2 obtained good rescheduling solutions for all the considered disturbances. However, compared to ALG1, ALG2 is slow in obtaining solutions. ALG2 took as long as 6 min for a disturbance that is solved in 6 sec using ALG1 (see scenario 6). When solving disturbances caused by a delayed or a malfunctioned train, a dispatcher can use ALG1 to quickly obtain a decent solution. If the comparatively slower ALG2 is to be used to solve these disturbances, the following are a few suggestions to improve its speed: (i) reduce the number of objectives by merging two or more of the lower-priority objectives into a single objective and (ii) increase the number of parallel threads simultaneously exploring the solution space. A suggestion to improve the practicability of ALG1 is to limit the number of track reassignments while solving disturbances where multiple trains have primary delays. This can result in more practical rescheduling solutions that are easier to implement. For several of the disturbances considered in the dataset, ideal rescheduling solutions were obtained (with respect to \(\text{TFD}_{3}\), \(\text{TAD}_{3}\) and \(\text{TPD}_{3}\)). For most other disturbance scenarios, the Pareto-optimal solution obtained by ALG2 is very close to the hypothetical ideal solution. The frequent existence of a feasible solution in the solution space that simultaneously minimizes \(\text{TFD}_{3}\), \(\text{TAD}_{3}\), and \(\text{TPD}_{3}\) is surprising. Future work could investigate the conditions under which a multi-objective train rescheduling problem contains an ideal solution in its solution space, particularly with respect to the train and passenger delays. **Author Contributions**: Conceptualization, S.P.J. and J.T.K. ; Methodology, S.P.J. and J.T.K. ; Software, S.P.J. and J.T.K. ; Validation, S.P.J; Formal analysis, S.P.J. ; Investigation, S.P.J. ; Resources, S.P.J. and J.T.K. ; data curation, J.T.K. ; Writing--original draft preparation, S.P.J. ; Writing--review and editing, S.P.J., J.T.K. and L.L. ; Visualization, S.P.J. ; Supervision, J.T.K. and L.L. ; Project administration, J.T.K. ; Funding acquisition, J.T.K. All authors have read and agreed to the submitted version of the manuscript. **Funding**: This research was funded by the Shift2 Rail project: FR8 Rail II (Grant No: 826206), and the research project BLLXTEN (Grant No: TRV 2018/108023) funded by Trafikverket via KAJT. **Acknowledgments:** Many thanks to the anonymous reviewers for their constructive comments, which greatly improved the paper. The authors would also like to thank [PERSON] and [PERSON] for providing valuable comments on several sections of a preliminary version of this paper. **Conflicts of Interest**: The authors declare no conflict of interest.