Teilnahme an der Konferenz OR 2015 in Wien

Auf der Konferenz OR 2015 (International Conference on Operations Research, 01.09.-04.09.2015, Wien) hat unsere Mitarbeiterin Kirsten Hoffmann einen Vortrag zum Thema "A hybrid solution approach for railway crew scheduling problems with attendance rates" gehalten.

Abstract Vortrag:

The railway crew scheduling problem is to find an allocation of train services to crew members satisfying legal requirements and operating conditions in order to minimize total costs. Previous crew scheduling models and solution approaches mostly deal with covering all trips of the given train timetable. The diminishing importance of operational tasks and increasing cost pressure, however, force responsible authorities in Germany to reduce the deployment of conductors. Therefore, transportation contracts defining all frame conditions for different transportation networks determine one or more percentage rates of trains or kilometers that have to be attended by conductors. Typically, these rates are distinguished between product types, lines, track sections, or time windows.

In this talk, we present a model for railway crew scheduling problems dealing with such rates. For real-world instances, this model contains millions of feasible duties and, thus, variables. To avoid generating all duties a priori, the problem is decomposed in a master and a pricing problem. After solving the restricted master problem with an initial schedule, dual values are used to generate new feasible duties iteratively (pricing problem). The most common approach to solve the pricing problem is to find a shortest path according to resource constraints. As we have to find good crew schedules for planning periods of two weeks or even one month in a few hours in practice, we present a genetic algorithm as a faster solution approach for the pricing problem. Based on a set of real-world instances, we compare our hybrid solution approach with the enumeration approach with respect to resulting total costs and computation time.