Duty scheduling is arguably the most difficult and the most important step in the operational planning process of a public transport company. It deals with the assignment of pieces of driving work to duties for the drivers. Besides driving, a duty usually contains additional components such as sign-on and sign-off elements, travel elements, and breaks.

Duty scheduling involves various types of often complicated rules. First, there are physical constraints for the concatenation of individual duty elements, such as minimal travel times. Second, there are rules for the legality and costs of individual duties, e.g., break rules that force a driver to take a break even if it would be technically possible to go on driving; these rules arise from legal restrictions, company agreements, and the like. Usually, there are several types of duties, such as early, middle, late, part time, and split duties, each with its own set of rules. Limited availability of staff, rostering requirements, and similar conditions give rise to a third group of capacity constraints for duty types; these are often called base constraints.

The goal in duty scheduling is mainly the minimization of crew costs; however, criteria such as quality of work, equal treatment of drivers, schedule robustness, and so on are also important in practice.

Duty scheduling problems are among the best studied combinatorial optimization problems. The classical approach is to formulate the problem as a set partitioning integer program and to solve this IP with linear programming based column generation techniques.

The column generation method is based on a graph theoretic formulation of the problem that involves a duty scheduling digraph. The nodes of this digraph are individual units of work, the so-called duty elements. The duty elements are linked by arcs that correspond to possible concatenations of such elements, i.e., by continuing to drive, by changing a vehicle, by taking a break, etc. Duties correspond to paths in this digraph; however, not every path is a legal duty: only paths that conform to the rules of a duty type are legal. (Readers familiar with vehicle scheduling problems in public transit will notice that these path constraints are precisely the difference between vehicle and duty scheduling). The duty scheduling problem becomes a path covering problem in the duty scheduling digraph; it gives rise to an implicitly defined, very large set partitioning problem whose variables are all possible duties. Additional base constraints on capacities of duty types can be added to extend this model.

The basic idea behind column generation is to solve this set partitioning problem by iteratively generating duties to improve some initial schedule, until no further improvement is possible. To implement this idea, an instrument of guidance is needed that directs the method to improving duties; this instrument is provided by the so-called shadow prices which are associated with the duty elements. These shadow prices measure the cost of covering a duty element using only the currently known duties; they can be computed by solving a linear program. Given the shadow prices, one searches for duties that are cheaper than their shadow price and which therefore improve the schedule; this search is known as the pricing step.

Column generation is a well established and successful technique in combinatorial optimization. The secret of success in its application to duty scheduling is an efficient pricing algorithm to identify improving duties. A key ingredient in this procedure are pruning criteria that allow to terminate a search in an unproductive direction as soon as possible. We have developped a novel Lagrangean path search technique that provides an effective lookahead by computing high-quality estimates of additional costs that can not be avoided to complete a partial duty; if this minimum extra cost is too high, an unproductive search can be aborted and redirected to a more promising region.

Our algorithm solves industrial duty scheduling problems with several thousand duty elements, dozens of duty types, and complex base constraints on a routine basis. Even very large and complex problems are usually tackled within a couple of hours.

Our duty scheduling optimization module DS-OPT is integrated into the commercial planning systems MICROBUS II of IVU Traffic Technologies AG and BERTA of the Berliner Verkehrsbetriebe (BVG) and commercially marketed. Further development and support is done by the ZIB spin-off company Löbel, Borndörfer & Weider GbR. The tool is in use in many public transport companies, among them Athens, Berlin, Bonn, Connex Germany, DB Regio, Genova, Milan, Munich, and Norgesbus.

The Stadtwerke Bonn report that the optimization of their production plan for 30/06/2001 with DS-OPT has resulted in savings of 4.3% of their bus and 2.5% of their tram duties, the Verkehrsbetriebe Ennepetal-Ruhr have saved even 9.1% of their bus duties.

• BMBF-VS: Vehicle Scheduling in Public Transit
• BMBF-IS: Integrated Vehicle and Duty Scheduling in Public Transit
• CS: Airline Crew Scheduling
• Telebus: Vehicle Scheduling in a Dial-a-Ride Service

• Pröhl, Thomas. Lagrange-Verfahren für Set-Covering-Probleme. Diplomarbeit, Technische Universität Berlin, 1998.
• Ralf Borndörfer, Martin Grötschel, Andreas Löbel. Optimization of Transportation Systems. Forschungsbericht ZIB-Report 98-09, Zuse-Institut Berlin, 1998.
• Ralf Borndörfer, Andreas Löbel, Uwe Strubbe, Manfred Völker. Zielorientierte Dienstplanoptimierung. In: Heureka '99: Optimierung in Verkehr und Transport, pp. 171–194, Köln, 1999. ZIB Report 98-41.
• Ralf Borndörfer. Optimierung im Nahverkehr. Forschungsbericht Symposium Verkehr und Mobilität am 07.07.2000 in Adlershof, , 2000.
• Ralf Borndörfer, Andreas Löbel. Dienstplanoptimierung im ÖPNV. Forschungsbericht Arbeitskreis Mathematik und Praxis 463: 18. Symposium “Modellierung und Simulation von Verkehr”, Bad Honnef am 18./19.11.1999, Gerhard-Mercator-Universität Duisburg, 2000.
• Byun, Chul-Young. Lower Bounds for Set Partitioning Problems. Diplomarbeit, Technische Universität Berlin, 2001.
• Wensierski, Saska. Diensteinsatzplanung im öffentlichen Verkehr: ein Überblick und eine Studie der holländischen Bahn. Diplomarbeit, Technische Universität Berlin, 2001.
• Ralf Borndörfer, Marting Grötschel, Andreas Löbel. Duty Scheduling in Public Transit. In: MATHEMATICS –- Key Technology for the Future, Willi Jäger and Hans-Joachim Krebs (Eds.), pp. 653–674, Springer Verlag, Berlin, 2003.
• Schlechte, Thomas. Das Resource-Constraint-Shortest-Path-Problem und seine Anwendung in der ÖPNV-Dienstplanung. Diplomarbeit, Technische Universität Berlin, 2003.