Applying the Pebble Motion problem: studying the feasibility of the Train Unit Shunting Problem

Applying the Pebble Motion problem: studying the feasibility of the Train Unit Shunting Problem

Hanou, Issa (TU Delft Electrical Engineering, Mathematics and Computer Science)

de Weerdt, M.M. (mentor)
Mulderij, J. (mentor)
van Iersel, L.J.J. (graduation committee)

Delft University of Technology

Computer Science | Software Technology

2022-07-06

Shunting yards are the locations where trains, which are not included in the train schedule at a certain time, are parked until they are required again. Managing the parking of the trains such that all trains can leave at the desired time is a complicated task, and results in the problem formally known as the Train Unit Shunting Problem (TUSP). This problem is an NP-hard problem, and current algorithms cannot always determine whether an instance is feasible. We analyze a simplified variant of the TUSP, leaving out details from the real-world scenario to study the theoretical conditions for basic scenarios to be feasible. To this extent, we identify essential elements of the TUSP and include these in a modification of the Pebble Motion problem. Based on this Pebble Motion variant, we establish new problems that can be studied to analyze the feasibility of the TUSP. For each of these problems, we examine the complexity and look into different solution approaches.

train shunting
TUSP
pebble motion
feasibility
train length
pebble size
arrival and departure
pebble sequences

http://resolver.tudelft.nl/uuid:2ca12cd2-315e-4a31-9a2a-67a77d8988bf

Student theses

master thesis

© 2022 Issa Hanou