Subgraph ejection chains and tabu search for the crew scheduling problem |
| |
Authors: | L Cavique C Rego I Themido |
| |
Institution: | 1.Instituto Politécnico, EST,Setúbal,Portugal;2.Faculdade de Ciências, DEIO,Lisboa,Portugal;3.Instituto Superior Técnico, CESUR,Lisboa,Portugal |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|