《航空系统管理》由会员分享，可在线阅读，更多相关《航空系统管理（35页珍藏版）》请在金锄头文库上搜索。
1、摘要摘要民航机组排班问题是人员安排类型中经典的 NP-hard 难题，涉及到较多的限制条件和优化 因素。在航空公司的运营费用中，人力资源支出的费用占据了很大的比例，近年来更是成 为继航油费用之后航空企业第二大成本支出。因此，合理地科学地进行机组排班，将有利 于充分利用航空公司人力资源，降低运营成本，提高航空公司的竞争力。本文在分析国内外研究的基础上，首先详细论述了机组排班的主要流程，分析了机组 配对、人员分组和机组指派等关键环节和技术。比较现有算法如遗传算法、模拟退火算法、 蚁群算法、粒子群算法和人工神经网络算法的可行性可靠性，选择符合实现要求的遗传算 法，对编码方式、概率值和初始种群的产生进
2、行改进调整，使得更便于系统实现。接下来 对排班问题的机组配对、机组指派环节建立数学模型，设计系统中所需要的数据结构和数 据库中的表结构，将算法和数学语言描述的解决方法用计算具体实现。最后总结了有待改 进的地方，提出改进设想。关键词:机组排班，机组配对，机组搭配，人员指派，遗传算法 第一章绪论第一章绪论 1.1 课题研究背景和意义课题研究背景和意义现今社会发展日新月异，对问题的探索研究已经从简单的可行性更进一步的要求了快 速、高效。这不仅要实现我们的工作学习的基本需要，而且在资源利用上也要求达到精益 求精，如对时间、经济、空间的投入。而民用航空运输便是其中一个典型例子，它作为一 种不可或缺的现代
3、交通方式，在运输体系中发挥着重要作用，民用航空运输产业与国家经 济增长率息息相关，在经济建设发展中具有不可替代的地位。在快节奏高效率的今天，对 于民航运输，各大航空公司也不再是单纯的满足国民正常的出行需要。为了相互增强航空 公司的竞争力，更要求在资源的利用与消耗上达到最低，在民航飞行运营中占据主导地位 的运营成本大致包含有以下几个方面：航油消耗、客机的运行及维护成本、机组人员薪资 待遇和相关基础建设成本。如何节约人力成本与时间成本自然成为重中之重，而一直备受 广大计算机学者关注的就是怎样将各个航班合理调度，总结开发出一种快速、高效的调度 方案。因此，巨大的经济效益背后通常是航班合理调度过程中微
4、小的优化，这也对航空运 输业的安全性和高效性有着不可忽视的影响。纵观全球，各国也普遍意识到航班的合理调 度是减少航空业运营成本、增加经济收益的重要途径之一。作为发展中国家，我国民航业由于起步比较晚，相比于其他国外发达国家信息化程度 较低。通过对我国民用航空业现状的调查研究，结合具体实际应用需求，本文对航班调度 的基本算法进行了研究与分析，并探索出具有可行性的实现方案和具体步骤。执飞人员工 作调度不仅要符合中国民航总局的法律法规，也要贴合各个航空公司内的各项规章制度， 而且还需要分析机组人员、航班、飞机、航线变动等突发事件的处置情况，客观来讲任务 较为复杂繁重，通常一些细微的调整会牵扯到整个后续
5、计划的变动。结合机组排班的数据 量庞大与限制条件诸多的现状，若单纯凭借人工方式执行调度，其中工作量不仅非常巨大， 而且要求排班人员必须有一定的工作经验。伴随着各大航空公司日益扩大的运营规模与日 趋完善管理模式，虽然借助于计算机系统辅助机组排班这项新技术已经有了些许发展与进 步，有的航空公司甚至引进了国外的计算机排班系统以增强竞争力，但是国内航线较之国 外航线情况更为复杂，所引进的机组自动排班系统并不能完全迎合国内各大航空公司的需 要。国外的诸多大型航空公司均是基于多枢纽航线结构来运行，每日的航班计划大同小异， 而我国各大航空公司的运营策略依旧是基于单枢纽航线结构：各大航空公司的航班主要依 靠一
6、个基地机场调度，基地机场采取点对点的航线连接其它城市。因此基地机场就成为了 飞机的维护保养基地，同样也是不同航段飞机和机组人员的主要驻地。但日常的飞行计划 会受不同因素影响而产生较大的差异，计算机系统排班时需分析的约束条件较复杂，现有的国外研究成果并不完全适用于我国航空运输业的具体情况，也不能完解决国内机组排班 的具体实际困难。因此，完善航班机组排班系统对航空公司而言是至关重要的，对航空公 司的正常运作与经济效益有着决定性影响。 1.2 课题研究现状课题研究现状航班机组调度是各个航空公司面临且亟需解决一个关键性的技术难题。同样机组的运 营成本也成为了仅次于航油费用的第二大运营资金成本。对于航班
7、机组排班系统研究的兴 起要追溯至上个世纪七十年代，从事该问题探索分析的以一些国际性团体为主。近半个世 纪以来，人们通过利用基于遗传算法与神经网络等多种途径试图解决关于机组排班调度的 问题。在航空运输业日新月异的今天，越来越多的机构和团队把目光转向到了该问题的探 索与研究，并取得了阶段性的进展。广义上我们将当前从事与研究航班机组调度系统相关 的人员分为三大类：一为国际性研究团体，其中的主要代表有国际航空运输协会（IATA ，International Air Transport Association） 、国际运筹学联合会的航空公司工作组（AGIFORS, Airline Group for I
8、nternational Federation of Operation Research）等。二为科研机构和院校， 比较著名有美国麻省理工学院交通运输研究中心（Center for Transportation Studies ） ，乔 治亚工学院，瑞典的应用数学研究所 （ITM, The Swedish Institute of Applied Mathematics） 等。他们的研究取得的成果基本涵盖了航空公司的运营与收益管理、资源的控制与优化等 诸多项目。而关于机组调度这一关键范畴，他们主要将精力投入航班机组排班算法上。三 为各个航空公司中的技术开发部门还有众多面向服务于航空公司的计算
9、机领域公司：如 Sabre , Mercury Systems, Lufhansha 航空公司等。相比于院校、机构与团体，他们的工作重 心则更加倾向于系统的实用性，并在实践中研发出了基于解决航空公司机组调度这一难题 的具体方案与较为成熟的系统，积累了大量丰富的实践经验，如 Mercury System 的 Nova Crew Planning 以及 Lufhansha 的 Lisline 等。而我国自上世纪九十年代末民航业迅速崛起，在机组调度方面的研究进展也是突飞猛 进。目前，航班机组排班系统的重要性不言而喻，但大部分的航空公司依然在使用或改进 从国外引进的管理系统，国内研究的成果过于侧重于理
10、论，在实践应用中缺乏创新，如南 方航空公司和东方航空公司的飞行队信息管理系统。但结合我国自身情况，引进国外的航 班调度控制系统具有相当的局限性，应用于我国各大航空公司并不稳定。因此，针对于我 国国情航班机组排班的理论研究并加以应用推广，便具有了深远的意义。 1.3 文章的组织结构文章的组织结构文章有一下几个部分组成:第一部分绪论，介绍机组排班的课题背景和意义、课题的国内外研究现状。第二部分分析航班飞行排班的具体过程，拆解机组自动排班问题关键，介绍机组配对 相关规则和机组成员指派相关规则。第三部分研究机组调度中所引用的常见算法，分析比较各算法并选择最终算法。介绍 遗传算法的特点与缺陷，并在此基础
11、上改良算法。第四部分设计航班机组排班各个阶段的算法后建立数学模型，研究航班机组排班理论， 结合算法所涉及到的初始种群生成策略，对求解过程完成优化设计。第五部分描绘航班机组各个子系统的流程图，分析其数据结构，最终通过计算机将改 进的遗传算法加以具体实现。第六部分归纳了全文的内容，总结并对下一步的研究进行了展望。第二章第二章 航班飞行排班问题分析航班飞行排班问题分析 解决机组排班问题的出发点为查找出一个涵盖全部航段的可执行勤务组集合，而后按照 要求指派飞行人员与乘务人员到合适机组，并且要求机组相关人员执行勤务时所消耗的时 间、经济成本为最小。在优化组合的问题中较为典型，具有 NP-hand 复杂度
12、。相比于其他 类型的人员规划问题，航班机组自动排班所需要分析的方面更多，内容涵盖面更广也更复 杂。需要分析以下三个层面：其一是根据各个民航公司的规章与条例，能够合理安排规划所有机组人员到可飞行的 具体航班中，并确保包含全部航班无缺。其二在确保航空机组排班可执行且正确合法的基础上，要求飞行航班的使用消耗最小， 降低执行过程的时间消耗和相关工作人员的工资成本，最终达到减少飞行用油与人员安置 等诸多费用的目的。其三需要综合分析机组排班的平衡性与抗变换性。平衡性分两点：一是航空公司机组 人员的工作与休息时间要保持平衡；二是所往返不同航线的收入支出要保持平衡。抗变换 性主则是指在遇到恶劣天气，必须对客机
13、班次进行调整，机场工作者的应急工作是否满足 实际情况的变化，并根据实际情况进行方案的调整。 2. 1 航空运输调度相关流程航空运输调度相关流程航空运输生产过程由地面的运输生产组织、飞行组织保障和指挥调度等工作与空中的 运输飞行两大部分组成。分机航班、航行时间、载客量、飞行效率以及飞行线路有效率等 因素都能影响到航线计划，它主要是为完成飞机运输工作而制定的计划。与之对应的是航 班计划，它主要涉及飞行线路、飞机型号、航班和飞行时间以及起飞降落时间，主要是为 实现空中运输工作而制定的方案，在它的基础上来进行空中运输任务的安排。因此，合理 规划航空运输对于高效完成运输生产任务与提高运输生产质量，有着至
14、关深远的意义。航 空运输调度的相关流程可以看到大致分为三个部分：第一步先通过对历史信息的数据采集 与分析，预测各航空公司所属所有航线运量。得出这些数据后，筛选出一种或者多种运量， 在预测出相关方法后将结果优化，并将不同的结果相比较，从而计算得出在预计的时间范 围对空中运输任务的预期。第二步根据不同地域的航线分布和距离与各个航空公司所预测 的航线载客量和预期市场竞争情况，结合飞机机型安排生成航班计划表。第三步进行飞机 调度阶段，结合航空公司机组人员（飞行人员与勤务人员）的工作休息情况，安排规划飞 行任务与地勤保障，最终完成具体航班机组飞行。本文重点分析与研究的内容为机组排班。它包括机组配对(Cr
15、ew Pairing)和机组人员指 派(Crew Rostering)，在机组配对部分，主要是指根据各个航空公司的相关要求并结合己有 的航班计划，编排相关机组航段，对于达到要求的飞行时间的航段集合(不含机组人员)生 成一个勤务，并将包含全部航段(去除重复)的勤务最终生成出勤务表。在机组人员指派部 分，主要是指根据不同机型和航线等各种不同需求生成达到机组飞行要求的机组人员（飞 行人员与勤务人员）名单，最后按照人员的工作休息情况合理排班调度。 2. 2 机组配对概况机组配对概况 机组配对(Crew Pairing)又称勤务工作团队，构成部分是分属不同时空范围的飞行路径， 它的整个运行范围都属于勤务
16、组内部的基站。一般来说，机组配对的时间跨度为 15 天， 最多不超过 25 个航段。机组配对具体分两个步骤，先要筛选出一个包含全部航段机组配对 的集合，而后在这些集合中匹配成本最低的机组配对结果。 通过对飞行时间进行分析，首先将飞机的航段组合为勤务，这是实现将所有航段的勤 务整合起来的前提。所谓勤务，就是在不违反航空管理制度的前提下，严格依照飞行线路 和起飞降落时间的相关要求，针对每个机组在当天的飞行时间所做出的计划安排，它是构 成机组的最小单位。图 2.1 勤务示意图在图 2.1 中，D (t)为勤务（duty）时间，把开始飞行某一个勤务的准备时间设为起始点， 把飞行完毕该勤务之后的勤务交替设为终止点。D (t)=勤务准备时间 b+航线时间f+经停时间s+d变异概率计算染色体各基因位和并与当前基因位求积是否为第一位基因以机组配对数目求模以求模后的值替换当前基因位的值以求模后的值替换当前基因位的值以机组人员数求模图 5. 10 机组指派染色体变异流程图第六章总结与展望第六章总结与展望 本文重点分析了航空企业机组排班问题根本论点与常规计算方式，在研究对比各类现 有计
