Duty Scheduling in Public Transit

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.