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).

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 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.

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 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.

Results

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.