| With the growth of transportation demand,the flight schedules of airlines are designed more and more tightly.However,unforeseen factors such as bad weather and equipment failure will frequently disrupt the normal execution of them.When the normal flight schedule is disrupted,rapid recovery is one of the top priority affairs for airlines.The passenger itinerary recovery problem is one of the most important parts of the airline recovery process.Passengers,as the main service objects of the airline,are the decisive factor in the airline’s profitability.Providing passengers with matching high-quality recovery plans can effectively reduce the losses of airline,improve passenger satisfaction,and restore the reputation of the company.The currently used methods of artificially assisted decision-making have been difficult to meet the needs of the passenger recovery problem.The realization of intelligent decision-making through optimized algorithms is an urgent need in civil aviation.Based on the actual operating scenarios of airlines,this paper studies the passenger itinerary recovery problem modeling and optimization algorithm.The main work and results include the following aspects:(1)In order to be able to effectively match the application requirements,starting from the actual needs of the airlines,considering the PNR indivisibility constraint,the transfer flight seat-sharing constraint,and the passenger multi-itinerary connection constraint,a multi-objective problem model is constructed.The optimization goal of this model is to maximize airline revenue and passenger satisfaction.Multiple optimization goals are handled by assigning different weights to different goals.(2)The data is preprocessed by constructing a passenger itinerary recovery graph to represent the passenger itinerary recovery process.An optimization algorithm based on variable neighborhood search is proposed.In order to obtain the initial solution of the problem,a backtracking search algorithm based on a tabu list is proposed.In the process of optimization,three different neighborhood structures are designed to construct neighbors,and a method of randomly selecting neighborhoods to generate solutions for local search is used to avoid falling into local optimal.Experimental results based on different test data show that this method can achieve good optimization results in a short time.(3)To further optimize the passenger itinerary recovery problem,the problem is decomposed into the main problem and sub-problems based on the column generation method.The integer programming model of the restricted master problem,and the subproblem model are established respectively.Then a branch and price optimization algorithm is proposed to solve the integer solution.In order to solve sub-problems,a greedy search based on node pretreatment algorithm is proposed.The restricted master problem is solved using the mathematical programming solver CPLEX.The experimental results show that the algorithm can obtain better results than the variable neighborhood search optimization algorithm within the similar time period,and it is very close to the theoretically optimal solution,and the most deviation is only 3.34%. |
