A variable neighborhood search approach for the crew pairing problem

In this paper we propose a Variable Neighborhood Search approach for the Crew Pairing Problem. This problem consist in assigning a crew to each of the flights of a flight scheduling, in a predefined time horizon. The main objective of the problem is to minimize the number of cabin crews needed to cover all the flights subject to a set of constraints. These constraints are real-life specifications regulated by airline rules and other operational challenges. In particular we propose a General Variable Neighborhood Search algorithm to tackle the problem and we have tested our approach over a real instance provided by an airline and over an additional set of generated instances. The obtained results have been compared with a previous multi-start approach in the state of the art and with the initial solution provided to the algorithm which, in the case of the real instance, was the solution in use by the airline.