Dealing with conflicting trains

Dealing with conflicting trains: Effectively avoiding and resolving conflicts during shunting

Gribnau, Mees (TU Delft Electrical Engineering, Mathematics and Computer Science)

Hanou, I.K. (mentor)
Dumančić, S. (mentor)
Hai, R. (graduation committee)

Delft University of Technology

Computer Science and Engineering

CSE3000 Research Project

2023-06-28

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.

Train unit shunting problem
Conflicts
Constraint Programming (CP)

http://resolver.tudelft.nl/uuid:0d5e2fca-247a-4e94-bde4-d39a6818daed

Student theses

bachelor thesis

© 2023 Mees Gribnau