Research On Integrated Optimization Of Airline Crew Scheduling

With the continuous development of China's aviation,its operating organization has gradually shifted from extensive management to refined management.The crew scheduling is an important part of the airline's operation management plan,and its preparation work will gradually become an automated and intelligent mode.The majority of existing crew scheduling is set up manually resulting in low efficiency.The quality of the results often depends on the experience of the staff and was difficult to adjust.Moreover,The existing automatic methods have a larger decision granularity and a little lack of refinement,making it difficult to adapt to increasingly complex operations management requirements,it is more difficult to achieve efficient and personalized scheduling organization.Therefore,it is of great significance to to study a set of efficient methods for crew scheduling problems of airline for improving the efficiency and reducing the redundant work of management personnel,reducing the cost of operation,and also giving a new idea for personnel scheduling areas.Considering the complex and difficult rules of China's airline crew scheduling problem,the numerous and sophisticated objectives and the limitations of traditional stepby-step optimization methods,this paper innovatively research the crew scheduling problem from the perspective of integrated optimization.The main research work is as follows:(1)Analysis and solution strategy research of airline crew scheduling problem.Firstly,the characteristics of the flight crew scheduling plan are analyzed,and the dimensionality reduction strategy of the problem decision unit is proposed to solve the bottleneck of the difficulty in characterizing the rules of personnel collocation and the difficulty in constructing the integrated solution framework.Secondly,on the basis of comparative analysis of the applicability of arc-based network flow models and pathbased set coverage models,a solution strategy based on task-unit matching modeling is proposed.(2)In the background of the multi-base and uncertain initial state,propose an integrated optimization model of airline crew scheduling based on the match of duty and crews.Firstly,a precise description method of the ride-on situation is proposed,and a depth-first search strategy is combined with pruning rules to preprocess the decision unit.Secondly,on the basis of detailed analysis of the cost structure,optimization objectives,and calculation and expression of constraints,a class assignment model based on taskunit matching is established.Among them,for the optimization goals,the calculation methods of fixed costs,boarding costs,and resource aggregation costs are analyzed and designed,and a linearization method based on "mean estimation" is proposed to describe the personnel balance goals;for the constraints,the flight connection network is analyzed in detail Constraints such as construction,task generation in the dimensionality reduction pre-processing stage of the decision-making unit,and task-person matching in the upper decision-making stage are processed and characterized.(3)Developed an efficient method based on column generation.In view of the characteristics of the assignment likewise model with exponential number of decision variables,the column generation technique is used to decompose the problem into a global restricted main problem and multiple local pricing sub-problems.In order to overcome the difficulty of increasing the column density caused by the integrated optimization strategy and prone to degradation,a time decomposition strategy of singleday assignment and rolling optimization is proposed to control the problem scale and refine the problem decision granularity.Aiming at the difficulties of high complexity of sub-problems and low solution efficiency caused by personnel collocation rules,a variety of strategies including local search and precise search mixing,pruning based on lower bound estimation and multi-threaded concurrent calculation are proposed to accelerate algorithm convergence.(4)Finally,conduct one experiment with real-world data from a China's airline company.The results show that the method developed in this paper can obtain highquality solutions to complex combination optimization problems that consider personnel collocation rules such as large-scale unit scheduling in a reasonable time.