（计算机应用技术专业论文）航空公司小规模机群飞机排班问题的数学模型和算法分析.pdf

中国民用航空学院硕上学位论文 a b s t r a c t a i r l i n eo p e r a t i o n a lp l 锄i n g ，e s p e c i a l l y 碱1n 啪b c ra s s i g 舯e n t ( t n a ) ，i sv e 咖a r da | l d i m p o r t a n tw o r k ，w h i c hq u a l 毋a 1 1 de 币c i e n c yi sc o n c e m e d 谢mt h es a f e t ya n db e n e mo f a i r l i n eo p e r a t i o n b e c a u s eo fm ec o m p l e x 姆o ft n ap m b l e m ，m e r ei sn oa c k n o w l e d g e d r e s 0 1 v em e a i l sa tp r c s e n t t h em a m e m a t i c a lm o d e l i sn o tp r o c l a i m e da l s o 1 1 1 i sd i s s e n a t i o nd e t e n n i n e st h es t u d ys u b j e c ta st n a p r o b l e m i 1 1m i n i a t u r e t h e o r e t i c a l ly ，c o n s t n 】c tt h em a t l l e m a t i c a lm o d e l w h i c hi s 印p r o p r i a t ef o ra i r l i n e si nc h i m 丘r s t t h c np r e s e n tm ec o n c e p to fr e s t r i c t i o n s p a c e ，a n dm er e s u l ti sc i r c u m s c r i b e dw i t h i n r e s t r i c t i o n s p a c e a s 廿i n g e n c ya n a l y z eo fs i m p l e 趾ta l g o r i t mi su n d e n o o kb a s e do n m a r k o vp r o c e s s a c c o r d i n g a s 6 0 。p r i n c i p l eo fg e o m e t r y i n f o n i l a t i c s ，t h er e p u l s i v e p h e r o m o n ca n d 删n c t i v ep h e r o m o n ea r ei n t m d u c e di 1 1 t oa n ta l g o r i 恤m ，i n s t e a dm eo n l yo n e p h e r o m o n ea n dan e w a n ta l g o r i t h mi sd e v e l o p e d c o n t r a s tt 0f u l l - s e a r c hm e m o d 肌d c u p i d i t y a l g o r i ，t 1 1 en e wa ma l g o r i i sb e t t e r t h a l lo t h e r s i np r a c t i c e ，t l l et n a 访f o m a t i o n s y s t e mf o rt i a n j i nn l i a l eo f a i rc h i n ai sd e v e l o p e db a s e o nm em 抽e m a t i c a lm o d e la 工l dt h en e wa n ta l g o r i t h m ，a i l da sas u b s y s t e mo f t h em a i n t e n a n c e m a i l a g e m e n t1 n f o n a t i o ns y s t e m ，w a sc h e c k e da 1 1 da c c e p t e db yh e a d q u a r t e r so fa i rc h i n 巩 r e a l i z e d 廿l et r a n s f o mf b mt l l e o r yi n t op r a c t i c e k e ) 唧o r d s ：t a i ln 岫b e ra s s i g m e n t ，趾ta l g o r i l i i l ，g e o m e t 叫n f o m a t i c s i i 中国民用航卒学院硕士学f 电论文 第一章绪论 飞机排班是航空公司制定生产计划时的项基本内容，即排班人员根据飞行时刻表 和飞机维修计划以及飞机的空中时间给出的飞机调度决策，为每个航班指定一梨具体执 行的飞机。飞机排班本质上是组合优化问题，是民航界著名的n p - h a r d 问题，但又是无 法叫避的问题，该问题解决的好坏直接关系着民航的安全与效益，因此每个航空公司都 十分关注该问题的进展。 由于飞机排班问题的复杂性，目前尚无公认的软件解决方案，许多航空公司在e 机 排班的环节上仍然采取人工编排的模式。在机群规模较小( 数量级为1 0 1 ) 时尚可依靠 人工完成，然而当机群规模达到一定限度( 数量级为1 0 2 ) 时，人工排班不仅浪费大量 的人力及时划，而且效果也不尽如人意。 随着2 0 0 8 年奥运会的临近，我国民用航空业开始加速发展，航空公司运营规模1 i 断扩人，完全依靠人工完成飞机排班工作的难度越来越大，甚至已不可行，各航空公司 均迫切需要借助于计算机来提高飞机排班的工作效率，保证飞机的安全运营。因此解决 民航飞机排班问题极具现实意义。 为此，我的导师王锦彪教授于2 0 0 4 年提出了多巢多食蚁群算法研究与民航飞机 排班的科研课题，得到了国家自然科学基金资助( 编号：6 0 4 7 2 1 2 1 ) ，列入了国家自 然科学基金委2 0 0 5 2 0 0 7 年度蓝天计划。本文的研究就是在该课题的背景下开展的，是 该课题的重要组成部分。 本文的研究内容包括： 1 适用于我围围情的小规模机群飞机排班问题数学模型的建立 由丁飞机排班问题的复杂性，目前尚无公认的软件解决方案。国外知名的软件公司 虽然已有相关的产品，但是价格昂贵，酊且不适用于我国航空公司的具体情况：向国内 软件公司一直缺乏清晰的数学模型和理论支持，因此至今没有推出高水平的飞机排班模 块。本课题研究的最终目标是要丌发出具有自主知识产权的飞机排班软件，所以从小规 模机群入手，建立适用于我国国情的飞机排班数学模型就成为本课题研究的笫一个关键 环节。 2 蚂蚁算法的研究 研究表明，蚂蚁算法对实现飞机排班数学模型有突出的优势，但是许多文献在论述 蚂蚁算法的时候普遍提到了收敛速度较慢的问题。由于飞机排班问题的时效性，在航空 公司运营规模不断扩大和机群数日不断增加的情况下，设计一种新型的、快速的蚂蚁算 法就显得十分必要。 3 飞机排班系统的开发。 飞机排班问题研究的最终目的是要为航空公司服务，由计算机取代人工来进行有效 的排班，以提高排班的效率。因此在研究过程中以国航天津分公司航修基地为依托，在 的排班，以提高排班的效率。因此在研究过程中以国航天津分公司航修基地为依托，在 中国民用航空学院硕士学位论文 飞机排班实践中不断加深对人工排班经验的认识，总结升华为数学模型和算法，开发出 飞机排班原型后，再到实践中与人工编排过程进行比较，通过航空公司飞机排班的具体 实践来检测算法的j 下确性和可行性，使理论研究与实际生产相结合。 本文组织情况如下： 第二章介绍了近年来国内外在航空公司生产计划，特别是飞机排班方面的研究成 果、蚂蚁算法方面的研究成果以及蚂蚁算法在飞机排班问题中的应用。 第三章叙述飞机排班问题的理论基础。包括飞机排班问题的数学复杂性分析、建立 飞机排班数学模型、约束空间的建立、简单蚂蚁算法的收敛性分析和蚂蚁的几何信息学 原理。 第四章介绍了作者在国航天津分公司生产计划中心长达一年的实习过程中获取的 飞机排班问题的各种约束条件以及排班规则，并根据蚂蚁几何信息学原理设计了求解飞 机排班问题的新型蚂蚁算法，通过与遍历和贪心算法的比较，得出了该算法较优的结论。 第五章介绍了适用于国航天津分公司的飞机排班系统的开发与实践。 第六章在总结小规模机群飞机排班数学模型与算法研究成果的基础上，对我国中大 规模机群飞机排班问题的解决方案提出建议。 中国民用航空学院硕士学位论文 第二章综述 随着全球航空公司之间竞争的加剧，各航空公司均采用先进的管理方法来降低成 本，提高收益，以图维持并扩大自己在民用航空运输领域内的市场份额。 在国外，由于航空运输生产实践和市场的需求，航空公司生产计划制定的优劣直接 影响到公司效益。航空公司生产计划主要包括机型分配计划、飞机调度、收益管理、机 组人员分配、机场资源分配等方面。由于航空运输中生产计划工作的重要性和复杂性， 欧美的许多大型航空公司从上个世纪八十年代开始广泛应用生产计划管理系统软件，以 提高生产计划工作的质量和效率，并取得了巨大的成功。以美利坚航空公司为例，1 9 8 8 年航班机型分配系统软件在该公司投入使用后仅一年，就实现了7 5 0 0 万美元的收入增 长，机组管理系统软件，每年可为公司节约机组成本2 0 0 0 万美元【2 j 利用另一个收益 管理系统软件，该公司使航班的空闲座位率从1 5 降至3 ，机票超售损失减少了 6 2 1 3 】【4 】。 航空公司生产计划一直是m s 0 r 领域研究的热点。这些研究工作可分为以下几个 方面： 1 机型分配问题( f l e e ta s s i 2 n m e mp m b l e 卜f a m ) 机型分配问题是指给航班分配合适的执行机型，使所有航班执行后所获得的总利润 最大。主要研究包括：m a r k s d 嬲l 【i n 基于各航空公司普遍采用的单枢纽结构的特点，建 立了一个描述f a m 的整数规划模型，并应用l a g r a i l g i c a i l 松弛算法求解了航班总收益 的上界值【5 】。h a n ec _ a 通过求解大规模的整数规划问题研究了一般形式下的机队分配问 题，并成功地处理了一个拥有1 1 种机型，每日航班达到2 5 0 0 个的大型航空公司的航班 机型分配问题1 6 】；z w c l a r l 在h a i l e 研究的基础上，进一步考虑了飞机维修计划安排以 及机组排班等因素的限制，并对h a n e 提出的数学模型进行了完善，使解更接近实际的 需要【7 】i8 1 。b r i a n 等进一步研究了带有航班时间窗的航班机型分配问题，该项工作的价值 在于不仅能进一步优化航班的机型分配，而且为航班时刻的优化调整提供了一个有效的 分析工具【9 1 。 2 维护路径问题( m r p m a i m e n 眦er o 谢n gp m b l e m ) 欧美等国家的航空公司在编制飞机排班计划时必须考虑的一个很重要的约束就是 “4 天维护计划”( 4 d a y s m a i m e n a n c e m l e ) 。即在任意一相邻4 天内，必须安排飞机在 有维修能力的基地过夜一次以便于安排维修工作，这样做是为了最大限度的减少由于飞 机停场维修而造成的运力损失，一般将各维修工作的内容分解，重组并打包，每个维修 工作包的内容基本上可以在一次过夜时间完成，同时沿航线网为每种机型建立了多个维 修基地，飞机每到达一个有维修能力的基地时就完成一个维修工作包，并规定每相邻两 次维修工作的间隔不得超过4 天，因此飞机航班编排与飞机的维护路径编排保持一致。 这方面的研究工作有：k a b b a i l i 和p 嘶通过生成航班路径集合( 1 i n eo fn i g h t s ) 从 中国民用航空学院硕士学位论文 第三章飞机排班问题的理论基础 3 1 飞机排班问题定义 飞机排班是指排班人员根据公司的航班计划( 体现为飞行时刻表和调整表) 和飞机 维修计划为每一个航班指定一架具体执行的飞机，也就是给每一个航班号分配一个相应 的机尾号( 1 ：a i l n u m b e r a s s i g n m e n t t n a ) 。 为了叙述方便，明确以下几个概念。 排班周期：即进行一次排班所安排的航班计划的天数。一般为一周，即7 天。 飞行时刻表：航空公司下发的明确规定了需要执行的所有航班的航班号、执行机型、 班次、班期、起飞到达时间、起飞到达航站以及执行的日期段的航班计划。一般一年下 发两次，分别称为冬春航班计划和夏秋航班计划，是航空公司的中长期航班计划，一般 不作调整或很少调整。如表3 1 所示。 表3 1 飞行时刻表 班 航航航 航班号机型班期起飞到达起飞到达起止u 期 次站站 站 b 7 3 7 北兰 1 5 - n o v 2 5 m a 卜 c a l 2 7 161 24 5 6 78 ：3 01 0 ：3 5 7 0 0尿卅l0 50 6 c a l 3 7 1b 7 3 7 天 海天1 1 n o ”2 1 ，m 61361 6 ：4 01 9 ：5 02 0 ：3 52 3 ：4 5 ，23 0 0津 口津0 50 6 lilllil i i i i 航线：即航空公司开展运营的路线，包括起点、终点、经停等要素。航线资源是航 空公司的宝贵财富，航空公司要想在某条航线上开展运营，首先必须取得航线的运营权。 1 9 8 3 年美国泛美航空公司破产后，其太平洋航线经营权的拍卖价达到1 8 7 亿美元【3 4 j 。 班次：班次规定了该次航班每周执行的次数。如班次为6 ，则说明该航班每周执行 6 次。 班期：班期规定了该次航班在一周内执行的日期。如班期为136 ，说明该航班 于每周的周一、周三和周六执行。 飞行时刻表中的起止臼期规定了该航班执行的时间段。班次、班期和起止日期共同 确定了航班的具体执行日期。 调整表：航空公司下发的对飞行时刻表中特定航班的临时调整计划。由于售票或其 他一些原因，在航班执行中会对飞行时刻表中的航班做一些局部调整，如取消某r 某航 班或将某日某航班的执行机型更改等，这就通过调整表来实现。 中国民用航宁学院顾十学位论文 机型：指执行该航班所嚣辩打赫铂订蝓! 渤j 竞争不断加剧衙嶙堙? 司逐渐意识。到加帮至：r 豇。烈室；学森龉警。青 蒋葙答。括秤福真：总体来说，关于机队；硼度管理。豆驯叫州益 型r 鹭最斛二澎习 朝喃i 嗡甬萧势堇x 痞m 声辑褰舅一翻氟。莉鸶张赫帚k 孔雏舡赢鞘烈雕鳓若烈霄 j 复衙；l 筝磊里囊1 0 ；粥研。 填喇；爵一一 扫排班问题、基于最少需用飞机数的排班问题和基于飞机使用均衡 要求的排班问 题三种典型排班模式中的一种，针对基于飞机调度指令要求的排班问题提出了标号算法 和分阶段指派算法；对于最少需用飞机数的排班问题将寻找航班节衔接方案转化为一个 二部图的匹配问题，进而通过解两个二部图的最小权最大匹配，寻找使需用飞机数最少 的飞机调度方案；对于飞机使用均衡要求的排班问题，通过构造一个描述航班节间衔接 关系的航班节网络模型将原问题转化为一个使目标函数最小的航班节编组问题，并构造 了模拟退火算法【1 7 】 1 8 【1 9 l 【2 0 1 。崔林琳等提出飞机排班需兼顾乘客流向及其变化规律，利 用交互式的乘客订票系统，可以使航班分散，从而缓解忙时运力紧张、闲时运力浪费的 局面川。 受到自然界中真实蚁群集体行为的启发，意大利学者m d o ri g o 于1 9 9 1 年，在他的 博士论文中首次系统的提出了一种基于蚂蚁种群的新型优化算法蚂蚁算法，由于算 法中用多个蚂蚁共同进行优化搜索，所以又称为蚁群算法( a n tc o l o n yo p t i m i z a t i o n ， a c o ) 。蚁群算法中提出了人工蚂蚁的概念。人工蚂蚁具有双重特性，一方面，它们是 真实蚂蚁行为特征的一种抽象，通过对真实蚂蚁行为的观察，将蚁群觅食行为中最关键 的部分赋予了人工蚂蚁；另一方面，由于所提出的人工蚁是为了解决一些工程实际中的 优化问题，因此为了使蚁群算法更有效，人工蚂蚁具备了一些真实蚂蚁所不具备的本领。 除了已经得到公认的遗传算法、模拟退火算法、禁忌搜索法、人工神经网络等热门进化 方法，新加入这个行列的蚁群算法正在丌始崭露头角。 蚁群算法最初应用于旅行商问题( t s p ) 田】【”，自从在旅行商问题和工件排序问题 上取得成效以来【2 ”，已经陆续渗透到其他领域中，如：图着色问题【2 、大规模集成电路 设计【2 7 1、通讯网络中的路由问题以及负载平衡问题口8 】、车辆调度问题口0 1 等。蚁群算 法在若干领域已经获得了成功的应用。可以将这些应用分为两类：一类应用于静态组合 优化问题，其典型代表有t s p 、二次分配问题( q u a d r a d c 船s i 印i n c n tp m b l e m ，q a p ) 、车 间调度问题、车辆路由问题等；另一类应用于动态组合优化问题，例如网络路由问题。 二次分配问题【3 1 j ( q a p ) 就是将n 个设备分配给n 个位置，从而使得分配的代价最 小化。代价是将设备分配到位置上的方式的函数。m a n i e z z o ，c 0 1 0 m i 和d o r i g o ( 1 9 9 4 ) 将 最小一最大启发信息引入蚁群算法并用于求解q a p ，因此产生的算法a s q a p ，在一系 列标准问题上进行了测试，结果表明该方法优于其他方法。蚁群算法在车间调度问题 ( j s p) 中的应用也得到了初步的研究，利用j s p 的极取图模型与t s p 问题的相似性， 可用蚁群算法求解j s p 问题，并取得了一系列较好的实验结果。d c o s t o 等人在m d o r i g o 中国民用航空学院硕士学位论文 “飞机一航班组”的匹配要求如表3 6 所示： 表3 6 飞机航班组匹配 b 机 航班组 前周末定婚酶搓季郸嚣瞢 釜暑薹| ：臼嗾鼍偿臻骥 乇_ 唰舶利酣耻墼静轧 夏搦蚋m 塞南囊型叁型礴葛薹耻 h 燃业姜苇痹* 滴繁诺雪。牾被舞4 肼鬻揍澄刈。哪目峨洌臻m 碾砸悝崾狮埯孝 1 幽獬一烈局昏器熊；葫裂裕兰类铺* 越l 吖翳翥揣咎。栽掣囊翼藤降西幕嘎提并 重新打包，因此现在只有a 检、c 检和d 检) ： a 检包括对飞机外部、内部缺陷的目视检查，操纵系统、电子电气系统的测试 等工作，一般需要5_ 8 个小时。一般安排在航后，并在有维修能力的基地进行，不需要 停场。 c 检c 检每次需停场8 1 2 天，主要工作内容涉及地板的腐蚀性检查、受力构件 的疲劳损伤、所有电子电器仪表拆下测试等。 d 检又称为飞机结构性大修，每次需3 0 天左右，需要将飞机彻底拆散并对主要 受力部件如大梁、受力隔框等进行金属材料疲劳、腐蚀程度等的检查及处理，然后将飞 机重新组装。 各项字母检进行的时间安排与飞行时间间隔和机型有关，如b 7 3 7 3 0 0 飞机，a 检 的时间间隔为2 5 0 飞行小时，即从上次a 检完成到下次a 检开始，飞行时间的间隔不 得多于2 5 0 小时，c 检的时间间隔为4 0 0 0 飞行小时，d 检的时间间隔为2 5 0 0 0 飞行小 时；而b 7 3 7 7 0 0 飞机，a 检的时间间隔为5 0 0 飞行小时或6 0 天，先到先算。c 检的时 间间隔为4 0 0 0 飞行小时，d 检的时间间隔为2 5 0 0 0 飞行小时。 故障保留项目 现代航空器普遍按照多裕度设计理论设计的，因此允许飞机在一定条件下保留故障 飞行以提高机队的派遣放行率，并便于维修部门合理制定飞机排故计划，降低维修成本。 具体说就是对于符合最低放行设备清单( m e l ) 以及构形偏差清单( c d l ) 要求的故障 设备，允许飞机按照一定的限制，在规定期限内继续飞行。但是这种保留故障放行的措 施毕竟是一种权宜之计，因此在适航管理条例中规定了严格的故障保留申请和批准制 度，并制定了严格的故障保留底线，如a 类故障为2 4 小时，b 类故障为7 2 小时，c 类 故障2 4 0 小时，d 类故障2 8 8 0 小时等，所以维修控制部门在批准规章保留的同时必须 制定相应的排故计划。 适航通告( a d ) 项目 在适航管理工作中，民航当局及飞机制造厂家经常会根据飞机使用中发现的问题针 中同民用航空学院硕士学位论文 3 4 1 简单蚂蚁算法的收敛性分析 下面给出几个有用的引理( 由于篇幅限制，引理的证明请参照附录b ) ：引理1 1 。( 一刁，s m 。c r ，s 、n - ( - 一刁，+ 旦二! ：； 9 兰! 竺( 3 1 9 ) 2 z，岫c-一叩，cn+51=-；i：!；!i尘堡 3 2 0 引理21 矩阵h l l 为概率矩阵( 即每行之和为1 ) 2 当u 宝堡，薹。驯邕黜裂j 鏊搪_ ：f 于s 币羹掣孽趔鱼h 虹吼j 尘群i i 热不：瞰每秀休思时间币一得世土永卉孽藓旦伍臻翁暇缉 震l鍪l i 譬羹l ； 辖珥耋 群；0 。目；i 强i 霉姓毯“髓种皓“鲥弱嚣幽t 罐獭! 滤i i l j i 喜。羹绢历扭于亍的蓟个| 。 拙烈l醣蜀丽西基i 青幂抽 系列准备工作，包 括飞机检查、飞行前准备以及办理飞机过站的手续，这个时间的长短随机型及航班的性 质而定，如b 7 3 7 型飞机执行的国内航班一般需要4 5 分钟，而a 3 4 0 型飞机执行的国内 或国际航班一般需要9 0 分钟以上。飞机衔接是指分配给一套机组执行的航班应尽量安 排一架飞机执行，这样不仅可以方便机组，减少由于换飞机而带来的无谓工作，而且更 重要的是可以避免由于回程航班延误而引起的关联航班延误。 公平性。由于不同航班所飞的区域、航程、航班时刻的不同，从而决定了不同 航班的工作强度、复杂性、待遇不同。对于国内的航空公司，这个问题尤其突出。例如： 飞国际航班是公认的好差使，因为不仅飞行津贴高而且享受带薪休假；而每天的早班和 晚班，因为需要早出晚归很辛苦，因此一般飞行员都不愿意飞。此外，飞行时间短而起 落多的航班、涉及复杂航线和机场等的航线一般不愿意飞，因为工作强度大，技术难度 高，因此在编制机组人员排班计划时还应做到“好、坏”航班的均衡。 要以最小的人工成本完成所有的航班任务。这是最核心的一条。航班执行过程 中发生的机组人工成本受很多因素影响 删 4 5 】【4 6 】m ，这里不做详细叙述。 鉴于机组排班工作的重要性和复杂性，国外各大航空公司均专门聘用了许多m s o r 领域的学者从事这一方面的理论方法研究，并研制了专用的机组排班管理软件。例如美 国航空公司的a ir c r e w s 软件【4 8 1 ，利用该软件，每年可以节约人工成本2 0 0 0 万美元。 近年来国内各大航空公司也纷纷加强了这方面的工作，陆续建立了自己的机组管理系 统软件，如南方航空公司的s o c 软件中就包含了一个机组排班模块。 中国民用航空学院硕士学位论文 眠，) ；乱竖华型即得慨旷，骢兀 又因为v7唯一，所以熙s，的每行向量为v7a注意到v7为概率向量，各 分量之和为l ，因此不论t _ m 1 时蚁群处于何种状态。在f 一+ m 时必以概率1 收敛于全局最优。 342公式与参数讨论 f 面定性地讨论在其他参数给定的条件f ，关于选掸概翠公式和曩减度q 的取值 问题。当不考虑变异因素时，有如下定理： 定理2 ：若算法s a a 中s t e p 2 的选择概率公式取为式( 3 1 7 ) ，则算法不以概率l 遍 历解空间： 证明：考虑迭代次通驯i 强一南二玲撵骗刽! 划丑韶静m 辨靳；豁筝艮雾i ；i 蛆 戥删脚嬲纠桨铷2 黧蠢! 滞臻虬二蠢剖翥烈鞯巍戡蟊 蟛灏；慧! 。篓羹j 藜! 一 晨 湖i l l * x l ；一耋i ：毒；圣；! 一蓦商= 一；誊； ；i 2 i i 善j + 囊鬟鬟箍| i 于该项工作的高度专业性， 本文不作详细介绍【5 0 1 。由于在制定运营飞行计划的过程中需要进行大量数据的分析和优 化工作，因此在实际工作中需要借助于专门的分析软件来完成，常见的这类软件工具如 j e p p so n 公司的l f t s t a r 软件，s a b r e 公司的f l t p 御软件等。 4 2 飞机排班问题 如上章所述，飞机排班是根据航班计划和飞机的维修计划所做出的飞机调度决策， 如图4 2 所示： 由图中可以看出，飞机排班主要涉及三个方面：飞行时刻表中的所有航班集合、待 中国民用航空学院硕士学位论文 图3 2 树根分布图 研究结果显示，当蚂蚁外出觅食或在返巢的途中，一般情况下它们都会释放特殊的 信息素标示行进的轨迹当行进路线出现一定角度的转弯，它们便会释放这种微量的 特殊气味作为路口路标，同时标示出来可以暮釜烈引掰w m 删捎小睡节鲥引薪；鞫目稚 能拍一豳墼稀髓囊茜 露。捌产乱懈甜简芰萋奇龟型墟蠖拔塑那鹕簟j “蛳列“航 站( 例如国际航站等) ，则飞往这些航站的航班不能指派给该架飞机。 分配给飞机的航班任务要与飞机的维修计划相匹配。如某飞机某日安排停 场维修，则该日不能给该飞机指派航班；某飞机某日晚上安排了维修工作， 要求于1 9 ：0 0 点之前返回基地，则该同1 9 ：o o 点以后才返回基地的航班不 得指派给该架飞机；某飞机由于维修的需要，某同必须到达某基地以接受 检修，则该日到达航站不是该基地的航班不能指派给该架飞机。 与调度通告的匹配。如通告某飞机只能执行特定的航班，则其他航班不能 指派给该飞机来执行。 飞机排班除了要满足以上最基本的约束条件之外还要参照飞机维修计划。飞机停场 维修计划是根据飞机本身状态信息和市场信息制定出来的，而飞机执行航班会改变自身 的状态信息，如自开始飞行时间等。因此飞机航班编排和制定维修计划两者是相互影响， 相互支撑的。一方面，飞机航班的编排要根据维修计划，在计划安排的字母检或其他停 场大修之前使飞机的自开始飞行时间尽量接近规定的飞行小时数，以减少经济损失；另 一方面，飞机维修计划的制定也是根据飞机的自开始飞行时间，参照有关规定及维修基 中国民用航空学院硕士学位论文 图3 3 根据拉特尼克斯的蚂蚁6 0 度法则设计的蚂蚁寻食路径网络拓扑图 图3 4 树根分布俯视图 3 5 2 蚂蚁的寻食和返巢的两个不同的行为 寻食：为了达到以最小的能量换来食物定位，即最大范围的覆盖寻食区域，因此， 蚂蚁的协同寻食过程应该是排斥的。即不应该过度重复已搜索过的路径。可以想象，前 行的蚂蚁应给后来的蚂蚁留下一种寻食信息素，告诉他们，当前的路径他们已经走过。 后来的蚂蚁则选择不同的方向继续搜索。或者说，寻食的蚂蚁到达一个6 0 度分叉，它 应该选择信息素浓度小的方向前进。只有这样，协同寻食的蚂蚁才能最大覆盖蚁巢附近 能够提供食物的有效平面。 返巢：根据刚才的分析可以知道，以蚁巢为中心，存在一个信息场。其浓度呈现递 减的趋势。如图3 5 所示。因此，蚂蚁应该受到这个信息场的驱动，返巢时会直接朝向 中国民用航空学院硕上学位论文 有，将n 个有效航班根据衔接规则组合为m 航班组，即【c 】卅。二 ；。崮；。时孽零雕s 粪黧 。熏瓣； 鬻塑i 釜萎i 咎一i j 彳j i i 霪：；掣工恻茎配至每种类型， 堕l ，? 疣州v 删匕蕊掣；i ；l ；4 雏湘矿帮韬i ；。悭旧吲 遥灌惜铡喾嘉蓑& i 拦弘堋夔覆踅鞘手蓬要鱼渺燮覆钙蜓些彗阢予扎强灯薹 霾髫确酾碥饼；拍，囊 3 号飞机为b 7 3 7 - 3 0 0 型，4 号、5 号飞机为b 7 3 7 70 0 型，周一执行机型为b 7 3 7 3 0 0 的航班的飞行时 间总和为1 2 飞行小时，执行机型为b 7 3 7 7 0 0 的航班的飞行时间总和为1 0 飞行 小时，周六与周一相同。则计划飞行时间如表4 2 所示。 d 人工调整计划飞行时间。 由于各架飞机的自丌始飞行时间不同，为使同一机群中各飞机的停厂维修时 间呈阶梯状分布，且互不重叠，可能会要求某架飞机多飞或者少飞，以便使飞机 在计划的停场定检之前尽量飞够需要的小时数，减少损失，因此需要排班人员来 人工指定有特殊要求的飞机的计划飞行时间。除指定的之外，同机型其余飞机平 均分配剩余飞行时间。如表4 3 ( a ) 所示的计划飞行时间，人工指定3 号飞机本 周在停场之前要飞够2 5 飞行小时，则该飞机周一至周五的计划飞行时间为5 ， 其余飞机的计划飞行时间如表4 3 ( b ) 所示。 表4 3( a ) 4 3 4 5 466 3 2 43 4 54 中国民用航守学院硕士学位论文 4 约束空间。以上讨论的是无约束空间飞机排班的情况。实际的飞机排班是在许多 约束条件下实现的。这些约束主要表现在对蚂蚁交换路径的阻塞上，可表示为m = m 一， 组合空间由c 三变为c 三一f ，如果考虑到每天的约束差异，可表示为则算法复杂性可 描述为： 兀( q 一。) j 2 l 本算法充分考虑了飞机排班过程中的航班衔接规则、飞机禁飞属性等构成的对解空 间的约束作用。这种约束虽然造成了算法实现的编程困难，但是，也正由于这些约束使 飞机排班解空间的坍缩，才给我们提供了解决飞机排班问题的机会。 中国民用航空学院硕十学位论文 图4 - 3 排班流程吲 具体的排班过程如图4 3 所示：在原有飞机维修计划的基础上，排班人员根据飞机 的状态信息( 主要是空中飞行时问) 对飞机的停场维修计划给予修正，并结合修正后的 维修计划计算出本排班周期各架飞机的计划飞行时间。同时将飞行时刻表中的航班具体 化为本排班周期需要安排的航班，再结合维修计划及各种约束条件，依据各飞机的计划 飞行时间进行排班，得到排班结果。若无临时的航班调整通知，则此排班结果即为最终 结果，如l 每时收到调整通知，则对已排好的航班进行局部修正，以满足调度通告。排班 结果的执行又影响了飞机的状态信息，同时又进入了下一排班周期，如此周而复始。 由于约束条件过多，人工排班过程中容易遗漏一些约束条件，使排班结果不能达到 要求，在排班完成检查时才能发现，往往需要多次返工，不仅浪费了大量的时间，而且 排班的结果仅能保证排班工作的完成，无法保证排班结果的最优，即在浪费大量人力和 时间的同时只能找到一个可行解，而不是最优解，最终可能导致飞机的定检时间不能避 开血一、国庆等黄金周时间，不能在市场需求最旺盛的时候提供充足的运力，直接影响 了航空公司的经济利益。 使用计算机自动排班不仅能将排班人员从繁杂的手工劳动中解放出来，而且能从总 体上控制各飞机的飞行时间，使之在可控范围之内飞行，在定期完成检修的前提下提供 充足的运力。 4 3 计算机排班 本节中计算机排班是指根据排班周期内所有待排航班的飞行时间和各飞机的维修 计划，计算出各飞机在本排班周期的计划飞行时间，然后根据各种约束条件进行排班。 计算机排班过程可分为以下几步： 中国民用航空学院硕士学位论文 实际应用上的可行，先将待排航班按照一定的规则分组，在分组过程中处理“航班 一航班”匹配问题。 航班分组结束 图4 5 航班分组流程图 首先将周一( 周二至周日航班同样处理) 待排航班按照执行机型分类，然后选择 其中的一类，例如b 7 3 7 3 0 0 类航班( 其余各类同样处理) ，按照图4 5 所示步骤分 组： a 每个航班独立为一组，确定航班组数t ，并为每个航班组确定属性，以便于随 后分组的进行。航班组属性包括：始发时间、到达时间、始发航站、到达航 站、飞行时间、是否高原、是否包含预排飞机信息。对于只有一个航班的航 班组，航班组的属性为该航班的属性。确定b 7 3 7 3 0 0 机型的飞机总数m 、有 效飞机( 即本日可以执行航班的飞机) 数m 以及停场飞机数s 。显然有m = m + s 。 b 若t m ，转步骤c ，若t = m ，转步骤d ，若t m ，转步骤e 。 c 对于航班组集合中的任意两个航班组，如果他们能够满足以下条件，则可以 将这两个航班组合并为一个新航班组，加入航班组集合，并删除原来两个航 班组。 夺过站时问衔接。即一航班组( 不妨设为a ) 的到达时间与另一航班组( 不 妨设为b ) 始发时间满足过站时问约束。 中国民用航卒学院硕士学位论文 夺过站地衔接。a 航班组的到达航站与b 航班组的始发航站相同。 夺若a 、b 航班组都预先指定了执行飞机，则执行飞机必须相同。不允许 两个航班组都具有预排飞机信息但预排飞机不同。 合并之后，a 航班组的始发时间为新航班组始发时间，始发航站为新航 班组的始发航站：b 航班组的到达时间为新航班组到达时间，到达航站为新 航班组的到达航站。a 、b 两航班组的飞行时间和为新航班组的飞行时间。若 a 、b 航班组中至少一个为高原航班组，则新航班组也为高原航班组，否则为 非高原航班组。若a 、b 航班组至少一个预排了执行飞机，则新航班组也预 排了此执行飞机，否则没有预排信息。 确定新的航班组集合中的航班组数t 1 ，若t = t 1 ，转步骤f 否则令t = t 1 ， 转步骤b 。 d 若s = o ，即该日没有停场飞机，则航班分组结束。否则添加s 个空航班组，即 始发时间、到达时间、始发航站、到达航站、高原信息、预排飞机信息均为 空的航班组，以便于后继处理工作。 e 选择航班组集合中飞行时间最长的航班组，将其按照步骤c 的逆过程拆分为 两个航班组。确定新的航班组集合中的航班组数t 1 ，令仁t 1 ，转步骤b 。 f 至此航班不能全部安排，提醒排班人员，去掉部分航班后，转入步骤a 重新 分组。 经过以上步骤分组之后的航班组与飞机能够互相匹配，即航班组数目等于飞机 数m ，并且有效航班组数等于有效飞机m ，空航班组数等于停场飞机数s 。 4 确定约束空间，处理“飞机一航班组”匹配问题 分组后的航班组数目与同机型飞机数是相等的。即若某一机型有m 架飞机，则 每天的待排航班为m 组。根据前文对飞机排班问题复杂性的讨论可知，在无约束条 件下，为m 架飞机安排一周的航班有( ( m 1 ) ! ) 7 种方式。随着飞机数量的增加， 无约束排班空间也在急剧增大，在其中找出一个最佳甚至较佳的方式都是非常困难 的。 然而实际当中的排班并非无约束的，由于各种限定条件，各航班组不能随意指派 给任意一架飞机。满足各种约束条件的排班方式构成的解空间为约束空间【”】。相对 于无约束排班空问，约束空问中的排班方式不仅实际可行，而且规模要小很多，有 利于在其中找到一个最优或者较优的排班方式。 约束空间来源于无约束空间。形象地说，如同纯净水的过滤，无约束空间就好像 未经处理的原生水，不仅有满足实际要求的排班方式，还包含其它理论上可行而实 际上不可行的方式。而各种约束条件就如同一层一层的滤网，每经过一层，就去掉 一些不适用的排班方式，直到最后得到在实际当中真正有用的约束空间，如图4 6 所示。 中国民用航空学院硕上学位论文 喜墓彰慧箸 崔辜善z j 层 专辜菩三三；，黜束层 鲁要善三乏j 层 z 三三三三圣三至三三三三：i ：，一，一一起飞或到达航站约束层 等三善乙一觚船哒帅缄层 么二二j 二二二7 图4 6 约束空间及约束层示意图 为了方便表示，用以下所示的选择表来代表排班空间。其中，每行代表了待排 的飞机，每列代表了排班周期中的每个班期，每个单元格列出了行确定的飞机在列 确定的班期所能安排的航班组集合。航班组用t i i ( 1 i m ，1 j 7 ) 来表示周 的第i 个航班组。具体举例说明如下。表3 5 中列出了3 架飞机p 1 、p 2 、p 3 的无约 束排班空间的选择表。p 1 与周1 确定的单元格表示飞机p 1 在周l 可以安排执行的 航班组为t l l 、t 1 2 和t 1 3 。 表4 4 无约束空间选择表 周l周2周3周4周5周6周7 p 1 t 1 1t 2 1t ，lt 1 2t 2 2t 3 2 t 1 3 t 2 3l 3 t 1 4t 2 l 4t 1 5t 2 5 8 5t 1 6 t 2 6 t 拍t t 2 7 t 】7 p 2 t i it 2 i l it 1 2t 2 2t 3 2t 1 3t 2 3 t 3 3t 1 4t 2 4 t 3 4t 1 5t 2 s l 5t 1 6t 2 6 t 3 6t 17 t 2 7 t j 7 p 2 t l lt 2 】t 3 l t 1 2 1 k l 2t 1 3t 2 ，t t b l 4t 1 5t 2 5 l 5 t 1 6 t 2 6t 3 6t 1 7 t 2 7 t 3 7 约束空间的确定过程实际上就是去掉无约束空间中的不适合约束条件的排班方 式的过程。对于选择表来说，就是去掉相应单元格表示的航班组集合中的不适合元 素。下面列出了选择表对于各种约束层的添加方法。 ( 1 ) 高原( 或国际) 约束层。 由于限飞高原( 或国际) 的飞机不能执行飞往高原( 或国际) 的航班组，因此 该约束的添加就是在航班组选择表中去掉属性为限飞高原( 或国际) 的飞机行中属 性为高原( 或国际) 的航班组。如p 1 飞机限飞高原，表3 5 中t 3 l 、t 1 3 、t 1 5 、t 2 5 为高原航班组，则高原约束层的添加就是去掉这些航班组。 中国民用航空学院硕士学位论文 ( 2 ) 起始航站约束层。 由于飞机是连续执行航班的，因此它在排班周期第一天早上的所在航站( 如 果没有其他特殊情况( 如调机等) ，即是上个排班周期最后一天的过夜航站) 决 定了可以执行的航班组的始发航站。因此对于排班周期的第一天，即周一来说， 始发航站与飞机所在航站不同的航班组不能指派给该架飞机来执行，也就是在选 择表中去掉相应的航班组。 ( 3 ) 停场限制约束层。 对于在排班周期内有停场维修计划的飞机，在停场期间不执行航班，也就是 执行空航班。则对于选择表要做两方面的调整，首先去掉该架飞机和该停场同所 确定的单元格中的其他非空航班组；其次去掉在该日无停场维修计划飞机所确定 单元格中的空航班组。 ( 4 ) 预排约束。 调度通告中有时会指定某些航班必须由某驾飞机来执行，对于选择表的修改 就体现在去掉其他非指定飞机的航班组集合中包含指定航班的航班组。 ( 5 ) 限飞城市约束。 由于政治上或其他一些原因，某些飞机( 如机身喷有某些标志或彩绘的飞机) 不能飞往一些城市，则在排班之前就要排除掉这种可能，以免引起一些不必要的 争端。在选择表的调整上体现在去掉其它飞机的航班组集合中包含飞往限飞城市 的航班的航班组。 ( 6 ) 起飞或到达航站约束。 由于各个基地维修能力的不同，有些基地可能进行一些飞机大修项目，如d 检，有的则不行。如果需要维修的飞机执行航班飞往该基地维修，或者维修完成 执行航班离开该维修基地，则能大大地节约成本。在排班问题上则体现在指定该 架飞机在特定日期的起飞或到达航站。实现方法是去掉调整表中该架飞机该日航 班组集合中起飞或达到航站与指定航站不同的航班组。 ( 7 ) 起飞或到达时间约束。 有些维修工作不需要停场，在日常的航前、航后或者过站就可以完成，如a 检。这种维修工作的安排在排班上通常体现在起飞或达到时间的限制中。如某飞 机某日晚上安排了维修工作，由于工时的要求，该飞机必须于该同1 9 ：o o 点之前 返回维修基地。添加约束的方法是去掉调整表中该飞机该日起飞( 或到达) 时间 早于( 或晚于) 指定时间的航班组。 各种约束层添加完成后，可以得到约束选择表，约束选择表大大简化了原来的无约 束选择表。如表4 5 就是添加各中约束条件后得出的一个约束选择表。 中国民用航空学院硕七学位论文 表4 5 约束空间选择表 岗l周2周3周4周5周6周7 p l t l it 2 2 t 3 2t 2 3 t 3 3t ht 2 4t 3 5 l 6 1 k t 1 7 p 2 t 1 lt 3 lt 3 2t 1 3t 3 4t 15 t 2 5 t 3 s t 1 6 t i 7 t 2 7 t 3 7 p 2 t 2 l t 3 lt t 2t 2 2t 13 t ”b b 4t l5t 1 6 1 kt 3 6t 17t 3 7 约束空间选择表中包含了满足以上约束条件的各种排班方式，但这些排班方式 也不一定是实际可行的，因为没有考虑过夜航站约束，即第i ( 1 j 6 ) 天的到达 航站要与第i + l 天的始发航站相同。只有在由约束空间选择表动态生成排班序列时 加入过夜航班约束条件，才能得到最终的排班约束空间。 无约束排班空间随着飞机数量的增加会变得很大，即使对于小规模排班问题， 其无约束排班空间也大得难以想象。如果先处理这些约束条件，通过约束条件先构 造一个满足实际情况的约束排班空间，则会将选择排班空间大幅度缩小，使在其中 找到最优解成为可能。 通过实验已经证实，对于小规模排班问题，随着各种约束条件的添加，可以使 有上百力种排班方式的空间大幅塌缩，有时只有数百种甚至只有几十种排班方式， 在这么小空间中寻找最优解就比较可行，也为之后的排班优化做好了铺垫。 5 飞机排班 虽然约束空间已比无约束空间大大缩小，但是随着机群规模的扩大，寻找最优解仍 然比较困难。 根据蚂蚁几何信息学原理，我们设计了飞机排班的新算法( 参见第三章) ，达到了 比较理想的效果。 以国航天津分公司为例，编排2 0 0 6 年1 月9 日至1 月1 5 日一周的航班计划( 1 5 架飞机) ，表4 6 给出了三种算法的排班时间对比。 表4 6 三种算法排班时间对比表 算法平均排班时间 遍历数个小时 贪心算法1 5 分钟 融合几何信息学原理的蚂蚁算法 1 0 秒钟 从表中可以看出，运用新算法的排班时间远远小于遍历或者贪心算法的时间。下面 给出新算法的收敛曲线图，如图4 7 所示。 中国民用航空学院硕十学位论文 图4 7 国航天津分公司2