Algoritmo GRASP para el problema de programación de tripulaciones de vuelo

Abstract

La industria aérea se caracteriza por estar en constante expansión, incrementando el tamaño de su flota para cada vez abarcar mayor mercado. En este crecimiento, se ve afectada la complejidad y la magnitud de la programación de tripulaciones de vuelo, las cuales son uno de los mayores problemas de planeación de la industria. Por esta razón, las compañías han invertido recursos para resolver este problema, y contratan software de proveedores externos a un alto costo. Se utilizan rigurosos modelos matemáticos y algoritmos para resolver este problema. Este artículo propone una metodología de solución para el Crew Pairing Problem (CPP) basada en la metaheurística GRASP y una variación de este aplicando una estrategia de filtrado. Se presentan resultados computacionales para instancias construidas a partir del itinerario comercial de una aerolínea colombiana de mediana escala. Se compara el desempeño entre los algoritmos propuestos y la operación histórica de este itinerario, además se analiza el beneficio de la estrategia del filtrado. Como trabajo futuro se propone crear un conjunto de instancias que estén disponibles al público en general para comparaciones justas

The airline industry is characterized by being in constant expansion, increasing the size of its fleet to cover more and more market. In this growth, the complexity and magnitude of the flight crew scheduling are affected, which are one of the biggest planning problems in the industry. For this reason, companies have invested resources to solve this problem, and they hire software from third-party vendors at a high cost. Rigorous mathematical models and algorithms are implemented to solve this problem. This article proposes a methodology solution for the crew pairing problem (CPP) based on metaheuristics. GRASP and a variation of it applying a filtering strategy. Computational results are presented for built instances from the commercial itinerary of a Colombian medium-scale airline. Performance is compared between algorithms proposed and the historical operation of this itinerary analyzes the benefit of the filtering strategy. As future work, it proposes to create a set of instances that are available to the public for fair comparisons.