关键词: 机组排班, 机组配对, 列生成, 启发式算法

Abstract: Labor costs are the second largest expense in the total operating costs of airlines (fuel comes first). Taking China Southern Airlines, China Eastern Airlines, Air China, Spring Airlines, Juneyao Airlines, and China Express Airlines as example, the six airlines’ employee compensation costs accounted for about 20% of total operating costs in 2022, according to their publicly released annual reports. The two biggest controllable factors that lead to aircraft delays and flight cancellations are the lack of personnel to connect flights and backup crew members. The cost caused by overnight crew risk (some airports are susceptible to extreme weather or non-agreed hotels often have crew checking out 10 minutes beyond the agreed chargeable time point, requiring airlines to pay for an additional half a day or one day) is also a significant cost expense for airlines, with an airline company with 50 aircraft spending more than 100 million yuan per year on crew accommodation costs. Therefore, studying the optimization of airline crew scheduling considering overnight risk will effectively improve the current situation where airlines are less profitable or even lose money. The crew scheduling problem is usually decomposed into the crew pairing problem and crew rostering problem. Since the crew pairing problem is the first stage of crew scheduling and is more important to the overall quality of final crew scheduling, this paper focuses on the crew pairing problem. There is still a gap in the literature on crew scheduling studies that consider overnight risk, and there is a lack of studies based on China’s civil aviation industry regulations on duty period limitations, flight time limitations, rest periods, and the simultaneous consideration of airlines’ operating costs and overnight risk. Therefore, we study the crew pairing problem considering the overnight risk to minimize the crew pay cost, deadhead penalty cost, overnight cost, and penalty cost of overnight risk. Under the requirement of meeting all regulations (such as crew duty time and rest time), covering all flights, and ensuring the optimal utilization of all resources, a high-quality pairing plan is generated. Strengthening the management of crew members can not only effectively reduce costs but also improve the operation of flights. Reducing the number of overnight stays for crew members and the risk of overnight stays plays an effective guarantee role in their normal performance of flight tasks and has a significant impact on effectively improving consumer satisfaction.
We model the crew pairing problem as a set-partitioning model (containing the master problem and subproblem models, respectively). We design a heuristic algorithm based on column generation to solve the model. The column generation algorithms are widely used to solve large-scale integer programming, where the optimal solution to the linear master problem is obtained by iteratively solving the master problem and subproblems. The CPLEX software solves the linear master problem, and the dual variables are obtained and passed to the subproblem. The subproblem is solved by the labeling algorithm, where the parameters, expansion rules, and dominance rules of the labels are designed according to the characteristics of the problem. The purpose of solving the subproblem is to obtain the columns with a negative reduced cost and add them to the master problem model. The master problem and the subproblem are solved iteratively until the column with a negative reduced cost cannot be found after solving the subproblem, and the optimal solution of the linear master problem is obtained. If the obtained solution is an integer solution, the integer solution is the optimal solution for the problem. We suppose the optimal solution to the linear master problem is a non-integer solution. In that case, we use a heuristic branching strategy to obtain a high-quality integer solution to the problem by invoking column-generated solving at each branch node. Finally, the efficiency of the solution algorithm is verified by testing multiple sets of different scale instances.
The experimental results show that the optimal solution or a high-quality integer solution can be obtained within 20 seconds for small-scale instances. The optimal solution or better integer solution can be obtained within 2 minutes for larger-scale instances. By analyzing the influence of the overnight risk on the solution results, it can be seen that the consideration of overnight risk can effectively reduce the number of overnight stays at airports in risky areas, which can not only effectively improve the operation of flights but also help enterprises reduce the corresponding human resource costs, provide a scientific basis for making actual operational decisions, improve efficiency and achieve the goal of cost reduction and efficiency. Airlines should consider the risk of crews staying overnight at off-base airports in advance when making flight schedules and can use the algorithm proposed in this paper to assess the risk of crews staying overnight in advance and then make adjustments to flight schedules to reduce the risk of crews staying overnight.

Key words: crew scheduling, crew pairing, column generation, heuristic algorithm