Circulation of Railway Rolling Stock: A Branch-and-Price Approach

We describe an algorithmic approach to determine an efficient railway rolling stock circulation on a single line or on a set of interacting lines. Given the timetable and the passengers? seat demand, we develop a branch-and-price algorithm that results in an allocation of rolling stock material to the daily trips. In order to efficiently utilize the train units, they can be added to or removed from the trains at some stations along the line. These changes in train composition are subject to several constraints, for example corresponding to the order of the train units within a train. A solution is evaluated based on three criteria, i.e. the service to passengers, the robustness, and the cost of the circulation. The branch-and-price algorithm that we developed is tested on real-life instances from NS Reizigers, the main Dutch operator of passenger trains.