A Graph Theoretical Approach To The Shunting Problem

AbstractIn this paper we propose a graph theoretical approach to the problem of train shunting in a railway depot. Especially during the night, the trains have to be parked in a shunting depot in such a way that the operations in the next morning can start as smoothly as possible. The general problem is very difficult and includes many subproblems. We focus on the following subproblem: how to arrange the trains in a “correct” order on the available tracks by avoiding shunting operations for outgoing trains of the morning. We discuss different cases of the problem, and we propose both algorithmic solutions and heuristic approaches