摘要
航空机组人员排班是航空公司运营调度过程中的重要环节,现有文献对该问题的研究主要集中在排班成本的最优化以及排班结果的鲁棒性等方面,但排班计划对机组人员工作状态的影响尚未在已有的研究中得到充分的讨论与重视。因此,本文借鉴了最早提出于车辆路径规划等问题中的一致性概念,通过对华东地区某大型民营航空公司真实航班数据的分析,提出一类新型的、具有重要价值的一致性规范约束。该类约束具体体现在生成排班计划过程中,对人员工作班次的一致性与人员过夜城市的一致性做出要求。基于我国民航规定与真实航班数据,本文构建了航空公司机组人员排班的基础模型以及包含一致性约束的拓展模型。求解算法采用了列生成算法框架,并且在针对该框架中复杂子问题的求解提出了一种新的基于动态规划的启发式算法。数值实验结果表明,该求解算法可在短时间内求解大规模的机组排班问题,求解结果显著地提升了机组排班计划的一致性,这对航空公司实际机组排班计划的制定具有重要的价值。
With the improvement of living standards in recent years,the Air Transport industry plays an increasingly important role in social and economic activities.According to a report from the Civil Aviation Administration of China(CAAC)published in 2019,the civil aviation industry has achieved a total transport turnover of 120 billion tonne-kilometers,a year-on-year increase of 11.4%,and passenger traffic reached 611 million passengers,a year-on-year increase by 10.9%.At the same time,airliners now face even bigger challenges.As a service industry,crew members in any airline are no doubt one of the most important strategic resources.Therefore,airlines around the world have been striving to make good use of these resources for a higher service level and at the same time their competitiveness in the industry.However,when dealing with aircrew scheduling,airlines come up with plans mostly based on the objectives such as minimizing total operational cost or operating stability.They fail to take into account the aspect of consistency for crew members.Therefore,to better ensure the safety and efficiency of airline operations,this work pays more attention to the physical and mental conditions of the crew members when generating the aircrew schedules.Several crucial factors,such as the balance of the crew′s work and rest time and night-stay location changes are taken into consideration,largely for flight safety.Aircrew schedule is a complex task,which is affected by the distribution of airbases and regulatory requirements stipulated by the Civil Aviation Administration.Based on the classical aircrew scheduling model,this work proposes a set of new consistency constraints to ensure adequate rest and good working conditions for the crew members.The main task is to formulate a working plan utilizing minimum crew members and meeting both the legal and feasible requirements,as well as the newly proposed consistency requirements for work-rest shifts and night-stay locations.More specifically,the proposed four requirements are as follows.First,the legal requirements specify that the schedule plan must meet the regulations stipulated by the Civil Aviation Administration.The feasibility requirement refers to that all duties must be assigned to at least one crew.The shift consistency requirement is to ensure consistency in the working hours of crews during the duty period.The night-stay location consistency requirement is to reduce cases where crew members have to rest overnight in an unnecessarily large number of different cities during the tours.Airline crew scheduling problem is one of the most difficult operational research problems in the airline industry because of a large number of constraints and large feasible solution space.We propose a mixed-integer programming model for the problem,but exact methods are inefficient and exhibit huge computation time even on instances of relatively small size.Hence,taking the newly proposed two types of consistency constraints into consideration,we use a heuristic algorithm bases on column generation combined with a novel dynamic programming method.The master problem of the model is modeled as a set cover model,and the subproblem constructs a feasible unit scheduling plan with negative reduced cost based on the dual price obtained from the master problem.Besides,the scheduling plan must satisfy the legality constraints and consistency constraints.Specifically,we convert the before and after dependencies of flights to a directed acyclic graph and regard the flight and duty time required by flights as resources.The subproblem is considered as a problem to find the longest path in a directed graph with resource constraints.Considering the consistency criteria,we calculate the number of work-rest shifts and night-stay locations during the path search process.We exploit a novel dynamic programming algorithm to solve the subproblem.In detail,an adjustable variable concerning the time dimension when defining the DP states is proposed,which can greatly reduce the computational time and memory space.Several self-adjusting parameters borrowed from the Adaptive Large-neighborhood Search(ALNS)algorithm are also used when handling the night-stay location consistency.Extensive experiments are conducted to assess the performance of the algorithm.We conduct computation experiments on real data from a large private airliner in Eastern China.Firstly,we evaluate the correctness of the proposed model and the efficiency of the algorithm by comparing the results with those obtained by the state-of-the-art commercial solver(CPLEX).The algorithm presents a high-quality solution for the large-scale aircrew scheduling problem with consistency.Besides,we conduct a sensitivity analysis about the consistency constraints.Regarding the number of crew members,it increases after the consistency constraint is added,but the cost is within an acceptable range.The new plan retains the benefits of the original plan while being more reasonable and taking into account the health issues of the crews.Experiments show that the model and algorithm can effectively solve the large-scale crew scheduling problem on real data,and help airlines to develop crew scheduling plans.The algorithm is shown to be efficient and robust for the aforementioned two different scenarios and thus providing great managerial insights to airliners for their crew-scheduling plans.
作者
马弘
沈倪
朱靖
夏佳楠
MA Hong;SHEN Ni;ZHU Jing;XIA Jianan(School of Engineers,Zhejiang University,Hangzhou 310015,China;School of Management,Zhejiang University,Hangzhou 310058,China)
出处
《管理工程学报》
CSSCI
CSCD
北大核心
2022年第6期191-204,共14页
Journal of Industrial Engineering and Engineering Management
基金
国家自然科学基金资助项目(71821002、71201141)。
关键词
机组排班问题
一致性规范约束
列生成算法
动态规划算法
Airline crew scheduling problem
Consistency constraints
Column generation
Dynamic programming
