Solving shunting yard disturbances using conflict-based search

Abstract

At railway shunting yards, trains are parked and service tasks are performed. Ongoing research has resulted in a local search algorithm to generate shunting plans which is capable of solving realistic, large problems. However, in practice, there might be disturbances at the shunting yard, which might make the computed schedules infeasible. In this thesis, we explore solving these disturbed problems by using conflict-based directed search. We take the original shunting plan, incorporate the disturbance, and then look at the conflicts which might arise. To solve this, we consider specific changes to the schedule which might resolve these conflicts. The conflict-based directed search algorithm is tested on two different shunting yards and is compared against the original algorithm which was used to generate the feasible, undisturbed shunting plans. We motivate the considered changes to the shunting plan in order to solve the disturbed problem and show how these could solve certain types of conflicts.