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

摘要： 加强机组人员管理,可以有效改善航班的运行状况。研究考虑过夜风险的机组排班问题,同时考虑了机组薪酬成本、置位惩罚成本、过夜住宿成本及过夜风险惩罚成本。基于现实约束及相关规定,建立集合划分的数学模型,采用基于列生成的启发式算法求解该整数规划问题。在求解时,首先构造初始解,通过CPLEX求解主问题;其次,采用标签算法求解子问题,根据研究问题的特征,设计标签扩展规则和占优准则。通过迭代求解主问题和子问题后,针对非整数解采取启发式分支策略获得整数解。最后,在不同规模下进行基于实际数据的实验,实验结果表明:1)验证了基于列生成的启发式算法的有效性;2)通过求解时间可知,本文提出的算法可以在2分钟内获得最优解或高质量的整数解;3)通过分析过夜风险对求解方案的影响可知本文设计方案可有效减少机组在风险地区机场过夜的次数。本研究不仅可以改善航班的运行状况,还可以帮助企业减少相应的人力资源成本,为企业制定实际运营决策提供科学依据,提高工作效率的同时也实现了降本增效的目标。

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