Study On Recovery Of Passengers Itinerary

With the rapid development of China's civil aviation,the airline irregular operations has became a critical social problem.Flight operations recovery is dealing with rescheduling the operation resources such as time slot,aircraft,crew and passengers during the occurrence of disruption,such that the following flight could operate as previous plan.The quality of flight recovery is very crucial to the degree of the delay problem and related cost.Due to the complexity of the issue,the recovery problem has been divided into different steps.In this paper,we are conducting an extensive research on the passenger recovery part,the results are as followed:We propose a heuristic for solving the LP relaxation problem based on row-and-column generation.The passenger recovery problem is basically an enormous set partitioning problem with additional restrictions,the classic column generation technique shows low efficiency because it has to solve tens of thousand pricing sub-problems every iterations.We propose a dualloop method to address this difficulties.In the inner loop,we only reschedule some passengers itinerary,and the outer loop will reorganize the inner problem.This algorithm has been tested under different delay levels,passenger load factor and passenger scale.The experimental result shows that,this algorithm gains much better result compared with classic column generation methods.For difficult problems,compared with full passengers recovery column generations,our method's solving speed increases by almost 2 times,with very similar optimal outcomes.We also propose an algorithm combining local search technique and branch & pricing method to solve IP.This method will define a local area based on the current LP result and best IP result,generate a set of new variables,and conduct the local search using classic branch and bound.And then instead of the conventional path branching method,we branch the nodes based on a relaxation network flow model.Moreover,an independent thread has been used to run the genetic algorithm,which shares the same buffered IP solutions pool to interact with the branch and price algorithm.The experimental result shows that,this method could significantly reduce the number of cancelations and delays,and it could obtain encouraging results within the time limit especially for large size problems.