Solving large set covering problems for crew scheduling

This paper presents a computationally effective heuristic method which produces good-quality solutions for large-scale set covering problems with thousands of constraints and about one million variables. The need to solve such large-scale problems arises from a crew scheduling problem of mass transit agencies where the number of work shifts required has to be minimized. This problem may be formulated as a large-scale non-unicost set covering problem whose rows are trips to be performed while columns stand for round trips. The proposed method is mainly based on lagrangian relaxation and sub-gradient optimization. After the reduction of the number of rows and columns by the logical tests, ‘greedy’ heuristic algorithms provide upper and lower bounds which are continuously improved to produce good-quality solutions. Computational results, regarding randomly generated problems and real life problems concerning crew scheduling at Italian Railways Company, show that good-quality solutions can be obtained at an acceptable computational cost.