Crew recovery optimization through disruption analysis and deep learning driven column generation

Abstract

Thanks to globalization, new travel opportunities and economic development have increased the interest in the aviation industry and air transport. The increase in the number of passengers and compliance with the regulations on passenger rights make transformation inevitable for the aviation industry and airlines. Airlines are reorganizing and managing all their resources in line with this transformation. The most critical resources of commercial airlines are the crew and aircraft, which together with passengers are key components of operational efficiency. Unforeseen events such as bad weather conditions, aircraft malfunctions and crew absence may result in inefficiency in operations and thus in the utilization of aforementioned resources. These events are called disruptions. As disruptions such as delays are the primary and fundamental factor in passenger satisfaction and the airline's financial conditions, aviation companies devote valuable resources to analyzing disruptions and taking necessary actions. Actions known as recovery actions are the ones decided by the airline operations control center to overcome problems in the execution of plans due to disruptions. The crew recovery problem is a complex optimization problem in the airline industry that involves scheduling and assigning crews to flights while taking into account various constraints such as legal regulations, crew availability, and cost. Several methods have been proposed to solve this problem, including heuristic and metaheuristic algorithms, integer programming, and constraint programming. It is a type of optimization problem that aims to choose the best recovery strategies to overcome crew disruptions. The main goal is to find the minimum cost combination of assignments that solve the problems related with crew plans while considering all constraints, especially flight time limitations. One popular method for solving the crew recovery problem is the column generation algorithm, which involves generating and adding columns to the problem's LP relaxation until an optimal solution is obtained. Other optimization methods include simulated annealing, genetic algorithms, and ant colony optimization. However, despite the various optimization methods proposed, the crew recovery problem remains a challenging and computationally expensive task due to the large number of variables and constraints involved. Furthermore, real-world crew recovery problems are dynamic and uncertain, requiring the ability to adapt quickly to unexpected events. This is where machine learning (ML) can play a crucial role in developing an optimization method with AI support. By leveraging machine learning algorithms, we can learn from past data and experiences to make informed decisions and generate optimized solutions quickly and efficiently. Recovery strategies can be realized by using actions known as recovery actions. Especially during the preparation of recovery models, more effective strategies are produced by using the actions learned from the past disruptions as inputs in the model. The main motivation behind using actions as input is that learning-based approaches have the potential to generate more effective algorithms for large-scale and difficult optimization problems by inferring insights from historic datasets. Especially with the learning process, important points that people may miss in the solution process become easily noticeable and increase the success of the recovery process. In this study, recovery actions provided by a customized deep learning (DL) model are used as input to the proposed optimization model, in which the objective function minimizes the total assignment cost of crew. Crew disruption data including some of the flight disruptions from a large scale airline is analyzed. Based on the analysis of the data, features are generated and recovery actions are extracted. The recovery actions are used as label and supervised learning methodology is used to train a customized deep learning model. Our hypothesis is based on the assumption that deep learning can provide needed insights in order to solve the problem in a shorter time while preserving the optimality at a certain level. The fundamental insight that we derive from the deep learning model is the recovery actions, which will be used while generating new columns. The actions are used in order to configure the columns faster than the classical column generation by either directly modifying the column itself or narrowing down the solution space. The resource or resource groups including crew and aircrafts are filtered according to the information provided by the deep learning. This makes it possible to search for new columns in a narrower solution space, which makes the search time shorter compared to the classical column generation techniques. The primary goal of the study was to develop a model that balances solution quality and speed. Results indicate that the proposed method outperforms the reference model in terms of runtime while maintaining an acceptable level of optimality. This approach can be valuable for airline companies looking to efficiently address crew recovery challenges. Moreover, it contributes to the existing literature by introducing a new mathematical model and approximation method, demonstrating the potential of deep learning and optimization techniques for addressing complex aviation sector optimization problems and offering valuable insights for future research in the field of crew recovery.