An optimization model for the simultaneous operational flight and pilot scheduling problem

This paper describes and solves the operational pilot scheduling problem for one day of operations. The problem consists in simultaneously modifying, as necessary, the existing flight departure schedules and planned individual work days (duties) while keeping planned aircraft itineraries unchanged. It requires the covering of all flights from one day of operations with available pilots while minimizing changes in both the flight schedule and the next day's planned duties. The newly constructed personalized duties must not exceed the maximum duty duration. Flight precedence constraints, coming from existing fixed aircraft itineraries, must be respected as well. The problem is mathematically formulated as an integer nonlinear multicommodity network flow model with time windows and additional constraints. To solve the problem, a Dantzig–Wolfe decomposition combined with a branch-and-bound method has been used. The master problem comprises the flight-covering constraints and a new set of flight precedence constraints. Subproblems consisting of time-constrained shortest-path problems with linear time costs are solved by a specialized dynamic-programming algorithm. The proposed optimization approach has been tested on several input data sets. All of them have been successfully solved in very short computational time.