（应用数学专业论文）不正常航班调度的模型研究.pdf

羹霪霪茎l 琴笪三雾 茎 曼重薹妻矍墓矍垂雾主雾囊鏊謇虿霎 一茎霎一 萋 霎塞霪垂雪謇 奏囊萋蚕零薹囊霪薹妻薹鹱i 垂霎i 冀星囊篓囊囊曼薹雾墓薹主霎薹 霎耋搴主耄蓁蓁羹薹里冀薹藩薛鐾襄耋薹萋 薹蚕霎囊 薹囊霎蚕篓雾蚕雾羹冀喜 蓁藿冀冀薹雾 鋈辇荔矍霪 羹蓁薹羹雾霎薹蓁妻奏辇p 嚣 蒌篓萋薹墓萋蓦踵 蒌耋冀囊篓薹囊篓萋墓鍪薹妻蠢冀囊羹 姜霎萋i 茎萋 蠢薹善霎蓁萋囊羹囊羹妻囊霪萋荔囊幕隧i 一羔至錾藿 雾耋i 霎i 量 析 羹鍪薹萋 霎雾誊萋羹秦耄霎薹霎蓁鍪蠡蠹誓囊蓦鋈 霎蠢霎薹耋矍囊奏萎型j 耋墓雾蚕 耋 蘑霎鬈蠡霎孽 塞昏蓥霎 i 蓉蓁蓁薹藿量写蓁冀薹薹墓霎辇霉妻薹菲羹 篓遣鬟主要至耋孽要戛毫羹鎏饕善萋夏塞霎 i 妻 藿瑟 誊 嚣 霎茎 冀 垂耋 亳 i 重 霎j 囊霎 主 雩i 孝i耋 雪i 毒 a b s t r a c t r e s e a r c ho ni r r e g u l a rf l i g h to p e r a t i o nm o d e l m a j o r n a m e s u p e r v i s o r a p p l i e dm a t h e m a t i c s h u i m i ny a n g p r o f g u o c a nf e n g a b s t r a c t w i t h 血ei n c r e a s i n gd e m a n do fc i v i l a i r 仃a n s p o r t a t i o n c o m l i c t sb e 铆e e n t i a n s p o r t a t i o nd e m a i l da 1 1 d 仃a 伍cv o l u m eb e c o m em o r ea n dm o r ea b r u p t d u et 0 m e t e o r o l o g i c a lc o l l d i t i o n s t e c h n i c a lf a i l u r e si nt h ea i r c r a r a i rt r a 币c c o n t r o l b r e a k d o w n si na i r c r a r 铲o u n ds e i c i n ge q u i p m e n t 柚ds o m eu n c o n t r o l l e df i a c t o r s i r r e g u i a rn i g h t so c c u ro f t e n t i m e s w h i c hr e s u l ti nh u g ee c o n o m i cl o s s e st oa i r l i n e s t h e r e f o r e t 0i m p r o v et h em a n a g e m e n ta i l ds c h e d u l i n ga b i l i t i e so fi r r e g u l a rf l i g h t sh a s b e c o m eo n eo ft h em o s ti m p o r t a n t v o r ke m p k 峪e so fa i r l i n e s o p e r a t i o l l sc o n t r o l m a n a g e m e n t w h e ni r r e g u l a rn i g h t so c c u r n i g h ts c h e d u l ec a n tb ei m p l e m e n t e d d i s p a t c h e r s m u s tr e c o v e rt h e s en i 曲ts c h e d u l e st h r o u 曲r e a s s i g n m e n t s d e l a y i n ga i l dc a n c e l l a t i o n t om a l en i g h t sr e g u l a ra ss o o na sp o s s i b l e t h er e c o v e 巧o f f l i g h ts c h e d u l ei sv e 巧 d i 伍c u l t m i c hs p e n d sp l e n 够o f h 啪a 1 1r e s o u r c e sa i l dt i m e t h i sp a p e re m p h a s i z e so nt h er e s e a r c ho fm em o d e lo fi r r e g u l a rn i g h to p e r a t i o n w h i c hg i v e ss o m er e f e r e n c e st od i s p a t c h e r s w i t ht h er e l a t e dr e s e a r c ha th o m e 觚d a b m a d m i sp a p e rd i s c u s s e sa i l dd e v e l o p st h em o d e lo fi r r e g u l a rn i g h to p e r a t i o n a l c o s t i n c l u d i n gt h ec o s to fd e l a y i n gn i g h t s s w a p p i n ga i r c r a r s f e h y i n g c a l l c e l i n ga n d c o m b i n i n gn i g h t si i ld e t a j l s t h i sp 印e rs 蛐姗a r i z e sm ei 玎e g u l a rn i 曲to p e r a t i o n m o d e l w h i c hu s e st i m e s p a c en e t w o r kt od e m o n s t r a t et h em o d e l 访t ha no b j e c t i v e m n c t i o nm i n i m i z i n gt h eo p e r a t i o n a lc o s t a n dt h ea l g o d t h i l lt os o l v et h em o d e l w h j c h u s e sah e u r i s t i cp r o c e d u r e 砒l dr e f i e r st o h u n g a r i a l la l g o r i t l l i i lf o rs e l e c t i n gw t l i c h a i r c r a f ta r cr e m u t e d a t l a s t a l le x 锄p l ew a sg i v e nt od e m o n s 仃a t et l l ef e a s i b i l i t o f t h em o d e la n dt h ea l g o r i t h m i i i 2 0 0 9 1 1 4萤羹蠹 丐 薹囊l 誓产缝蘩夔羹蓟薹霾荤嗣襄蓁囊蒌萋一薰藩 蓁芒茎 一j 耄鍪茎囊垒d 鬟囊萤霄妻 蓁u 望囊一薹蒂耋荠羹 第一章绪论 卸货物 或因天气使机场通信导航等保障设施受损 短时不能保障飞行 或 因天气增加空中飞行时间等原因造成航段不正常的班次 2 流量控制 已按时关舱门 但因控制交通管制部门调整飞机的飞行间隔 而造成航班不正常 3 工程机务 因飞机机械故障 不包括 最低放行清单 允许的不工作项 目 因维护检查责任导致的飞机存在故障 机务人员使用的地面支持设备 气源 电源和空调车等 故障 或不能按时提供等原因造成的航班不正常 4 运输服务 因组织旅客登机 货物行李装卸和宣传服务等原因造成的航 段不正常 5 机场 因机场净空 跑道 滑行道 停机坪 目视助航设备 灯光 标志 候机楼行李传送设备 登机设备 飞行区和航站区供电保障 机场除雪和鸟 群等影响航班正常运行而造成的航段不正常 6 航行保障 因通信导航设备故障 以及因空中交通管制 通信 导航 气象和航行情报责任等原因造成的航段不正常 7 空勤人员 因空勤组及飞机客舱准备等原因造成的航段不正常 8 公司计划 因公司航班计划和飞行时刻安排不当 以及没有客货取消航 班等原因造成的航班不正常 9 飞机晚到 因航班推迟到达 使航班不够规定的最少过站时间而造成的 航班不正常 1 0 场区秩序 因飞行区有人 畜 车辆等进入跑道 滑行道等原因造成的 航班不正常 1 1 禁航 因重要飞行 科学试验 敌情警报 军事活动 国家或军事领导 部门指示等原因引起的航路 机场关闭造成的航班不正常 1 2 飞机清洁 因未按时做好飞机客舱清洁工作造成的航班不正常 1 3 食品供应 因未按规定时间或预订份数供应飞机上饮料 食品等造成的 航班不正常 1 4 油料保障 因油品质量 未按计划供油 加油设施故障 加油不按时等 原因造成的航班不正常 1 5 安全检查 因安全检查设备故障或没有及时进行安全检查等原因造成的 3 中山大学硕十学位论文 航班不正常 1 6 联检 因海关 边防 卫生检疫 动植物检疫等原因造成的航班不正常 1 7 地面事故 因地面车辆撞坏飞机或发动机尾流吹坏飞机等原因造成的航 班不正常 1 8 意外情况 在地面或在飞行过程中遇到不可抗拒的意外情况造成的航班 不正常 1 9 旅客 因旅客证件不符 携带危禁物品 伤残旅客登机 没有按时办理 有关手续 未按时登机和登机后发生意外情况 等造成的航班不正常 2 0 其它 上述各项未能包括的原因造成的航班不正常 以2 0 0 5 年度为例 如表1 2 反映了影响航班正常的主要因素及比率 3 2 0 0 5 年影响航班正常的主要因素及比率表1 2 因素不正常航班数 班次 不正常率 公司计划 9 7 8 6 83 9 9 天气原因 4 4 4 6 01 8 1 3 流量控制3 7 6 4 7 1 5 3 5 需要说明原因 2 4 9 4 01 0 1 7 工程机务 1 4 7 7 26 0 2 旅客原因7 6 0 83 1 禁航原因 6 7 0 72 7 4 机场设施4 8 311 9 7 由上表可以看出 以上八种主要因素影响的航班数占不正常航班总数的 9 7 3 8 如果按影响因素进行进一步分类 我们会发现 航空公司原因影响不正 常航班总数约4 7 左右 空管原因影响不正常航班占总数的3 3 4 8 其中天气 占1 8 1 3 流量控制占1 5 3 5 机场原因影响不正常航班占总数的2 0 4 旅 客原因影响不正常航班占总数的3 1 总数约2 7 6 因此 由数据分析可知 禁航等可能涉及军航影响不正常航班占 航空公司原因造成的不正常航班占不正 常航班总数约半数 加强航班运行控制管理对降低航班不正常率 减少航空公司 成本起决定性作用 4 第一章绪论 1 1 3 航班计划恢复策略 由于一架飞机在一天中要执行多个航班 各航班之间存在前后衔接关系 因 此 一个航班的延误会波及到下游许多其他航班 局部的航班延误很容易演化为 大面积的航班不正常 当不正常情况出现时 运行调度人员会根据航班的计划时 间 飞机的航线 飞机的维护和保养计划 以及机组的编排计划等一系列信息 考虑飞机资源的重新分配 提出飞机计划的调整方案 尽量使航空公司的航班能 在较短的时间内恢复正常 调度人员在人工决策时 一般的指导原则是 采用最 简单的调整方案 使得受影响的航班最少 我国航空公司机队规模小 飞机资源 稀缺 国内航空公司在不正常航班的恢复调整中一般都采取能延误则延误 迫不 得已再取消的策略 而且通常不会对计划的恢复设时间限制 只要求调整方案保 证在飞行日结束恢复原计划的机型配置 尽可能不影响次日计划的执行 从解决 不正常航班问题的过程来看 计划的调整主要是进行飞机的调配和机组的调配 飞机的调配是为了重新部署飞机的资源 使得在未来的某一个时刻 各架飞机能 够在所要求的时间处于正确的机场位置 满足更改后航班的需要 本文主要研究 飞机的调配 具体来说 解决不正常航班问题的主要策略有以下五种 1 航班顺延 航班顺延是在一个航班发生延误 但不取消任何航班的情况下 依次顺延其 后的所有航班 保证每个航班的延误时间都控制在4 个小时之内的方法 该方法可以降低航空公司的成本费用 但是有很大的局限性 一是需要对整 体航班计划重新做安排和调整 二是要求其后的航班必须不能出任何问题 特别 是飞机状况必须良好 因为一旦飞机再次出现故障 航班计划将被安全打乱 运 力无法保障 三是航班顺延会造成航班大面积延误 正点率大大降低 违背了解 决航班延误问题的初衷和目的 2 飞机置换 飞机置换即当某一航班发生延误时 由本机场的飞机来替代延误飞机执行航 班任务 简单地说即为同一机场的飞机相互置换执行航班任务 这其中涉及是否 5 中山大学硕士学位论文 方法 a r g u e l l o 等在文献 9 中给出了飞机调配问题的资源分配路径流模型 将飞 机指派给飞行路线 p a t h r o u t e 从每架飞机所在的机场开始 找出所有可行的路 线 并将每架飞机指定给可能路线中的一个 使总费用最小 这个模型思路清晰 刻画了飞机调配问题的实质 但求解困难 a r g u e l l o 在文献 1 0 中针对文献 9 的 模型 提出利用路径生成技术 用一个可行解寻找另一个可行解 类似于复杂网 络流问题中采用的列生成方法 但计算时间很长 不能满足实时调配要求 文献 1 1 提出了关于航班恢复的一个时间段网络优化模型 把飞机路线问题转化成基 于离散时间的网络流模型 s t e p h a n eb r a t u 等 1 2 j 介绍了一种航班恢复的模型和算 法 在不正常航班发生时 能够在同时考虑飞机 机组和乘客的情况下 决定推 迟还是取消哪个航班 目标是使互连的总运营成本和评估出的乘客总延误和取消 成本最小 目标函数是希望在各个成本之间寻找一个平衡点 以上模型实质上都 是构造出飞机的飞行路线和取消的航班 从中挑出费用最小的方案 困难在于如 何生成可行的飞机路线和取消航班路线 又如何计算出每一可行路线的费用成 本 到目前为止 还没有文献通过直接求解这些模型来找到精确最优解 1 3 研究目标及主要内容 1 3 1 研究目标 我国不正常航班调度的研究尚处于起步阶段 虽然国外相关研究已有很大的 进展 但国外航空公司飞机拥有量多 航班密度高 且航线网络以枢纽结构 h u b a n d s p o k e 为主 而中国航空公司飞机拥有量少 航班密度低 且航线网络 以点对点 城市对结构 p o i n tt op o i n t c i t yt oc i t y 为主 从而在面对不正常航班问 题进行航班调度时 所采取的策略有显著的不同 本文主要在借鉴国外现有经验 和研究成果的基础上 结合我国具体国情 建立适合中国民航运输市场和航空交 通管制特点的不正常航班服务调度模型 研究与之对应的快速和实用的算法 在 此基础上 进一步实现相关应用软件的开发 最后成为可供航空公司调度人员进 行不正常航班调度的决策参考 减少工作人员的工作量 并进一步减少航空公司 8 第二章航班不正常情况成本模型 第二章航班不正常情况成本模型 定量的分析航班延误造成的经济损失有助于空中交通管制部门合理的调配 航班 以及航空公司有效的控制成本和提高效益 国外在航班延误成本分类计算 方面的研究已经取得了一定的成果 1 3 1 如分为航空公司 旅客及环境的延误成 本来分别计算 但是这种分类也不是很完善 没有考虑延误给机场和空管带来的 成本 只是用航班延误作为评价国家空域性能的指标之一来估计国家空域性能对 航空公司营运成本的总体影响 没有单独研究航班延误对航空公司营运成本带来 的总体影响 国内只在进行有关空中交通流量管理的研究时 提到了航班延误成 本 l 2 引 并且主要把总体航班延误成本的最小化作为流量管理模型中的目标函 数 对延误成本的函数形式进行了一定的假设 进而有利于空中流量管理模型的 建立和仿真 但是没有对航班延误成本计算进行更深入的研究 既没有计算航班 延误成本的具体指标 更没有估计方案 本章主要为建立不正常航班调度模型建立理论基础 从而重点在于通过借鉴 和学习国内外的先进理论考虑航班延误给航空公司带来的成本 以便为航空公司 进行相关的决策提供有力的指导 考虑到计算航空公司遇到不正常航班情况时的成本 根据航空公司所采取策 略的不同 则其相应的成本模型也不同 本文成本模型建立以单个航班延误成本 为基础 2 1 航班顺延成本计算方法 在文献 2 1 中 作者只考虑了航班延误对航空公司造成的隐性损失 提出了 旅客失望溢出成本的概念 在文献 2 2 中 作者采用直接方法计算了航空公司延 误成本 其中讨论了航班延误时造成的飞机的延误成本 笔者认为航班延误不仅 造成了飞机成本而且也带来了隐性损失 应结合两篇在计算航班顺延成本时的方 第二章航班不正常情况成本模璎 飞机的单位时间营运成本 d r 为航班歹的延误时间 j f 为航班号 3 特定时期内的航空公司延误成本计算 t a d d c a d d c j l 式中 t a d d c 为航空公司在特定时期内的延误成本 a d d c j 为执行航班 的飞机延误成本 n 为航空公司在特定时期内的航班延误班次 为航班号 j 1 2 拧 要进行参数估计 首先根据前面提出的模型计算单位时间飞机营运成本 其 中各种机型的飞机年营运成本和年运输时间数据都可以搜集到 用各种机型的飞 机的年营运成本分别除以各自的运输飞行时间 即可得到各种机型的单位时间飞 机营运成本 假设航班 的延误时间为d zr a i n 使用的机型为b 7 3 7 8 0 0 则可根据中国 民航统计年鉴 2 3 查出b 7 3 7 8 0 0 年营运成本为72 0 76 7 33 6 2 5 2 元 运输飞行时间 为2 0 07 3 1 0 1h 该机型的单位时间飞机营运成本约为5 9 8 4 5 元 m i n 进而计算 出执行该航班的飞机延误成本为5 9 8 4 5 元 针对任何一个延误的航班 都可以确定其使用的机型 并根据该机型当年的 营运成本和运输飞行时间数据计算出该航班相应机型的单位时间飞机营运成本 再根据该航班的延误时间 计算出执行此航班的飞机延误成本 如果要计算在特 定时期内的航空公司延误成本 只要将此时期内单个航班的飞机延误成本加总求 和即可 因此 前面提出的飞机延误成本模型在应用方面是可行的 由于航班长时间延误而导致航空公司要安排旅客食宿 从而这方面的成本也 应该计算在其中 由于航班延误等级的不同 则旅客所得到的补偿也是不同的 延误等级分为 一 1 5 分钟到1 小时 二 1 小时到2 小时 三 2 小时到3 小 时 四 3 小时到4 小时 五 4 小时以上 假设每个延误等级提供的补偿不同 设每个等级每人补偿成本分别为 c c c 3 c 4 c 5 则食宿成本计算则 为根据延误等级不同 确定每人补偿成本 然后再乘以乘客数即得 即 f c f 无梭织机开口凸轮加工方法探讨 凌志浩 河南工业技师学院河南郑州4 5 0 0 0 7 摘要 将数控加工技术和成组技术有机结合 应用于织机的开口凸轮加工 在有效降低加工成本 提高生产效 率方面显示出极大的潜力 在多品种 小批量产品的加工中 有显著的优势 关键词 成组技术数控加工凸轮运动集中加工 r 嗡心h 伽n 佻e s s i 哩c 蛐p a r t s 稍mg m 叩i 呜t t 曲n i q 呲 删gz 越一 1 k n 饥胍甜加m 姚矿z 锄 l o 姗y 踟阴g 旆础 4 5 0 0 c r 7 2z k 耐o 佴锄掰肘4 小i 删y 肘 心细t 埘昭c o 厶d z 妇咖 m m l4 5 0 0 5 3 a k 栅c t t h eo r g 帅i ci n t e 簪a t i o n0 fg m u p i n gt e c h i i i q u e 锄dn ci n a c h i n i n g t e c h n i q u ei nr i f i g e n tc 啪p r e 船i n gc 伽j dl a wt h ec o s t i m p r o v ee m c i e n c y a n d 幽m a l e 舯o b r i o u ss u p e r i o r i t yi np r o c 朗8 i n go f 删o u b k i n d 8 锄d 蚰1 a ub 砒c h 鹪 k e yw o r i l s g t c n cm 卵h i n i l l g c 帅 m o v e 啪n t c e n t r a j i z e dp d o o 鹤s i l l g 一前言 纺织机械上采用许多凸轮来控制机构的复杂运动 在织机上 也有广泛的应用 由于织机上的运动大多具有循环性 凸轮曲线 可以根据需要设计符合规律的运动 凸轮形状比较复杂 加工存在 一定的难度 有些凸轮随织物品种的变化 运动曲线也将发生变 化 织机是批量生产的产品 多品种的凸轮的批量生产 其工装 刀具等投入是很大 本文通过应用成组技术的方法 将织机上所 用凸轮分组 归类增大批量 2j 重点探讨了利用成组技术将结构 相同但曲线不同的凸轮运用一个夹具在加工中心上加工的工艺和 曲线编程方法 二加工工艺和曲线编程方法 一 加工工艺 中山大学硕士学位论文 动态网描述了油轮的调度问题 2 4 由于时空网络的逻辑体系很容易被理解 为 研究者提供了一个明确地看问题结构的方式 因此被广泛地应用在调度问题和路 径问题的建模 时空网中的每个连接都代表时间空间的变动 从当前时点丁的地点转换到时 点丁 x 的另一地点 其中时间变动值x 大于零 时空网络可以用几种方式表示 首先是通用的二维时空网络 以航空公司航班调度问题为例 空间 机场 是一 维 而时间是另一维 第二种是复杂的二维时空网络 在这个网络中时间被进一 步细分 如划分为飞机到达的时间 飞行准备好离开的时间 飞机离开机场的具 体时间等等 这两种方式的主要差别在于 复杂网络可以同时解决机队指派问题 和飞机路径问题 而通用网络首先解决机队指派问题 然后解决飞机路径问题 最后通过使用网络流分解方法 n e t w o r kf l o wd e c o m p o s i t i o n 获得所需要的调 度方案 第三种表达方式是三维时空网 这个网络由一系列二维图 自下而上堆 积起来表示时间 三维时空网中的一条弧可以从地图上的点指向较晚时间地图上 的点 然而 由于此类时空网络的图形具有高度复杂性 很少有研究人员使用这 种方式 下面结合航班调度问题介绍二维时空网络 2 5 j 在调度问题中 每一个网络 节点指代在一个特定时间的特定机场 每一个弧的连接与网络中不同时间事件相 关联 航班调度问题时空网络中的主要节点和弧有 l 航班弧 飞行弧 f l i g h ta r e 航班弧连接飞机的出发和到达节点 只是指代一个可能的飞行 通常弧上的 流量为l 航班弧的成本由机型和路径长度决定 2 过站弧 地面活动弧 g r o u n da r c 这个弧连接在同一机场两个不同时间的节点 流量代表在过站时间内留在地 面的飞机 过站弧的成本为停场费用 设施使用费用等 通常过站弧不产生收益 3 过夜弧 沉淀弧 o v e r n i g h ta r c 过夜弧是另一类过站弧 弧流量为在具体机场过夜的飞机数量 弧费用和过 站弧的类似 4 调机弧 f e r r y p o s i t i o na r c 调机弧表示在不正常情况下 调动飞机到某一机场去服务而不携带任何旅 第三章不正常航班调度模型 客 假设调度控制员需要的话 调机弧从一个供给节点 s u p p l yn o d e 发出一束弧 连接被调用飞机所在的节点到所有需要的节点 并且将这一束弧的总流量设置为 小于等于l 调机弧的费用包括操作费用和一些管理费用 不产生收益 5 延误弧 d e l a ya r c 延误弧表示可能采取的延误策略 通过在原计划的飞行弧上添加带离散时问 间隔的平行弧 例如 假设航班在9 o o p m 离开p 机场且于1 1 o o p m 到达d 机场 若以1 5 分钟为延误方案间隔 则可以在p 机场9 1 5 p m 9 3 0p m 9 4 5p m 等时间点上添加延误弧 相应地连接到d 机场1 1 1 5p m 1 1 3 0p m 1 1 4 5p m 时点上 延误弧的费用包括延误费用和由于延误引起的操作费用 6 加速弧 s p e e du pa r c 加速弧是表示加大飞行速度减少飞行时间 可以提前的时间量由出发和到达 的机场距离决定 如果飞机在飞行 则由当前地点到目的地的距离决定 费用为 耗油费用 没有其他的惩罚费用 在空中交通管制较为发达的国家 可以允许航 空公司决定飞行时间 但我国目前的空中交通管制体制不允许航空公司这么做 因此这类弧用的非常少 除非是特殊情况 7 其他类型的功能弧 根据各种研究领域的特点 时空网中可以出现一些不代表具体活动的弧 例 如 y ug a n g t 2 6 2 8 1 等在研究不正常航班调度问题时就引入了一类航班计划保护弧 p r o t e c t a r c 用以表示经停航班 联程航班任务的计划完整性 沉淀弧 s i n k a r c 指向最终需求节点的弧 表示飞机所在航班任务结束 8 飞机到达节点 a i r c r a f ta r r i v a ln o d e 飞机在特定的时间到达特定的机场 则该节点记录了到达时间和机场 在网 络中 一个航班的连接将汇集在到达节点 9 飞机离港节点 a i r c r a f td e p a r t u r en o d e 飞机在特定的时间离开特定的机场 则该节点记录了离开时间和机场 在网 络中 一个航班的连接将从该节点连接到其他的机场 1 0 供给节点 s o u r c e s u p p l yn o d e 供给节点表示拥有一定可使用飞机数量的特定时点 供给节点可以位于一天 的起始时刻 或者是经过修复后飞机的所在时点以及空闲飞机所在的时点 2 1 中山大学硕士学位论文 l1 需求节点 s i n k k d e m a n dn o d e 需求节点可认为是事件节点 如果出现在一天中间的时刻 则表示在某个机 场的这个时刻出现飞机短缺 如果它出现在一天的末尾 则是真正的需求节点 表示所有的飞行结束后飞机的聚集点 在需求节点上 机场拥有的飞机数量可以 与早晨出发时同样多 也可以不相同 图2 1 时空网示意图1 2 5 1 如图 横轴代表机场 纵轴代表时间轴 图中的圆圈代表节点 每个节点指 代在一个特定时间的特定机场 其中包括初始供应节点 最终需求结点 及中间 节点 图中的箭头代表不同的弧 指代时间空间的变动 也包含了航班调度所有 可能采取的措施 不正常航班调度问题即为找出使得调度成本最小的那些弧 并 这些孤代表所要采取的调度策略 且满足一些约束条件如流平衡约束 机队平衡 约束等条件 第三章不正常航班调度模型 3 2 不正常航班调度的数学模型 目前国外部分航空公司在不正常情况下的计划调整实践中 主要采用时空网 络的模型 利用拉格朗日松弛启发式算法和商用数学优化软件i l o g 求解 但从 实际应用看 上述的方法仍存在以下的不足 1 人数少的航班往往被分配较长 时间的延误或是取消 2 9 然而 出于市场的考虑 某些特定的航班即便是人数 少也不能延误过长时间或是取消 l r s 算法和i l o g 在模型中增加这些调整的约 束将使得建模和求解变得复杂 2 l r s 算法和i l o g 通常只给出一个解 如要 获得多个解 只能通过模型中增加延误时段 修改成本参数和在第一阶段i l o g 生成解的基础上另外设计启发式算法取消不同的航班来获得f 3 0 j 3 时空网模型 通过给飞行弧添加平行弧表示不同时间的延误选择 当飞行弧较多且添加的延误 选择较多时 将使模型的变量和约束条件成倍增长 导致运算时间过长 因而在 生成调整方案时通常以1 5 或是半小时为间隔添加延误选择弧 这使得生成的方 案与实际情况有较多不符 影响了方案的可执行性 4 l r s 算法和i l o g 难以 对环境变化加以考虑 模型的可控性不强 由于上述的不足 目前该类问题的求 解开始关注设计更高效的启发式算法 3 1 和采用仿真方法 3 引 为了便于建模 假设每个航班具有唯一的航班号 即不考虑联程班问题 在 目标函数的选取上 一般可以选择航班收益最大化 运行成本最小化 调整后的 航班计划与原计划改动最小化 取消航班最小化等为目标 也可以是上述目标的 组合 目前现有的文献绝大部分是单目标模型 多目标模型比较少见 本章以调 整成本最小化为目标函数 建模采用时空网技术 2 6 2 5 j 调度模型及相关符号定义 描述如下 d 机队需求节点集合 即计划中飞机的过夜机场 e 机型集合 f 所有点到点航班弧的集合 g 地面弧集合 第四章不正常航班调度算法 第四章不正常航班调度算法 4 1 不正常航班调度的机理分析 对于一个给定机号的飞机 该机号的路径为在时间上连续 符合规定过站时 间标准的多个航班所构成的航班串 由于航班延误具有传递性 当路径上某个航 班发生延误 如果不进行调整 路径上后继航班的延误时间将会不少于当前的延 误时间 记航班 厂的延误时间为悦砟 为便于描述算法 首先给出两个定义协l 定义4 1 机号矿就绪时间r d 易 指矿完成地面保障服务 旅客登机完毕 后关舱门准备离港的时间 定义4 2 机号矿的路径延误时间尺说乙 设旷路径上有航班 环 7 厂7 是厂的后继 若在计划调整过程中 厂与其它路径的航班 环 发生置换 则旷执行完置换航班后再次执行厂 的预计就绪时间与原计划就绪时间的差值称 为机号矽的路径延误时间 尺d 三易可以取负值 表示空闲等待 定义路径延误的意义在于 如果路径的后继航班不发生调整 则路径延误时 间即为后继航班的实际延误时间 在实际调度中 出于机组 旅客中转等因素的 考虑 路径的调整需要尽可能保持多经停 联程航班的衔接 借助路径延误的定 义可以帮助评估方案调整对后继航班的影响 图4 1 给出了两种不同飞机的航班转换示意图 严 1 嘲 l 粥d 1 5 瑭 图4 1 航班转换示意图 中山大学硕士学位论文 图中有机号为b 2 5 0 l 的波音7 3 7 8 0 0 和机号为b 2 9 5 8 的波音7 5 7 2 0 0 不同机 型的两架飞机 假设波音7 3 7 8 0 0 过站时间为3 0 分钟 7 5 7 2 0 0 过站时间为6 0 分钟 原计划b 2 5 0 1 的就绪时间为1 0 0 0 因故必须延误到1 2 0 0 b 2 9 5 8 就绪时 间为1 0 3 0 无延误 若调度人员决定由b 2 9 5 8 执行 门一厂2 一厂7 一厂8 b 2 5 0 1 执行 厂5 一 6 一厂3 一厂4 根据图中标示时间不难算出 d 丁 d r 3 0 t 2 d r d r 9 0 j sj 6 脱乃 说丁 2 l o 3 d 正丁 三丁 3 0 7 i 置换之后两个机号的路径延误分别为 r d 瓦2 5 0 1 1 8 3 0 3 0 1 5 3 0 2 l o m i n s 肋 瓦2 9 5 8 1 5 3 0 6 0 1 8 0 0 一9 0 m i n s 置换之后 路径上航班的延误时间是不相同的 但是 调整后的机号路径延 误时间却有一个明显的特征 即路径延误之和等于初始延误的时间之和 为验证 其正确性 需要证明如下命题 2 5 1 命题4 1 设机号矾原计划就绪时间为f 因故需延误至瓦 在延误期内有门 个机号西 f 昏 2 玎 参与置换 且气 o 死 则 r d 瓦一 证明 设须参与置换的航班z 的飞行时间为形 西的过站时间为 i 则v f o 有 r d l t 硗 以i d g t i 一乜i n i 9 1 3 以i d 一班i 对于江0 有 尺d 正r 矾 瓦 疗 o o o 疗o 瓦 形 一f o o 对f 求和 有 r 脱 瓦一气 一 j 中山大学硕士学位论文 4 2 1 匈牙利算法简介 在现实生活中 有各种性质的指派问题 a s s i g i l n l e n tp r o b l e m 例如 有若 干项工作需要分配给若干人 或部门 来完成 有若干项合同需要选择若干个投 标者来承包 有若干班级需要安排在各教室里上课等等 诸如此类问题 它们的 基本要求是在满足特定的指派要求条件下 使指派方案的总体效果最佳 匈牙利 算法是解决指派问题的高效算法 指派问题的标准形式 3 3 以人和事为例 有刀个人和疗件事 已知第f 个人做第 件事的费用为 f 1 2 玎 要 求确定人和事之间的一一对应的指派方案 使完成这胛件事的总费用最少 一般 称矩阵c b j l l 为指派问题的系数矩阵 c o e 伍c i e n tm a t r i x 在实际问题中 根据c 盯的具体意义 矩阵c 可以有不同的含义 如费用 成本 时间等 系数 矩阵c 中 第f 行中各元素表示第f 个人做各事的费用 第 列各元素表示第 事 由各人做的费用 指派问题的数学模型 引入万2 个0 1 变量 勤 仨戮鬟瓣事 幻乩2 一 可一1 0若不指派第f 个人做第 件事 j b 白一v 问题的数学模型可写成 栉月 m i n z 勺勤 等l 胃l n 嘞 1 1 2 聆 f l 砒 嘞 1 f l 2 栉 l b 0 或1 f 1 2 栉 4 1 4 2 4 3 4 4 模型中 约束条件 4 2 表示每件事必有且只有 个人去做 约束条件 4 3 表 3 0 第四章不正常航班调度算法 示每个人必做且只做一件事 对于问题的每一个可行解 可用解矩阵x b 上 来表示 当然 作为可行 解 矩阵每列各元素中只有一个1 以满足约束条件 4 2 每行各元素中都有 且只有一个l 以满足约束条件 4 3 则理论上指派问题有刀 个可行解 但往 往指派问题的要求是找到满足最优条件的那个解 从上述数学模型可知 标准的指派问题是一类特殊的整数规划问题 又是特 殊的o 1 规划问题和特殊的运输问题 因此 它可以用多种相应的解法来求解 但是 这些解法都没有充分利用指派问题的特殊性质 而不能够有效地减少其计 算量 但匈牙利算法充分利用了指派问题为o 1 规划问题的特性 有效地减少了 指派问题的计算量 匈牙利算法的原理是利用了指派问题最优解的以下性质 若从指派问题的系 数矩阵c h 上 的某行 或某列 各元素分别减去一个常数七 得到一个新的 t 矩阵c 勺i 则以c 和c 为系数矩阵的两个指派问题有相同的最优解 因 h x 疗 为系数矩阵的变化并不影响数学模型的约束方程组 而只是使目标函数值减少了 常数后 所以 最优解并不改变 匈牙利算法的一般步骤可以表述如下 步骤l 变换系数矩阵 先对各行元素分别减去本行中的最小元素 再对各列元 素分别减去本列中最小元素 这样系数矩阵中每行及每列至少有一个零元素 同 时不出现负元素 转步骤2 步骤2 在变换后的系数矩阵中确定独立零元素 若独立零元素有刀个 则已得 出最优解 若独立零元素少于 个 则作能覆盖所有零元素的最少直线数目的直 线集合 然后转步骤3 为了确定独立零元素 可以在只有一个零元素的行 或列 中加圈 标记为o 因为这表示此人只能做该事 或此事只能由该人来做 每圈一个 0 同时把位 于同列 或同行 的其他零元素划去 标记为 这表示此事已不能再由其他人来 做 或此人已不能做其他事 如此反复进行 直至系数矩阵中所有零元素都被圈 去或划去为止 在此过程中 如遇到在所有的行和列中 零元素不止一个时 存 在零元素的闭回路 可任选其中一个零元素加圈 同时划去同行和同列中其他 3 l 中山大学硕士学位论文 成本矩阵为c r 另一延误时间r r o 所对应可供置换的机号数量为 聆7 0 刀 成本矩阵为c 记采用匈牙利法对两个成本矩阵进行指派得到的成 本为c o s r c o s f r 则有 推论4 2r f 0j c o s 7 c o s 于7 结合推论4 1 和推论4 2 可以得到两个重要的结论 第一 在延误策略下 采用匈牙利算法处理指派约束 如果一个机号路径有多种延误方案 则不论对路 径后继的航班如何调整 较长延误时间方案的最终成本不会少于较小延误时间方 案的成本 这也表明延误路径上航班的首轮调整对最终总成本具有关键的影响 第二 由成本矩阵的性质和匈牙利算法解的最优性 只要在路径上按匈牙利算法 提供的指派进行置换 则置换后的总成本是非增的 因此 基于路径调整的算法 可以通过在路径上寻找可行的置换来达到延误时间分配和降低成本的目的 4 2 3 多航班情形 受恶劣天气 流量控制等原因 在同一机场往往不止一个航班受到影响而 致使多个航班出现延误 此时 进行航班 航班环 置换会面临一个机号有多种 置换选择的情况 在文献 2 5 中作者把飞机指派问题转化为求集合无关子簇问题 其建立的数学模型如下 假设机场尸在某时段内有 个不同机号的航班任务出 现延误 总共有m 个不同机号的飞机可供置换 m 该问题的数学描述如 下 妒 可供置换的飞机集合 妒 眈l 1 m 脚 延误的航班集合 叩 扫e i f 1 s 黝只 对每一个嬲利用匈牙利算法求出参与置换的机号组合 s 黝ec 腰 孵妒 踞 s 黝e 所产生的效用值 o 由含有晖的s 黝e 所组成的集合 3 4 第四章不正常航班调度算法 k 集合隶属变量 若踢 s w a f 则取值为l 否则取值为o 无关子簇问题 i p p 1 3 1 m a x s c w 4 5 一 妣 w j i 1j l m 4 6 o l f l n j 1 m 4 7 发生延误的机号也可以属于其它机号的置换集合 即给已经延误了的航班再 次分配新的延误 这类情况在实际的调度并非少见 例如为了保证要客 v i p 航 班的出行 调度人员必须让其它航班延误 求解问题 4 5 其实是 个将机号与 航班任务间多对多的映射规范为多对一映射的过程 因此可以通过删除多余的对 应关系和更改映射的集合来进行 算法以在s 黝e 中去除踢所造成的成本增加值作为效用值 求解按以 下步骤进行 步骤1 将同时属于多个置换集合的 踢提取出来存入集合以f 步骤2 g v tp a f 中的每一个踞计算 w 找出最大数值对应的机号 记为 甄 将所有含有s f o 的置换集合存入 中 步骤3 对每一个s w a f 分别计算从置换方案中去掉s y o 所导致的成本增加 值a c 记在s v c 么f 置换指派中分配给s f o 的延误时间为出 则a v c f 缸 就 是s 黝只关于瓯的单位时间成本增加值 找出m a x y 对应的置换方案 记为 s w a f o 步骤4 依据s w a f o 更改机号路径 延误信息和时刻表 若仍有延误航班未进行 置换 返回步骤l 若p a f 算法结束 求解步骤2 3 的实质是删除多余映射分支的步骤 在s w a f o 中保留s f o 可 以使该次置换产生最大的成本削减 这些步骤使得多对多的映射规范为多对一的 映射 避免产生一个机号执行多个航班的情形 第四章不正常航班调度算法 性 我们用文献 2 1 中的数据进行模拟运算并对求解的结果进行了分析 算例中 某航空公司有1 2 个航班执行任务 以j 机场为研究背景 其中有4 个航班石 止 以 六为始发航班 8 个到达航班六 兀 石 石 由于执行航班六的 飞机发生故障 短时间内无法修复 如果利用备用空闲飞机r 则需要6 小时准备 就绪 与航班六相同机型可替换飞机的航班分别为 六 石 石 石 及备用空 闲飞机r 希望得到一种航班调度方案使调度成本就小 航空公司的基本数据如 下表4 1 所示 表4 1 某航空公司航班基本数据 航班号始发机 始发时 到达时出发时 结束时停驻机旅客人平均票 场间间间间场数价 5 0 0 5 0 0 5 0 01 6 5 05 0 08 7 0 zs ls l 7 0 0 7 0 07 0 01 8 0 05 5 07 9 0 五墨墨 7 3 07 3 07 3 01 9 3 05 8 05 7 0 六 s i 9 0 09 0 09 0 02 1 3 07 0 08 0 0 墨墨 8 0 0 8 4 0 2 2 0 08 2 01 2 5 0 s s 2j 2 1 0 1 01 1 0 02 1 0 02 1 02 1 3 0 l 占2j 2 1 0 4 01 1 2 02 0 5 02 0 09 9 0 1s 3岛 1 1 5 01 2 3 02 2 0 01 2 01 5 6 0 s 4j 4 1 2 4 01 3 2 02 1 5 01 0 01 8 9 0 j砖如 1 3 5 01 4 3 02 2 l o2 3 01 7 6 0 石 s 6氏 1 4 3 01 5 1 02 3 0 02 9 02 9 l o z j s 一 1 6 0 0 1 6 4 02 2 3 0 1 2 01 8 0 0 五2 s s i 如果利用备用空闲飞机尺则延误6 个小时 由于后继旅客人数较多 若取消 航班则成本较大 则可以利用可以置换的飞机采取飞机置换策略 可替换飞机的 3 9 中山大学硕士学位论文 航班分别为 石 z 及备用空闲飞机r 由文献 2 1 中的延误时间的定义 设勺为f 时刻航班由歹时刻航班的飞机执行 延误时间 即为 时刻航班的 到达时问 一f 时刻航班的 到达时间 由表中 的每个航班的到达时间信息可以得到每种飞机置换的延误时间 由于文献 2 1 中 延误时间计算错误 笔者在本文中做了相应的更正 则延误时间矩阵丁为 a t 石 z l 11 凡 o1 6 02 8 0 01 0 02 2 0 i n f0 1 2 0 i n fi n f 0 i n f i n fi n f z l r 3 9 0 3 6 0 3 3 0 3 0 0 2 3 0 2 0 0 1 1 08 0 00 矩阵第一行分别表示由执行航班a 的飞机来执行航班六延误时间为 分钟 由执行航班石的飞机来执行航班以延误时间为1 6 0 分钟 依此类推 i i l f 表示一 极大数 表示航班已经起飞 不能置换 如果对矩阵丁采用匈牙利算法处理 最 小延误时间为3 0 0 分钟 得到以下四种置换方案 以 t q 彳l l t t z l l l f u 1o o o 0 0 l0 0 0 o0lo0 oo oo l 00 o l0 4 5 1 11 9 n 10 o 0 o 0 o10 0 o1o o 0 0