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.

Electronic Notes in Discrete Mathematics
Eduardo García Pardo
Eduardo García Pardo
Associate Professor

Miembro fundador del grupo de investigación GRAFO, cuya línea de investigación principal es el desarrollo de algoritmos para abordar problemas de optimización, temática sobre la que versa la Tesis Doctoral del investigador y en la que se enmarcan sus publicaciones más destacadas.