Duty Scheduling in Public Transit
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 largescale 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 EnnepetalRuhr 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).
Problem
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 signon and signoff 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.
Method
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 socalled 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 socalled 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 highquality 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.
Results
Our duty scheduling optimization module DSOPT 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 spinoff 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 DSOPT has resulted in savings of 4.3% of their bus and 2.5% of their tram duties, the Verkehrsbetriebe EnnepetalRuhr have saved even 9.1% of their bus duties.
Publikationen
2012 

Andreas Langenhan, Ralf Borndörfer, Andreas Löbel, Christof Schulz, Steffen Weider  Duty Scheduling Templates  Proceedings of Conference on Advanced Systems for Public Transport 2012 (CASPT12), 2012 (preprint available as ) 
BibTeX

2010 

Ralf Borndörfer  Mathematical Optimization and Public Transportation  Habilitation, Technische Universität Berlin, 2010 
PDF
BibTeX URN 
Ralf Borndörfer  Mathematical Optimization and Public Transportation  TU Berlin, 2010 
BibTeX

Ralf Borndörfer, Martin Grötschel, Andreas Löbel  The Quickest Path to the Goal  Mathematics Everywhere, pp. 2751, 2010 (preprint available as ZIBReport 1021) 
PDF (ZIBReport)
BibTeX 
2003 

Martin Grötschel, Ralf Borndörfer, Andreas Löbel  Duty Scheduling in Public Transit  MATHEMATICS – Key Technology for the Future, pp. 653674, Willi Jäger, HansJoachim Krebs (Eds.), Springer, 2003 (preprint available as ) 
BibTeX
DOI 
2000 

Ralf Borndörfer, Martin Grötschel, Andreas Löbel  Der schnellste Weg zum Ziel  Alles Mathematik, pp. 4576, Martin Aigner, Ehrhard Behrends (Eds.), Vieweg Verlag: Braunschweig/Wiesbaden, 2000 (preprint available as ZIBReport SC9932) 
PDF (ZIBReport)
BibTeX DOI 
Ralf Borndörfer, Andreas Löbel  Dienstplanoptimierung im ÖPNV  2000 
BibTeX

Ralf Borndörfer  Optimierung im Nahverkehr  Forschungs und Anwendungsverbund Verkehr & Initiativgemeinschaft Außeruniversitärer Forschungseinrichtungen in Adlershof e.V., 2000 
BibTeX

1999 

Ralf Borndörfer, Andreas Löbel, Uwe Strubbe, Manfred Völker  Zielorientierte Dienstplanoptimierung  Heureka ’99, pp. 171194, 1999 (preprint available as ) 
BibTeX

1998 

Ralf Borndörfer, Martin Grötschel, Andreas Löbel  Alcuin’s Transportation Problems and Integer Programming  Charlemagne and his Heritage. 1200 Years of Civilization and Science in Europe. Karl der Grosse und sein Nachwirken . 1200 Jahre Kultur und Wissenschaft in Europa, Paul Leo Butzer, Hubertus Jongen, Walter Oberschelp (Eds.), Brepols Publisher: Turnhout, pp. 379409, 1998 (preprint available as ZIBReport SC9527) 
PDF (ZIBReport)
BibTeX 
Ralf Borndörfer, Martin Grötschel, Andreas Löbel  Optimization of Transportation Systems  ZIBReport SC9809 
PDF
BibTeX URN 
1997 

Ralf Borndörfer, Martin Grötschel, Andreas Löbel  Dienstplanung im öffentlichen Nahverkehr  Mathematische Verfahren zur Lösung von Problemstellungen in Industrie und Wirtschaft, BMBF Mathematikprogramm 03GR7ZI1, 1997 
BibTeX
