（交通运输规划与管理专业论文）航空公司飞机排班问题：模型及算法研究.pdf

西南交通火学博士研究擞学位论文第i 页 摘要 航空公司的生产计划编制怒一项非常艰巨丽重要的工作，其实质在于通 过爨爨瓣缓织窝精确葭计划，实凝各生产资溪要素赘优亿聚菱，它兹溪量窝 效率关系到生产遮麓的安全、正常和效益。本文在深入分析当前国内各航空 公司，土产计划工作现状的基础j 二，选择了1 i 机排班计划作为研究课题，通过 系统分撰飞礁捧爨工终熬滚程秘要求，提嵩了接述飞枧蓑 班闽题懿数学模 型。由于该问题是多目标、菲线性的，因此寻找一种统一的能够适应各种具 体要求，并且满足工程应用需爱的多项式算法存在理论上和技术上的困难。 为此论文在借鉴手：e 编制摊班计划经验的基硪上，将一个具体的飞枧摊班闻 题，归结为三静典黧群班模式中的秘，酃：基于飞祝调度指令要求的擗班 问题，基于飞机使用均衡要求的排班问题和基于最少需用飞机数的排班问 题，对于每种典型的飞机排班模式，在对次要的约束条件进行箍化、松驰的 董愁t 构造出辕应静麓够潇跫z 程应雳要求敬扁发式算法，著分析了簿法的 复杂性。该项研究为研制飞机排班决策支持系统软件奠定了理论基础。 论文的主要创新工作在于： l + 投摆当瓣强肉蕊空公司瓣运营蓬织竣式特点，戮及飞祝蓑 斑i 睾豹 实际需求，提出了描述飞机排班问题的数学模型，并通过将一般形式的飞机 排班问题归结为三种典型的飞机排班模式，构造出相应的启发式算法，填补 了国内在此领域的磷究空白。 2 在解决基予飞机调度指令要求的飞机排班阉题时，本文提出的分阶 段指派算法较好地克服了标号算法的缺陷，该算法能普遍地应用于处理类似 的固定工件排序问题。 3 - 在解决菠飞祝均衡爱穗的飞季晁簿爨闻楚时，奉文利用航班节的网络 模型将原问题转化为一个使目标函数最小的航班节编组问题，在此基础上构 造了个模拟退火算法。 4 在解决最少震雳飞橇数要求的飞瓿骛瑷阀题时，本文将寻找救班节 衔接方案问题，描述成个二：部蹦的匹配问题，进而通过解两个二部图的最 一一一 西南交通大学博士研究生学位论文第ii 页 小权最大匹配，寻找需用飞机数最少的飞机调度方案。 关键词：飞机排班问题，航班节，启发式算法，航班节网络模 型，算法复杂性 西南交通大学博士研究生学位论文 第i ii 页 a bs t r a c t a i r l i n e o p e r a t i o n a lp l a n n i n g i s v e r y h a r da n d i m p o r t a n tw o r k ，w h i c h q u a l i t y a n d e f f i c i e n c y i sc o n c e r n e dw i t ht h es a f e t ya n db e n e f i to fa i r l i n e o p e r a t i o n t h ee s s e n c e o ft h i sw o r ki so p t i m i z i n gt h ec o n f i g u r a t i o no f p r i m a r y a i r l i n er e s o u r c e sb yp r e c i s eo r g a n i z i n ga n dp l a n n i n g ，b a s e do na n a l y z i n gt h e s t a t u so fd o m e s t i ca i r l i n e o p e r a t i o n a lp l a n n i n gs y s t e m ，t h i s d i s s e r t a t i o n d e t e r m i n e st h e s t u d ys u b 3 e c t a st a i l n u m b e r a s s i g n m e n t ( t n a ) p r o b l e m f i r s t l y ，a 0 - 1 i n t e g e rp r o g r a m m i n gm a t h e m a t i c a l m o d e li sc o n s t r u c t e dt o d e s c r i b et a i l n u m b e r a s s i g n i n gw o r kh a p p e n e di nd o m e s t i ca i r l i n e ，s i n c et h e p r o b l e mi sn p c ，au n i f i e dp o l y n o m i a la l g o r i t h mw h i c hs a t i s f i e se n g i n e e r i n g r e q u i r e m e n ti su n a v a i l a b l e i l l u m i n a t e db yt h ep r a c t i c a le x p e r i e n c e ，as p e c i f i c t n a p r o b l e mi s c l a s s i f i e di n t oo n eo ft h r e et y p i c a lt n am o d e s ：t n ab a s e d 0 nf l e e td i s p a t c h i n gc o m m a n d s ，t n ab a s e do nf l e e tb a l a n c ea p p l i c a t i o n ，t n a b a s e do nm i n i m u mf l e e tr e q u i r e m e n t ；s e c o n d l y ，b ys i m p l i f y i n ga n dr e l a x i n g s o m em i n o rc o n s t r a i n t s ，c o r r e s p o n d i n gm a t h e m a t i c a lm o d e l sa n dh e u r i s t i c a l g o r i t h m sa r er e c o n s t r u c t e df o re a c ht y p i c a lt n a m o d e ；f i n a l l y ，c o m p u t i n g c o m p l e x i t i e sa r ed i s c u s s e d a l lt h e s er e s e a r c hs e t sap r i m a r yf o u n d a t i o nf o r d e v e l o p i n ga i r l i n et a i ln u m b e ra s s i g n i n gs y s t e ms o f t w a r e t h e p r i m a r yi n n o v a t i o n sa r ea sf o l l o w s ： 1o nt h eb a s i so fo p e r a t i o n a lc h a r a c t e r so fd o m e s t i ca i r l i n e b yn o w - , a m a t h e m a t i c a lm o d e l d e s c r i b i n g t n a p r o b l e m i s c o n s t r u c t e d ，a n d b y e l a s s i f y i n g as p e c i f i ct n a p r o b l e mi n t o o n eo ft h r e e t y p i c a l t n a m o d e s ， c o r r e s p o n d i n gh e u r i s t i ca l g o r i t h m sa r er e c o n s t r u c t e d t h i sr e s e a r c hs u p p l i e sa d o m e s t i cg a pi nt h i sf i e l d 2 w h e ns o l v i n gt h e f n a p r o b l e mb a s e do nf l e e td i s p a t c h i n gc o m m a n d s ，a s t a g e a s s i g n m e n ta l g o r i t h mi sb u i l dt oo v e r c o m et h ed e f e c to ff i f oa l g o r i t h m ， w h i c hc a nb ew i d e l ya p p l i e dt oc o p ew i t hf i x e d j o bs c h e d u l i n gp r o b l e m 3w h e ns o l v i n gt h e n ap r o b l e mb a s e d0 1 1 f l e e tb a l a n c ea p p l i c a t i o n ，a 两南交通大学博士研究生学位论文 第iv 擞 f l i g h tp a i r i n gn e t w o r k m o d e li sb u i l d ，b yw h i c ht h ep r i m a r yp r o b l e mt r a n s f e r r e d t oad i r e c t e dp a t hd e c o m p o s i t i o np r o b l e mt om i n i m i z et a r g e tf u n c t i o n ，a n da s i m u l a t e da n n e a l i n ga l g o r i t h mi sc o n s t r u c t e d 4 w h e ns o l v i n gt h et n a p r o b l e m b a s e do nm i n i m u mf l e e tr e q u i r e m e n t ，a b i p a r t i t eg r a 两d e s c r i b i n gf l i g h t - p a i r i n g l i n kp r o p e r t yi sc o n s t r u c t e d ， b yw h i c h t h ep r i m a r y p r o b i e m i st r a n s f e r r e dt ot w ow e i g h t e db i p a r t i t em a t c h i n g k e yw o r d s ：a ir ii n et a i | n u m b e ra s s i g n m e n tp r o b i e m f ii g h t p a ir i n g h e u r is t ica 1 9 0 r i t h i n s ，f ii g h tp a ir in gn e t w o r km o d e c o m p u t e r i z i n gc o m p i e x i t y 甄南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学梭保留并肉豳家有关部门或机构送交论文的艇印件和电 子版，允许论文被查淹釉氆阁。本入授校瑟露交逮大学霹强将本学 位论文的全都或部分内容编入有关数据库进行检索，可以采用采用 影印、缩印成扫描等复制手段和汇编本学位论文。 本学位论文藉予 1 保密口，在一。年后解密后适用本授权书； 2 。不傈整口，通趟奉授权书。 学位论文作者然名：指导教师签名： 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本 文的研究做出贡献的个人和集体，均已在文中作了明确的说明。本 人完全意识到本声明的法律结果由本人承担。 本论文的主要创新点如下： 1 在系统分析当前国内航空公司的运营组织模式特点的基 础j 二，根据飞机排班工作的特殊要求提出了描述飞机排班问题 的数学模型( 第2 章第2 节) ，并通过将一个一般形式的飞机排 班问题归结为三种典型的飞机排班模式( 第2 章第3 节) ，构造 出相应的启发式算法，从而为研制飞机排班决策支持系统软件 奠定了理论基础，本文的研究填补了国内在此领域的研究空白。 2 在解决基于飞机调度指令要求的飞机排班问题时，本文 提出了两种启发式算法，其中标号算法具有简便、易于与数掘 库产品融合的优点，但是没有考虑航班节之间的重要性差异( 第 3 章第3 节) ，而分阶段指派算法较好地克服了标号算法的缺陷， 但是在计算机上实施时比较复杂，需占用很大内存空间，在用 数据库语言编程实现中需要很高的编程技巧，该算法能普遍地 应用于处理类似的固定工件排序1 0 7 题( 第3 章第4 节) 。 3 - 在解决最少需用飞机数要求的飞机排班问题时，本文将 寻找航班节衔接方案描述成一个二部图的匹配问题( 第5 章第2 节) ，进而通过解两个二部图的最小权最大匹配，寻找使需用飞 机数最少的飞机调度方案( 第5 章第3 节) 。 4 - 在解决飞机均衡使用的飞机排班问题时，本文通过构造 一个拙述航班节涮衔接关系的航班节网络模型( 第4 章第2 节) ， 将原问题转化为一个使目标函数最小的航班节编组问题，在此 蕊礁上筠遗了一令模叛退火算法( 第4 章黧3 节) 。 学位论文 乍者签名： 日期：年 月日 西南交通大学博士研究生学位论文第1 页 第1 章绪论 1 1 航空公司生产计划问题综述 在航空公司的日常生产经营活动中，需要解决一系列的生产计划，这些 生产计划的制订过程实质是对各生产要素的优化配置过程，因此生产计划的 质量和效率不仅关系到运输生产能否顺利进行，而且还从根本上决定了企业 的市场竞争能力。企业的规模越大，航空运输业的市场化程度越高，生产计 划工作的重要性就越突出。 航空运输生产中最重要的生产计划有：航班计划，机队维护计划，客货 销售计划，机组排班计划，飞机排班计划以及航班运营飞行计划等，它们之 问的关系可以用图1 1 中的生产计划流程图表示。 1 - l l 航班计划 航班计划是航空公司一切生产活动的基础和核心，其它任何生产计划都 是圈绕并建立在航班计划的基础上并为航班计划的顺利实施提供保障的，完 整的航班计划包括以下基本要素： 航线：即航空公司开展运营的路线，包括起点、终点、经停等要素，航 线资源是航空公司的宝贵财富，航空公司要想在某条航线上丌展运营，首先 必须取得航线的运营权，1 9 8 3 年美国泛美航空公司破产后，其太平洋航线 经营权的拍卖价达到18 7 亿荚元【4 j ： 航班：航班包括航线、航班号、航班的出发时刻和到达开、j 刻等要素，同 航线一样，航班资源也是航空公司的宝贵资源，； 班次：即航班频率，指航空公司一天中在同条航线上有多少个航班： 班期：指某一航班在一周中的哪几天执行； 机型：指执行该航班所使用的飞机型号，不同机型有不同的飞行性能( 如 航程、升限、最大起飞全重、爬升能力等) ，因此不是所有的机型都能用来 匕某一航线，此外，不同机型对应不同的座位布局，当然运营成本也不相同， 如b 7 3 7 3 0 0 型飞机的座位数司到1 4 4 座，直接运营成木在3 5 j 元，j 、时之 m ，而a 3 4 0 2 0 0 型飞机的座位数达到3 8 0 人，直接运营成本在1 0 万元孙 西南交通大学博士研究生学位论文第2 页 时以上。 图1 1 航宅公i j 生产i i 划流程 在制订航班计划的过程中，确定所飞的航线、航班时刻、班次、班期等 工作被称为市场计划部分( m a r k e tp l a n n i n g ) ，其目标在于最大限度地扩大 公司在航空运输市场中所占的份额，增加销售收入，其依据主要是刈客货销 售额的统计分析以及对市场供需情况发展的预测，而确定航班所使用的最佳 机型的_ f ：作被称为机型分配计划( f l e e ta s s i g n m e n tp l a n n i n g ) ，制订该项l 作的依据主要是航线对机型的适航限制，每种机型的座舱布局，该机型在不 刚航线上的运营成本分析以及对每个航班卜客货流量的预测等，其目标是通 过对航班机型的优化分配，以最小的运营成本来完成航班生产任务。 从对航班计划的上述简要分析中不难看出：编制航班t t 划足项非常复 杂而且l ：作量庞大的任务，对于一个有5 0 架飞机，同航班量近3 0 0 个的航 西南交通文学博士研究擞学位论文第3 页 空公司，该王戛工l 睾箨要3 令诗划爨三令胃豹王 擘壁，魏莱完全壕靠天王亲完 成，则当计划编制好并开始实施时，市场环境早已发生了改变，因此，航班 计划制订的是否成功，不仅取决予计划工作本身的质量，而且还取决于编制 计划的周期长短。在国外，从上蜮纪八十年代束开始许多大型航空公司纷纷 开始毽韵予专盟靛蠢霆班诗矧警懋较孝 亲完戏编籍靛班诗期豹工 睾，跨澍惫貔 化航班的机型分配计划i 4 3 5 5 l 。近年来，随着航班规模扩大，国内的几家大 型航空公司如国航、东航等已逐步认识到航班计划工作的霞要性，并先后从 国外b i 避了相关的敬体应用于航班诗划工作中。 1 t 2 飞枕维护计划 与汽车、火车、轮船等不嗣，飞机是种特殊的空中运输工具，为了保 障航空运输的安全，各国普遍制订了严格的航空器适航管理法规以规范航空 爨懿搜强、维骛王孬，中莓蔑翔簸空器逶簸管理条翻( 又称c c a r 2 5 帮) 就是一部这样的法规【1 0 3 ，根据陔部法规的要求，国内各航空运输企业必须 依掘c c a r 2 5 部的规定建立完管的飞机维护制度并严格遵照执行，违者将 受到适航当局的严魇惩处。所谓飞辊维护计划是关于舷空公司所执管懿机队 中每蘩瓿接受维护工停蕊秘撩安捺，透过缡铡飞枫维护计矧不仅麓确裸每 架飞机在适航条例舰定的期限内宠成检修排放工作，而且将有助于公司可用 运力的稳定 2 。 所谐飞机的维修是维护稠修蠼的总称，其中维护是为了保持飞枧鬓煮麓技 术谴能并发挥萁最大效能所采致的技求措施；瓶修理是指当飞机 _ 现性熊褒减 或部件失效或发生故障时，为恢复其正常状态而采取的技术措施。维修的真接 目的是保证飞机处于良好可用状态，即维持飞机的适航性，主要的维修内容有 ( 1r 3 】： 经棒检查：邵飞祝每次在航站过站经停时所徽的俩行检缒、保养工作， 如轮胎、刹车的磨损状况检查等： 航髓航后检查：口口飞机在执行每天的第一个航班任务之盼以及最后一个 靛褒经务缝寒之后所送雩亍弱硷查、保姜工佟，包摄对一些霉要飞簿仪表系统 的检查、测试： 周梭：列飞机的菜些重要系统如液压、润滑系统等进行的较全面的保养， 每周进行一次，为避免毪机停场丽影响公司运力，一般尽黛结合航后梭套或 较垂乏时瓣熬过站经露宠藏，毽努须在畜麓力瓣基遣送暂： 定梭：定检是指每经过定的使j j 周期就需要对飞机溅行的一一系列检修 西南交通大学博士研究生学位论文第4 页 工作，根据内容分为a 检、b 检、c 检、d 检四类： a 检一包括对飞机外部、内部缺陷的目视检查，操纵系统、电子电气系 统的测试等工作，一般需要5 - 8 个小时，一般安排在航后，并在有维修能力 的基地进行； b 检一又称大a 检，检查项目与a 检大致相同但更具体、细致，例如 需要将飞行仪表拆下检查，并对平时不使用的应急系统，如灭火系统等进行 测试，b 检原则上要求安排飞机进机库，并停场1 2 天： c 检一一般每3 0 0 0 小时须安排一次，每次需停场8 1 2 天，主要工作内 容涉及地板的腐蚀性检查，受力构件的疲劳损伤，所有电子气仪表拆下测 试等； d 检一每2 0 0 0 0 小时须安排一次，又称为飞机结构性大修，每次需3 0 天左右，需要将飞机彻底拆散并对主要受力部件如大梁、受力隔框等进行金 属材料疲劳、腐蚀程度等的检查及处理，然后将飞机重新组。 故障保留项目的处理：现代航空器普遍按照多裕度设计理论设计的，因 此允许飞机在一定条件下保留故障飞行以提高机队的派遣放行率，并便于维 修部门合理制订飞机排故计划，降低维修成本。具体说就是对了二符合最低放 行设备清单( m e l ) 以及构形偏差清单( c d l ) 要求的故障设备，允许飞机 按照一定的限制，在规定期限内继续飞行。但是这种保留故障放行的措施必 竟是。种权宜之计，因此在适航管理条例中规定了严格的故障保留申请和批 准制度，并制订了严格的故障保留期限，如a 类故障为2 4 小时，b 类故障 为7 2 小时，c 类故障2 4 0 小时，d 类故障2 8 8 0 小时等，所以维修控制部门 在批准故障保留的同时必须制订相应的排故计划。 适航通告( a d ) 项目的处理：在适航管理工作中，民航当局及飞机制 造厂家经常会根据飞机使用中发现的问题针对某一类飞机的某部件发出 限期检查、更换的适航通告，航空公司的维修控制部门应在通告限定的期限 之i 河完成规定的维修工作。 编制维修训划是航空公司机队管理工作中一项控制性的 。程，其重要性 在于： i 维修计划关系到飞机的适航性，任何飞机如果不能按照适航条例的要 求完成维修：【作，则不再适航，使用不适航飞机丌展运营将受到局方的严厉 惩罚： 2 维修计划关系到航班计划的实施，航班计划的制订和实施是需要以必 要的飞机运力作保障，因此编制维修计划时还要考虑到航班计划对运力的总 一 西南交通大学博士研究生学位论文第5 页 量需求和结构性需求； 3 维修计划关系到维修工作的质量和效率，维修工作的顺利开展取决于 航材、设备、人力( 维修技师) 及维修工卡等四个基本要素，合理编排并严 格执行计划有助于生产车间优化配置资源，缩短工期，控制维修成本； 从上述分析可知，维修计划是中长期的，且一经制定就应努力维持计划 的稳定，为此需要通过制订飞机排班计划来实现。 1 1 3 客货销售计划 航班计划下达后，销售部据此制订每个航班的客货销售计划，其中主要 包括： 航班超售计划：航空运输中的一个重要特征就是存在n o s h o w 旅客( 即 旅客虽然定座但并不旅行，这种情况是由丁旅客订票后又在弋机起飞前临时 决定取消订座或旅客进行了重复订座等原凶引起的) 和g o s h o w 旅客( 即 事先没有订座而直接赶到机场要求乘机的旅客) ，自h 者将导致航班上的座位 虚耗从而降低了航班的收入，而后者则由于急于出行而宁愿接受较高等级的 票价。所谓超售就是指有计划地使接受的旅客订座数超过相应票价舱化的实 际座位数或飞机的最大允许座位数，以减少n o s h o w 旅客带来座位虚耗并 最大限度地获取g o s h o w 旅客带术的额外收入，超售的关键在于精确预测 n o s h o w 和g o - s h o w 旅客的比例以及发生的概率，并据此确定适度的超售 比例，即超售策略【2 4 2 7 。 收益管理：收益管理是发源于航空运输行业的市场营销手段，其实质是 通过市场细分以实现收入的最大化，我们知道航空运输市场中旅客需求是多 层次的，有些旅客( 如商务旅客) 不太在意票价的高低而更多地关心能获得 哪些优质的服务和便利的旅行条件，而有些旅客则对票价非常敏感而不会在 意对旅行条件附加一些限制，收益管理就是将同一航班上的相同座位划分成 若干种等级( 即舱位) ，每种舱位对应不同的票价和旅行限制条件( 如订票 时i 嘲，升舱，转签等) ，通过满足不同层次旅客的需求以实现航班收入的最 大化。收益管理计划就是通过对每个航班上不同层次旅客订座情况的预测， 优化航班的舱位等级划分，确定各舱位的票价，投放的舱位数以及投放时间。 山于这一_ _ r = 作的复杂性和重要性，这项工作必须借助于收益管理分析软件来 进行【5 ，6 ，2 吼 西南交通大学博士研究生学位论文第6 页 1 1 4 飞机排班计划 飞机排班是航空公司机队管理工作中的一个非常重要的部分，其实质就 是依据公司的航班计划和飞机维护工作安排为每一个航班指定一架具体执 行的飞机，也即给每一个航班号分配一个相应的机尾号( ta i l nu m berassignmen t ) 。合理的飞机排班不仅有助于航班的安全、 正点运行，而且还能提高机队的利用率，并便于飞行运营和机务维修工作的 组织实施，并能有效地降低运营及维护成本。在我国，飞机排班工作具体是 由机务调度人员负责。 在排班中应遵循以下一些基本原则： 1 航线运营限制 不同航线对允许运营的机型，甚至具体的机载设备配置都有详尽的要 求，这些要求分别写入了航空公司的运行规范，机型手册中并得到民航当局 的批准。因此，在进行飞机排班时，每一架飞机对于所运营的航线，必须是 满足运营限制要求的，这是保证运营安全与合法的需要。以拉萨航线为例， 西南航空公司被授权使用a340 和b757 型飞机运营该航线，但是在该 公司的15 架b757 型飞机中，仅有7 架完成了动力系统和氧气系统特殊 改造的飞机j 能执行该航线。 2 与航空时刻表中公布的机型尽量一致 航字时刻表中的信息( 航班时刻、机型等) 是航空公司对社会公丌作出 的服务承诺，因而对公司的经营行为是具有定约束力的。公司内外的各相 关部门也主要依据航班时刻表制定自己的销售或旅行计划。因此飞机排班中 的机型应与航空时刻表尽量一致。 3 与飞机的维护工作计划相一致 这是影响飞机排班的一个主要因素，具体表现在三个方面： ( 1 ) 既要避免因安排飞行而影响飞机的及时进厂维护，又要避免凶维 护而造成不必要的地面停留时间过长，从而影响运营。 ( 2 ) 避免在同一时段内出现多架飞机( 特别是同机型飞机) 同时需进 场维护，从而造成人为的运力紧张和维护工作拥挤。 ( 3 ) 在给即将接受维护工作的飞机安排航班任务时，应充分考虑到维 护基地所在的地理位置，尽量避免因为维修而空调飞机造成浪费。在我国， 各航空公司普遍采用了“甩辫予航线”，例如西南航空公司的双一京一如 一 沪一濡一沪一烟航线，执行这类航班的飞机一股当天并不返回公司基地。在 西南交通大学博士研究生学位论文第7 页 给运营这类航线上的飞机排班时，尤其要考虑到飞机的维护计划。 ( 4 ) 考虑飞机寿命的合理结构。一般地，一架飞机的寿命是由总服务 年限，轮档时间，起落次数，机体大修次数等四项指标构成的，其中任一项 指标达到限定的数据，即意味着飞机寿命的终结。因此，e 机排班时应使长、 短航线结合，使寿命结构比较合理。 ( 5 ) 提高飞机利用率。在我圈，飞机的同利用率低是一个普遍存在的 问题。合理的飞机排班方式可以最大限度地缩短地面停场时问，从而提高飞 机利用率，这意味着在不增加机队规模的条件下，通过运营更多的航班进而 降低琶机的小时成本。 ( 6 ) 考虑飞机的过站时l 刈要求。在不同机场的不同时刻，不同机型的 最低过站时间要求是不同的，因此飞机排班时应在衔接航班之间留出必要的 过站时间，以避免由于计划原因人为地造成航班延误。 从上述分析中可知，e 机排班是一项非常复杂和重要的计划工作， 特别是当航空公司的机队规模和航班量较大时，其复杂性和重要性就显得尤 为突出。在航空运输业发达的国家，这项工作是利用飞机排班计算机系统自 动完成的。而在我国目前各航空公司还是普遍采用人工排班，工作量大，排 班的合理性，灵活性较低，从而直接影响到公司运营组织和维护i 作的顺利 实施，增加了运营成本和维护成本。随着我国各航空公司机队规模的扩大， 航班量的增长，特别是航线网的同益大型化和复杂化，人工排班的落后方式 已难以满足运营管理工作的要求，因此实现飞机排班工作的自动化己成为大 势所趋。 1 1 5 机组排班计划 所谓机组排班是指：对于航班计划中的每个航班，根据其机型属性，为 该航班指派相应的飞行人员( 包括机长、剐驾驶、机械员、领航员、通信员 等) 、乘务员和空中保安以承担该航班的飞行和机上服务作业。在航空运输 生产中，机组成员尤其是飞行人员是一项非常重要而且昂贵的生产要素，在 欧美等国家，机组的人工费用是航空公司直接运营成本的第二人组成部分， 仪次于燃料成本，对于像u s a i r 、d e l t a 等类的大型航空公司，人员费用侮年 超过1 0 亿美元，机组资源的利用是否合理对公司每年运营成本的影响超过 1 亿美元，因此，在竞争激烈的航空运输市场，合理编制机组排班计划就成 为航空公司实现运营成本控制的项关键管理工作f 7 1 i o l 。 编制机组排班计划是项非常复杂而且，i ：作量巨大的管理工作，其团难 麟南交通大学博士研究生学位论文第8 礅 在于：蓄先。必矮臻缳壤缝安捺鞠会法性，撬缀签滠员必襞确保摇派绘每会 航班的机组成员是符合民航总局及公司的各项勰章条铡的，例如c c a r l 2 1 部中关于机组资格、训练的规定，c c a r 6 l 、6 2 部中关于机缀天气标准，机 组成员搭配的规定，c c a r 8 1 部中机组成员飞行、体息时间的规定等，例如 飞行辊绻每天静飞雩j 二瓣溺不褥超过9 小时，每援飞雩亍露阉不越过4 0 小时， 每天体息时间不得低予9 小时等。 其次，是机组排班的可行性，即分配给每一套机组执行的航班任务应符 台舷站衔接、过站时间衙接以及飞机衔接的要求。所谓航站愆接是指每套枫 组藏菰行的麓一个靛辍麓到这 晁场与后一个靛班瓣起。毪爨瑗魔保持一致；遥 站时间衔接是指每套机组所执行的相邻两个航骥之问应留育必要的嗣俐间 隔以使机组成员能有斑暂的休息并完成飞机过站的一系列准备工作，包括飞 机检查、飞行前准备以及办理飞机过站的手续，这个时闻的长短随祝型及盎葱 臻蕊瞧蔟丽定，如b 7 3 7 鼙飞祝巍霸瀚西内航班一般需要3 0 + 4 0 分锋，两a 3 4 0 型飞机执行的航班或圈际航班则一般需要9 0 分钟以上；飞机衔接是指分配 给。套机组执行的航班应尽量安排“架飞机执行，这样不仅可以方便机缀， 减少由于按飞枕两带来瓣无键：l ：俘，瑟且更重瑟的是可以避免由于豳程兢班 延误丽引起麴关联航班延误。 再次，是机组排骥的公平性。由于不同航班所飞的区域、航程、航班时 刻的不同，从而决定了不同航班的：l ：作强度、复杂性、待遇不同，即航班有 “好球之分”，对予露凑戆舷空公司，这个趣蹙茏其突出，镄如：飞爱际黥 班是公认的好差使，豳为不仅飞行津贴高丽且享受带薪休暇；而每天的旱班 和晚班，圜为需要旱出晚归很辛苦，斛此一般飞行员都刁j 愿意e ：此外，飞 行时f 可短瓶起落多的航班，涉及复杂航线和机场等的航线则一般不愿意毽， 困为l j 謦强褒大，菽零赡度裹，n 戴视缀签滠羹在缡爨毒趸缀褥斑诗剜霹还应 做到“好坏”航班的均衡。 最后，也是最核心的一条就鼹要以最小的人工成本完成所有的航班任 务。航班执行过程中发生的机组人工成本受很多因素影响，在此夺打算作详 囊分毒厅，详绥蠹褰茸参考畜关文酝 5 9 ，6 0 ，6 ，6 3 。 鉴于机组排班工作的重要性和复杂性，国外各火航空公司均专门聘嗣了 许多m s o r 领域的学者从事这方面的理论方法研究，并研制了专用的机 组排班管壤骏传。铡如美匿舷空公趟的a i r c r e w s 软传两l ，剥眉该软传簿 年；t j 节约久j ：成奉2 0 0 0 力美7 。逐； ；# 束，雷内各大航空公司也纷纷船滋了 这与诃的工作，陆续蟪立了自己的机组管理系统软件，如南方航空公司的 西南交通大学博士研究擞学位论文第9 页 s o c 软馋中裁毽含了一令援缝撵臻模块。 1 1 6 航班运营飞行计划 根摄c c a r l 2 l 部，也即航空承运人运行合格审定规则的规定。航空 公司运露控割中心静飞 亍签潺爨必须为每个簸褒准备一份运营飞行诗鲻，具 体工作包括：根据爨体执行该航班的飞税的技术状况，飞行机组的投术等级， 航班的计划业载，舟觅路及沿线机场的天气条件，航行限制霾求等，计算航班 的最大起飞限重以及着陆限重，合理选择飞行航路和备蹲机场，优化航班的 飞行期嚣，台理计魅班蕊起飞浚量。裁罚+ 运霪飞牙诗翅楚霆茏斑飞露翦准备 工作的核心内容，蕊价值在于： 首先，通过严格评估航空嚣的性能状况，机场及航路的现状，天气系统 的最瓤变化等对航班运行的影响，可以最大限度地保障髋班的安金。 其次，遥过懿订飞孬诗蘩，碍戬精确颡溺著控裁囊悫臻镌颞达时刻，蕊薅 减少由于计划原因造成的航班延误，提高航班的正点率，维护公司的信誉。 最后，通过合理选择飞行航路，优化飞行剖面，采取二次放行，利用燃 浦差价簿措旌，能够有效地增加航班业载，减少燃油消稷，从丽提赢舷班鳃 经济毪。舀此，一个科学、经济、合理静飞行计翔对予豫簿舷窀公司运营的 安全、效益、正点勰着举足轻鬓的作用。 制订航班的运营飞行计划有一套标准的计算程序和工作规则，山卡该项 工作鹃高度专业性，因此本文不钶冀在此作具体分板，详缀内容请参鲻寿鞋关 文献【i ，1 0 1 】。需黉说疆豁是：由于在青订运营飞行计划静过穗中需凝送行 大量数据的分析和优化工作，因此在实际工作中需要借助于专门的分析软件 来完成，常见的这类软件工具如j e p p s o n 公司的f l t s t a r 软件，s a b r e 公司粒f l t p a t h 较传等。 1 1 7 豳内外航空公司生产计划工作的现状 l 。国外航空公司生产计划e 作现状 由于诀识到舷空运竣中生产计划工作鹳滚要瞧手l 复杂十琏，欧美懿诲多大 型虢空公司孰上个照纪，k 十年代开始在生产中j 一泛应瓒生产计划管理系统 软件，以提高生产计划工作的质璺和效益，并取得了巨大的成功，以藏利坚 航窄公司为例，i 9 8 8 年航班机型分配系统软件在该公司投入使用后仅一年 溉实瑗了7 5 0 0 万美元的收久增长，它努发麴枧缰管理系绫较嚣，每鼋三可为 公司节约机组成本2 0 0 07 j 美元，利用另一个收益管理系统软件该公司使航 西南交通大学博士研究生学 巅论文第10 贸 褒载空闲糜位辜获1 5 z 降至3 ，聪蔡超售攫失减少了6 2 2 8 ，4 3 ，4 8 ，7 0 。 2 。戮内航空公司生产计划工作现状 当前因内各航空公司编制生产计划的工作揍本上依靠手工完成，由此带 来的问题有： ( 1 ) 生产诗划工 筝效率糕下，暖麓班诗翅为弼，编裁。份盎悫斑诗划嚣要 3 个月的时间，航班引4 划严重滞后于市场需求的变化； ( 2 ) 航班运营成本过高，影响了航空公司的市场竞争力，这在国际航线 上反映搭缦为充分； f 3 ) 丈量魏售息嚣溪靠调痉员人工楚理，越噩毛调渡员黪工佟强度籀费饪 眍力很大，很容易出现纰漏，从而影响航班生产正常进行。近年来，国内各 公司逐渐意识到存在的问题，并从阁外引进一些生产计划管理软件，但这些 软件不弱程度逢存在蛰“承不伏”的问题，潮与国内目前幻生产组织与 管理模式不辐适应，闲此许多软俘没有发挥密应有的作用。 1 2 国内外研究现状 1 2 1 国外研究现状 在幽外，由于来自航空运输生产实践的强烈需求，飞机调度问题赢是 m s o r 领域硬究的一个热点，综合怒柬，这些磷究工作可以分为网个方巍： i 靛班簸橇型分黼问题( f l e e a s s i g n m e n tp r o b e m f a 疆) f a m 问题的核心魁通过给每个航班分配合理的机型，使完成所有航班所 获得的总利润最大化，末要的研究有：m a r k s d a s k i n 基于欧洲各航空公司 普遍采用的单枢纽靛线缝毒奄斡特点，建裒了一个罐述f a m 载整数援翔模鍪， 并应用l a g r a n g i c a n 松弛算法求解了航班总睃麓的上界值 5 4 i 。h a n et 。a 通 过求解大舰模整数规划问题研究了一般形式下的机队分配问题，并成功地处 理了个十 甘有1 1 种机型，每r 航班达到2 5 0 0 个的大型航空公司的航班机型 努配润逐 9 ：l 。w 。c l a r k e 在h a n e 研究貔基藤上，进一步考虑了瓿绦修 计划安手j 以及机组排搬等因素的限制，并对h a n e 提出的数学模型进行了完 善，使解更接近实际的浠要 4 4 ，4 j j ：b r i a n 等邋一步研究了带有航班时问窗 的航班机溅分配问题，该项工作的价值不仅在于能进一步优化航班的机型分 醚，磊盈为簸臻时裂瓣傀讫缓整爨供了一令有效的分橱工其f j 6 。 2 琶机维护路径问题( m r p m a in t o n a n c e r o u t i n gp r o b l ) 西南交通大学博士研究生学位论文第1 1 页 欧美等国家的航空公司在编制飞机排班计划时必须考虑的一个很重要 约束就是“4 天维护计划”( 4 - d a y s m a i n t e n a n c e r u l e ) ，即在任意相邻4 天内，必须安排飞机在有维修能力的基地过夜一次以便于安排维修工作，这 样做的原因在于：为了最大限度地减少由于飞机停场维修而造成的运力损 失，般将各项维修工作的内容分解、重组并“打包”，每个维修工作包的 内容基本上可以在一次过夜时完成，同时沿航线网为每种机型建立了多个维 修基地，飞机每到达个有维修能力的基地时就完成一个维修工作包，并规 定每相邻两次维修工作的间隔不得超过4 天，因此，飞机排班实际上就是安 排飞机维护路径。 这方面的研究工作有：k a b b a n i 和p a t t y 通过生成航班路径集合( l i n e o f f 1 i g h t s ) 从而将原问题转化为求集分割问题，并提出了一种启发式算法 寻找飞机维护路径 2 9 ：， a r r a h 利用整数规划方法研究了飞机维护路径的分 配，c l a r k e 将维护路径问题转化为带有边约束的旅行商问题( t s p ) 并构成 了一种基于l a g r a n g i a n 松弛的启发式算式 4 4 t4 5 ，t a 1u r i 和g o p a l a n 合 作利用图论x , j 飞机的k 天维护路径问题进行了全面的讨论，在文献 3 4 中他 们通过构造航班维护路径图，并在其上寻找e u l e rt o u l 一的方法建立了一种 解决3 天维护路径问题的多项式算法，在文献 3 5 中他们分析了解决4 天以 上飞机维护路径问题的算法复杂性，存在可行解的条件，并构造了一种 “4 - m e t ”问题的启发式算法。 3 带有航班时问窗的飞机调度问题 在编制航班计划时，经常需要根据运力安排的需要对航班时刻进行调 整，通过引入航班时间窗可以定量评估航班时刻对公司运力安排的影响，从 而更好地优化航班时刻，因此，该项研究在生产实际中有较大的应用价值。 n ；q n 的研究工作主要有：b r i a nr e x i n g 在美国联合航空公司的协助 f 研究带有航班时间窗的航班机型分配问题5 6 。在一般的飞机调度问题的 研究中，一般均假定每个航班的出发和到达时刻是固定不可改变的，而在编 制实际生产计划时，允许对航班的计划出发和到达时刻做一定程度的调整以 便于获得更灵活、成本更低的飞机调度方案，并且这种航班时刻的调整事实 l x , j 运输生产不会构成重大影响。在此之前，l e v i n 等人在研究单机型的航 班时刻优化及飞机路径安排问题时首先引入j ，航班时刻窗的概念 5 7 ，之后 b a n d e r 与d e s a u l n i e r s 等人进。步研究了多机队的航空公司的机掣分配和 飞机维护路径安排问题，通过目标分解，生成最优航班路径的方法寻找最优 的机队调度方案，解决了f 航班量在4 0 0 个以下的航空公司飞机调度问题 一 西南交通大学博士研究生学位论文第12 页 4 6 ，b r i a nr e x i n g 在这些研究的基础上，通过对时刻窗的离散化处理，提 出了两种适用于解决大规模机型分配问题的算法：一种是基于提高处理速度 的直接算法( d s t ) ，一种是基于减小内存占用的迭代算法( i s t ) m j 。 4 飞机交换问题 在生产调度工作中，经常需要对某些航班的机型及其执行的飞机进行调 整，称为飞机交换问题。c l a r k e 和t a l l a r i 等人分别利用图论对此问题进 行了研究：3 6 ，4 5 。 5 飞机维护基地选址问题 飞机维护基地的分布及数量不仅关系到飞机维护工作能否按计划正常 开展，还影响到航班计划能否顺利执行，而设置过多的维修基地又将增大公 司的维护成本，因此，如何优化维护基地的分布，使其能适应航班计划以及 航班机型分配计划的要求，从而以最小的基地数量保证航班计划和飞机维护 工作的顺利进行就是一个很重要的规划问题。f e o 和b a r d 等人对此问题进 行专门研究，通过研究f e o 帮助美利峰航空公司将其b 7 2 7 机队的维修基地 从2 2 个减少到1 7 个，每年仅节省基地的基本运营成本一项就达到l o o 力- 美 元 1 7 。 1 2 2 国内研究现状 从国内来看，由于航空公司规模普遍偏小，因此前些年对生产计划管理 工作缺乏重视，计划方式简单、粗放，因而对生产计划管理方面的研究需求 非常有限。近几年来，随着运营规模的扩大，航空运输市场的丌放，市场竞 争不断加剧，航空公司逐渐意识到加强生产计划管理工作的重要性和急迫 性，但是总体来说，关于机队调度管理方面的理论研究还处于起步阶段，主 要的研究有：孙宏等人在文献 18 ，2 1 ，9 8 1 以需用飞机数最少为目标研究了 航班衔接问题，在文