Airline Tail Number Assignment Problem: Model And Algorithm

Airline operational planning is very hard and important work, which quality and efficiency is concerned with the safety and benefit of airline operation. The essence of this work is optimizing the configuration of primary airline resources by precise organizing and planning. Based on analyzing the status of domestic airline operational planning system, this dissertation determines the study subject as Tail-Number-Assignment (TNA) Problem. Firstly, a 0-1 Integer programming mathematical model is constructed to describe Tail-Number-Assigning work happened in domestic airline, since the problem is NPC, a unified polynomial algorithm which satisfies engineering requirement is unavailable. Illuminated by the practical experience, a specific TNA problem is classified into one of three typical TNA modes: TNA based on fleet dispatching commands, TNA based on fleet balance application, TNA based on minimum fleet requirement; Secondly, by simplifying and relaxing some minor constraints, corresponding mathematical models and heuristic algorithms are reconstructed for each typical TNA mode; Finally, computing complexities are discussed. All these research sets a primary foundation for developing Airline Tail Number Assigning System software.The primary innovations are as follows:1. On the basis of operational characters of domestic airline by now, a mathematical model describing TNA problem is constructed, and by classifying a specific TNA problem into one of three typical TNA modes, corresponding heuristic algorithms are reconstructed. This research supplies a domestic gap in this field.2. When solving the TNA problem based on fleet dispatching commands, a Stage-Assignment algorithm is build to overcome the defect of FIFO algorithm, which can be widely applied to cope with fixed job scheduling problem.3. When solving the TNA problem based on fleet balance application, aflight pairing network model is build, by which the primary problem transferred to a directed path decomposition problem to minimize target function, and a simulated annealing algorithm is constructed.4. When solving the TNA problem based on minimum fleet requirement, a bipartite graph describing flight-pairing-link property is constructed, by which the primary problem is transferred to two weighted bipartite matching.