Research On The Airport Task Assignment And Disrupted Flight Recovery Of Airline Scheduling Problem

This dissertation studies the problem of airport task scheduling and interrupted flight recovery in aviation scheduling.Among them,the problem of airport task scheduling is to assign tasks with special properties to a limited number of shifts,and the completed task will produce corresponding benefits.Due to the diversity of the properties of airport tasks and shifts,the specificity of constraints,which make the problem is a very complicated combinatorial optimization problem,and belongs to NP-Hard problem.And disrupted flight recovery problem is due to bad weather,aircraft failures,airport close and other external conditions of uncertainty often resulted in some flights are delayed or even cancelled,the original flight schedules unfeasible,which requires operation center to recovery the interrupted flights quickly.Interrupted flights caused great inconvenience to passengers,and brought huge economic losses to airline,which is the key of airline to improve the competitive ability of the industry and the quality of service,the interrupted flight recovery problem is made to solve this problem.Interrupted flight recovery problem belongs to large-scale integer programming problem,which has a real-time requirements,and complex variables and constraints.So far,the research results that can meet the raquirements of airline practice are very few.Based on the high complexity of the above problems,this paper deeply explores the problem from the perspective of problem characteristics,mathematic model,algorithms respectively.The main research results of the paper are discussed below:(1)Based on the characteristics of the problem,the interge programming is established to meet the various constraints between tasks and shifts,the goal of the problem is maximum benefit frome excuted tasks by shifts.CPLEX optimization software is used to solve this mode.Based on the Dantzig-Wolfe decomposition principle,the original problem is decomposed into the main problem of the set segmentation model and the subproblem of the shortest path.The branch-and-pricing algorithm(combination of column generation algorithm and branch-and-bound algorithm)is adopted to solve the decomposed problem.In addition,in order to accelerate the solution speed of subproblem,heuristic algorithm is proposed for problem solving firstly,get some high quality column will be added to the main problems,then use the Label Setting Algorithm to solve andbased on optimality criterion theorem to judge whether the current solution for the optimal solution timely.To the four factors influencing the objective function values: task number,flight number,the task properties,and shift working hours are tested respectively,and the test results are analyzed and summaried.(2)The objective is minimize the recovery expense of the interrupted flight recovery problem,and an improved time-space Network algorithm is presented,gives the dominant criterion,effectively reduce the amount of the combination of the flight route,implement in time and space for aircraft routes to track at the same time,and try to adopt a variety of scheduling policy,including the flight delay,flight cancellation,maintenance cancellation,aircraft exchange and punishment measures such as the airport aircraft imbalances in the end.Based on the improved time-space Network,the mathematical optimization model is established and CPLEX optimization software is used to solve this mode.By testing the actual example of the airline,it is shown that the “Improved Time Space Network” algorithm proposed in this paper can rapidly reduce the solution space,and CPLEX can solve the problem in a short time.(3)Based on Dantzig-Wolfe decomposition principle,the set partition mddel of Restricted Linear Master Problem and the shortest path model of sub-problem of interrupted flight recovery problem are established respectively.And column generation algorithm is adopted to solve the problem.In order to reduce the number of iterations between the master problem and sub-problem,improve the algorithm's efficiency,a good initial solution for the problem is structured,then use CPLEX solves the master problem obtain dual variables,the dual variables as cost reduction coefficient to the objective function of sub-problem.It is difficult to solve the sub-problem of the shortest path problem with the general dynamic programming algorithm,this paper adopts a MultiLabel-Setting Algorithm to solve the problem.Finally,the correctness and effectiveness of the proposed algorithm are verified by the test of various scale examples,and the good performance and advantages of the proposed algorithm are also verified.