The Formulation Of Large-Scale Crew Pairing Problem Without Initial Solution And The Optimization Of Solving Method

Airline planning is a main part of the airline company’s daily operational management, it directly determines the management level of an airline company. Crew pairing plays the same role in airline planning. What a better crew pairing offers not only reduced costs, but also balanced use of human-resources. Exploring various methods to solve crew pairing problem to get better and faster solution is meaningful.In this paper we try to explain the complexity of crew pairing problem without initial solution and give the optimization design of its’solving method. First we describe the information flow and time constrains of the problem then model it as a set partitioning problem. We introduce the column generation method and give the optimality prove of its SP’s solution. Applying penalty function help us to get an initial solution. We use heuristic search to explore some good initial columns for the algorithm which improved the quality of our solution, meanwhile we design a generation strategy for sub-problem to get better convergence. Another work is to optimize the solving method of slack problem by present a new best combination of using Newton barrier method and dual simplex method. After this we design a duty-based formulation which heuristic search and penalty function help us to get initial solution. Then we apply Dantzig-Wolfe decomposition trying to optimize our formulation, break the problem into two stages. We optimize the duty-based method by adding airport flow-balance constrains. This method allows us to get a duty set with minimum costs and could be covered by legal pairings. The computational experiments we conducted is based on some actual data offered by a domestic airline company. We change parameters to get better illustrations for all methods, the experiment shows that the speed and quality of the solution is acceptable, which proves the method is feasible in a sense. At last we state the drawbacks of this research and potential improvement of this method.