Crew scheduling-An approach based on several heuristics

The work described in this paper was developed in co-operation with the Lisbon Metro Company, in the framework of a broader project aimed at developing a Decision Support System for Crew Management named GETRIDE. A brief description of the global problem is presented together with the model on which the DSS was based. The crew scheduling problem may be formulated as the determination of the minimum number of duties necessary to cover a pre-defined timetable. Duties may have one or two periods and are subject to contractual rules. It is a large size combinatorial problem ranging from 500 to 700 pieces of work. To obtain an initial feasible solution a run-cutting heuristic, which was later improved by tabu search techniques was used. Information about computational implementation as well as results obtained with real timetables are presented.