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

Master thesis (2022)

Authors

I.K. Hanou Electrical Engineering, Mathematics and Computer Science

Contributors

M.M. de Weerdt Algorithmics - EEMCS (supervisor 1)
J. Mulderij Algorithmics - EEMCS (supervisor 1)
L.J.J. van Iersel Discrete Mathematics and Optimization - EEMCS (supervisor 2)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2022 Issa Hanou
TUSP Train shunting Feasibility Pebble motion Train length Pebble size Arrival and departure Pebble sequences
More Info
expand_more

Published Date

06-07-2022

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

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.