Creating New Train Timetables in Case of Disruptions

Creating New Train Timetables in Case of Disruptions: Optimising a Branch & Bound Algorithm

van den Akker, Yoshi (TU Delft Electrical Engineering, Mathematics and Computer Science)

Yorke-Smith, N. (mentor)
Erkin, Z. (graduation committee)
van Schie, Arjen (graduation committee)

Delft University of Technology

Computer Science

2024-05-16

The Dutch railway system is one of the most densely used systems worldwide and the busiest in Europe. Given the tight schedules, incidents can quickly cascade through the entire country if not handled properly. Alternative timetables are created to help train traffic controllers swiftly resolve such incidents. These schedules are currently created manually, but the team cannot keep up with demand. This is why CGI is developing VGB Solver, an application to automatically generate such timetables. The solver uses a branch and bound algorithm in which nodes are processed in best-first order, based on a heuristic value. For this thesis, different performance optimisations for this algorithm were implemented and analysed.

Various alternative formulations of the heuristic value, used to determine the likeliness of a node leading to a good solution, showed promising results.
One of these formulas resulted in solutions for 96% more scenarios than before, and improved the quality of solutions for other scenarios.

Using machine learning, a decision tree was created to predict whether applying another new formula for the heuristic value gives better results than the old formula. This classifier achieved an accuracy of 73.5% on the test data. Having the solver choose between the old and new formula based on that classification resulted in some scenarios with worse scores, but twice as many improved, and the average improvement was higher than the average deterioration.

Recommendations are made to conduct further experiments related to the heuristic value calculation. Furthermore, it is suggested to separate the scores for evaluating solution quality from the heuristic value formula, to facilitate more fine-grained changes to the calculation of the heuristic value.

Branch and Bound
optimisation
heuristic

http://resolver.tudelft.nl/uuid:06d9cb8a-c886-46b6-bf24-a4787b3f529f

Student theses

master thesis

© 2024 Yoshi van den Akker