Expand your Planning Horizons with Duty Rostering

DR-OPT

Characteristics

DR-OPT is an optimizer for calculating duty rosters. In duty rostering, existing (daily) duties are combined into duty sequences that are either cyclic or can span over a planning horizon of several weeks.

Description

The duty and duty roster scheduling are the two substeps of the planning process in public transport, which determine the personnel deployment. In duty rostering, duties are assigned to duty rosters that span several weeks, i.e. a roster is a sequence of duties and days off for a certain period of time. Like the daily duties, the duty rosters must also comply with a comprehensive set of rules. In Germany, the most important provisions are those of the working time laws (Arbeitszeitgesetz).

Another important point in duty rostering is the balance between cost minimization (e.g., by avoiding overtime or paid leisure time), and maximizing driver satisfaction, which is particularly dependent on the duty roster. A duty roster is usually designed to maximize driver satisfaction without incurring substantial additional costs.

DR-OPT generates a duty roster over a particular scheduling horizon (e.g., 4 or 8 weeks) in which the daily duties and a previously set number of reserve duties are allocated to abstract personnel. Alternatively, DR-OPT can also generate a cyclic duty roster, a so-called weekly scheme. A duty roster is typically displayed in tabular form. The duties for a personnel are displayed in each line for the planning period, so the number of lines also corresponds to the number of personnel required. The personnel are abstract, since neither their past is taken into account in the form of accumulated working time accounts, nor their qualifications or their absence times. The rows of a duty roster must be assigned to specific personnel in the next planning step, the personnel dispatch.

DR-OPT is based on set-partitioning models, with various primal heuristics. Among others our DEX heuristic is used. For details, see BRSSSW2015.

Duty Rostering for Control Duties

In a recent project (see BSSS2016) we have combined DR-OPT with a system for the creation of control duties. This makes it possible at the same time to form integrated duties for control teams and to schedule them in a duty roster. The duties of the control teams does not have to be created from predefined tasks like in DS-OPT, but the duties have to be formed by a selection of a number of events which should be controlled, such that on the one hand, we got efficient duties, on the other hand we meet certain control quota requirements. Events to be controlled may include trips where tickets are checked or certain routes where at a certain point in time a certain check is to be carried out.

The control duties are subject to various legal and operational restrictions similar to those described above. Additional, there are feasible control areas for certain personnel. We use a multi-commodity flow model with additional constraints to integrate the creation of control duties and the duty rostering. The entire range of integer programming methods from column generation, cutting planes, branch-and-bound to various primal heuristics are used.

In cooperation with the Zuse Institute Berlin, we have been developing and supporting an integrated control duty and duty rostering algorithm since 2014, which has been used by the Federal Freight Transport Authority since 2014 to generate monthly duty rosters for more than 200 vehicles and 400 controllers. The optimized control duties and duty schedules guarantee network-wide control, while also taking into account the time and space distribution of the traffic to be controlled, in order to efficiently use the limited number of control teams.