Simulation optimisation approaches for robust scheduling of airport ground handling tasks and teams

Abstract

Aircraft ground operations (baggage loading/unloading, refuelling, etc.) are usually very tightly scheduled, so that even small variations in the task durations or travelling times of handling teams between two aircraft can result in long departure delays. Therefore, having robust plans for handling such operations by leaving enough idle (slack) time between activities to enable rapid recovery from such delays is the primary goal of all service providers, as well as of the airport operator and/or the airlines. This can be viewed as a two-stage problem and this thesis will hence propose two novel models for each. The first one will address the resource-constrained project scheduling problem (RCPSP) as applied to ground handling tasks for setting the minimum size team requirements. The second tackles the vehicle routing problem with time-windows (VRPTW) to achieve robust routing of teams through a set of novel objectives: maximising the minimum slack, workload balancing, and maximising the total slack across all teams of the same SP.

A lexicographic approach is adopted by taking advantage of both constraint programming (CP) and mixed integer programming (MIP) optimisation methods. The scheduling problem is solved to optimality of which the start times of each individual handling task, as well as the minimum team requirements are determined. This information, then used to find good routing solutions per SP. At this stage, due to the complexity of the routing model, optimality is not guaranteed for maximising the total slack. Thus, the initial solution is exploited in an LNS based matheuristic framework. The robustness of the routing solutions are then assessed using Monte Carlo sampling for team routing plans, while the airport-wide solution is evaluated through discrete-event simulation (DES). This is repeated iteratively until robustness is achieved at both levels within a simheuristic scheme, by allowing the results from the simulation to provide constructive feedback to the search. These tailored constraint-based feedback routines are automatically generated from simulation outputs, and are used to constrain the search space to solutions more likely to ensure robustness. This is the first simheuristic study to introduce such elaborate feedback mechanisms for solving combinatorial optimisation problems.

The proposed approach shows increased convergence on finding a robust solution when compared to a current state-of-the-art approach. Furthermore, it introduces a semi-centralised decision making architecture which avoids the need to share sensitive information among competing SPs in a multiple stakeholder environment.