Duty scheduling is the assignment of tasks of work to staff by means of a schedule. Problems typically involve complicated rules for the legality and the costs of duties that are due to the law, tarifs, company, and other regulations. This project deals with duty scheduling in public tranport, i.e., the construction of the daily shifts of work for bus, subway, and tram drivers. Very similar problems come up in air traffic, at railways, in hospitals, etc.

We have developed a set covering/partitioning based column generation optimization algorithm for the solution of duty scheduling problems. Its duty generation module implements a novel Lagrangean path search technique that allows the solution of complex and large-scale instances with several thousand duty elements and dozens of duty types (this corresponds to a medium sized public transportation company or a depot of a large company).

Significant savings can be achieved with these methods. The Stadtwerke Bonn, e.g., have saved 4.3% of their bus and 2.5% of their tram duties, the Verkehrsbetriebe Ennepetal-Ruhr even 9.1% of their bus duties.

Our methods are part of the scheduling systems MICROBUS II of the IVU Traffic Technologies AG and BERTA of the Berliner Verkehrsbetriebe (BVG).

• IVU Traffic Technologies AG
• HanseCom GmbH
• Löbel, Borndörfer & Weider GbR