A set partitioning approach to the crew scheduling problem

The crew scheduling problem (CSP) appears in many mass transport systems (e .g., airline, bus, and railway industry) and consists of scheduling a numbe r of crews to operate a set of transport tasks satisfying a variety of cons traints. This problem is formulated as a set partitioning problem with side constraints (SP), where each column of the SP matrix corresponds to a feas ible duty, which is a subset of tasks performed by a crew. We describe a pr ocedure that, without using the SP matrix, computes a lower bound to the CS P by finding a heuristic solution to the dual of the linear relaxation of S P. Such dual solution is obtained by combining a number of different boundi ng procedures. The dual solution is used to reduce the number of variables in the SP in su ch a way that the resulting SP problem can be solved by a branch-and-bound algorithm. Computational results are given for problems derived from the li terature and involving from 50 to 500 tasks.