Research On Crew Pairing Problem

The crew pairing problem is one of the fundamental elements in strategic planningof airline companies. However, faced with various kinds of regulations, the crew pairingproblem is a highly constrained and complex problem, which makes it extremelydifficult to find optimal solutions. Optimization modeling is a scientific and efficientway to solve the crew pairing problem, and will help to reduce crew cost whileimproving performances of airline companies.Crew pairing is the process of matching crew members with flights, and used todepend mainly on manual labor. With the fast development of airline industry andexpansion of airline networks, the manually-depended way finds its difficulties inmeeting the operation requirements of modern airline companies. Therefore, an efficientdecision support system that can deal with large-scale application problems is greatly inneed.Based on a review of researches on the crew pairing problem, a single-based crewpairing optimization model is proposed using mathematical programming method. Thismodel aims to minimize the total costs related to crew pairing process, and besides frombasic constraints,“dead-heading” is taken into account in this model. To better solvethis model, we introduce a heuristic column generation algorithm, which is proved to behighly efficient.So far, crew pairing is mostly modeled as a deterministic problem, not concerningabout flight delays. However, the airline industry is currently under great pressure toimprove its on-time performance, so researches on robust models and solutions are ingreat need. Based on the analysis of flight delays, a robust crew pairing model withconsideration of stochastic disruptions is proposed in this paper. A heuristic columngeneration algorithm is introduced to solve the model. Finally, simulations are given toevaluate the performance of the model. Computational tests show that our model couldsignificantly increase robustness of crew pairing problem.In this paper, Mixed Set Programming (MSP) is used for the first time to study thecrew pairing problem. Quite different from mathematical programming, MSP supportsglobal reasoning over a mixed domain of real numbers, integers, booleans, and sets. Taking advantage of its powerful model building capacity, we propose a crew pairingoptimization model based on mixed set programming, and by combining OR algorithmwith industrial logic of crew pairing process, we design optimizing strategiescharacterized by simplicity, accuracy and efficiency. Computational test shows thatproblems of real-world size can be solved efficiently within reasonable time. Moreover,we compare the mixed set programming model with mathematic programming model fromdifferent aspects, such as theoretical basis of programming methods, model structure,and optimization efficiency, to better understand the characteristics of the two models.