Models and algorithms for ground staff scheduling on airports

Herbers, Jörg; Hromkovic, Juraj

doi:HT014351855

Models and algorithms for ground staff scheduling on airports

Herbers, Jörg (Author)

2005

Verantwortlichkeitsangabevorgelegt von Jörg Herbers

ImpressumAachen : Publikationsserver der RWTH Aachen University 2005

UmfangXVI, 259 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2005

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Hromkovic, Juraj (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2005-03-14

Online
URN: urn:nbn:de:hbz:82-20050708
URL: http://publications.rwth-aachen.de/record/59558/files/Herbers_Joerg.pdf

Einrichtungen

Fakultät für Mathematik, Informatik und Naturwissenschaften (100000)

Inhaltliche Beschreibung (Schlagwörter)
Flughafen (Genormte SW) ; Bodenpersonal (Genormte SW) ; Personalplanung (Genormte SW) ; Ganzzahlige Optimierung (Genormte SW) ; Constraint-Programmierung (Genormte SW) ; Handel, Kommunikation, Verkehr (frei)

Thematische Einordnung (Klassifikation)
DDC: 380

Kurzfassung
Die Planung von Bodenpersonal an Flughäfen beinhaltet eine Reihe anspruchsvoller Optimierungsprobleme. Das Arbeitsaufkommen für Abfertigungsdienste wird typischerweise in Form von Arbeitsaufträgen dargestellt, z.B. für die Gepäckentladung oder für Check-in-Dienste. Dieses Arbeitspensum muss durch geeignete Mitarbeiter abgedeckt werden. Die Planung wird üblicherweise stufig durchgeführt: In der Bedarfsplanung wird das Arbeitsaufkommen aggregiert und analysiert, in der Schichtplanung werden geeignete Schichtdienste generiert, und in der Dienstplanung werden Dienstpläne für die Mitarbeiter erstellt. Die einzelnen Phasen sind dabei eng verzahnt, und auf jeder Stufe müssen verschiedene Optimierungsprobleme gelöst werden. Personalplanungsmodelle bauen traditionell auf aggregierten Bedarfszahlen auf, die in diskreten Zeitschritten angegeben werden. Für die tatsächliche Generierung einer solchen Bedarfskurvenrepräsentation sind in der Literatur allerdings keine Modelle oder Algorithmen beschrieben worden. Darüber hinaus ist eine Planung auf Basis grober Bedarfszahlen nicht immer ausreichend. Wenn hinreichend genaue Informationen über abzufertigende Flüge und Passagier-/Gepäckzahlen zur Verfügung stehen, ist man vielmehr daran interessiert, die einzelnen Arbeitsaufträge zu verplanen. Schicht- und Dienstplanungsansätze in der Literatur gehen zudem durchgehend von speziellen Annahmen aus oder behandeln vereinfachte Probleme, was ihre praktische Anwendbarkeit einschränkt. In dieser Arbeit werden Optimierungsprobleme für verschiedene Planungsschritte gelöst. Es wird gezeigt, wie eine geeignete Bedarfskurvendarstellung unter Berücksichtigung verschieblicher Aufträge generiert werden kann, indem Elemente des Vehicle Routing und des Resource Levelling kombiniert werden. Darüber hinaus werden zwei Algorithmen für die auftragsbasierte Schichtplanung entwickelt, die auf Modellen des Vehicle Routing und des Shift Scheduling aufbauen. Die erste Methode ist ein Verbesserungsverfahren, das auf den Ergebnissen einer Konstruktionsheuristik basiert und ein komplexes Schichtplanungsproblem behandelt. Der zweite Algorithmus bezieht sich auf eine Teilproblemklasse und löst viele praktische Probleminstanzen beweisbar optimal. Schließlich wird ein Algorithmus für die Erstellung komplexer Schichträder auf Basis einer aggregierten Bedarfsdarstellung konzipiert. Der Ansatz baut auf einem Modell zur impliziten Darstellung flexibler Pausen auf und löst das Shift Scheduling- und Dienstplanungsproblem imultan. Die Modelle und Algorithmen in dieser Arbeit sind stärker integriert und berücksichtigen komplexere Nebenbedingungen als frühere Beiträge. Moderne Techniken des Constraint Programming und der ganzzahligen Programmierung (einschließlich Spaltengenerierungs- und Branch-and-Price-Ansätzen) werden eingesetzt. Für die vorgestellten neuartigen Optimierungsprobleme werden Komplexitätsuntersuchungen durchgeführt. Alle Algorithmen werden auf großen, komplexen Testfällen aus der Praxis von Fluglinien, Flughäfen und Bodenverkehrsgesellschaften evaluiert.

The planning of airport ground staff gives rise to a number of challenging optimisation problems. Ground handling workloads are naturally represented as work tasks, e.g. for baggage unloading or passenger check-in. These workloads must be covered by appropriate employees. Staff scheduling is usually carried out in several stages: In demand planning, workloads are aggregated and analysed, in shift planning, appropriate shift duties are generated, and rostering consists in generating lines of duty for the workers. These phases are strongly interrelated, and different optimisation problems have to be solved at each stage. Workforce scheduling models have traditionally built upon aggregate labour requirements given in discrete time periods. However, the literature does not describe any models or algorithms for the generation of appropriate workload representations. Additionally, it will not always be sufficient to cover coarse-grained abstractions of workloads. If information on flights as well as passenger and load figures are sufficiently exact, we will rather be interested in directly covering individual work tasks. Furthermore, shift scheduling and rostering approaches have regularly taken special assumptions or investigated simplified problems, limiting their practical applicability. In this work, we tackle optimisation problems at different planning stages. We show how in the presence of movable tasks, we can obtain a suitable demand curve representation of workloads, using a levelling procedure which combines aspects from vehicle routing and resource levelling. Furthermore, we devise two algorithms for task-level shift planning which relates to vehicle routing and shift scheduling models. The first method is an improvement procedure, building upon the results of a construction phase and dealing with a complex shift planning setting. The second algorithm focuses on a subclass of task-level shift planning and is able to solve many problems to proven optimality. Finally, we design an algorithm for complex cyclic rostering on the basis of aggregate workloads. The approach builds upon a novel model for representing flexible breaks and solves the shift scheduling and rostering stage simultaneously. Models and algorithms proposed in this thesis are more integrated and tackle more complex settings than previous approaches. We employ modern constraint programming and integer programming solution techniques, including column generation and branch-and-price. For the novel optimisation problems treated in this work, we provide complexity results. All algorithms are evaluated on complex large-scale test cases from the practice of airlines, airports and ground handling companies.

Fulltext:
PDF
(additional files)