【作者】 孙宏；

【导师】 杜文；

【作者基本信息】 西南交通大学 ， 交通运输规划与管理， 2003， 博士

【摘要】 航空公司的生产计划编制是一项非常艰巨而重要的工作，其实质在于通过周密的组织和精确的计划，实现各生产资源要素的优化配置，它的质量和效率关系到生产运营的安全、正常和效益。本文在深入分析当前国内各航空公司生产计划工作现状的基础上，选择了飞机排班计划作为研究课题，通过系统分析飞机排班工作的流程和要求，提出了描述飞机排班问题的数学模型。由于该问题是多目标、非线性的，因此寻找一种统一的能够适应各种具体要求，并且满足工程应用需要的多项式算法存在理论上和技术上的困难。为此论文在借鉴手工编制排班计划经验的基础上，将一个具体的飞机排班问题，归结为三种典型排班模式中的一种，即：基于飞机调度指令要求的排班问题，基于飞机使用均衡要求的排班问题和基于最少需用飞机数的排班问题，对于每种典型的飞机排班模式，在对次要的约束条件进行简化、松驰的基础上构造出相应的能够满足工程应用要求的启发式算法，并分析了算法的复杂性。该项研究为研制飞机排班决策支持系统软件奠定了理论基础。 论文的主要创新工作在： 1．根据当前国内航空公司的运营组织模式特点，以及飞机排班工作的实际需求，提出了描述飞机排班问题的数学模型，并通过将一般形式的飞机排班问题归结为三种典型的飞机排班模式，构造出相应的启发式算法，填补了国内在此领域的研究空白。 2．在解决基于飞机调度指令要求的飞机排班问题时，本文提出的分阶段指派算法较好地克服了标号算法的缺陷，该算法能普遍地应用于处理类似的固定工件排序问题。 3．在解决使飞机均衡使用的飞机排班问题时，本文利用航班节的网络模型将原问题转化为一个使目标函数最小的航班节编组问题，在此基础上构造了一个模拟退火算法。 4．在解决最少需用飞机数要求的飞机排班问题时，本文将寻找航班节衔接方案问题，描述成一个二部图的匹配问题，进而通过解两个二部图的最小权最大匹配，寻找需用飞机数最少的飞机调度方案。更多还原

【Abstract】 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.更多还原