Optimizing Manpower Allocation for Ground Handling Tasks in Airports using Column Generation

The Manpower Allocation Problem with Time Windows, Job-Teaming Constraints and a limited number of teams (m-MAPTWTC) is the problem of assigning m teams to a number of tasks, where both teams and tasks are restricted by time windows outside which operation is not possible. Tasks may require several individual teams to cooperate. Cooperating teams have to be synchronized with each other. Due to the limited number of teams, some tasks may have to be left unassigned. The objective is to maximize the number of assigned tasks. The problem arises in various crew scheduling contexts where cooperation between teams/workers, possibly with different skills, is required. This study focuses on the scheduling of ground handling tasks in some of Europe's major airports. Any daily schedule must comply with the time windows and skill requirements of tasks, transportation time between locations, the working hours of the staff, synchronization requirements between teams, and union regulations. The problem is solved using column generation in a Branch-and-Price framework. Synchronization between teams is enforced by branching on time windows. The resource constrained shortest path subproblem is solved by a label setting algorithm. 12 authentic data sets from two of Europe's major airports are used for testing. Optimal solutions are found for 11 of the test instances. Keywords: Manpower allocation, crew scheduling, vehicle routing with time windows, synchronization, column generation, Branch-and-Price, time window branching, set partitioning, set covering, integer programming.