Subgraph ejection chains and tabu search for the crew scheduling problem

Subgraph ejection chains and tabu search for the crew scheduling problem

0.00 Avg rating0 Votes
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: , ,
Keywords: transportation: rail, heuristics
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.

Reviews

Required fields are marked *. Your email address will not be published.