1999 | OriginalPaper | Buchkapitel
An Exact Branch and Cut Algorithm for the Vehicle and Crew Scheduling Problem
verfasst von : Christian Friberg, Knut Haase
Erschienen in: Computer-Aided Transit Scheduling
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present a new model for the vehicle and crew scheduling problem in urban public transport systems by combining models for vehicle and crew scheduling that cover a great variety of real world aspects, including constraints for crews resulting from wage agreements and company regulations. The main part of the model consists of a set partitioning formulation to cover each trip. A column generation algorithm is implemented to calculate the continuous relaxation which is embedded in a branch and bound approach to generate an exact solution for the problem. To improve the lower bounds, polyhedral cuts basing on clique detection and a variant of the column generation algorithm that suits the cuts were tested.