Train Routing Algorithms: Concepts, Design Choices, and Practical Considerations

摘要

Routing cars of trains for a given schedule is a problem that has been studied for a long time. The minimum number of cars to run a schedule can be found efficiently by means of flow algorithms. Realistic objectives are more complex, with many cost components such as shunting or coupling/decoupling of trains, and also with a variety of constraints such as requirements for regular maintenance. These versions of the problem tend to be NP-hard, and thus the standard powerful tools (e.g. branch-and-bound, branch-and-cut, La-grangian relaxation, gradient descent) have been used. These methods may guarantee good solutions, but not quick runtimes. In practice, two major railway companies, German Railway and Swiss Federal Railway, do not use either approach. Instead, their schedulers create solutions manually, modifying solutions from the previous year. In this paper, we advocate an intermediate, semiautomatic approach. In reality, not all constraints or objectives can be easily formulated mathematically. To allow for interactive human modification of solutions, the system must work rapidly, allowing a user to save desired subsolutions, and modify (or just start over on) the rest. After careful examination to find which constraints and costs we can easily integrate into a flow model approach, we heuristically modify network flow based solutions to account for remaining constraints. We present experimental results from this approach on real data from the German Railway and Swiss Federal Railway.