A heuristic approach to the bus driver scheduling problem (Q1068719)

We consider the problem of finding a set of bus driver duties which covers a given set of running boards (bus schedule) so as to minimize the number of drivers and satisfy a set of constraints given by the union contract and company regulations. It is known that mathematical programming formulations of this problem are generally too complex to be exactly solved for real-world applications. We present a heuristic approach which identifies the basic components of the problem and solves each of them either exactly or heuristically. The method is particularly suitable for cases where heavy constraints on meal breaks are present. The package based on this algorithm is currently used by a public transit company.