Dealing with conflicting trains

Effectively avoiding and resolving conflicts during shunting

Bachelor thesis (2023)

Authors

M. Gribnau Electrical Engineering, Mathematics and Computer Science

Contributors

I.K. Hanou Algorithmics - EEMCS (supervisor 1)
S. Dumančić Algorithmics - EEMCS (supervisor 1)
R. Hai Web Information Systems - EEMCS (supervisor 2)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2023 Mees Gribnau
Train unit shunting problem Conflicts Constraint Programming (CP)
More Info
expand_more

Published Date

28-06-2023

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

A shunting yard is used to store trains between arrival and departure. A conflict arises in a shunting yard when one train obstructs another from leaving. Resolving a conflict is done by re-allocating the trains obstructing the departing train to other tracks in the shunting yard. However, these re-allocations complicate the problem at hand and incur high costs for train operators. Therefore, it is desirable to avoid conflicts whenever possible. The aim of this paper is to find an effective manner to deal with conflicts in a train shunting yard in an existing planner system. We propose the split into a portfolio planner, which first tries to find a solution without any re-allocations, and if that does not yield a solution will look for a solution with re-allocations. For both planners, a model is defined. Furthermore, the paper explores techniques to increase the speed of the first planner, namely heuristic search, a set partitioning approach, and constraint programming. An implementation of the latter approach has exhibited excellent performance across problems of all sizes.