Article ID: | iaor20002080 |
Country: | United Kingdom |
Volume: | 50 |
Issue: | 6 |
Start Page Number: | 608 |
End Page Number: | 616 |
Publication Date: | Jun 1999 |
Journal: | Journal of the Operational Research Society |
Authors: | Themido I., Cavique L., Rego C. |
Keywords: | transportation: rail, heuristics |
The tabu search algorithms for the Crew Scheduling Problem (CSP) reported in this paper are part of a decision support system for crew scheduling management of the Lisbon Underground. The CPS is formulated as the minimum number of duties necessary to cover a pre-defined timetable under a set of contractual rules. An initial solution is constructed following a traditional run-cutting approach. Two alternative improvement algorithms are subsequently used to reduce the number of duties in the initial solution. Both algorithms are embedded in a tabu search framework: Tabu-crew takes advantage of a form of strategic oscillation for the neighbourhood search while the run-ejection algorithm considers compound moves based on a subgraph ejection chain method. Computational results are reported for a set of real problems.