关键词: 航班环, 列生成算法, Floyd 算法, KM完美匹配

Abstract:

Tail assignment is the basic work in the airline manufacturing operations process,but it directly impacts the costs of the airline operating and the safety of flight. In this article,firstly,we found the integer programming model of flight-loop construction aiming to maximum the maintenance opportunity and made use of the combination of the column generation and Floyd shortest path algorithm to generate the flight-loop of multimaintenance base. Secondly,we used program by Matlab of branch-and-bound to obtain 0-1 optimal solution of programming model. Then,adopted the KM algorithm to complete the perfect match of the aircraft and flight-loop and realized the dynamic allocation of the flight-loop. Finally,through analyse of an instance we validated the correctness and efficiency of the method.

Key words: flight-loop, column generation algorithm, Floyd algorithm, KM perfect match