（计算机应用技术专业论文）分阶段机组排班方法的研究与实现.pdf

中国民用航空学院硕十学位论文 摘要 机组排班是航空公司信息化建设的重要课题，是机组资源合理利用的重要方面，机 组成员的飞行任务安排是否合理关系到航班的飞行安全和服务质量。机组排班问题是一 个非常复杂的多目标规划问题，具有n p 难的特点。 在课题组前期对排班问题模型和遗传算法的研究基础上，经过深入地分析航空公司 排班工作实际，进一步明确了分阶段排班的思想，将排班问题分解为机组生成和机组分 配两个阶段。本文首先实现了基于c s 结构的机组资源管理与排班原型系统的开发，为 分阶段排班方法的深入研究建立了软件平台；对前期以人员工作负荷均衡为目标的单目 标模型进行了改进，建立了基于机组人员工作负荷均衡和机组人员协调性好的多目标模 型。同时对影响机组协调性的因素进行了深入的分析，根据人员技术、时间、性格等因 素的搭配互补原则给出了机组生成的方法，并采用模糊优选动态规划方法对生成的机组 进行了协调性评价，将较优的机组使用遗传算法分配到最合适的航班。 本文采用面向对象的方法，在n e t 平台上实现了分阶段的排班方法，完善了机组 排班系统的软件功能，使用航空公司实际数据迸行试验，与原型排班方法结果进行了对 比分析，在人员工作负荷均衡和机组协调性两方面都取得了比较满意的结果。经过对分 阶段排班方法进行全面的研究，本文在机组排班问题的理论和实践两方面都做了更深入 的探索。 关键词：机组排班，分阶段方法，机组生成，协调性，模糊优选 中国民用航空学院硕士学位论文 第二章基于c s 结构的机组资源管理与排班原型系统实现 2 1 系统分析 2 1 1 系统业务流程分析 排班系统的目标是完成各种情况下飞行人员和乘务人员的航班派遣与管理工作。机 组资源管理的核心是航班计划和人员资源。航班计划包括固定航班和临时航班，机组资 源包括登缎嚣基础近儿年来增酒嵯琳费鏊型堕鬻嘿每两燃峰滢测妻剐崾绺j 机组 根 据目前国内航空公司的实际情况，围绕机组排班的优化问题， 以机组人员工作负荷均衡为基本目标，创建了机组排班的数学模型1 ，并采用遗传算法 进行对排班优化算法的仿真实验，为解决排班算法问题奠定了一定的理论基础。 但机组排班是个非常复杂的多目标规划问题，具有n p 难的特点。航班任务执行的 安全性与服务质量的好坏不仅体现在机组人员工作负荷均衡一个方面，执行同一航班的 机组人员之间搭配的协调性，在很大程度上决定了航班的飞行安全，而乘务组人员之问 搭配的协调性则决定了航班的服务质量，因此排班过程中人员的分组问题成为了排班中 必须研究的一个难点。 1 3 2 研究内容 课题组前期的研究工作主要是基于机组人员已经分配合理的基本条件，以时间均衡 为目标建立的机组排班算法模型和仿真实验，机组生成与排班的过程未能完全实现软件 化，因此，本文在前期理论研究的基础上，结合航空公司机组资源管理的实际情况，主 要在以下方面开展了进一步的研究和开发工作： 1 在前期理论研究的基础上，开发基于c s 结构的机组资源管理与排班原型系统，实 中国民用航空学院硕士学位论文 行，也可以在服务器进行，而且具有较强的事务处理能力，能实现复杂的业务流程。为 此，c s 模式的数据分布处理的特性可以使飞行组和乘务组分布于不同的客户端进行排 班工作，工作可以在客户端完成，减轻了服务器端的工作负荷。 2 1 3 功能分析 服务器 图2 2 机组排班系统体系结构 从机组排班的流程可以看出，排班原型系统是对机组人员信息，机组任务信息进行 管理。机组排班系统主要由两大部分构成：机组资源信息管理( 乘务人员信息管理、飞 行人员信息管理) 、机组排班管理( 机组生成、机组分配) ，如图2 3 所示。 早早早 露蓐 ，一一t 、 p ：= = - = _ _ ： i | 、堂塑嘎一， 图2 3 系统功能构成图 排班原型系统开发主要依据实际的排班流程，根据航班计划机型的定员要求逐一地 将需要的机组人员安排到每一航班中。机组排班过程由机组生成和机组分配两个阶段构 成，原型系统开发过程中机组人员的搭配是按照航空公司机组排班的基本原则进行的。 1 航班信息的管理 航班计划是航空公司切生产活动的基础和核心，是机组排班的基础。航班计划是 中国民用航空学院硕士学位论文 由航空公司生产计划部门制定并管理，在实际系统中要设计一个接口，直接将航班信息 导入机组排班系统。本系统就设计了航班信息管理数据接口( 但没有与航空公司运营系 统连接) ，为实现机组资源管理与排班提供基本数据支持。 航班信息的主要内容如下： 航班号：一个航班号代表一个航班。 班次：即航班频率，指航空公司一天中在同一航线上有多少个航班； 班期：指某一航班在一周中的哪几天执行； 班次和班期是排班中重要的时间要素。 机型：指执行该航班所使用的飞机型号，不同的飞机类型有不用的飞行性能。 机型信息在排班中的作用是提供每一种机型配备的最低机组人员数量限制。排 班时为航班排多少飞行人员、排多少乘务人员都是按照机型最低定员要求进行。 离港压0 港时刻：指飞机离开基地航站与返回基地航站的时问。 起飞站到达站：航班的起飞点和终点。 经停点：航班执行过程中中途经过的航站，经停点可以是一个，可以是多个， 甚至可以没有。航班可以用起飞点+ 经停+ 终点表示。 2 机组资源信息管理 图2 4 机组资源信息关系模型 中国民用航空学院硕士学位论文 机组资源信息管理对所有机组资源有关信息进行管理，包括乘务员和飞行员基本信 息、技术信息、休假培训信息、飞行时间信息、人员经历记录、飞行品质信息、机型信 息、人员关系等，各种信息之间关系如图2 4 所示。同时也提供各类资源信息查询功能， 并提供生成报表和其它文档功能。 3 机组排班管理 机组排班是机组排班系统的核心模块，包括对航班计划( 静态航班和动态航班) 进 行机组生成和机组分配，并能够让用户根据实际情况对系统自动排班的结果进行手工调 整。 图2 5 系统总体用例图 在系统开发的初始阶段，根据系统功能和业务流程，给出系统总体用例图，如图2 - 5 。 用例图是用来描述系统功能、系统使用者以及各用例之间的关系，可以描述系统的静态 使用情况。在下文系统模块设计与实现中，将对某些主要用例进一步细化，给出比较详 细的设计过程。 2 1 4 系统开发流程 在上一小节中分析了系统的功能，并使用u m l 的方法建立了系统的总体用例，从 用户需求的角度描述了系统，本节将介绍系统的开发流程。 系统的开发过程使用r u p 流程框架，将开发过程划分为开始、细化、构造、和移 交四个阶段，按u s ec a s e 模型、用户体验模型、设计模型、数据模型、实施模型以及部 署模型来描述和管理整个系统的设计与开发“。同时，将每个阶段分解成不同的开发增 量进行迭代式开发。按照前面总体用例，系统共确定三个开发增量，由于用例系统登陆 和用户管理包含在前几个用例中，所以放在第一个开发增量中，以确保流程的完整性。 同时，自动排班贯穿开发的整个过程，因此，自动排班这个用例，是同时在增量一和增 量二中迭代开发的。具体每个增量所包含的用例如图2 6 所示i 每鎏。翟 鍪 中国民用航窄学院硕上学位论文 2 2 系统设计 2 2 1 静态模型设计 隰弭巴 i 登录系统i 卜亡i - 1 更新用户信息j l 退出系统 i 瓷溽信息管理l 刁f i 自动捧班 f ，、 音i e 慝嚣震1 l 任务书首理l 理 图2 6 系统增量模型 系统静态模型的建立是使用面向对象方法进行设计的基础，对系统的静态结构进行 分析与设计，用于对应用领域中的概念以及系统实现有关的内部概念建模，它将行为实 体描述成离散的模型元素，但不描述与时间有关的系统行为o “。静态建模包括类、对象 和包的建模。 类是任何面向对象系统中最重要的构造块，是一种重要的分类器( c l a s s 谢e r ) ，用 来描述结构和行为特性的机制。类是一组具有相同属性、操作、关系和语义的对象的描 述。 经过对机组排班系统的进一步分析和理解，从上节用例和系统描述中的名词可以分 析出系统中至少有如下的重要类：航班( s c h e d u l e df 1 i g i l t ) 、乘务员( c a b i n 缸s i s t a n t ) 、 飞行员( p i l o t ) 、排班方法( a m e t l l o d ) 、持久存储类( p 哪i s t e i m ) 、结果与报表( a r r i k s l l l t 壮df o 彻) 、辅助类( a l l x i l i a r v ) 。 其中，航班是排班系统中的核心。根据航班计划，对乘务人员、飞行人员进行合理 的任务分配和管理，形成最终的飞行机组航班计划表。排班方法是实现机组排班算法的 类，包括排班过程中使用的方法和参数。持久存储类为商业对象的持久存储提供了支持， 实现从数据库文件中读写对象属性的操作。结果与报表类主要是对排班结果进行存储和 修改，还包括各种格式报表的设计和打印。辅助类包括临时变更记录、人际关系、历史 飞行记录、机型定员要求这些类。由于乘务员、飞行员、其它人员等拥有一些共同的属 性和方法，所以通过建立基类p r e s o u r c e ( 人员资源类) 并进行派生而得到乘务员、飞 行员、其它人员类。 除此之外，用面向对象的方法丌发信息系统在考虑与用户交互的时候定义用户界面 7 中国民用航空学院硕士学位论文 类，采用图形化界面，因此还要定义系统用户界面类。 由于排班过程中类比较多，想要识别出类之间的关系不是很容易，这种情况下要将 类进行分类，分层次描述系统的各个方面，更容易使系统模型清晰明了。包图的作用在 于将那些语义相近并趋于一致变化的类组织起来归于不同的包，方便地理解和处理整个 模型。同时也便于轻松地控制这些元素的可见性，设计良好的包是高内聚、低耦合的， 并且对其内容的访问具有严密的控制。 可将系统中的类分为三个包：实体包( e n t i t v ) 、用户界面包( g u i ) 和数据处理包 ( d p ) 。每个包又包括不同种类的类，如图2 7 。 岛仁 图2 - 7 系统包图 e n t i t y 包中包括系统中的实体，包括航班类、飞行人员类、乘务人员类和其他人员 类，d p 主要指排班算法，其中包括排班方法类、永久存储类和结果和报表类，g u i 包 包括所有的用户界面类。g u i 包依赖于d p 包和e n t i t v 包，而e n t i t v 包又由d p 包进行 维护，所以也是依赖关系。 1 实体包( e n t i t v ) 中包括类p r e s o 眦e 类( 人员资源类) 、乘务员( c a b i n 加s i s t 柚t ) 、 飞行员( p i l o t ) 、其它人员类( o t h e f ) 和航班类( s c h e d u l e df 1 i 曲t ) 和辅助类( a m x i l i 盯y ) ， 辅助类包括排班需要的其他一些信息，例如机型信息，航班最低定员要求等。e n t i t v 包中类及其关系如图2 - 8 所示。乘务员、飞行员、其它人员的基类是人员资源类。 图2 - 8e n t i t y 包中的类及其关系 中国民用航空学院硕士学位论文 2 g u i 包中包括系统中所有的用户界面类。包括登录界面类、主菜单界面类，各个功 能模块界面类，下一级窗口类依赖于上一级窗口类。 3 d b 包中包括了排班方法类( a r rm e t h o d ) 、排班结果和报表类( a r e s u l ta l l df o 珊) 和持久存储类( p e r s i s t c n c e ) ，如图2 9 。排班结果和报表类是依赖于排班方法类和 持久存储类，而排班方法类的实现又依赖于持久存储类。 2 2 2 动态模型设计 图2 9 d b 包中的类及其关系 动态建模是对系统的动态结构进行分析与设计，建立相应的动态模型。动态模型描 述了系统随时问变化的行为，这些行为是从静态模型中抽取的系统瞬间值的变化来描述 的【2 4 】【矧。动态模型主要是建立系统的交互图和行为图，交互图包括时序图和协作图；行 为图则包括状态图和活动图。 状态图( s l a t ed i a 掣a m ) 可以描述一个对象在生命周期中拥有哪些状态，该对象在 这些状态下的行为，以及什么样的事件会导致状态发生改变。 时序图( s e q u c n c ed i a 掣a m ) 可以描述对象之间是如何进行交互和通信的。时序图 中的主要焦点是时间，可以实现一组对象为了实现某一功能是如何彼此发送和接收 一连串消息的。每个用例都能够用一个时序图来描述，而且如果需要，可以分别对 用例中的功能建立时序图。 协作图( c o l l a b o f a t i o nd i a g r a m ) 也可以描述对象之问是如何交互的，但协作图中的 主要焦点是空间，更注重对象之间的空间关系。 活动图( a c t i v i t yd i a 擎a m ) 也是一种显示交互的方法，但它的主要焦点是工作，描 述用例要求所要进行的活动及活动问的约束关系，有利于识别并行活动。 本文根据各个模块的性质，使用不同的动态视图来描述系统的各个功能，使得系统 设计模型更加清晰。 1 机组资源信息管理 机组资源信息管理包括乘务人员信息管理和飞行人员信息管理。主要对人员信息进 行管理，包括对人员档案、技术信息进行管理，它是机组排班的必要前提。机组资源信 息管理是对人员信息进行增加、删除、修改和查询。 爱翠一 中国民用航空学院硕士学位论文 以飞行员信息插入功能为例，给出航班插入功能的时序图，如图2 1 0 。 nn 簧* 、r - 一r 一 黜l 燮i 鬯鲨驾 图2 1 0 插入功能时序图 乘务人员信息和飞行人员信息管理功能模块的设计与航班模块功能类似，不再重复。 2 机组排班管理 本文首先使用了航空公司排班的原型方法进行了机组排班模块的设计。 机组排班模块是系统最重要，也是最复杂的模块。它根据一段时期内的固定航班计 划为飞行组人员和乘务组人员进行排班，排班的依据是航空公司实际排班的流程。由于 人员排班工作是根据航班信息的要求来选择合适的人员的过程，过程中有很多人员属性 判定、航班属性判定的工作，所以在这部分主要使用活动图进行功能设计。乘务人员和 飞行人员的活动图如图2 1 1 和图2 1 2 所示。 图2 1 1 乘务人员排班活动图 1 0 中国民用航空学院硕士学位论文 图2 1 2 飞行人员排班活动图 乘务人员排班流程和飞行人员排班流程中都有共同的一个动作：取得具有飞行资格 的人员。由于排班过程中要注意的规则和要求很多，过程很复杂，根据航班取得人员时 要考察人员的很多属性，要使得过程更加清晰明了，可以对活动图中某些动作再进行分 解，使用分层的方法一层一层地描述系统。 图2 1 3 和图2 1 4 是根据航班取得能够担当飞行任务的乘务人员和飞行人员的活动 图。 图2 1 3 取得能够派遣飞行任务的乘务员图2 1 4 取得能够派遣飞行任务的飞行人员 中国民用航空学院硕士学位论文 2 3 系统实现与分析 2 3 1 功能实现与算法分析 图2 1 5 为航班信息管理模块的界面图，包括航班所有信息显示，个别航班加载，航 班操作功能。 图2 - 1 5 航班管理功能界面图 系统主要实现了对固定航班进行自动排班，图2 1 6 和图2 1 7 为排班界面。 排班之前由用户选定需要排班的航班，航班确定后根据各个航班的要求进行排班。 通常排班量比较大，资源使用较多，系统有一段响应时间，这里使用提示框提示用户系 统正在排班过程中。 原型排班实现过程非常复杂，主要的困难在于分配过程中人员与人员的匹配，即在 挑选完机组中一名人员后，后继该怎样挑选其他人员与这名人员进行匹配成机组，人员 与人员之间怎样匹配才是完美搭配? 根据飞行员与乘务员工作的性质不同，设计不同的 算法进行排班。 1 飞行人员排班算法 由于原型方法排班的目标主要是人员飞行负荷均衡，所以时间为第一考虑要素，同 时，飞行人员工作的技术要求比较高，排班时更加注重人员之间的配合性，强调人员各 种属性的互补，例如飞行能力强的要与飞行能力弱的进行互补，年轻的要和年龄大的搭 配等等。可以将这些因素综合考虑，对这些因素设置一定的优先级，排班时首先要挑选 符合优先级高的因素的人员1 。 另外飞行组人员数量较小，飞行的主要责任在于正驾驶和第一副驾驶，所以这二者 中国民用航守学院硕士学位论文 的搭配应当作为重点。 本文在原型排班系统中主要考虑了以下几个因素，并设置各因素的优先级如下： 人员关系 行政职位因素 飞行能力 年龄，英语能力 算法步骤如下： ( 1 ) 根据航班机型特性和航线要求，选择飞行量最少的具有飞行资格的正驾驶作为 机长； ( 2 ) 从具有飞行资格的副驾驶中删除与已经选择的正驾驶关系不好的人员： ( 3 ) 挑选与正驾驶行政职位因素互补的人员保留转下步，若无全部保留转下一步； ( 4 ) 挑选与正驾驶飞行能力因素具有互补性的人员保留转下一步； ( 5 ) 挑选与正驾驶年龄差异在一定范围的人员进行保留转下一步，若无全部保留转 下一步； ( 6 ) 挑选英语能力互补性最好的作为第一副驾驶； ( 7 ) 选择与已排好人员的关系较好的人员作为机组其他人员。 2 乘务人员排班算法 乘务人员的工作方式比较简单，注重的是个人的属性与航班属性的配合和个人的服 务质量，只要人员之间没有关系不好的情形，就比较容易完成飞行任务。 算法步骤如下： ( 1 ) 确定乘务长h a 根据航线品质要求从具有飞行资格的乘务长中确定一个飞行量最少的作为乘务 长： ( 2 ) 确定头等舱乘务员e a ( 仅限有头等舱的航班机型) 从具有飞行资格的e a 中删除与h a 关系不好的人员，其他保留： 根据航线方言和外语要求选择f a ，所有的f a 之间的关系必须保证没有不好； ( 3 ) 确定公务舱或经济舱乘务员 从具有飞行资格的乘务员中删除与h a 关系不好的人员，其他人员保留； 根据航线方言和外语要求选择乘务员，所有的乘务员之间的关系必须保证没有 不好。 中国民用航空学院硕士学位论文 2 3 2 结果分析 图2 1 6 使用原型排班法进行飞行人员排班 圈2 1 7 使用原型排班方法进行乘务人员排班 系统实现了航班、机型等基本信息的处理，对机组人员、乘务人员档案信息进行管 理，为航空公司各类人员提供各种资源查询功能，可生成报表、打印等。以航空公司实 际排班为原型对航空公司固定航班进行排班，提供对排班结果的手工调整功能。 本文对排班系统主要模块飞行员自动排班模块进行分析，以天津国航2 0 0 4 2 0 0 5 冬 春航班( 9 3 0 一1 0 2 8 ) 一个月的航班为依据进行排班( 只排航班机型最低要求人员数) 。 现列出航班c a l 0 3 4 的排班结果，如表2 1 所示。 从表2 1 可以看出，对航班c a l 0 3 4 一个月的计划来说，符合此航班要求的正驾驶 有0 0 0 0 0 2 ，0 0 0 0 0 6 ，o 0 0 0 1 7 三人，能与其搭配的副驾驶员有o o 0 0 1 1 ，0 0 0 0 1 5 ，o o 0 0 0 9 ， 0 0 0 0 1 3 ，0 0 0 0 1 5 ，0 0 0 0 1 l 六人，这个结果完全符合实际情况中一段时间内航班搭配几本 固定的要求，这样可以比较好的保证航班飞行安全。但是，从结果中，0 0 0 0 0 2 号正驾驶 只和0 0 0 0 1 1 号副驾驶进行搭配，而0 0 0 0 0 6 号正驾驶可以和0 0 0 0 1 5 ，o o 0 0 0 9 ，0 0 0 0 1 3 ， 1 4 中国民用航空学院颅士学位论文 o o 0 0 0 8 ，0 0 0 0 1 1 号副驾驶搭配，o o 0 0 1 7 号正驾驶和o 0 0 0 1 5 和o o 0 0 1 1 副驾驶搭配，可 以看出人员在固定时间内固定搭配的数量不均衡。 表2 1 航班c a l 0 3 ，4 排班结果 航班号排班号 日期 正驾驶 副驾驶 c a l 0 3 ，432 0 0 5 9 - 3 0o 咖0 20 0 0 0 1 1 c a l 0 3 ，482 0 0 5 1 0 - 10 0 0 0 0 60 0 ( ) 0 1 5 c a l 0 3 “1 42 0 晒1 0 20 0 0 0 0 60 c 1 0 0 0 9 c a l 0 3 ，42 2 2 0 ( ) 5 1 0 3 0 0 0 0 0 60 啪1 3 c a l 0 3 ，4 2 72 0 ( ) 5 1 0 - 40 0 0 0 0 6 0 0 0 0 0 8 c a l 0 3 ，4 3 22 0 d 5 1 咐 0 0 0 0 0 20 啪1 1 c a l 0 3 ，4 4 0 2 0 0 5 1 0 60 0 咖60 0 0 0 1 5 c a l 0 3 ，4 4 6 2 0 0 5 1 0 _ 70 0 0 0 1 70 0 0 0 1 5 c a l 0 3 45 12 0 8 5 1 0 80 0 0 0 1 7d 咖1 1 c a l 0 3 45 72 0 0 5 1 0 - 90 0 0 0 d 60 0 0 0 1 1 c a l 0 3 46 52 0 0 5 1 0 1 00 0 0 0 0 60 咖1 3 c a l 0 3 ，47 02 0 0 5 1 m 1 10 0 0 0 0 6删9 c a l 0 3 ，47 52 0 0 5 1 0 - 1 20 0 0 ( ) 0 20 0 0 0 1 1 c a l 0 3 ，48 32 0 日5 1 0 1 30 ( ) 0 0 0 60 0 0 0 1 5 c a l 0 3 ，4 8 9 2 0 0 5 1 m 1 4 0 0 0 0 1 7 0 0 0 0 1 5 c a l 0 3 49 42 0 q 5 1 0 1 50 0 0 0 1 7 0 0 0 0 1 l c a l 0 3 ，4 1 0 0 2 0 ( 1 5 1 0 1 6 0 0 0 0 0 6 0 1 ) 0 0 1 1 c a l 0 3 41 0 82 0 0 5 1 0 - 1 70 ( ) 0 0 0 6o 0 1 3 c a l 0 3 41 1 32 0 0 5 1 0 1 80 0 0 0 0 60 【1 0 0 0 9 c a l 0 3 h1 1 82 0 0 5 1 m 1 90 0 0 0 0 20 0 0 0 1 1 c a l 0 3 41 2 62 伽6 1 0 2 00 ( ) 0 【) 0 60 0 0 0 1 5 c a l 0 3 41 3 22 0 0 5 1 0 2 10 0 0 0 1 70 0 0 0 1 5 c a l 0 3 “1 3 72 0 0 5 1 0 - 2 20 0 ( ) 0 1 70 0 0 0 1 1 c a l 0 3 ，4 1 4 3 2 0 0 5 1 m 2 3 0 0 0 0 0 60 0 0 0 1 1 c a l 0 3 41 5 12 0 【) 5 1 0 - 2 40 0 0 0 0 60 ( ) 0 0 1 3 c a l 媳谴 1 s 6 2 0 0 5 1 0 2 50 0 0 0 0 60 1 ) 0 0 0 9 c a l 0 3 ，41 6 1 2 0 0 5 1 0 - 2 6 0 0 0 0 0 2 0 0 0 叭1 c a l 0 3 ，41 6 92 0 0 5 一l o - 2 70 0 0 0 0 60 0 0 0 1 5 c a l 0 3 ，4 1 7 5 2 0 0 5 1 0 2 80 0 0 0 1 70 0 0 0 1 5 这种原型排班方式的主要目标是时间均衡，对各种规章制度进行约束是在排班过程 中实现，图2 1 8 和图2 1 9 给出各飞行组的人员搭配情况和飞行时间图。从这个结果中 很明显地得出，排班工作量很不均衡，产生这种结果的原因是排班算法是基于简单筛选 的方法，考虑的因素增多后，能够筛选的人员规模急剧缩小，甚至出现人员不足的情况。 同时，算法中将人员搭配作为约束，增加了约束条件的个数，再加上任务分配严格的时 间约束，在强制处理这些排班条件的时候，肯定会影响人员负荷均衡，图中可以看到1 1 号以后的正驾驶员、9 号以后的副驾驶飞行量很少，排班结果很不合理。 中国民用航空学院硕士学位论文 而且虽然在排班过程中简单考虑了人员之间的匹配问题，但这种从局部的角度进行 人员挑选的方法通常不能综合的考虑各种因素，人员匹配效果也不理想，如表2 2 。 营2 0 0 葫l o o 0 正驾驶e 行时间图 l35791 人员 图2 - 1 8 正驾驶飞行时问图2 1 9 副驾驶飞行时间 图中横坐标为人员，纵坐标为人员的总飞行量。 袁2 - 2 人员搭配情况 人员编号行政职位出生f 1 期年飞行时问英语等级飞行能力飞行等级人员关系 0 0 0 0 0 211 9 5 9 1 11 0 012 正驾驶一般 0 0 0 0 1 101 9 7 4 1 11 4 114 副驾驶一般 0 0 0 0 0 611 9 6 7 1 17 852 正驾驶好 0 0 1 501 9 7 9 1 11 4 742 副驾驶好 0 0 0 611 9 6 7 1 11 3 952 正驾驶一般 嘎1 0 0 0 9o1 9 5 7 1 15 632 副驾驶 一般 0 0 ( 岫0 611 9 6 7 - 1 11 3 952 正驾驶一般 0 0 1 3o1 9 7 7 1 18 423 副驾驶一般 0 0 ( 1 0 0 611 9 6 7 1 11 1 l52 正驾驶一般 o o 嘧01 9 6 5 1 19 543 副驾驶一般 0 0 0 0 1 7l1 9 6 2 1 18 951 正驾驶好 0 0 0 0 1 501 9 7 9 1 11 4 7 4 2 副驾驶 好 0 0 0 0 1 711 9 6 2 1 18 951 正驾驶 一般 0 0 0 0 1 l01 9 7 4 1 11 4 114 副驾驶一般 针对以上问题，下面将致力于改进系统中最重要模块一自动排班模块的排班方 法。并提出一种分阶段的排班方法，将本课题组已有的理论方法运用到机组排班系统的 开发中，从全局的角度进行排班，不仅要考虑人员工作负荷均衡，还要重点考虑人员组 搭配的问题，对机组生成方法和机组分配方法进行分析研究，提出机组协调性的评价模 型，使用模糊优选理论模型进行求解，使自动排班工作结果更符合实际情况的要求。 中国民用航空学院硕上学位论文 第三章分阶段机组排班方法与实现 上一章在课题组的理论基础之上，实现了基于c 届结构的机组资源管理与排班原型 系统。其中排班以人员工作负荷均衡为目标将已生成的机组分配到相应的航班，生成的 机组只按照实际的排班流程使用选择匹配的方法完成，没有系统地分析机组的生成方法 和机组协调性问题，导致排班结果脱离实际。 本章将针对机组生成方法和机组协调性评价进行研究，对课题组的通用排班模型进 行改进，使用分阶段机组排班方法解决排班问题，并在已建立的软件平台上进行理论验 证，以飞行人员排班为例给出该方法的实现过程。 3 1 排班问题模型的改进 本课题组前期已经以人员负荷均衡为目标建立了机组排班模型“”“。，考虑到对飞行 人员负荷的考察主要是时间均衡，除了很特殊的航班外，起降次数与飞行时间是有关联 关系的，所以对于飞行负荷只需考虑飞行时间即可。同时，鉴于对飞行事故产生原因和 目前比较流行的c r m ( 机组资源管理) 研究报告0 7 “”1 的分析，在模型中加入了机组搭 配评价最优的目标 假设对t 天内n 个飞行任务进行排班，共有m 个飞行人员。 飞行员的实际飞行时间与理想飞行时间相近度可以表示为： e 2 壶剥”) 2 】a ( 3 1 ) m 为飞行员数目，啦为t 天内第f 个飞行员的总飞行时间，口j + 为t 天内飞行员平均 飞行时间。 机组搭配的协调程度可以表示为： e 4 专著驴( w 彤- ，岛) 3 2 ) 其中，占l ，9 2 ，岛组成分配到任务，的机组g ， 盛为第f 个人员的特征向量，昏= ( g f l ，摩2 ，孙) ； 跏：第f 个飞行员的第七个特征值，i = l ，2 ，彤；七= 1 ，2 ，j ； 强：人员组占和第，个航班的搭配协调性值，其中o s ，s ，o s gs g 为航班个数，g 为最大搭配组数。 则目标函数为： 肘伽，j保证飞行员飞行任务均衡 1 7 中国民用航空学院硕十坐位论文 朋如尼保证机组搭配协调性最好 建立的关于飞行员排班问题的数学模型是一个多目标、非线性的o 1 整数规划模型， 直接求解该模型以获得一个关于机组排班问题的最优解存在以下困难： 1 关于非线性目标函数的处理 公式( 3 1 ) 是非线性的，虽然可以利用决策变量尬f 为0 - 1 变量这一特点转化为线性 表达式，但是将会额外增加辅助变量和约束方程，而且最终还是要面临求解0 1 整数规 划问题，而这类问题是n p 难的，且不存在好的多项式算法。 2 关于多目标函数的处理 多目标问题的求解有两种基本方式：一是当某一目标存在好的算法的情况下，再追 加另一目标，由于前一目标的最优解不止一个，这就有更多的空间讨论其它目标；解决 多目标问题的另一个方法是通过构造评估函数，或是通过对目标函数的加权组合，将多 目标问题转化为单目标求解，这种方法在解决数学规划问题中经常采用。但是，从目标 函数( 3 1 ) 和( 3 2 ) 可以看出，两目标方向不一致，量纲也不一致，要将两目标进行 均衡处理。 3 关于问题的规模 考虑一次州个航班环的排班任务，分配胛个飞行员上的组合数为小l ，要求每个 飞行员至少执行一个航班环的组合数也有埘0 矿个，p ，是从以个数中有序的挑选出m 个的组合数。因此求解所需的空间和时间可能同任务撑指数增长。 目前求解飞行员捧班问题的启发式方法，主要有以下几种： 派遣以天为单位，每天的航班任务委任给当天的可派飞行员去完成； 对飞行员从高级别到低级按顺序创建个人任务时间表，任何飞行员的个人任务时间 表一旦创建，则在整个过程中不再更改。”“； 以上两种方法的组合，这个方法分为两个阶段：第一个阶段是逐个给飞行员创建个 人任务时间表，第二个阶段是通过优化的方法重新调整所创建的表”“； 将派遣问题变成一个集分割问题( s e tp a n i t i o np r o b l e m ) 。对每一个飞行员产生数以千 万计的月度个人任务时间表。然后就是一个采用线性松弛和分支定界方法求解的o 一1 整数规划问题n “。 前三种方法由于都基于一些令人熟知的，经典算法和启发式算法，故而易于实现。 而且，它们也可以使一些排班人员的工作由计算机直接完成。但是由于大多数派遣问题 的规模非常巨大，所以很难在全局优化的角度上创建飞行员的个人任务时间表。大部分 现行的方法采用时序化( s e q u e n t i a lh e u r i s t i c s ) ，将大问题拆解成若干小问题以缩减问 x 中国民用航空学院硕士学位论文 机组分配阶段。这种方法首先衡量机组的协调性，对机组的协调性进行量化处理，然后 将协调性较好的人员分配到相应航班。由于机组搭配的协调性不能统一的一概用“好” 与“不好”进行评价，所以要将人员匹配的各种指标进行量化，总体评价得出机组协调 性的程度。 3 2 分阶段排班方法概述 分阶段排班方法是将机组排班分阶段进行求解，其基本思想是模型分解，即用不同 方法分开处理目标和约束条件。算法分成两阶段：机组生成阶段和机组分配阶段。 机组生成是将可搭配的人员编成组，生成航班最小定员要求组，并根据排班原则对 生成的机组进行评价，使用数学的方法量化机组协调性。一个人员可以和不同的人员搭 配成不同的组。 机组分配是将机组生成阶段产生的机组作为一个整体，综合航班的飞行时间和航线 要求将合适的机组进行分配以执行航班任务。这一阶段要综合考虑机组的协调性和人员 的工作负荷均衡两个目标。 在该方法中，机组生成和机组分配的准则是：在一定时期内对某飞行员来说其执行 的航班任务相对稳定。在航空公司，特定的一段时间内，某飞行员所飞的航线几乎是固 定的几条，而且对于某个航班任务来说，执行这个航班任务的飞行员也几乎是固定的几 人。这 x 中国民用航空学院硕士学位论文 图3 1 机组生成方法最后，结合航班飞行时间，以天为单位安排合适的机组执行航班任务。 33机组生成在航空公司实际运营中，将人员搭配成机组时要考虑以下因素。： n ) 飞行机组成员的嘈臻i 篷翟爨蓉刻蚕瓤i 桑燃i 嘣獯砸还傈基簿漆囊鋈i 用| 第亳窿或其官塑豆经袋蓼位剪# 翟描茸；垃馨翅璺二雕季砝鬟雾豁鬈辆融痢划露焉果螽t凼i 并表示了谢意。 研究生签名：趣楹日期：趔：垒竺 中国民用航空学院学位论文使用授权声明 中国民用航空学院、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复 印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文 的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文 的全部或部分内容。论文的公布( 包括刊登) 授权中国民用航空学院研究生部办理。 研究生签名：童j 歪篁翘导师签名：丝日 期：趔 x 中国民用航空学院倾士学位论文 假设人员昏g = ( g l ，9 2 ，9 3 ，9 4 ，9 5 ，9 6 ，9 7 ，9 8 ，9 9 ，g l o ，9 1 1 ) ，g i 为人员g 第i 个属性值。 ( 1 ) 技术因素 行政职位因素 由于具有行政职位的人员工作忙，参加飞行时间少，在安排他们参加飞行时要实事 求是，是什么飞行技术标准就安排在什么飞行岗位。无论是担任机长还是副驾驶，在排 班时都应为其选配较好的副驾驶或机长配合他们参加飞行。 ig ，= o人员g 不是行政人员 i g 。= 1人员g 是行政人员 l a 年龄 要掌握好机长与副驾驶的新老搭配。新老搭配就是年纪较大的机长最好和年轻的人 员配合，一般来说，年龄在5 0 岁以上的机长应该搭配技术较好的年轻的副驾驶。这样 做的好处是年纪大的机长可以弥补年轻副驾驶飞行经验不足，应变能力弱的缺点，而年 轻的副驾驶又可以弥补老机长头脑手脚反应慢的缺点，一旦空中发生特殊情况，二者可 以互相弥补。如表3 1 。 表3 1 年龄因素 年龄段 标志值( ) 2 5 以下 1 2 1 3 02 3 1 4 03 4 1 6 0 4 5 1 6 05 b 技术力量 掌握好技术力量强弱搭配。飞行技术较强的机长和力量较弱的副驾驶搭配，飞行技 术较弱的机长与较强的副驾驶搭配，是在排班中常用的一种强弱搭配法。尤其是在机长 少、航班多、人员紧张的情况下，采用此方法是合理调配机组力量的最好办法。 暑3 为人员技术力量标志：分为五个等级：1 ，2 ，3 ，4 ，5 ，依次为能力越强。五个等 级是根据飞行员长期飞行的状况和飞行时问以及飞行经历进行评定的。 c 英语水平 掌握好英语水平好与差的搭配。无论是操纵飞机还是飞国际航线的英语空中通话， 都要求每一位飞行员必须要具备较好的英语阅读和听说能力。从我国民航飞行部队的现 状看，大部分的飞行机长英语水平都较低，在执行国际航班时飞行机组必须要配有专业 报务员进行空中通话。近些年来，虽然飞行员的英语水平有了一定提高，但大部分人员 都是一些副驾驶。从以上情况看，机长与副驾驶的搭配，英语能力的好与差搭配也是一 个不容忽视的方面。 鼻4 为飞行员英语水平，分为5 个等级，方法与技术力量相同。 中国民用航空学院硕士学位论文 本文将人员之间关系分为以下4 个等级： 关系非常好( s u p e r c o o p ) 关系好( g o o d c o o p ) 关系一般( n o 姗a l c o o p ) 关系不好( b a d c o o p ) 2 单因素搭配评价体系的建立 根据航空公司、民航总局法律法规的规定和以上分析可知，影响搭配的因素之间不 完全独立，例如年龄问题，它和技术力量的关系非常密切，5 0 岁以上的飞行员要和年轻 的、技术力量强的其他飞行员搭配，同时行政人员与技术力量的关系也非常密切。所以， 对于有关联的诸因素，首先要对其分别进行考虑，然后再综合考虑。经过对排班问题进 行研究，并借鉴机组编排实际经验和机组资源管理( c i t m ) 的理论，对各个因素的搭配 进行分析，建立单因素搭配体系。 对单个因素搭配的评价要遵守以下几个基本原则。“： 独立性原则。同一层次上的各指标之间相互独立，没有交叉，尽可能避免明显的包 含关系，力求减少指标间的关联度。即要求在同一层上的a 指标与b 指标不能存在 重叠或因果关系，表示为彳n 口= 曲。 完备性原则。搭配体系应能全面反映评价对象的本质特点，使评价的全部主要内容 都包含在搭配体系当中。设d 为被评价对象，巩为搭配体系中的第f 个指标，那么 完备性原则可表示为：了阢。o 。 箭 一致性原则。搭配体系应与现行的排班制度相适应，要求评价能客观、真实地反映 现实排班系统的基本情况。 可测性原则。指标涵义明确，数据资料收集方便，计算简单，易于掌握。定量与定 性相结合的原则，既可使评价具有客观性，便于数学模型处理，又可弥补单纯定量 或定性评价的不足及数据本身存在的某些缺陷。 分析影响机组协调性的因素可知，单因素匹配评价体系分为两层，根据排班中的互 补原则，建立如下单因素搭配指标体系，如表3 3 。注：本文只对于静态航班进行排班，且航班与 机组搭配协调性评价中只考虑航班的航线和航班飞行时间两因素。 设： 某人员组合( 占 ) = g = ( g l ，9 2 ，9 3 ，9 4 ，9 5 ，9 6 ，9 7 ，9 8 ，9 9 ，9 1 0 ，9 1 1 ) ， = = ( l ， 2 ，i 1 3 ， 4 ， 5 ， 6 ， 7 ， 8 ，1 1 9 ， 1 0 ， 1 1 ) ， 航班口0 1 ，口2 ，) ，研为航班属性。 矗：人员组( g ， ) 的第i 层第，个因素的搭配值( 搭配评语) 。 建立如下单因素搭配评语集： o ( 不可搭配) 中国民用航空学院硕士学位论文 1 ( 搭配不合理) 2 ( 可以搭配) 3 ( 搭配合理) 4 ( 搭配很合理) 表3 3 影响机组协调性的单因素搭配指标体系 一级权重 指标 二级指标 技术 w 1 职位因素 g i - 1 ，h l = 1 l = 1 因素 矗1 ； g l = o ，h 产1 “= 4 毛1 ( 9 1 ，h 1 ) 勤2 1 ，h 1 2 0l = 4 9 1 = 0 ，h l 。0 “= 3 年龄因素 9 2 。4 ，h 2 = 4 矗2 = 0 矗产 ( 9 2 = 1 ，h 2 = 4 ) o r ( = 4 ，h 产1 ) 2 = 4 矗_ ( 9 2 ，h 2 ) ( 9 2 = 1 ，h 2 = 3 ) o r ( = 3 ，h 2 = 1 )毛2 = 3 ( 9 2 = 1 ，h 2 = 2 ) o r ( 9 2 - 2 ，1 1 2 = 1 )2 = 2 = 1 ，h 2 = 1 矗2 = l 。2 ，h 2 - 2 f 2 = 3 ( = 2 ，h 2 - 3 ) o r ( = 3 ，h 2 = 2 ) f 2 = 2 ( = 2 ，h 2 = 4 ) o r ( ：4 ，h 2 = 2 ) f 2 = 4 = 3 ，h 2 ；3f 2 = 3 ( = 3 ，h 2 = 4 ) w ( 9 2 = 4 ，h 2 - 3 ) f 2 = 4 技术力量 i “ g t = 1 ，h l = 1 ) o r船= a n y毛= 0 f 3 = f ，( 自，h 3 )( 9 2 = 4 ，h 2 = 4 ) )h 3 = a n y c l i f ( 幽= 1 ，h 1 = 0 ) 9 1 = 1 ，职= 4伽 嘶= 0 ，h 1 _ 1 ) i i ( 9 2 = h 3 _ 1 a n y ，h 2 = 4 ) 嘶= 4 ， h 1 = 1 h 2 = 4f 3 = h 1 = a n ”9 3 1 c l s c 船= 1 ，h 3 - 5岛= 4 船2 1 。h 3 。4 、 9 3 = 2 ，h 3 = 5 9 3 = 3 ，h 3 = 5 9 3 2 1 。h 3 = 1 f 3 = 0 9 3 = 1 h 3 = 2 审= 5 h 3 = 5 9 3 = 2 ，h 3 = 2如；1 9 3 = 4 ，h 3 = 5 9 3 = 2 ，h 3 = 3毛；2 9 3 = 3 h 3 = 3 9 3 = 4 ，h 3 = 4 9 3 = 1 ，h 3 = 3 中国民用航空学院硕士学位论文 员不能够搭配，两个年龄大的也不能搭配，因为这样搭配的机组违反了人员搭配的原则， 任何一个要素不满足就不能搭配。我们设置人员搭配的“底线”，即根据上节建立的单 因素搭配评价体系，两人员搭配的所有因素中有一个因素搭配评价为“不合理”，则一 个机组中如有这两个人员共同存在，这个机组就为不可搭配的。 假设有埘个正驾驶和副驾驶，用平面上m个点的点集s表示这m个驾驶员，在所 有点之间连一条无向弧，表示将肌个驾驶员进行两两搭配，设弧度