（交通运输规划与管理专业论文）飞机一体化排班研究.pdf

南京航空航天大学硕士学位论文 摘要 航班计划是航空公司日常经营中的一项重要活动，如何有效地利用飞机等资源已是航空公 司面临的一大问题。目前航班计划的制定主要依赖手工和经验，缺乏科学性并且效率低下，已 成为航空公司成本增加的主要影响因素之一。 飞机排班是航班计划中最重要的环节。为了优化航班计划，提高决策的自动化水平，本文 对飞机排班进行了研究。首先，介绍了飞机排班制定过程和基本规则，建立了综合考虑机型指 派、路线选择、尾号指派，以最小化成本为目标的飞机一体化排班模型；其次，引入了约束编 程的概念，使用约束满足问题分析飞机路线生成问题，利用i l o g 平台建立飞机路线生成模型： 然后利用列生成算法求解飞机排班，主问题为线性规划问题，子问题为基于约束编程的飞机路 线生成问题。编写s c r i p 脚本将各个模块整合为一体，在列生成子问题和限制主问题之间不断 迭代，列生成停止后，求解最优的飞机一体化排班整数解。最后实例验证模型和算法的有效性， 对于飞机一体化排班具有重要价值。 关键词：航班计划，飞机排班，列生成，约束编程，i l o g 飞机一体化排班研究 a b s t r a c t t h ef l i g h tp l a n n i n gi sa ni m p o r t a n ta c t i v i t yi na i r l i n ed a i l yo p e r a t i o nm a n a g e m e n t + a i r l i n e sh a v e r e c o g n i z e dt h a ti ti si m p o r t a n tt on l a k eg o o du s eo fr e s o u r c e ss u c ha sa i r c r a f t n o w a d a y s ，m a i n l y d e p e n d i n go nh a n d c r a f ta n de x p e r i e n c ea i r l i n ef l i g h tp h n n i n gi sl e s ss c i e n t i f i ca n de f f i c i e n tw h i c h g r e a t l ya f f e c t st h ec o s ta n dr e v e n u eo fa i r l i n e s 。 a i r c r a f ta s s i g n m e n ti so n eo ft h em o s ti m p o r t a n ts t a g e s i no r d e rt oi m p r o v ea i r l i n ef l i g h t p l a n n i n go p t i m i z a t i o n ，t h i sp a p e rr e s e a r c h e st h ea i r c r a f ta s s i g n m e n t f i r s to fa l l ，t h ea i r l i n es c h e d u l e p l a n n i n gp r o c e s sw a si n t r o d u c e d ，a sw e l la st h ec o n t e n ta n dr u l e so fa i r c r a f ta s s i g n m e n ti nb r o a d $ e l l s e a0 - 1i n t e g e rp r o g r a m m i n gm o d e lw i t ht h eo b j e c t i v eo fm i n i m i z i n gc o s t sw a se s t a b l i s h e d , w h i c h c o n s i d e r e dt h ef l e e ta s s i g n m e n t ，a i r c r a f tr o u t i n ga n da i r c r a f ta s s i g n m e n ts i m u l t a n e o u s l y a n di t i n c l u d e dc o n s t r a i n t so na i r c r a f tr e s o u r c e s ，f l i g h tc o n n e c t i o n ，f l i g h tl i m i t a t i o na n dp r e - a s s i g n m e n t t h e nt h ec o n c e p to fc o n s t r a i n tp r o g r a m m i n gs 动w a si n t r o d u c e d a i r c r a f tr o u t e sg e n e r a t i n gw a s c o n s i d e r e da sc o n s t r a i n ts a t i s f a c t i o np r o b l e mw h i c hc o u l d b es o l v e db yu s i n gi l o ga i r c r a f t a s s i g n m e n tp r o b l e m sw e r el a r g e - s c a l eo p t i m i z a t i o np r o b l e m sw h i c hc o u l db ea d e q u a t e l ys o l v e db y c o l u m ng e n e r a t i o nb a s e do nc o n s t r a i n tp r o g r a m m i n g t h em a i np r o b l e ms o l v e dt h es e tc o v e r i n g p r o b l e m w h i l et h es u b - p r o b l e mi sc o n s t r a i n ts a t i s f a c t i o np r o b l e ma n dg e n e r a t e dc o l u m n sd y n a m i c a l l y w ed e s i g n e de f f e c t i v ec o n s t r a i n tp r o p a g a t i o na l g o r i t h ma n ds e a r c h e ds t r a t e g yt os p e e du pt h ed o m a i n r e d u c t i o n s 。 f i n a l l y , t h ee n t i r ea l g o r i t h m w a si n t r o d u c e da n ds o m ei n s t a n c e sw e r ea n a l y z e di nd e t a i lt os h o w t h ee f f e c t i v e n e s so ft h em o d e la n dt h ea l g o r i t h m k e y w o r d s ：f l i g h tp l a n n i n g ，a i r c r a f ta s s i g n m e n t , c o n s t r a i n tp r o g r a m m i n g , c o l u m ng e n e r a t i o n , i l o g 南京航空航天大学硕士学位论文 图表清单 圈l 。l 航班计越综合饶化方法4 图2 1 连接网络示意图9 图2 2 时空网络示意图9 图3 。li l o g s o l v 嚣搜索算法系统参数赛匠图2 2 图3 2 选择点随搜索次数变化图2 5 图3 3 搜索树变化过程2 5 图4 。1 列生成算法结构2 8 圈4 2 捌生成算法滚稷图3 3 表1 1 论文章节安排和主要内容6 表2 。l 一天靛班计划s 表3 1 飞机路线生成模型数据声明2 0 表3 2 飞机路线生成模型变量声明。2 0 表3 3 飞撬路线生成模型约束声魄。2 l 表3 4 航空公司航班信息。2 3 表3 5 航空公司飞机信息。2 4 表3 6 飞机a 3 0 0 1 可行路线集2 4 表3 7 飞机可行路线集。2 6 表4 1 线性规划主问题模型数据声明。2 9 表4 2 线性规划主问题模型变量声明3 0 表4 。3 飞机一体化排班系统组成3 2 表4 4 列生成算法目标函数和列集变化过程。3 4 表4 5 列生成最优解1 s 机的对偶值。3 4 表4 6 剃生成最优解辘班的对偶僮3 4 表4 7 列生成算法给如飞视排班结果与手工排班比较3 5 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下， 独立进行研究工作所取得的成果。尽我所知，除文中已经注明 引用的内容外，本学位论文的研究成果不包含任何他人享有著 作权的内容。对本论文所涉及的研究工作做出贡献的其他个人 和集体，均已在文中以明确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复 印件，允许论文被查阅和借阅，可以将学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复 制手段保存论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名：盔主 e 1 期：冽q 五：拗 南京航空航天大学硕士学位论文 第一章绪论弟一早硒了匕 随着我国经济快速稳定发展窝人民生活承平静提嵩，我国民用靛空灶高速发展，在国民经 济建设中的地位也越来越重要。国内航空公司的规模急剧扩大，生产计划的重要性越来越突出。 飞机排班是对机队资源的优化配置过程，是航空公司运输生产中一项非常重要的生产计划。飞 机运行鲍费用占据总营运成本褶当大的跑例，因此如何有效运用视队资源是靛空公司急需解决 的闯遂。 1 1 研究背景与目的 运输鼗是屋民经济和社会生活的联系纽带，是把市场生产和供给蛊接连通酶渠道，因藤运 输业是国民经济的动脉，没有它的连接，任何生产和生活活动都不能成为一个有机的整体。在 运输业中，相对公路、铁路、水运等交通运输方式而言，航空运输出现得最晚，但发展得最快。 靛空运输在客运中占有缀大比例，在一些发达国家航空运输客运量占总运输量的5 0 以上f l 】， 而且航空运输对国民经济的发展具有重要的推动作用。w i l b u rs m i t ha s s o c i a t e s 机构代表荧国联 邦航空局( f a a ) 对航空运输在美国经济中的推动作用进行了评估【2 】，2 0 0 0 年因提供航空公司 服务、通用航空活动、机场运行和飞机购鬣，共带来1 7 7 3 亿美元的总产出值，并创造了1 2 0 万个 以上的工佟枫会。2 0 0 3 年，全世界8 9 6 条航线上的定期靛班承担了1 6 。5 7 亿旅客( 相当予全球总 人口的2 5 以上) 的运送，以及3 4 5 0 万吨货物的运输。航空运输业是最受关注的国家基础产业 部门，具有重要的经济地位。 我国的民航运辕业虽起步较晚，僵发震逐速。特别怒改革舞敖以来，经济麓毫速增长带动 了我国民航业的迅猛发展。2 0 0 4 年中国民航的旅客运输量创下了有史以来的最高记录，首次突 破了1 亿人次大关，同时增长幅度也创下了2 0 年来的最高记录，2 0 0 4 年民航业全年收入达- 至1 j 1 2 5 0 亿元。2 0 0 5 年，我国航空运输总周转量在憷界的排名由第三位上升至第：位，超过德国，成为 仅次子美国的世界第二航空运输大国 3 1 。2 0 0 6 年我国民用航空继续快速发展，全行业完成运输 总周转量3 0 6 亿吨公里，旅客运输量1 6 亿人次，货邮运输量3 4 9 万吨，分别比上年增长1 7 0 、 1 5 5 和1 3 9 。2 0 0 7 年第三季度全行业分别完成运输总周转量、旅客运输量和货邮运输量9 8 7 亿吨公里、5 1 9 1 2 万久次帮1 0 5 。2 万吨，我去年霆褒分别增长1 6 、1 5 ，3 帮1 1 。5 。其率，国内 航线( 含港澳) 运输总周转爨、旅客运输量和货邮运输量分别完成6 5 1 亿吨公里、4 7 3 2 7 万人次 和7 5 5 万吨，比去年同期分别增长1 4 8 、1 5 1 和8 3 ；豳际航线运输总周转量、旅客运输量 蠢货邮运输爨分别完成3 3 。6 亿睫公里、4 5 8 。6 万人次帮2 9 。7 万吨，比去年麓凝分别增长1 8 。3 、 1 飞机一体化排班研究 1 7 4 和2 0 7 1 4 1 。整个民航业的快速发展使得航空公司开始经历快速发展，机队规模、航线数 量、航班数量以及机组人员数量等都在成倍增长。截止2 0 0 9 年底，我国境内民用航空机场共有1 6 6 个，其中定期航班通航机场1 6 5 个，定期航班通航城市1 6 3 个，旅客吞吐量4 8 6 0 6 3 万人次，货邮 吞吐量9 4 5 6 万吨，飞机起降架次4 8 4 1 万架次。2 0 0 6 年中国航空工业第一集团发布了未来2 0 年 民用飞机中国市场( 未包括港澳台) 的预测报告【5 】，按照目前航空业的发展速度，预计至u 2 0 2 5 年我国航空运输业机队规模将会达至j j 3 3 7 0 架，其中大型喷气飞机2 4 7 0 架，支线飞机9 0 0 架。未来 2 0 年，为满足运量的增长和替换退役飞机，我国航空公司将需要补充3 1 1 0 架飞机，其中大型喷 气飞机2 2 3 2 架，支线飞机8 7 8 架。 民航改革之初，由于国内客流量不足，航线也都集中在大城市之间，航班数量少，机队规 模小。进入新世纪以来，作为朝阳产业的航空运输业进入了一个快速发展的时期。不仅航空公 司自身在快速发展，航空公司间的联合重组也在不断地进行，目前已经形成了国航、东航、南 航、大新华四大航空集团公司。航空公司的快速发展和联合重组使得自身的规模变得十分庞大， 这对飞机排班工作提出了严峻的挑战。 目前，航空公司的飞机排班工作主要根据经验手工完成，手工排班操作简单，但工作量大， 并且依赖于航空公司预测的运力需求和工作人员的技能水平，另外航空公司各部门之间缺乏沟 通，使得排班的合理性、灵活性较低，而且手工排班得到的结果往往只是一个可行解，没有对 飞机排班问题进行优化，因而没能充分利用飞机这一宝贵资源为航空公司创造更多的利润。航 空公司已经意识到了信息化建设必要性，纷纷购买国外成熟的软件，2 0 0 3 年中国东方航空公司 与美国s a b r e 公司签署合作协议，建立东航的运行控制系统。2 0 0 6 年中国国际航空公司也同美 国s a b r e 公司签署了s o c 项目合同。但是国外的系统往往不能结合国内航空公司实际的运营模 式，因此无法发挥很好的作用，并且引进国外系统的成本非常高。 针对以上问题，本文提出一种切实可行的飞机排班优化方法，研究飞机一体化排班，改变 目前手工排班的局限性，实现航空公司资源利用的最大化，将机型指派、飞机路线选择以及机 尾号指派综合考虑，对飞机排班问题进行全局优化，提高航空公司的收益。同时力争将飞机排 班优化方法同计算机技术结合，实现飞机排班的自动化，解决手工排班无法解决的大规模计算 问题，提高工作效率。 1 2 航班计划问题概述 航班计划有狭义和广义之分，广义的航班计划按照制定的先后顺序一般地可分为以下5 个步 骤： 2 ( 1 ) 市场分析和预测 通过市场分析，在给定航线的基础上，航空公司能够预测一段时期内每一条航线旅客需求 南京航空航天大学硕士学位论文 分布，若有充分酶数据支持，则还应该预测国一天不同眩猁每个o d 流旅客人数的分布情提。 ( 2 ) 航班频率和对刻的确定( s c h e d u l ed e s i g n ) 在获取航线旅客需求以后，航空公司可以根据旅客需求和飞机资源，确定每条航线的航班 频率，进一步结合机场时刻资源，编制出航班时刻表。 ( 3 ) 撬鍪指派( f l e e ta s s i g n m e n t ) 机型指派问题是指根据不同机型具有不同的舱位数量、运行成本和潜在收益，指派不同的 飞机类型给定期航班。机型指派也称为机队指派，是以航班时刻表为依据，满足航班衔接的约 束，为每一个航班确定唯一的飞机视型( 并未指定具体的菜一架飞机) ，从两使得靛班逡营成本 尽可能最小。 ( 4 ) 飞机排班( a i r c r a f ta s s i g n m e n t ) 飞机排班包括飞机路线问题和尾号指派问题，其实质是在航空公司完成机型指派膳，依据 公司的靛班黠刻表纛飞橇维护工作安排必每一令靛班指定一架具体执行的飞祝，郄为每个航班 分配一个相应的机尾号。飞机排班主要是为了使每架飞机能够满足规定的维护维修需要，同时 能够使得运营和维护成本尽可能地小，并且保持机队的使用率在较高的水平。 ( 5 ) 橇组捺班( c r e ws c h e d u l e ) 机组排班是指航空公可根据每个航班的机型属性，为每个航班指派相应的飞行人员，乘务 员等机组人员。 狭义的航班计划指前3 个步骤，在国内大多数航空公阅中，这3 个计划都是由市场部( 商务 部) 负责铡定豹。广义航班计翔的毒l 定通常按照以上5 个步骤按顺序完成，同时又是环环摆扣， 在具体制定计划时，执行不同阶段航班计划的工作人员需要反复沟通交换意见，最终生成满意 的航班计划。 飞机撼班也有狭义与广义之分。狭义的飞梗i 捧班只包食路线问题耩尾号指派。本文研究能 对象实际上是广义的飞机排班，指机型指派、飞机路线问题和尾号指派，即飞机一体化排班。 1 。3 国内外研究现状 1 3 1 国外研究现状 有关飞机排班研究工作，国外很早就已经开展了。在机型指派方面，1 9 8 9 年a b a r a 提出了 规型指派问题为整数规划问题，利用连接网络建模1 6 1 ；1 9 9 3 年b e r g e 提戳瞻空网络，该网络的 弧表示航班，节点表示机场、时闻确定的二维时空点t 7 ；h a n e e t a l 在1 9 9 5 年提出给予时空网 络结构来建立机型指派模型：机型指派问题的基本模型无法充分考虑旅客溢出因素，因此k n i k e r 引进p a xm 模型计算旅客溢出成本最优指派问题，使得成本的计算更加准确。另外b r i a n 等 进一步研究了带畜靛班辩闻窑麓航班机型分配阀题，为航班时亥l 的优化谖整提供了一个有效翡 3 飞机一体化排班研究 分析工具强】。在飞机路线方瑟，c l a r k e 将飞机路线问题转换为带有边约束的旅行商问题( t s p 并利瘸l a g r a n g i a n 松弛算法求解翻；t a l l u r i 分析了4 天以上飞辊维护路线闻题的算法复杂性， 存在可行解的条件，并构造了一种“4 - d m r ”问题的启发式算法【1 0 1 。在机尾号指派方面，e l i n g 等建立机尾号指派的约束编程模型，并与列生成算法结合使用f 1 1 1 。 实际搡作中，航班计划通常是按照顺序分阶段完成靛，通过不断酶反馈修正最终褥至g 满意 可行的航班计划。现在越来越多的研究趋向于综合考虑广义航班计划中两个或者多个层次的计 划，例如将航班时刻表制定与机型指派综合考虑，机型指派与飞机路线综合考虑以及飞机路线 与机组接臻综合考虑等，主要酶综合优化方式如图1 1 魇示。 图1 1 航班计划综合优化方法 蘧着计算规糍力提嵩，综合优纯方法越来越受欢迎。1 9 9 7 年d e s a u l n i e r s t l 笱锋对一天酶航 班计划提出两个综合优化的模型：集合分割模型和带有时间约束的多商品流模型：1 9 9 8 年 b a m h a r t 以航班串为基础提出了一个机型指派和飞机路线的综合优化模型。r e x i n g ( 2 0 0 0 ) 弓 进了 前后两衔接靛班之闼时闻阕隰的交化，构建了嚣噻傲带有时阀窑的规型指派模型f a m t w 。它主 要考虑每航班的出发时间可以在1 0 - 3 0 分钟的范围内变化，把时间窗分割为1 1 等份，每等份点 为一种可能的出发时间方案，最优方案怒每航班出发时间从1 1 种方案中选取一种，同时完成机 型指派。这样可以给航班计划一定的柔性，使机型指派更有效，其后的飞杌路线问题的可行性 褥到了加强。k l i e w e r 提邂一个综合飞机指派和需求颈镤l 豹模型，但是缺乏细节。另外将枕组 排班与飞机路线结合，以及航班扰动后，综合考虑路线与机组、旅客流恢复也是目前研究的学 术趋势1 3 t 1 4 1 。 人键在研究综合优傀方法熬同对开始关注综合闻遂豹复杂性和求熬方法。i o a c h i me ta 1 与 4 南京航空航天大学硕士学位论文 d e s a u l n i e r se ta l 。提出基予分枝定界的d a n t z i g - w o l f e 分解法求解飞机指派和路线选择综合润题 润；c o r d e a ue ta 1 使用b e n d e r s 分鳃来实时解决飞枧路线和视组捧班综会问题；m e r c i e re ta l 。 1 6 1 扩展了c o r d e a ue ta 1 的模型并且使用b e n d e r s 分解，与c o r d e a ue ta 1 相比转换了次序，使用 机组配对问题代替飞机路线作为主问题，并进一步提出增加刚性条件以改善收敛性和降低计算 时阕瑟7 , 1 8 , 1 9 。 c h a n g 分析了先前的学者对广义航班计划的研究成果，构造了航班时刻优化和机型指派的 综合模型2 0 】( 2 n ，通过对旅客需求、航班计划的经济性以及可操作性的分析，分别建立了三种数 学模型，然惹针对这三方瑟的分析，改进了先前盼三个模型扶两建立了个裁定航班计划的菲 线性规划的综合模型。虽然在建立综合模型过程中，c h a n g 将很多实际情况作简单纯处理，但 从运算效率来看，c h a n g 的方法还是令人鼓舞的。此外，y a h 和t s e n g 基于旅客需求设计了一 个航班计划和飞机排班的综合模型，这是一个整数规划l a g r a n g i a n 松弛法结合多商品网络流模 型，该模壁霹以帮劲航空公霹露时铯化航班时刻的建立帮飞视捧班闻题，并且透蓬对台湾豹一 家航空公司进行实例验证( 包含2 个不同的机队，共2 4 架飞机，1 2 8 0 0 豳航班量和1 1 个关联 机场) 。 1 3 。2 国内研究现状 国内关于航班计划研究非常不足。相对而言，在航班计划内部组合和飞机排班内部组合有 过试探性研究，例如航班频率对亥4 与机型指派综合优化，飞机路线选择和飞机指派综合优化。 李耀华等辫1 分析飞视排班计划的编制流程，建立了航班串编制的v r p 模型，模型不仅考虑了 航班时间、出港到港机场衔接之间的约束，而且还考虑了客流量、维修基地机场的约束。为了 模型求解，构造了免疫算法，利用仿真验证。朱星辉等人瞄】提出了分阶段多航空公司竞争下航 臻频率研究，然癌又根据飞枧舱谴戆力、运营成本、潜在收益及飞视可潮性建立了周枫减指派 模型，并利用特殊有序集分枝定界算法求解。另外肖东喜 2 4 】等人以飞机维修最大化为目标函数， 建立了基于航班环的一周飞机路线的整数规划模型，采用列生成算法和f o l l o w - o n 规则，动态 构建满足“三天维修规则”的航班环。孙宏等【2 5 】将具体的飞机接班问题分成三种典型排班模式： 基于飞杌调魔指令要求，基于最少需用飞机数，基于飞机使用均衡要求。李丽娟泌l 提出了基予 乘客组合的飞机排班模型，徐进【2 7 】在已知旅客需求的时间函数条件下，建立了航班频率、时刻 优化模型以及固定航班时刻下的机型指派模型，这些模型按次序结合称为顺序优化模型，以此 提出闻时考虑靛班对蕤优鬣和枧型指派的综含优纯模型，并剩蔫对翔窑允许霹航班的蠢发到达 时间做一定程度的调整以便于更灵活成本更低的飞机调度方案。 5 飞机一体化排班研究 1 4 研究内容和方法 1 4 。1 研究内容 本文的研究内容包括飞机一体化排班模型的建立和模型求解两个方丽。首先介绍航空公司 飞机排班前提、规羹| l 及其约束，建立综含考虑飞枫冀 班多个层次的飞帆一体化排班模型，改进 飞机排班的效率。其次运用约束编程在i l o g 平台土构建飞机路线生成模型。然后设计歹| j 生成 算法求解模型，实现动态列生成，最后使用航空公司实例验证。 薹4 。2 研究方法 本论文以大量收集和阅读相关的文献资料为基础，充分借鉴国内外先进的理论成果，以运 筹学、最优化理论、计算机人工智能为基础，按照提出问题、定性分析、建立优化模型、开发 计算祝系统、分柝运算结果的愚路对飞执一薅耽接班模型与优让算法，i l o g 平台进蜇了探索 性的研究。在研究飞机路线的生成方法时，主要运用了约束编程的思想，并针对飞机一体化排 班为大规模艇数规划的特点，利用运筹学中的列生成算法，用算例对模型和算法的有效性进行 了分析。模型求解以及飞机路线生成方法实现主要应用i i d g 软件及其缀转。 1 5 论文结构 本文用五个章节对上述研究内容进行详细论述，具体安排见表1 1 。 表l 。l 论文章节安排和主要态容 阜 精 主要内容 第一章1 1 研究背景与目的介绍了论文的研究背景与目的，阐述了 绪论l 。2 靛班计划翔题撅述 航班计划内容和制定过程，综述了蕃内 1 3 国内外研究现状外研究现状，概述了论文的研究内容、 1 4 研究内容和方法 方法和文章结构。 l 。5 论文结构 第二章2 + l 飞视捧班闻题描述分缨了飞祝捧臻的流程和规煲| l ；从而提 飞机排班问题分析2 2 飞机一体化排班模型出综合机型指派与飞机指派的飞机一 与建模2 3 本章小结体化排班模型。 第三章3 。1 约束编程及i l o g 分绥 分绍了约束编程特点、公式及i l o g 软 约束编程与i l o g3 2 飞机路线生成模型件，详细描述了飞机路线生成问题以及 3 3 算例分析利用约束编程开发飞机路线生成模型 3 4 本章小结 酶过程。 6 南京航空航天大学硕士学位论文 表1 1 论文章节安排和主要内容( 续表) 第四章 4 1 主问题 针对飞机排班为大规模整数规划问题， 基于约束编程的列 4 2 约束编程子问题 提出列生成算法，线性规划作为主问 生成法 4 - 3 飞机一体化排班算法实题，基于约束编程的路线生成作为子问 现 题，实现动态列生成。 4 4 实例分析 4 5 本章小结 第五章5 1 论文工作总结对全文进行总结，探讨今后可以继续研 总结与展望5 2 研究展望究的方向。 7 飞机一体化排班研究 第二章飞机排班问题分析与建模 靛空公司生产计划的制定过程实凄楚对各生产要素憋优纯配置过程，因为生产计划蘸质量 和效率不仅关系到运输生产能否顺利进行，而且从根本上决定了企业的市场竞争能力。台理有 效地按照市场需求、自身资源等进行飞机排班是保证航空运输顺利进行的一个重要环节。本章 首先介绍飞桃排班约束和鼷标，然后给出飞机一体化摊班优化模型。 2 。l 飞机排班问题描述 飞机体化排班内容广泛。本文研究对象是将机型指派、飞机路线选择和尾号指派三个阶 段综合考虑的飞机排班阍题，郾在满足约束前提下，为每个靛班指定一絮具体尾号鳃飞机的过 程，并且使得总成本最小。约束分为基本约束和扩展约束，基本约束包括机型指派中的航班覆 盖约束和飞机资源约束，飞机路线选择中的连接约束，维修约束，航班限制等约束，以及尾号 指派的预指派约束。扩震约束指除基本约束终的约束。飞机接班的最优化目标也是多样的，可 以是成本最小化，也可以是飞祝数最小化以及飞机均衡使用等。 2 1 1 连接约束 连接约束是飞瓿撵班约束中最基本豹约京。篱 惹言之，连接约束包括黠闻衔接和机场衔接， 指同一飞机连续执行两个航班之间满足最小过站时间( m i n i m i z ec o n n e c t t i m e ，m c t ) ，前航班 到达机场与后续航班出发机场一致。过站时间内，飞机进行清洁、加油、为后续航班准备，更 换规缓和旅客登机。在繁虻襁场，过站时闻内飞机还会更换登机桥或者航站楼。另外，过站时 间长短与机型、航班类型有关，通常大型飞机过站时间较小型飞机长，国际航班过站时间较国 内航班长。 8 表2 1 一天航班计划 航班号出发机场到达机场漱发时闻裂达时闻 m u l o oda8 ：0 09 ：3 0 m u l 0 1da9 ：0 01 0 ：3 0 m u l 0 童a毛l l ： 1 2 ：0 0 m 时1 0 3a l1 2 ：3 0 1 3 ：3 0 m u l 0 4 fa1 4 ：0 01 5 ：1 5 m u l ac1 5 ：4 51 6 ：2 5 南京航空航天大学硕士学位论文 连接网络积时空网络是常见的两种网络类型。连接网络中的节点表示活动，有向边表示活 动与活动乏闻的连接，每个连接都是合法的，即满足时间、空闻约束，由于连接网络是非循环 的，而飞机排班具有周期性，因此难以实现时间回溯2 8 2 9 1 。表2 1 为航空公司机场a 的部分航 班时刻表，假设最小过站时间为3 0 分钟，连接网络如图2 1 ，虚线表示航班时刻表之钋航班的 连接。 8 ：0 0l o ：1 2 ：1 4 舯1 6 瑚 图2 1 连接网络示意圈 对空阙络中酶节点含有时舞和空间两维坐标。首先浚机场为纵坐标轴( 是离散的) ，耩各 机场的名称，对每个机场作一横轴，为时间轴，节点之阅纵向弧线表示一个活动，出发或者到 达节点可以合并删减以降低网络规模【3 0 , 3 1 1 。根据表2 1 航班计划得到的时空网络如图2 2 所示， 虚线表示地灏弧，从d 机场如发的航班m u l 0 0 与航班m u i o i 可以聚集隽一个节点。 2 1 。2 维修约束 8 ：0 0l o ：1 2 ：1 4 ：1 6 ： 图2 2 时空网络示意圈 飞机是一种特殊的交通运输工具，为了保证航空运输的安全，各国普遍制定了严格的航空 器适航管理法规以规范航空器的使用和维修，中国民用航空器适航管理条例是一部关于我国 靛空器适靛管理豹法撬。飞耄毽的维修是维护和修理麓总称，其中维护是为了保持飞辊露有靛技 9 c l 舂 d f 飞机一体化排班研究 术性能并发挥其最大效能所采取的技术措施：而修理是指当飞机出现性能衰减或部件失效或发 生故障时，为恢复其正常状态而采取的技术措施。维修的直接目的是保证飞机处于良好的可用 状态，即维持飞机的适航性。在我国飞机的维修工作主要是航线维护和各种级别的定检( 字母 检查) 3 2 , 3 3 】。 l 、航线维护 航线维护包括航前过站检查、航后检查； 航前过站检查：检查飞机内外是否有明显的损伤、渗漏、缺件，各种设备是否工作正常。 按照实际需要做例行的勤务工作，例如加燃油或润滑油、机内清洁工作、排故等，这些工作都 是在停机坪上完成的，然后飞机放行。 航后检查：对运营中的飞机，每2 4 小时之内必须执行一次航后检查，或称过夜检查 ( l a y o v e r ) 。航后检查包括所有航前，过站项目和其它航后项目，并按照要求进行机内清洁和机 外清洁，排除空、地勤人员反映的故障以及保留故障。 2 、定检 定检是指每经过一定的使用周期就需要对飞机进行的一系列检修工作，根据检修的内容分 为a 检、b 检、c 检和d 检四类： a 检：一般每5 0 - 6 0 飞行小时安排一次，包括对飞机外部、内部缺陷的目视检查，操纵系 统、电子电气系统的测试等工作，一般需要5 8 个小时，一般安排在航后有维修能力的基地进 行； b 检：又称大a 检，一般每3 0 6 - 6 0 0 飞行小时安排一次，检查项目与a 检大致相同但更 具体、细致，例如需要将飞机仪表拆下检查，并对平时不使用的应急系统，如灭火系统等进行 测试，b 检原则上要求飞机进机库，并停场l 2 天： c 检：一般每3 0 0 0 小时须安排一次，每次需停场扣1 2 天，主要工作内容涉及地板的腐蚀 性检查，受力构件的疲劳损伤，所有电子电气仪表拆下测试等： d 检：每2 0 0 0 0 小时须安排一次，又称为飞机结构性大修，每次需3 0 天左右，需要将飞 机彻底拆散并对主要受力部件如大梁、受力隔框等进行金属材料疲劳、腐蚀程度等的检查及处 理，然后将飞机重新组装。 日常安排飞机路线时需要考虑的一个主要的维修问题是飞机的a 检，a 检安排在航后的晚 上进行。根据a 检要求，定检可以转化为“三天维修规则”，即飞机在连续的三天飞行过程中， 至少有一天晚上在维修基地过夜，或者转化为“一天维修规则”，即要求飞机在一天飞行结束后， 必须在维修基地过夜。 1 0 南京航空航天大学硕士学位论文 2 1 3 航线限制约束 许多航线对飞机或者视缓有特殊要求。菜些航线规定登须由菜类、甚至某架飞枫来执行飞 行任务，称为航线限制约束。例如某条国际航线只能由b 7 6 7 机型来执行，高原航线、跨海航 线等，对飞机也有特殊要求，以拉萨航线为例，只有完成了动力系统和氧气系统特殊改造的a 3 1 9 等机型可以执飞，有些航线禁止外籍飞行员执行航班。此外，有些飞机由予载油不足、缺少机 载娱乐系统而不能执行远程航班。这魑约束可以通过禁止或者指定具体飞机执行特定航班来建 模实现。 2 1 。4 其它约束 除了连接约束、维修约束和航班限制约柬外，飞机排班还受到其他一些约束的限制。主要 有以下几种： 1 ) 飞机路线与机缀匹配约束，邸飞机过站时闻满足撬组换班时间。 2 ) 飞机均衡使用要求，即保证飞机飞行时间或者着陆次数均衡。通常一架飞机每天的飞行 薅闻大概在8 一1 2 夺对之闻，起落架次在4 6 次；长距离的国际航线一天的起落架次可能为l 2 次。 3 ) 机场对飞机着陆次数黻制。 4 ) 还有一类约束不是针对具体某架飞枧，丽是对靛空公司所有飞机资源丽言的，比懿，要 求制定排班计划满足航班覆盖约束，飞机资源总数约束等，这类约束通常是机型指派的基本约 柬。 2 。2 飞机一体化排班模型 。传统上飞机排班是分步完成的，即在机型指派基础上，筛选出同一机型的航班，构建航班 环，并指派具体飞机。这样分步优化可以简化问题，降低求解难度，但可能不能得到全局最优 解。另终枧型措派并没有考虑维修等运行约荣，飞枫排班可撬无解。因此零繁提出飞机一体纯 排班模型，改善分步排班的次优性。 飞机捧班阀遂是多商品瓣络流闯e t 3 4 j 【3 弱，其中一架飞机代表一个商品，航线隧络上圈对流 动着多架飞机，网络中每条边的容量为l 。假设在网络上流动着k 种商品，令k = - i ，2 ，k 表示 任意第k 种商l i i l ，在任意边( 切上，商龋流存在容量限制，各种商品的单位流都是占有一个单位 的容量，因此各种商品流之和不能超过该边的容量魄，第k 秘商品的瞬络流爨( 总嚣求) 力d 七， 在边( f 力上的单位流费用是露，并进一步假设受到该种商品流容量“：的限制。根据以上假设， 多裔晶流阀题的数学模型是： 飞机一体化排班研究 n 畦n z = y , k k k = l 延矿批矿 fd ， f = j 珐一= t o ，o t h e r w i s e k = l 纠2 “，k ( 2 1 ) 缈上r | 刁， l = t r 4 ；i , j v ( 2 2 ) k - - - 1 0 - 4 k o - 歹v ，k = l ，2 ，k ( 2 1 3 ) ( 2 3 ) 式中每个商品的弧容量上界和下界为( o ，甜；) ，u u 为弧容曩，式( 2 1 ) 为每个节 点和商品流平衡约束。式( 2 2 ) 表示每条弧上各种商品流之和小于弧容量。利用式( 2 2 ) 的左 边是关于菇晶流求和的，州傲捆绑式约束。 裂耀多商品流霹络模糍是飞辊撵班阏题的一般求解思路，但是由予捆绑式约束的存在，使 多商品流问题的求解陡增为n p - h a r d 问题【3 6 t 3 7 3 8 】【3 9 】。观察发现，飞机摊班中的飞机路线是由飞 机与其执行的若干个航班组成，因此可以将多商品流模魁转化为基于飞机路线的飞机一体化排 班模型，通过构建飞机爨线来解决飞规排班闼题。 2 2 1 建模假设 飞机1 4 # 班一体化模型假设包括； 1 ) 已知靛班对刻表，即航班频率、航班对刻已经完成，本文只考虑一天内魄靛班计戈| j ，因 此不考虑航班频率； 2 ) 已知各航班旅客需求； 3 ) 不考虑经停航班，即只考虑航节，飞机完成一次起降所执行的一次飞行任务； 4 ) 机场停机坪无容熬限制。 2 2 2 飞机路线 安排飞机路线是航空公司日常运营过程中一项菲常复杂的工作，航班计划人员在制定航班 计划时，为了保证排出的航班计划不超过可用飞机数量，通常将航班时刻表一天中的航班进行 衔接，得到一系列的航班联线，也称航班帛。航班串指满足连接约束的航班按照顺序组合在一 超形残豹一缀靛班集合。 航班环指若干天内满足飞机维修定梭蒙求的航班组合成的航班串，该航班串的起点和终点 是同一个维修基地。以维修基地为起点和终点的航班环有广义和狭义两种：狭义的航班环要求 起点和终点是霹一维修基蟪，广义的航璇环只要求起点移终点楚维修基遮瑟可。磊煎邂内舷窒 1 2 南京航空航天大学硕士学位论文 公司在维修基地的设置方面存在单维修基地和多维修基地两种情况。一些大的航空公司通常拥 有多个维修基地，多种机型的飞机。但从飞机机型来讲，仍然是单维修基地为主，即同一机型 的飞机只有一个维修基地。“三天维修规则”中的航班环执行周期是3 天【2 4 1 ，本文只考虑狭义 的航班环，执行周期是1 天，即满足“一天维修规则”的航班环。 区别于航班环，一条飞机路线由一架尾号的飞机与一个航班环组成，飞机执行此航班环中 的航班，航班环满足该飞机的维修要求、航线航班限制等约束。飞机路线的成本包含运行成本、 旅客溢出成本和座位虚耗成本三部分构成。运行成本为航班环总飞行小时与该尾号飞机机型的 单位小时飞行成本之乘积。如果航班旅客需求小于飞机座位数，溢出成本为0 ，只发生座位虚 耗成本；反之，座位虚耗成本为0 ，只产生溢出成本，因此只需要计算溢出成本与座位虚耗成 本之和。 2 2 3 飞机一体化排班模型 针对国内航线网络和航班计划的特点综合考虑机型指派、路线选择以及尾号指派，建立成 本最小化为目标的飞机排班一体化0 一l 整数规划模型。建立模型所需变量说明： ，：表示航班集合，f f ，每个航班信息包括出发时间( f d e p t ) n i n o n ( f a r r t ) ， 出发机场( f d e p a ) ，到达机场( f a r r a ) ，预测旅客需求( f p a x ) 和平均票价( f f a r e ) 。 彳：表示飞机集合，a a 。 k ：表示机型集合，v a a ，七( 口) k ，七( 口) 表示飞机a 的机型。机型信息包括最小 过站时间( 尼m i n s t o p ) ；基地机场6 ( 后) ；机型座位数( k a ) ；日最大起降次数( k a t a x d u t y ) ； 机型单位小时飞行成本( k c o s t p h ) 。 b ：表示所有基地机场的集合，v a a ，6 ( 尼0 ) ) b 。 l ：表示飞机路线集合。a a ，l o 表示飞机a 所有可行的飞机路线集合，j l o l 。 t o w ( t ) 表示飞机路线，的首航班，u p ( 1 ) 表示尾航班。 ：表示预先规定必须由飞机a 执行的航班集合。 r ：表示预先规定不能由飞机a 执行的航班集合。 c t ：表示飞机路线z 的成本，包括该飞机执行所有航班的运行成本c 严；旅客溢出和座位虚 耗成本之和矿，即c t = 矿+ c ；p i 。 示性算子，即= 三 ：示性算子，= 三 飞机路线，覆盖航西眵 飞机路线，不覆盖航野 飞机a 可以执行飞机路线， 飞机a 不可以执行飞机路线， 1 3 飞机一体化排班研究 而：。- ，决策变量，西= 三 乏襄誓萎；篥蓑主中； m i n z = c j x t n e a t p 以夕西= 1 ，v f e f i e l 吃，而1 ，v a a l e l o 口，吃，而= 1 ，v a 彳，可只 ，e r 口夕而= o ，v ae 彳，v f r , i e r 口6 口，为 k ( a ) a 4 a x d u t y ，v ae a f e f x e i t - v a a ，= 1 有： ( 2 4 ) ( 2 5 ) ( 2 6 ) ( 2 7 ) ( 2 8 ) ( 2 9 ) ，= ，o l i ，j e f ，o r d e r e d b y ( d e p t ) ，i a r r a = j d e p a & i a