Train Marshalling Problems

Elias Dahlhaus, University of Koln

(joint work with P. Horak, M. Miller, J. Ryan)

The talk discusses the following problem. We would like to rearrange a sequence of freight railway cars in such a way that cars of the same destination appear consecutively. We consider the situation that two rails and a hub are available and minimize the number of back and forth movements. In general we show that this problem is NP-complete. Restricted requirements allow an efficient solution. We also discuss shortly the problem to minimize the number of rails and give a short overview on related problems.

back to seminar homepage