Models and algorithms for ground staff scheduling on airports

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