Freight Railway Crew Scheduling

The freight railway crew scheduling problem consists of generating crew duties to operate freight trains at minimal cost, while meeting all work regulations and operational requirements. Compared to similar problems in the airline industry, freight railway problems are typically more complex. As an example, a freight railway driver can travel as a passenger on different means of transportation (company train, passenger train, and taxi), an activity called “deadheading”. Due their large number, the deadheading connections that show the largest potential for reducing the overall crew scheduling costs have to be selected carefully. We show how current crew scheduling solution approaches can be adapted and extended to meet the needs of freight railway problems.

Large Scale Railway Crew Scheduling

Railway crew scheduling problems are typically very large in practice - still, they need to be solved in very short time, and only small deviations from the optimal solution are tolerated. Current decomposition approaches show large promise in reducing solution runtimes, but commonly suffer from a low quality of the generated schedules. To regain large parts of the solution quality that is lost with the decomposition, we are working on decomposing the crew scheduling problem sets into overlapping regions. The crew scheduling subproblems associated to these regions are solved in parallel. During optimization, we continuously exchange information on the optimization progress between the regions and adapt the regions if this is deemed beneficial. Extensive tests with real-world data show that our approach is capable of generating high-quality crew schedules at reasonable runtimes.

Robust Railway Crew Scheduling

Robust crew schedules anticipate delays in railway traffic in the planning phase. The usual practice is blocking a certain time period between connections as a buffer time. But practice has shown that buffer times are not distributed efficiently, leading to higher real cost than necessary. Research indicates that there are several factors that have an impact on the robustness of crew schedules such as the location of the buffer or the number of train changes. It is our goal to identify these factors for railway crew scheduling and to develop an algorithm that creates robust crew schedules for large scale problems.