A Genetic Annealing Algorithm for Optimal Shift Design in Airport Ground Staff Scheduling

The paper focuses on a shift design problem for the airline industry, which describes the process of constructing a set of shifts to cover the demands. This problem can be formulated as a set covering problem and is solved by finding a sequence of shifts from a pre-defined shift set. Recently, a more extensive variety of shifts are introduced to the airport ramp. These goals imply a larger-scale shift design problem, where the mixed integer programming and conventional heuristics have limitations. A hybrid heuristic has been constructed for this shift design problem. The proposed heuristic is based on the genetic annealing (GAn), which synthesizes the global search efficiency from genetic algorithm (GA) and the local search quality from simulated annealing (SA). The algorithm is tailored for airport ground staff scheduling. Finally, a set of real-world instances has been solved to demonstrate the proposed algorithms.