（计算机软件与理论专业论文）机组乘务员排班问题：系统研究与算法实现.pdf

机组乘务员排班问题：系统研究与算法实现摘要 论文题目： 专业： 硕士生： 指导教师： 机组乘务员排班问题：系统研究与算法实现 计算机软件与理论 张子臻 郭嵩山教授 摘要 在一个航空公司的同常运营过程中，人力成本占据了支出中较为重要的一部 分。在竞争激烈的航空运输市场，合理编制机组排班计划就成为航空公司实现运 营成本控制的一项关键管理工作。在国内，机组乘务员排班不仅要考虑成本的控 制，更重要的一个方面是要兼顾乘务员工作量的公平性。 本论文获取了国内某大型航空公司实际运营的数据，在详细了解了机组乘务 员排班运作流程的基础上，对整个排班系统做了深入的研究。论文描述了航班串、 执勤任务、航段的具体定义，分析了国内航空公司排班的状况，并列举了几类典 型的排班规则。然后建立了排班系统的数学模型，再利用一种新颖的混合启发式 搜索方法去解决这个问题。在许多文献中，机组乘务员排班问题通常以0 1 整数 规划问题加以描述，可以转化为集合分割或集合覆盖问题，此类问题己确定属于 n p 难问题，通常使用“生成一优化”准则去解决。由于论文涉及的排班目标函数 不是线性的，而且问题规模很大，约束很多，采用整数规划软件，如i l o gc p l e x 求解将遇到一些问题。本文尝试利用“破坏一重构”思想，结合2 - o p t 调整方法与其 它求解准则进行求解。通过大量的实验进行比较说明，得出该启发式方法是在实 际应用中是有效的、可行的。 关键词：乘务员、航班串、排班、公平性、启发式 t h l e ： m a j o r ： n a m e ： a i r l i n ec r e wr o s t e r i n gp r o b l e m ：s y s t e ma n da l g o r i t h m c o m p u t e rs o f t w a r ea n dt h e o r y z i z h e nz h a n g s u p e r v i s o r ：p r o f s o n g s h a ng u o a b s t r ac t i nad a y t o d a yo p e r a t i o no fa na i r l i n e ，t h el a b o rc o s th o l d sa l li m p o r t a n tp a r to f i t se x p e n d i t u r e i nt h eh i g h l yc o m p e t i t i v em a r k e to fa i rt r a n s p o r t a t i o ni n d u s t r y , t h e p r e p a r a t i o no fc r e ws c h e d u l i n gb e c o m e sak e yi nr e d u c i n gt h eo p e r a t i o nc o s t i n c h i n a , a i r l i n ec r e wr o s t e r i n gd o e sn o to n l yc o n c e mm i n i m i z i n gt h ec o s t ，b u tt h e e q u i t a b i l i t yo f c r e w w o r k l o a ds h o u l db et a k e ni n t oa c c o u n tt o o f o rt h i sp a p e r , w ec o l l e c ts o m er e a lo p e r a t i o n a ld a t af r o mo n eo ft o p5a i r l i n e c o m p a n i e sw o r l d w i d e a f t e rs c r u t i n i z i n gt h ec r e wr o s t e r i n gp r o c e s so ft h i s a i r l i n e c o m p a n y , w ei n v e s t i g a t et h i sp r o b l e mi n - d e p t h t h i sp a p e rd e s c r i b e st h ed e t a i l e d d e f i n i t i o n so fp a i r i n g ，d u t ya n dl e g ，a n a l y z e st h ec u r r e n ts i t u a t i o no fd o m e s t i ca i r l i n e i n d u s t r ya n dl i s t ss o m et y p i c a lc r e wr o s t e r i n gr u l e s w ei d e n t i f yt h eo b j e c t i v ef u n c t i o n o fo u ra i r l i n ec r e wr o s t e r i n gp r o b l e m , a n ds u c c e s s f u l l ya p p l yan o v e lh y b r i dh e u r i s t i c s t os e e kh i g hq u a l i t ys o l u t i o nf o ri t i nm o s to fp r e v i o u sl i t e r a t u r e ，t h ea i r l i n ec r e w r o s t e r i n gp r o b l e m sa r eu s u a l l ys o l v e db ya g e n e r a t i o na n d o p t i m i z a t i o n p r o c e s s , w h i c hc o n s i s t so fr o s t e r i n gg e n e r a t i o np r o c e s sa n ds e tp a r t i t i o n i n gp r o c e s s t h i s p r o b l e m i sv e r yc o m p l e xs i n c en u m e r o u sr u l e sa n dr e q u i r e m e n t sh a v et ob e c o n s i d e r e d t h et r a d i t i o n a li p o p t i m i z e r s , e g 。，i l o gc p l e x ，h a v en oc a p a c i t yt o h a n d l et h i sp r o b l e md u et oi t sn o n - l i n e a ro b j e c t i v ef u n c t i o na n dn u m e r o u st y p e so f c o n s t r a i n t s t h e h y b r i d h e u r i s t i c s r e p o r t e d i n t h i s p a p e r i sb a s e do n ”r u i n - a n d r e c r e a t e ”p r i n c i p l e ，2 - o p t ”a d j u s t m e n ta n ds o m eo t h e ro p e r a t i o n s al a r g e n u m b e ro fe x p e r i m e n t ss h o wt h a tt h i sh e u r i s t i c si se f f e c t i v ea n de f f i c i e n ti np r a c t i c e k e yw o r d s ：c r e w , p a i r i n g ，r o s t e r , e q u i t a b i l i t y , h y b r i dh e u r i s t i c s 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期：生! 1 2 ：丝 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 言蠢慧零嚣辫东篙；缘日期：2 0 。7 年r 月辨日日期彩巧年，碉巧。日 机组乘务员排班问题；系统研究与算法实现第1 章绪论 1 1 系统背景 第1 章绪论 个航空公司在同常的运营过程中，机票是收入的主要来源，同时航空公司 也需要进行多方面的支出，其中包括：飞机费用、燃油费用、维修费用、劳动力 成本和机场使用费等等。 在国外，航空公司工作人员的工资水平较高，约占总成本的三分之一左右， 例如欧美等国家，机组人员的劳动力成本是航空公司直接运营成本的第二大组成 部分，仅次于燃料成本。对于像u s a i r , d e l t a 等类的大型航空公司，劳动力成本 支出每年超过l o 亿美元，机组资源的利用是否合理对公司每年运营成本的影响 超过l 亿美元，因此，在竞争激烈的航空运输市场，高质量的机组排班计划是航 空公司降低运营成本的关键。 在国内，航空业的劳动成本相对于总成本的比重较低( 2 0 0 1 年仅占3 4 0 ) ， 即使将销售费用、管理费用和间接营运费中的人员成本考虑在内，根据2 0 0 1 年 对国内某一航空公司财务报表的测算，国内航空公司人员成本占全部成本的比例 也不超过6 ，因此薪资水平并没有对成本构成重大的影响。 飞行员与乘务员作为航空公司工作人员主要的构成部分，他们担负着航空运 输业的使命，因此如何对工作人员进行有效的管理，最大化和最优化的保证劳动 力的利用率，是航空公司关注的一个重要方面。因此当前国内的许多航空公司都 不惜花费巨额资金引进和购买国外先进的“航空公司运作控制系统”( s y s t e m o p e r a t i o n sc o n t r o l ，s o c ) 。例如1 9 9 7 年南方航空公司就与美国世博公司( s a b e r ) 合作引进了s o c 系统，2 0 0 6 年中国国航也同s a b e r 公司签署了s o c 项目合同。 机组管理系统是整个s o c 中业务最复杂，受制约因素最多的应用，它是航 空公司对飞行计划安排与人员管理的重要组成部分。而机组乘务员排班作为机组 管理系统的一大主要模块，其功能是提供自动排班与手动排班功能，根据用户提 供的航班与排班人员资料，合理的安排飞行任务、备份任务、地面任务、休假、 国家发展改革委网站l a i w w w n d r e o v e n ：民航国内航空运输价格改革方案听证会文件第二章 5 机组乘务员排班问题：系统研究与算法实现第1 章绪论 公务等活动，同时需要检查乘务员的各类资格条件，等等。 1 2 机组排班系统研究概况 整个机组排班系统是十分复杂的，涉及业务也十分广泛，因此相关的研究非 常多。所谓一个机组的排班，指的是对于航班计划中的每个航班，根据其机型属 性，为该航班指派相应的飞行员( 包括机长、副驾驶、机械员、领航员、通信员 等) 、乘务员和空中保安以承担该航班的飞行和机上服务作业。对机组进行排班 是一项非常复杂且需要进行大量沟通的工作，需要航空公司的各级部门有效的协 作才能进行。一个有价值的排班，能有效的控制航空公司的运营成本，符合民航 管理局和公司各项规章条例的限定，实现各类资源的优化配黄，同时也能满足公 平性的要求。 由于机组人员属性的不同，航空公司在编制排班计划时一般要把飞行员与乘 务员分开进行编排，而乘务员与一般的空中安全员可以混合进行编排。由于飞行 员的规则及约束特别复杂，与航班和飞机的耦合程度特别紧密，因此国内的航空 公司对飞行员的编排基本都是通过手工排班完成的，主要通过经验来指导排班完 成。相对于飞行员而言，乘务员的编排要相对灵活一些，但规则同样十分复杂。 因此对于乘务员排班的方法，国内航空公司大多借鉴国外航空公司的方案。一般 而言，航空公司排班的流程需要经过下面一些环节： ( 1 ) 航线安排( f l i g h ts c h e d u l i n g ) ：这个阶段用于确定我们平常所称为的 飞行航线或航段，航空公司将根据当前的资源与市场的需要来决定航线的安排。 ( 2 )机型指派( f l e e ta s s i g n m e n t ) ：这一阶段航空公司依据已确定的航段 去指派相应的机型，这一阶段要考虑飞机的载运能力以及维修计划等等的约束。 ( 3 )航班串配对( c r e wp a i r i n g ) ：该阶段要把已指派机型的航段搭配成航 班串( p a i r i n g ) ，航班串是首尾所处基地相同的一系列航段的排列，具体的定义 我们将在第二节详细给出。这一阶段航空公司的目标主要是要生成最小成本的航 班串集合，使其能尽量多的覆盖之前确定的航段。航班串配对一般又分为短程 ( s h o r t h a u l ) 航线与长程( 1 0 n g h a u l ) 航线的配对。 ( 4 )机组人员排班( c r e wr o s t e r i n g ) ：这阶段的实质是一个工作指派问题 6 机组乘务员排班问题：系统研究与算法实现第1 章绪论 ( a s s i g n m e n tp r o b l e m ) ，要解决的问题是如何将配对好的航班串分配给机组人员， 在满足各类约束条件的限制下，使排班的结果尽可能的优化。 航空公司的机组安排问题( a i r l i n ec r e ws c h e d u l i n gp r o b l e m ) 通常指的是最 后两个阶段：航班串配对和机组人员排班。但这两个阶段一般是独立分开进行的， 对于机组乘务员排班( c r e wr o s t e r i n g ) 阶段，目前航空公司使用的排班系统大概 可以分为以下两类： ( 1 ) 竞标系统( b i d d h gs y s t e m ) 竞标系统允许乘务员以竞标的方式获得排班周期里的工作。在北美，许多航 空公司采用一种称为“b i d l i n ea p p r o a c h 的排班方法，系统首先生成排班周期内一 系列完整的候选班表，然后机组人员以资历优先等方式竞选得出他们想要的班 表。还有一种方式称为“p r e f e r e n t i a lb i d d i n g ”，机组人员可以提出一些自己喜好的 班次，同样也是以一定优先顺序竞标获得周期内的所有班次，大多数欧洲航空公 司均采用此种方式。 ( 2 ) 公平性系统( e q u i t a b i l i t ys y s t e m ) 竞标系统一定程度上满足了机组人员等级高低的要求，但也容易造成人员对 排班结果的不满。公平性系统是以机组人员满意度作为考量的，对于同种资历的 人员，要尽量保证其安排的航班的公平性，保证每个人的飞行小时、工作时间、 好坏班次等达到公平的分配。公平性系统保证了工作量的平衡，但其的缺点是在 一定程度上限制了机组人员对喜好班次选择的自由。现在国内不少航空公司已开 始采用此种方式。 1 3 国内外研究状况 机组排班问题在国外的研究比较多，理论也较为成熟。早在上世纪6 0 年代， 已有学者开始研究。a r a b e y r ee ta 1 【l 】( 1 9 6 9 ) 对一些航空公司进行调查并尝试 用o 一1 整数规划的方法去实现员工与航班之间的配对。m m e t s c h m a i e r t 2 1 ( 1 9 8 5 ) 对2 0 年来航空公司排班问题作了系统的综述。c a m p b e l le ta 1 f 3 】( 1 9 9 7 ) ，j a r r a h a n dd i a m o n d f 4 1 ( 1 9 9 7 ) ，c h r i s t o ue ta 1 i s l ( 1 9 9 9 ) 描述了航空公司竞标系统的相 关应用与做法。d m r y a n t 6 1 ( 1 9 9 2 ) 首次将乘务员排班问题建模成集合划分问题， 7 机组乘务员排班问题：系统研究与算法实现第1 章绪论 并成功解决了6 5 0 个约束方程，2 0 多万个变元的问题。n i k l a sk o h l 【7 1 ( 2 0 0 4 ) 综 合了当前乘务员排班问题的成果，描述了现实生活中航空公司排班问题的模型与 解决方法，并给出了一个商业排班系统的解决方案。 另外，解决机组排班问题的方法主要有如下一些： ( 1 ) 分枝定界法( b r a n c h - a n d 。b o u n d ) ，文献有s t r a u s s t 8 】( 2 0 0 1 ) ，它以排班 人员效用最大化为目标，过程使用到了分支定界的方法，求解了多达7 7 9 个乘务 员，1 7 1 1 个航班串的排班问题。 ( 2 ) 分枝切面法( b r a n c h - a n d c u t ) ，是分枝定界与切平面法的融合，代表文 献是h o f f m a n 9 ( 1 9 9 3 ) ，他在搜索算法中通过削减多面体凸壳上的可行整数点， 并通过再形成过程和线性规划的一些方法来帮助快速获得问题的解。 ( 3 ) 列产生技术( c o l u m ng e n e r a t i o n ) ，是利用线性规划中的对偶理论来产 生新的列以缩小问题求解的规模。m i c h e lg a m a c h e 【l o 】( 1 9 9 9 ) ，利用列产生技术 解决了法国航空公司的上千个约束方程，上百个组员的排班问题。t o r s t e nf a h l e i 1 ( 2 0 0 2 ) ，将约束规划( c o n s t r a i n tp r o g r a m m i n g ) 和运筹学( o p e r a t i o nr e s e a r c h ) 的技术结合，基于列产生的方法解决了欧洲一些航空公司的排班问题( 6 7 个组 员，2 8 0 个任务) 。m e i n o l f s e l l m a n n ，e t a 1 【1 2 】( 2 0 0 2 ) 使用了约束规划，混合了列 产生技术与启发式树搜索，求解了5 0 个乘务员，7 6 6 个航班串的排班问题。j e s p e r h a n s e ne t a 1 1 3 】( 2 0 0 5 ) 也使用到了列产生技术，他对分枝定价( b r a n c h - a n d p r i c e ) 方法与启发式解约束规划作比较，解决了3 0 0 - 1 2 0 0 个乘务员的排班问题，但此 文没有涉及航班串的概念。 ( 4 ) 启发式解法( h e u r i s t i cm e t h o d ) ，使用启发式解放的文献相对较少，p a n t a l u c i c ，d u s a nt e o d o r o v i c t l 4 , 1 5 , 1 6 ( 1 9 9 8 ，1 9 9 9 ，2 0 0 7 ) ，利用贪心方法与各种启发 式方法( 模拟退火、遗传算法、禁忌搜索) 解决了6 0 多个乘务员，近6 0 0 个航 班串的排班问题。b y u n gt e c hk i m i t 7 】( 2 0 0 6 ) 也尝试使用贪心方法去求解1 6 0 个 乘务员，每天3 0 个航班的韩国航空公司排班问题。n a d i as o u a i 【1 8 1 ( 2 0 0 8 ) 用遗 传算法求解了航班串配对与乘务员排班混合问题，测试样本有6 8 个飞行员，5 5 8 个航班串。 在国内，乘务员排班问题相关的文献有林红等人【1 9 1 ( 2 0 0 1 ) ，孙宏【2 0 1 ( 2 0 0 3 ) ， 张应辉等人f 2 1 1 ( 2 0 0 6 ) 。 8 机组乘务员排班问题：系统研究与算法实现第1 章绪论 1 4 论文的研究内容与组织结构 本论文研究的是机组乘务员排班问题，主要涉及系统的构造与算法的实现， 其中乘务员排班的公平性是该问题的主要目标之一。在研究的过程中，我们查阅 大量的国内外文献，并结合国内某大型航空公司实际运营情况，提炼出了一套特 殊的目标函数与约束限制。在国外，问题求解的目标通常仅仅是最小化排班成本， 而在国内，乘务员公平性却是企业主要考虑的问题，所以，将两者结合起来考虑， 并结合实际设计了一个新的模型，是本论文的创新的地方。这个模型采用当前的 解整数规划问题的方法去解决存在着一些问题，于是我们提出了一种启发式的求 解算法，利用“破坏重构”思想，结合2 o p t 调整方法与其它求解准则，通过大量 的实验进行比较分析，得出我们的解决方法是有效的，在实际应用中要比航空公 司当前使用的系统效果要好，而算法应用在实验抽象出来的数据中的优化情况同 样也较为不错。 论文的组织结构如下： 第1 章：绪论，描述了机组乘务员排班问题的一些背景与国内外研究状况。 第2 章：机组乘务员排班问题定义，阐述了机组乘务员排班在整个业务流程 中涉及的问题及其定义。 第3 章：数学模型的建立，结合航空公司的实际情况提出了一套数学模型。 第4 章：机组乘务员排班问题的一种启发式算法，尝试采用这个启发式算法 去求解我们设计的模型。 第5 章：实验结果与分析，通过现实的数据去比较并说明了我们提出的算法 是可行、有效的。 第6 章：结论，做出了一些总结与展望。 9 机组乘务员排班问题：系统研究与算法实现第2 章机组乘务员排班问题定义 第2 章机组乘务员排班问题定义 该章我们将对航空公司机组乘务员排班( a i r l i n ec r e wr o s t e r i n g ) 整个业务 流程中包含的问题及定义进行详细阐述。这里我们假定机组排班前面的几个阶段 已经完成，剩下的任务主要是对乘务员与航班串的进行配对。虽然困内多家航空 公司在排班过程中的具体细节不完全相同，但是大概的业务流程可以归纳如图 2 1 所示。 图2 一l 乘务员排班系统业务流程 1 0 机组乘务员排班问题：系统研究与算法实现第2 章机组乘务员排班问题定义 2 1 制订乘务员排班计划 制订乘务员排班计划要涉及到以下几个方面的考虑：首先是排班的类型，一 般来讲，班次分为三大类：飞行班( f l y ) ，备份班( s t a n d b y ) 和地面班( g r o u n d ) 。 飞行班就是俗称的航班，即机组人员在飞机上的工作，同时包含签到及休息等活 动，2 2 节会详细阐明。备份班是为了应对意外情况( 例如乘务员病假) 而设置 的，备份班包括主备与次备，主备任务的乘务员必须在基地待命，而次备任务的 乘务员则可以留在家中待命。地面班包含的种类比较多，乘务员除了飞行班与备 份班的其它事务都可以归为地面班，例如一些例行会议、培训及业务活动等等。 地面班一般都是预先安排好人选的班，不需要经过自动排班系统编排。 其次是要确定排班的时间，由于当前航空业竞争愈发激烈，对一些突发事件 的响应也必须特别快，所以由市场部制订的航班的需求也变化得很快。对于乘务 员的排班周期，通常远程航班先安排1 个月，其他普通航班按周( 7 天) 进行排 班这样比较合理。同时排班时要考虑到历史的影响，因此往往会在数据库中提取 2 3 个月的数据作为参考。 另外就是必须保证排班的合法性与可行性。在排班过程中乘务员会受到许多 方面的限制，例如关于机组机型、护照类型、语言资格等限制，还有就是飞行时 间、休息规则上的约束，一个合法的排班必须满足所有硬性规则的要求。排班的 可行性主要是要考虑排班的间隙，一个乘务员不可能同时从事2 项或以上的工作 任务，并且在两个工作之间必须预留出一定的时间让乘务员能按时就位；在飞行 的前后也要预留集合与等待飞机起飞的时间；过站或者转机时希望能让乘务员有 短暂的休息并完成准备工作。我们在2 4 节将会介绍各类详细的规则。 还有计划要涉及到排班的公平性，公平性希望乘务员达到一些指标的平衡。 一个是工作时间的平衡，包括飞行时间与过夜的时间，另二个就是保证好坏班的 平衡。由于不同航线飞往的地区不同，出勤时间不同，工作强度不同，得到的待 遇也不同，因此希望保证相同等级的乘务员在各种不同类型的航班上能有一个平 衡。另外，一个合理的排班希望保证乘务员参与的某种类型航线的班在某段时间 内的重复次数要尽量的少，同时班次的分布也要尽量的平均。如何衡量公平性我 们在2 4 节中也会具体说明。 机组乘务员排班问题：系统研究与算法实现第2 章机组乘务员排班问题定义 最后就是成本控制，要保证航班安排的定额人数尽量满员，同时机组人员的 劳动力利用率达到最大。因为如果航班缺少定员，航空公司需要支付额外的薪金 来支付调配过来的员工以保证航班的正常运作，所以航班人员的覆盖率是影响排 班系统成本控制的主要因素。 2 2 载入排班乘务员资料 机组乘务员是安排在客舱的服务型人员，国内的乘务员素质都比较高。如果 按职位进行分类的话，依据职位顺序一般可以分为下面几个级别：主任乘务长 ( d a ，d e a na t t e n d a n t ) 、乘务长( h a ，h e a da t t e n d a n t ) 、头等舱乘务员( f a t , f i r s tc l a s s a t t e n d a n t ) 、商务舱乘务员( b a t , b u s i n e s sc l a s sa t t e n d a n t ) 、普通乘务员( a t , a t t e n d a n t ) 、安全员( s gs e c u r i t yg u a r d ) 和学员( s s ) 。( 对于安全员，国内分为 专职的安全员和兼职的安全员) 。一般来说，高职位级别的乘务员能力要比低职 位级别的乘务员能力要强，高职位级别的乘务员可以通过降级或兼职方式实施低 职位级别乘务员的工作，因此享受的待遇也较高。 如果按管理等级分类，可分为管理人员和非管理人员。对于管理人员，内部 也分成多个等级。由于管理人员要从事一些行政管理工作，因此飞行时间限制、 降级排班等规则与非管理人员会有所不同。一般而言，管理人员的排班需要单独 考虑。 乘务员的资料事先已经由相关管理部门收集并存储在数据库之中，可以通过 选择基地、级别或机型信息得出需要排班的乘务员资料。乘务员的资料包括以下 一些( 这里只列出可能在规则约束中使用到的) ： 人员基本信息，包括员工号、姓名、性别、出生日期、入职日期、合同 终止日期等。这里性别的差异会影响排班的效果，因为有些规则要求飞机上 至少要包含几位男性乘务员。 人员所处基地信息与职位级别信息。 人员可飞机型信息。乘务员通过各类飞行训练后，便可担当相应机型的 航班任务。 人员护照信息。护照信息规定了乘务员可以飞行哪些国际航班。 1 2 机组乘务员排班问题：系统研究与算法实现第2 章机组乘务员排班问题定义 人员降级与兼职资格信息。这些信息标识了乘务员是否允许降级或兼职， 具体的规则可参照2 4 节说明。 人员条件资格信息，包括专职教员资格、空警资格、长航线资格、高原 机场资格、语言资格等。 人员停飞信息，包括停飞国际航班、停飞过夜航班、停备份班等。 管理人员信息，包括管理人员的等级等等。 2 3 载入航班串信息 在进入乘务员排班系统之前，航空公司将依据上阶段制订的飞行计划，通过 搭班系统将各类航班搭配成航班串( 以下简称为p a i r i n g ) 。上一阶段主要解决的 问题称为职员航班串配对问题( c r e wp a i r i n gp r o b l e m ) ，而该问题如何解决本文 不做叙述，相关的文献有b a r n h a r t ，h a t a y , a n dj o h n s o n 2 2 1 ( 1 9 9 5 ) ；v a n c e 2 3 1 ( 1 9 9 7 ) ； a n d e r s s o ne ta 1 【2 4 1 ( 1 9 9 8 ) ：l a v o i e ，e ta 1 矧( 1 9 9 8 ) 等等。 在机组人员排班阶段，上阶段生成出来的航班串信息是必要的，这罩给出一 些专门术语的定义及其之间的关系。 2 3 1 术语定义 航段( s e g m e n t ) ：航段指的就是一段任务区问，在这段区间内，职员执行的 任务只有一个属性。航段一般可以分为飞行航段、过夜航段、休息航段、置 位航段。另p h ) i i 练飞行、备份任务、地面活动等也可以笼统归入航段之中。 s e g m e m 的主要类型如下： - 飞行航段( f l i g h ts e g m e n t l e g ) ：一个飞行航段就是指一段中间无任何停 靠站的航段，即飞机从一个机场p o r ts t r 起飞开始，到另一个机场 p o r te n d 降落终止的这段区间。 过夜航段( l a y o f f s e g m e n t ) ：过夜航段一般应用于较远程的航班，由于 这些航班的时间跨度较大，职员需要在某些机场落地休息，然后再执行 后面航段的任务。过夜航段就是在基地以外的过夜休息。 一休息航段( r e s ts e g m e n t ) ：休息航段就是一段休息的区间，而且休息的 1 3 机组乘务员排班问题：系统研究与算法实现第2 章机组乘务员排班问题定义 地点一定是发生在基地所处的城市之中的。 _ 置位航段( p o s i t i o n i n gf l i g h ts e g m e n t d e a d h e a d ) ：有时候，某个航段中的 职员并不足执行飞行任务，而是作为乘客飞行到另外一个机场再执行任 务的，这个航段我们称为置位航段。置位航段的产生是航班串配对阶段 遗留下来的问题，置位航段增加了航空公司的人力成本支出，因此置位 航段的数量一般比较少。 值勤任务( d u t y ) ：一个值勤任务由一系列的飞行航段所组成，期间还包含 一些短暂的休息和停留，值勤包含了航段前后的签入与签出时间，以方便工 作人员做好准备。另外飞行备份、置位航段等属于工作的任务也算入值勤之 中。执勤任务的类型包括： 飞行值勤任务( f l i g h td u t i e s ) ：包括了一些航段与航段f h j 的停留。一般而 言，一个属于飞行的值勤任务可以看成是员工一个工作f 1 的任务，所以 飞行值勤任务足没有过夜休息的( 但包括过夜航段) 。 备份值勤任务( s t a n d b yd u t i e s ) ：备份值勤任务是作为飞行值勤任务的后 备补充，因为当一个排班表确定以后，可能会有一些意外情况导致某些 机组人员的缺席，备份执勤任务就是安排一定数量的乘务员在基地或家 里以应对意外。 地面值勤任务( g r o u n dd u t i e s ) ：地面值勤任务包括一些地面指挥活动、 业务交流、培训计划、参与会议、健康检查等等。 休假任务( o f f - d u t i e s ) ：休假任务主要包括例行的假期或者一些社会的活 动。 航班串( p a i r i n g ) ：p a i r i n g 这一概念最早在研究机组排班问题时提出的，由 于机组是分处于不同的生活基地的，设置航班串的话，每套机组就可以从自 己的生活基地出发，执行了一系列航班任务后再返回自己的出发基地，形成 一个封闭的回路，这样问题的规模就大大的降低了。航班串是一些值勤任务 的集合，其中还可能包含一些过夜与休息的信息。它的种类一般可以分为飞 行任务、备份任务或者地面任务。在安排飞行任务时，每个航班的起飞站均 为上一个航班的落地站，而落地站为下一个航班的起飞站，整个飞行任务均 从基地出发，最后回到基地( 中间也可能返回基地) 。所有的航班串在任务 1 4 机组乘务员排班问a ：系统研究与算* 变现第2 蠢机蛆乘务员捶班问题定女 结束后均需添加一段休息时削，时间的长短根据任务性质小同而不同。个 航班串可能包古以卜一些信息： _ 航班串基本信息：包括航班序列号、所属基地、开始与结束时问。 航班串使用机型代码：描述了该航班串使用到的机型，如果不止一组， 往往用c a b ( c a b i n ) 标识，具体机型在航段中予以描述。常州客运的机 型包括a 3 l9 ，a 3 2 0 ，a 3 3 0 倍7 5 7 ，b 7 7 7 仃7 b ，e m 4 等等。 航班串需要和已安排的人员数量：包括各职位等级人员的数量。 航班串地域类型：包括国际航线、地区航线、国内航线。 特殊航班串标识：包括例如红眼航班( r e d e y ep a i r i n g ，即包古夜间e 行 的航段的航班) ，多段航班( 包含航段数较多的航班) 、高原航班等。 航班串所需资格：包括长航线资格，语言资格，健康证明等。 2 3 2 航段、值勤任务、航班串三者间的关系 航段、值勤任务和航班串存在一种医问包含关系，具体来讲，一个航班串包 含个或多个值勤任务，而一个值勤任务贝4 包含一个或多个的航段，我们以图 2 2 来分析。浚图描述了一个航班串，里面包含四个值勤任务，而缚一个值勤任 务只包含一个航段，一般飞行值勤都是以签入和签出作为开始和结束，飞行航段 则是以起乜和落地作为开始和结束。而对于其他的值勤任务，开始时间和结束时 间与包含的航段( 如果只有一个航段) 的) f 始时间和结束时问是一致的。 机组乘务员排班问癌：系统研究与算法实现第2 章机组乘务员排班目题定女 图2 - 2 航班串、执勤任务、航段关系( 一) 当然，并小是所有的值勤任务都只包含一个航段，以图2 _ 3 的描述的航班串 为例，它的航段是：c a n c t u ，c t uc a n ，c a n - x m n ，x m nc a n ，休 息。前面4 个e 行航段( 红色部分) 属于网一个值勤任务，航段之间只有短暂的 休息或停留( 蓝色部分) ，直到整个值勤任务结束后才分配一段时间的休息。整 个航班串由c a n 出发，中途返程回到c a n ，最后又返回了c a n ，形成了封闭 的吲路。 h 。5 ”i 。竺“d u t y ! “! ，4 1 兰! 卜一d u l y 2 一一_ h_ 一 一一_ 图2 - 3 航班串、执勤任务、航段关系( 二) 2 3 3 引入航班串的作用 系统生成航班串后，机纽乘务员排班问题便可转变成乘务员与航班串之间的 配刘关系，由f 每个航班串均以某个枢纽机场为起点和终点，并且在浚机场上有 固定的起飞和至q 达时刻，这样就很容易与机场的一套机组人员结合起柬安排，从 而使问题的僦模和复杂性大大降低了。 虽然引入航班串的概念后机组乘务员排班问题与执勤任务、航段的联系相对 较少，但是由于一些排班规则或者相关的报表统计可能使用到航段与执勤任务的 信息，因此系统不能将这三者脱离丌来。 机组乘务员排班问题：系统研究与算法实现第2 章机组乘务员排班问题定义 2 4 机组乘务员排班系统 该节我们将给出机组乘务员排班系统的一个业务设计框架并对使用到的一 些信息进行详细描述。 2 4 1 设计框架 一个排班系统需要实现的就是将员工安排到班次任务上，或者说把班次任务 分配给员工。我们已经在2 2 节和2 3 节阐述了这两部分重要的资源，下面给出 乘务员排班系统的一个详细设计框架如图2 4 所示。 规则信息 r u l e sa n dr e g u l a t i o n s 水、p 规则 h o r i z o n t a lr u l e s 垂直规则 v e r t i c a lr u l e s 特殊规则 s p e c i a lr u l e s 乘务员排班系统 c r e w r o s t e r i n g s y s t e m 结聚 r o s i e r s t + “ 乘务员 | 斑避录 r e c o r d so nc r e w ， 舰班人员记录 r e e ) r d so np a i r i n g 图2 4 乘务员排班系统设计 1 7 班次僻息 s e r i e si n 国r m a t i o n 摊班信息 a s s i g n m e n ti n f o r m a t i o n 万史摊班信息 h i s t o r y 顶摊班信息 。 p r e - a s s i g l r m e n t s 受j l ：假赐 c r e wv a c a t i o n 埂留弓谢绦绳务 r e s e r v e so r f r a i n i n g s m 巷孤 埘息童倍息藤 信h务幽迎三串唱住m段科 一一一一一 机组乘务员排班问题：系统研究与算法实现 第2 章机组乘务员排班问题定义 系统的输入有乘务员信息、班次信息，规则信息，排班信息和求解目标五个 部分。经过乘务员排班系统处理之后，将得到一个排班结果。该结果可以以一定 格式存储于数据库中，通过u i 用图形化方式展示给用户，也可以以生成报表的 形式供用户使用。由于乘务员信息与班次信息在整个机组乘务员排班业务流程中 已被提及，在此不再详述。我们将在2 4 2 节给出航空公司希望求解的目标，2 4 3 节将介绍民航总局与国内航空公司运营过程中制订的一些典型的规则信息，2 4 4 节则给出已知相关的一些排班信息，排班结果的形式我们将放在2 4 5 节。 2 4 2 排班目标 每个航空公司在机组乘务员排班过程中都希望能使一系列指标达到最优化， 因此乘务员排班问题是一个多目标资源优化的问题。在实际运营的过程中，排班 目标着重在以下几个方面： 排班费用：排班费用包括工资、奖金、补贴、保险、客舱服务费、差旅费、 飞行训练费等等。而排班影响的主要部分是航空公司支付给员工飞行的薪 酬，它由航班与员工的属性决定。对于相同的飞行任务，国际航班一般就比 国内普通航班支付得多，过夜航班也比非过夜航班津贴要高( 涉及到过夜酒 店住宿等问题) 。另一方面，对于相同的航班，职位高的乘务员需支付的薪 金往往也比职位低的乘务员要高些。如果一个航班串所需工作人员不能完全 分配到位，则需要通过招募新员工或其他方法抽调乘务员来补充到位，也有 可能直接取消航班。这两种方案都会产生额外的费用，对航空公司不利。 排班成功率：排班成功率反应了劳动力的利用率，是直接与费用挂钩的。排 班成功率可以从两个角度去分析，一个角度是满员航班的成功率，即满员的 航班串与所有待排航班串之比，该指标现实反应了排班算法的优劣。另一个 角度是排班人员的空档率，即所有的航班串各职位己填充人员与需要人员的 比值，因为有些航班可能只安排了一部分人员，在航班未取消之前，这些人 员也应考虑到排班之中。 公平性：国内的航空公司在既定的排班制度下，支付给员工的薪酬相对是比 较固定的，因此航空公司较为关注的目标是排班结果的公平性。这里的公平 性是指可以量化为数值的一些指标的平衡，或者是定性对排班结果分析希望 1 8 机组乘务员排班问题：系统研究与算法实现第2 章机组乘务员排班问题定义 做到的公平。值得注意的是，公平性一般都是对同一级别人员间的平衡，而 且是在规定一段时间内的平衡。如何形式化公平性本文将在第3 章给出。下 面列举一些公平性的指标： 飞行时间与执勤时间的平衡：飞行时间可以从航班串包含的航段信息中 获取，执勤时间则从执勤任务信息中得到。航班串的飞行时间是该航班 串包含各航段的实际飞行时问之和。排班结果要尽量保证乘务员的工作 时间不能相距太大。 过夜天数的平衡：过夜一般分为国内过夜和国外过夜，国外过夜航班是 一份公认的“好差事”，要做到同等级乘务员的过夜天数尽量平均。 _ 休息时间的平衡：一般来讲，休息时间越连贯乘务员将更为满意，而且 乘务员对安排在周末、周日的休息会更喜好。 好坏班安排的公平性：安排给乘务员的红眼航班、多段航班、高原航班、 早晚班等性质较特殊的航班其数量要相对的平均。 _ 重复性航班安排的公平性：希望在一段时间内某些类型的航班不要重复 安排太多次，另外希望重复安排的时间不要太集中，要尽量均匀。例如 连续3 个远程过夜航班被集中安排在半个月之内使得乘务员的工作压力 就很大。 一 降级与兼职排班的公平性：对同一个乘务员，不希望被经常的降级排班 和兼职排班。 其他：例如排班的健壮性，意外状况下是否易于调整和更换空乘人员；还有 排班是否符合个人的喜好，等等。 2 4 3 排班规则 一个合法的排班结果需要通过各种排班规则的检查，这些排班规则一部分是 由各类法规( 如中国民用航空总局令) 所规定的，一部分是各航空公司自行制订 的，还有一些可能是公司与员工之间达成的共识。 在我们的求解过程中，排班结果将以二维矩阵的形式表示出来。其中矩阵的 一行表示了一个员工的排班情况，矩阵的一列表示了一个航班串安排人员的情 况。据此我们将排班规则分成基本规则，水平规则，垂直规则还有特殊规则四类， 1 9 机组乘务员排班问题：系统研究与算法实现 第2 章机组乘务员排班问题定义 基本规则描述了一个乘务员与一个航班串问的排班关系，而水平规则影响了一个 员工的排班在不同航班串问的关系，垂直规则影响了多个员工的排班针对某一个 航班串的关系，特殊规则则是针对特别的人员和航班串的规则。由于每个航空公 司产生的排班规则均不同，不可能全部的列举出来，下面介绍一些我们认为重要 且典型的排班规则。 基本规则：基本规则描述了一个乘务员与一个航班串问的排班关系。 基地限制规则：乘务员所属基地必须与航班串所属基地一致。 机型组限制规则：乘务员应具备待排航班串使用的机型