（产业经济学专业论文）基于规则的启发式搜索算法在飞机除冰调度中的应用.pdf

摘要 飞机除冰调度问题是影响民航飞机运行安全及冬季航班正点率的重要因素 之一。其解决的好坏直接影响到机场及航空公司的安全和效益，在目前信息化 的大背景下，如何使用合适的算法来实现飞机除冰调度的计算机化，进行调度 问题的优化研究，具有重要的实际应用价值。 本文将基于规则的启发式搜索算法引入飞机除冰调度问题的研究中，通过 对实际除冰调度业务的流程进行研究，分析需要考虑的约束条件，建立启发式 规则，然后根据规则设计了启发式搜索算法。另外，设计了对于飞机除冰调度 问题的最基本的f c f s 算法。最后对两种算法进行了实现和实例测试及结果的对 比分析。实例计算的结果表明基于规则的启发式算法具有一定的优势，是可行 的。 关键词：飞机除冰，调度，规则，启发式搜索 a b s t r a c t a i r c r a f td e i c i n gs c h e d u l i n gp r o b l e mi so n eo ft h ei m p o r t a n tf a c t o r st h a ta f f e c tt h e s a f eo p e r a t i o no fa i r c r a f ta n dt h ew i n t e rf l i g h tp u n c t u a l i t y t h er e s u l to ft h e a s s i g n m e n td i r e c t l ya f f e c t st h ep r o f i to ft h ec o m p a n y t h e r e f o r e ，h o wt oa u t o m a t et h e a i r c r a f td e i c i n gs c h e d u l i n gu s i n ga p p r o p r i a t ea l g o r i t h ma n dt h eo p t i m i z a t i o n r e s e a r c hc o m et ob ea ni m p o r t a n tj o b t h i st h e s i si n t r o d u c e sr u l e - b a s e dh e u r i s t i cs e a r c ha l g o r i t h mt os o l v et h ea i r c r a f t d e i c i n gs c h e d u l i n gp r o b l e m t h r o u g ht h es t u d yo ft h es c h e d u l i n go p e r a t i o n so ft h e a c t u a la i r c r a f td e i c i n ga n a l y z i n gt h ef a c t o r ss h o u l db ec o n s i d e r e d t h e na c c o r d i n g t h e s ef a c t o r sid e s i g nt h eh e n r i s t i er u l e sa n dt h es e a r c ha l g o r i t h m i na d d i t i o n , t h e m o s tu s e da l g o d t h m - f c f si su s e dt od e s i g nt h es e a r c ha l g o r i t h mt ot h ea i r c r a f t d e i c i n gs c h e d u l i n gp r o b l e m 。 f i n a l l y , t w os e a r c ha l g o r i t h m sa r ei m p l e m e n t e da n do f f e r i n g 锄e x a m p l et o t e s t t h e s ea l g o r i t h m s t h er e s u l t so ft h ec o m p a r a t i v ea n a l y s i ss h o wt h er u l e - b a s e d h e u r i s t i c sa l g o r i t h m sa d v a n t a g e sa n df e a s i b i l i t i e s a i r c r a f td e i c i n g ，s c h e d u l i n g ，r u l e - b a s e d ，h e u r i s t i cs e a r c h a l g o r i t h m 学位论文版权使用授权书 本人完全了解对外经济贸易大学关于收集、保存、使用学位 论文的规定，同意如下各项内容：按照学校要求提交学位论文的 印刷本和电子版本；学校有权保存学位论文的印刷本和电子版， 并采用影印、缩印、扫描、数字化或其它手段保存论文；学校有 权提供目录检索以及提供本学位论文全文或部分的阅览服务；学 校有权按照有关规定向国家有关部门或者机构送交论文；在以不 以赢利为目的的前提下，学校可以适当复制论文的部分或全部内 容用于学术活动。保密的学位论文在解密后遵守此规定。 学位论文作者签名：碾形怨 导师躲稿 川年j 月局日 沙可年j 月声日 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导 下，独立进行研究工作所取得的成果。除文中已经注明引用的 内容外，本论文不含任何其他个人或集体已经发表或撰写过的 作品成果。对本文所涉及的研究工作做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法 律责任由本人承担。 特此声明 学位论文作者签名：币氍茅咎砂吖年歹月卢日 第1 章绪论 1 1 飞机除冰调度的研究背景及研究意义 1 1 1 飞机除冰的基本概念 飞机结冰指的是冬季飞机外表面( 如机翼、机身、螺旋桨、引擎等) 冰雪、 霜的凝结现象，飞机结冰常常会给飞行安全带来极大的伤害。如：飞机风挡结 冰会影响驾驶员的视野；机翼结冰会影响气动外形，增大飞行阻力、减少升力， 影响全机的操纵性及稳定性；发动机进气口结冰时，发动机进气受到影响，会 减少可用的动力；起落架装置上的结冰，会在收轮时损坏起落架装置或设备， 积聚在起落架上的冰雪再起飞时会脱落，从而损坏飞机；飞机外部传感器探孔 或探头，或传感器附近区域有污染的花，飞行仪表、发动机仪表或其他仪表及 自动系统会收到错误的信息；无线积冰影响通讯质量甚至使通讯中断等等。 在这方面，国际航空有很多血的教训。据统计，在过去2 5 年里，由于飞机 除冰问题已经造成了1 8 起空难，其中包括我国包头“1 1 2 l 空难、美国“1 1 2 9 科多拉州空难、英国“1 4 伯明翰空难等，导致千余人罹难。因此，冬季飞机 除冰问题已经成为影响飞机飞行安全的隐患之一。同时，飞机除冰问题也是造 成冬季冰雪天气条件下航班大面积延误的主要原因之一，特别是对大型枢纽机 场的影响尤为严重。民航总局也对飞机带有冰、雪、霜起飞进行了严格限制， 公共航空运输承运人运行合格审定规则( c c a r 一1 2 1 部) 第1 2 1 6 4 9 条明确规定： 当有霜、雪或冰附着在飞机机翼、操纵面、螺旋桨、发动机进气口或其他重要 表面上时，任何人不得使飞机起飞。因此，为了保证飞机在冬季能安全起降， 必须对飞机进行除冰。 在实际应用中，飞机除冰的过程主要有两个步骤：除冰、防冰。顾名思义， 除冰是指去除飞机大翼及机身表面的冰、雪、霜的过程，而防冰指的是在机身 喷洒防冰液，以保证飞机的防冰持续效应时间，如果超过了保持时间，为了安 全起见，将要进行二次除冰。这个二阶段的过程主要应用于飞机起飞前，起飞 后，飞机机载的除冰防冰系统将开始工作。清除冰冻层可以有很多不同的方式： 自动扫雪机、压缩空气除冰、红外线加热除冰、乙二醇基除冰剂除冰。目前应 用最广泛的除冰方法是乙二醇基除冰，它的优点是设备成本低，场地适应性较 好，但是容易带来环境问题。 传统的除冰是在机位除冰，整个过程如下图所示： 至i 这种除冰过程存在一定的缺点：机位相对狭小，容易与飞机碰撞；除冰液 无法回收，会造成一定的环境污染；可能产生冻融效应，破坏地面；除冰车往 返加液，造成时间上的浪费；另外，飞机起飞前需等待空管指令，其等待时间 并不确定，因此极容易产生二次结冰，从而造成飞机的延误。 新的除冰系统有专门的除冰坪，通过调度指令将飞机分配到不同的除冰坪 进行统一除冰。这种除冰系统的优势主要表现在以下方面： ( 1 ) 保证了飞行安全：实现了飞机除冰过程的统一指挥和协调，可以杜 绝二次除冰的问题。 ( 2 ) 可以提高除冰作业效率，减少延误：可实现除冰液的就地供给，减 少除冰车往返所消耗的辅助时间。 ( 3 ) 提高除冰车除冰作业能力：在一定温度下进行除冰液的配比作业， 并配备自动搅拌系统，可保证除冰液的充分混合，提高除冰液的除 冰效果。 ( 4 ) 缩短除冰除冰准备时间：可以减少除冰液预热时间和燃油加注频率。 ( 5 ) 减少除冰过程的刮蹭事故：避免了除冰车在狭小的机位空间与飞机 发生碰撞的机率。 ( 6 ) 减少机坪道面破坏：实现了除冰液的快速集中回收，避免了因冻融 效应导致的机坪大面积损坏。 ( 7 ) 保护环境和生态：除冰液的集中回收处理最大程度减少除冰液对机 场周围环境和生态的破坏。 在这个过程中，飞机除冰的过程控制与优化调度是一个关键因素，如果上 百架飞机同时等待除冰，结果可想而知，航班延误在所难免。在某些极端天气 条件下，如何合理地依据现有的除冰资源安排飞机除冰的次序，使旅客与航空 公司的损失尽可能的减小? 一个良好的调度系统是非常重要的。 1 1 2 飞机除冰调度的研究意义 关于除冰调度方面的研究具有一定的理论意义及现实意义。 首先，飞机除冰调度需要根据天气情况进行动态调整，因此具有一定的偶 2 然性和突发性，另外，由于除冰液和防冰液的特点，还具有一定的时效性。由 于除冰调度不合理而引发的一系列问题，如机场整体运行能力的下降，公司与 乘客利益的损失，往往在一些突发的气候灾害下影响很大，2 0 0 8 年的冰雪灾害 充分体现了这一问题。另外，对于飞机除冰调度的研究能更好的协助完善机场 方面应急预案，从而减少或避免在突发情况下的一些不必要的损失，具有一定 的现实意义。 其次，现阶段，关于飞机除冰调度方面的研究相对很少，还处于探索阶段， 但是，相类似的研究，如港口调度、以及工业生产中工件加工的分配问题等相 对较多，可以借助类似问题的研究方法来解决新的问题，构建新的模型。因此， 这种探索性的研究也有一定的理论意义。 1 2 飞机除冰调度的研究现状 1 2 1 确定性调度相关的研究成果 调度理论研究在工业生产中的研究较多，在服务行业的应用，典型的有港口 调度，登机口分配、机位分配等等。 b i s p o 和r o s e 等瞄一1 使用仿真与优化相结合的方法研究可重入生产系统的 能力分配、库存管理和生产控制等方面问题；王红湘、严伟睁1 采用启发式算法 对集装箱码头运作效率方面的泊位分配问题进行研究；喻道远、黄剑，采用组 合规则启发式算法对作业车间调度问题进行研究；常俊林n 铂等采用启发式算法 对并行机成组调度问题进行研究；宋万忠n 羽采用基于规则的启发式算法研究多 机场地面等待问题；宫华、陈大亨n 钔等采用启发式算法研究并行机的生产运输 协调调度问题；杨国兴、刘振武n 明采用启发式算法进行列车优化调度问题的研 究；王雄志、王国庆u 剐采用启发式算法对配送中心补货作业问题进行研究；陈 强、刘佐成、崔莉莉n 7 1 等采用启发式算法对集装箱配载问题进行研究； v e r m e u l e n n 8 3 等针对医院患者排队问题，提出了基于多a g e n t 的优化调度方案， 并对协调优化机制进行了探索性研究。 刘兆明、葛宏伟口采用遗传算法、模拟退火的思想进行了机场调度研究， 主要研究机位分配及滑行道分配的过程；宋芳、李燕乜鲫等采用了多a g e n t 技术 进行机场调度系统的研究；杨秋辉、游志胜瞳4 ，等采用遗传算法解决了多跑道到 达飞机的调度；程晓航乜引等采用自适应遗传算法实现了单跑道降落飞机调度问 题的求解；孙宏、张翔1 等采用模拟退火算法进行飞机调度研究。 3 1 2 2 飞机除冰调度的研究成果 在有关机场的调度问题研究中，主要有登机口的分配调度，机位分配调度， 机场地面整体调度方面的研究，专门对除冰调度的研究很少。x i a o y um a o 将协 调和竞争机制引入到飞机除冰优化调度中，提出基于多a g e n t 的飞机除冰调度 模型，并采用神经进化算法提高调度过程的效率和公平性。a d r i a a n 1 等提出了 基于多a g e n t 的飞机除冰调度方案，并对其协调机制进行了深入研究。 1 2 3 飞机除冰调度存在的问题 在之前的研究中，存在一些问题，如研究仅考虑单除冰坪的除冰调度问题， 忽略了飞机除冰过程与其它过程的耦合，如泊位分配、航空公司利益均衡等。 实际上飞机除冰过程既包括并行作业的多块除冰坪，有时还要考虑集中除冰和 机位除冰相结合的组合除冰作业模式，以及与其它系统的耦合关系，是复杂的 多目标非线性规划问题。对于飞机除冰问题的研究，必然要结合相关的过程来 考虑，同时，也将增加更多的限制因素。 1 3 研究内容及目的 本文以北京某大型国际机场飞机除冰为背景，利用现有的飞机集中除冰系 统装备，对具有多块除冰坪条件下的飞机除冰调度和过程控制进行深入的理论 研究，目的是在机场资源有限的条件下，对除冰设备设施进行优化调度与控制， 设计一个更加合理、优化的调度模型及算法，以期最大程度提高机场飞机除冰 的质量和效率，同时提高枢纽机场冬季冰雪天气条件下的运行保障能力。 飞机除冰调度的系统需要将除冰过程与其他相关联的过程( 如离港过程、 滑道调度、泊位分配等) 结合起来，在保证飞机及时除冰的同时，还要兼顾除 冰坪的利用效率，避免飞机进行二次除冰，另外，还要尽可能平衡各个航空公 司的利益。要达到全面的功能及约束，需要多种算法相结合。启发式算法有调 度速度快，结果较优的特点，在不易建立模型的情况下能充分发挥其优势。 本文主要考虑除冰效率问题，围绕基于规则的启发式算法进行分析研究， 主要的研究内容包括： ( 1 ) 机场除冰调度的完整业务流程及相关约束条件( 如起飞、除冰时 间，泊位分配等) ； ( 2 ) 分析目前已有的除冰调度理论与模型： ( 3 ) 结合相关的约束条件建立飞机除冰调度的理论模型； ( 4 ) 对启发式算法进行深入的研究与探索，建立启发式规则，并对调 4 度模型进行算法描述； ( 5 ) 建立最基本的f c f s 搜索算法。 ( 6 ) 对两种调度算法进行实现及实例测试，分析比较测试结果。 1 4 论文的组织结构 本文以我国大型机场的除冰调度为主要研究内容，采用基于规则的启发式 搜索算法进行研究，分析了飞机除冰调度需要考虑的限制因素，并结合实际需 要提炼出了主要约束条件，建立了启发式搜索规则，并设计了适合的算法，和 最基本的f c f s 算法进行比较。最后用实例说明该种规则和算法具有一定的优越 性和可行性。 论文共分为六章，其组织结构为： 第一章是绪论，主要介绍飞机除冰及调度的基本概念及研究意义，分析了 该领域的研究现状从而引出本文的研究内容及目标。 第二章主要对常用的调度方法进行简要介绍，并对不同的算法特点进行分 析比较，最后得出启发式搜索算法对于解决飞机除冰调度问题是比较合适的。 第三章建立了飞机除冰调度的启发式规则。是本文的主要创新点。首先， 分析了除冰调度的业务流程及调度需要考虑的多种约束条件，提出本文调度研 究的优化目标即：总延迟时间最短。最后分析最主要的约束条件，从航班除冰 自身的需求度及除冰位的争用度两个方面来建立了启发式规则。 第四章根据第三章建立的启发式规则设计启发式搜索算法，并且设计了 f c f s 搜索算法来进行对比。首先陈述了算法流程，然后进行了算法实现。 第五章用实例说明基于规则的启发式搜索算法对于本文研究的飞机除冰调 度的问题是可行的。首先进行了实例说明，然后对两种不同算法的运行结果来 进行总结分析。 第六章对论文的研究工作进行总结，并对今后的研究方向进行了展望。 第2 章常用调度方法的分析 2 1 调度的任务及分类 调度是决策的一种形式，在制造业和服务业中扮演着关键的角色。2 0 世纪 初，调度开始在制造业中受到重视。6 0 年代，人们在用动态规划和整数规划对 调度问题建模方面做了大量工作，8 0 年代，展开了对随机调度问题的研究，随 着计算机的广泛应用，人们开发出了生成实际可用调度计划的系统。在现阶段， 关于调度理论的研究主要集中在确定性调度和随机调度两个方面，其中，又有 单机调度和并行机调度之分。 在实际解决调度问题中，常用的方法有很多，如分派规则( 先来先服务规 则、最短队列优先规则等) ；过滤束搜索法( 分支定界法的改进，挑选最具潜力 的节点进行下一步搜索) ；局部搜索算法如模拟退火法、禁忌搜索法、遗传算法 ( 从一个任意选择出的完整的调度方案开始，在现有的调度邻域找到一个更好 的调度) ；启发式搜索算法等。启发式搜索算法有很多种，如约束引导的启发式 搜索方法，以满足优先约束条件来对调度进行调整；再比如，分配一排序启发式 算法，其主要思想是对工作进行排序，然后分派到指定的机器上。 2 2 实际中常用的调度方法 2 2 1 模拟退火算法 模拟退火算法是解决t s p 问题的有效方法之一，其最初的思想由 m e t r o p o l i s 在1 9 5 3 年提出，k i r k p a t r i c k 在1 9 8 3 年成功地将其应用在组合最 优化问题中。 模拟退火算法的模型 模拟退火算法可以分解为解空间、目标函数和初始解三部分。 解空间：为问题的所有可能( 可行的或包括不可行的) 解的集合，它限定了 初始解选取和新解产生时的范围。对无约束的优化问题，任一可能解( p o s s i b l e s o l u t i o n ) 即为一可行解( f e a s i b l es o l u t i o n ) ，因此解空间就是所有可行解的 集合；而在许多组合优化问题中，一个解除满足目标函数最优的要求外，还必 须满足一组约束( c o n s t r a i n t ) ，因此在解集中可能包含一些不可行解 6 ( i n f e a s i b l es o l u t i o n ) 。为此，可以限定解空间仅为所有可行解的集合，即在 构造解时就考虑到对解的约束；也可允许解空间包含不可行解，而在目标函数 中加上所谓罚函数( p e n a l t yf u n c t i o n ) 以“惩罚 不可行解的出现。 目标函数：对问题的优化目标的数学描述，通常表述为若干优化目标的一 个和式。目标函数的选取必须正确体现对问题的整体优化要求。例如，如上所 述，当解空间包含不可行解时，目标函数中应包含对不可行解的罚函数项，借 此将一个有约束的优化问题转化为无约束的优化问题。一般地，目标函数值不 一定就是问题的优化目标值，但其对应关系应是显明的。此外，目标函数式应 当是易于计算的，这将有利于在优化过程中简化目标函数差的计算以提高算法 的效率。 初始解：是算法迭代的起点，试验表明，模拟退火算法是鲁棒的( r o b u s t ) ， 即最终解的求得几乎不依赖于初始解的选取。 模拟退火的基本思想： ( 1 ) 初始化：初始温度t ( 充分大) ，初始解状态s ( 是算法迭代的起点) ，每 个t 值的迭代次数l ( 2 ) 对k = l ，l 做第( 3 ) 至第6 步： ( 3 ) 产生新解s 7 ( 4 ) 计算增量at = c ( s7 ) 一c ( s ) ，其中c ( s ) 为评价函数 ( 5 ) 若at 0 ，然后转第2 步。 模拟退火算法新解的产生和接受可分为如下四个步骤： 第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后 续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产 生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产 生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一 定的影响。 第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分 产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言， 这是计算目标函数差的最快方法。 第三步是判断新解是否被接受，判断的依据是个接受准则，最常用的接受 准则是m e t r o p o l i s 准则：若a t7 0 则接受s7 作为新的当前解s ，否则以概 7 率e x p ( a t7 t ) 接受s7 作为新的当前解s 。 第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对 应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前 解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时， 则在原当前解的基础上继续下一轮试验。 下图为模拟退火算法的流程图： 图2 1 模拟退火算法流程框图 模拟退火算法的应用很广泛，可以求解n p 完全问题，但其参数难以控制， 其主要问题有以下三点： 温度t 的初始值设置问题 温度t 的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、 初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间； 反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中， 初始温度一般需要依据实验结果进行若干次调整。 退火速度问题 模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温 度下的“充分 搜索( 退火) 是相当必要的，但这需要计算时间。实际应用中， 要针对具体问题的性质和特征设置合理的退火平衡条件。 温度管理问题 温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于 必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：t ( t + 1 ) = k t ( t ) 式中k 为正的略小于1 o o 的常数，t 为降温的次数。 2 2 2 禁忌搜索算法 禁忌搜索( t a b us e a r c h 或t a b o os e a r c h ，简称t s ) 的思想最早由 g l o v e r ( 1 9 8 6 ) 提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算 法，是对人类智力过程的一种模拟。t s 算法通过引入一个灵活的存储结构和相 应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态， 进而保证多样化的有效探索以最终实现全局优化。迄今为止，t s 算法在组合优 化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近 年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。 简单的禁忌搜索是在领域搜索的基础上，通过设置禁忌表来禁忌一些已经 历的操作，并利用藐视准则来奖励一些优良状态，其中领域结构、候选解、禁 忌长度、禁忌对象、藐视准则、终止准则等是影响禁忌搜索算法性能的关键。 简单t s 算法的基本思想是：给定一个当前解( 初始解) 和一种邻域，然后在当 前解的邻域中确定若干候选解；若最佳候选解对应的目标值优于“b e s ts o f a r 状态，则忽视其禁忌特性，用其替代当前解和“b e s ts of a r ”状态，并 将相应的对象加入禁忌表，同时修改禁忌表中各对象的任期；若不存在上述候 选解，则选择在候选解中选择非禁忌的最佳状态为新的当前解，而无视它与当 前解的优劣，同时将相应的对象加入禁忌表，并修改禁忌表中各对象的任期； 如此重复上述迭代搜索过程，直至满足停止准则。 简单禁忌搜索的算法步骤可描述如下： 步骤1 设定k = l ： 选择出一个初始序列) i ；设定) o = ) 1 ； 步骤2 从吨的邻域中选择候选调度吐； 如果移动以06 c 被禁忌表上的变换指令禁止，那么设定以+ k 瓯， 到步骤3 ； 如果移动o t o c 没有被禁忌表上的变换指示禁止，那么设定 s k l ：s c 9 将反向变换放到禁忌表的顶部； 将禁忌表中其它所有条目向下调整一个位置； 删除禁忌表底部的条目。 如果g ( o c ) 变量描述： a 表示航班a g e n t 集合； 卜表示除冰坪的集合； ( 1 ) ( 2 ) ( 3 ) ( 4 ) c 表示能够提供除冰服务的除冰机位关于除冰坪的函数； f 表示对于每个航班a g e n t 个体的开始除冰时间的函数； p 表示对于每个航班a g e n t 个体的除冰时间的函数； l 表示对于每个航班a g e n t 个体的航班延误损失的函数 除冰调度问题需要考虑多方面的因素，目前国内主要依赖人工调度，还没 有实际的系统实施，而基于规则的启发式搜索算法是专门依据实际经验所建立 的一套启发式规则来进行求解的。因此，本文采用基于规则的启发式算法来进 行分析设计。属于探索性的研究。 3 4 除冰调度理论模型的构建 3 4 1 除冰调度理论模型的描述 飞机除冰调度的问题在实际过程中，需要机场指挥中心、航空公司、地面 服务中心等多个部门的协调，主要依据保持时间、航班动态、跑道的分配情况 等条件将不同的航班分配到不同的除冰坪。假设某机场有m 个除冰坪，每个除 冰坪有n 个除冰位，另外，机场需要进行除冰的飞机有p 架，那么，该除冰调 度问题实质是在t 时间段内，将p 架飞机在m n 个除冰位之间的调度问题。 在生产调度的领域中，一个典型的研究问题就是n 个工件在m 台设备上进 行加工的问题，在该问题中，工件的工艺路线是预先给定的，每道工序的加工 时间是确定的，调度的目标是确定每台设备上不同工序的加工顺序，使得某项 性能指标达到最优。该调度问题需要满足一些约束条件，如：一台设备不能同 时加工两个工件，后道工序需要在前道工序完成后才能开始，考虑等待时间等 等。 我们可以发现，飞机的除冰调度问题与多个工件在多台设备中的调度问题 类似，对于存在一个设备集合，每个工件可以由多台设备来加工，对于每台设 备来说，又可能出现多个工件竞争一台设备的问题。在除冰调度中，对于每个 航班，存在一个除冰位的集合，一个航班可以在多个除冰位进行除冰，而对于 每个除冰位来说，也存在多个航班竞争个除冰位的问题。因此，飞机除冰调 度的问题可以简化为工件加工的调度问题。 对于飞机除冰调度的问题，由于每架飞机的除冰时间是确定的，因此属于 确定性调度问题，因为除冰过程中，多个除冰机是同时工作的，它也是一个并 行机调度的问题。总的来说，飞机除冰调度的问题属于确定性并行机调度的范 畴。 3 4 2 调度理论模型的目标函数及变量描述 设一个大型机场，时间段t 是一个除冰调度的时间段，对时间段t 内所有 需要进行除冰的航班进行调度分配。需要进行除冰的航班集合为i = ( ii i = l ，2 ，n ) ，所有的航班机型设为j ，m 代表跑道，n 代表每个除冰坪的除冰 机位。本文主要研究算法的可用性，另外，实际中各航班大部分采用c 、d 、e 三种机型，因此，假设每个除冰坪各有适合c 、d 、e 三种机型除冰的除冰机位 各一个。模型的变量描述如下： i 表示时间段t 内需要进行除冰调度的航班代码，i = l ，2 ，3 ； j 表示航班机型代码，j = l ，2 ，3 ； k 表示航空公司代码，k = l ，2 ，3 ； t 表示当前时间； o 表示延迟时间； 织表示巧航班的等待时间 m 表示跑道代码，m = l ，2 ，3 ； n 表示每个除冰坪的除冰机位代码，n = l ，2 ，3 ； 吒表示各航空公司的均衡值( k = 1 ，2 ，3 ) ，初始值均为0 。 1 一表示第m 号跑道的第n 号除冰位最后一个除冰任务结束的时间，初 始值设置为t n ，即除冰开始进行的时间。 表示第i 个航班； t 表示第i 个航班的起飞时间； 鼻詹表示第i 个航班所属的航空公司，p k ：1 ，2 3 。 ( j 第i 个航班的机型； l 2 肼i m 一表示除冰位的任务列表； l s 倒表示航班列表。 本文以总的等待时间最短作为优化目标，表示如下： ， r a i ny t p , j r j r r i = 1 3 5 启发式规则的建立 3 5 1 启发式规则的建立依据 基于规则的启发式搜索算法的核心问题就是建立一系列满足约束的启发式 规则，一般情况下，根据一定的经验和先验知识来制定。通过启发式规则的指 导，来控制可行解的搜索方向，最终得到一个满意解。使用启发式搜索方法求 得的解不一定是最优解，其求解性能的好坏主要取决于，所设计的启发式规则 是否适应于具体问题的特点，是否与实际的操作经验相吻合。 对于飞机除冰调度问题，一种简单的方法就是将待除冰的飞机看作是待加 工的零件，将多台除冰机看作是一个设备的集合，整个问题可以看作是一个排 队系统。需要确定的是，依照什么样的规则标准来安排任务。针对除冰这个特 殊的任务来说，如何来进行调度主要与航班动态及跑道的分配情况、机位匹配 等因素有关。 3 5 2 启发式规则的具体设计 针对本文研究的除冰调度问题，定义了航班除冰任务的需求度以及除冰位 的时间窗口争用度两个度量标准作为该问题的启发式规则。主要考虑到了以下 一些约束条件：除冰时间的约束、航班时间约束、跑道分配、机型与机位的匹 配、等待时间较短以及各航空公司的利益等。 ( 1 ) 航班除冰任务的需求度 该规则体现了各航班除冰任务的优先级。给每个航班进行除冰可以看作是 一个任务的集合，我们选择任务的一个常用方法是选择优先级最高的。在判断 不同航班的优先级的问题上，我们简化为一个时间的约束，即设置一个延迟时 间o 表示航班可以容忍的最大延迟时间，假设每个航班都是一样的。 若在t 时刻时，第i 个航班1 ，的延迟时间t o ，则具有较高优先级，若 有多个航班的延迟时间均大于等于o ，则从均衡各航空公司的利益角度出发， 选择调度最少的航空公司的航班。( 每个航空公司设置一个均衡值，代表其 拥有航班调度安排的程度，每调度其拥有的一个航班，则口k 值加l 。) 。 若对于所有的航班，其，o ，则该时刻离起飞时间最近的航班较为优先， 1 调度结果的测试函数 如果存在多个航班，则选择均衡值最小的航空公司的航班。 以上是对该规则的具体描述，在该规则里我们主要考虑的约束条件是航班 时间及各航空公司的利益均衡程度。每个航班的时间都是预排好的，因此，为 了尽量不造成航班的延误，除冰调度应保证在起飞前完成除冰，因此航班时间 的约束是一个必要的约束条件。在实际的人工调度安排中，是需要考虑各航空 公司的利益均衡的问题，因此，本文设置了一个均衡值吩，来协调调度安排。 另外，在选择航班的时候，如果只是优先选择起飞时间最早的航班，则有 可能出现某个航班延迟时间较长的问题，因此，我们设置了一个最大延迟时间 o ，以保证各航班延迟时间较为均衡。 ( 2 ) 除冰位的争用度 该指标体现了每个除冰位安排任务的情况，理想情况下，是选择竞争程度 最小( 争用度最低) 的除冰位，有利于减小航班的延误时间。 由于每种型号的飞机可以使用的除冰机位有多个，对于按照规则( 1 ) 所选 择的航班来说，被分配的哪个除冰位则按照该规则来选择，该规则在确定除冰 位的同时，也就确定了分配给某个航班的除冰资源。 参照实际经验，除冰液是具有一定的保持作用时间的，超过了保持作用时 间，飞机需要进行二次除冰，所以，在除冰位的分配过程中，需要考虑除冰结 束之后从除冰坪滑行到起飞跑道的时间，如果这个时间过长，则有可能进行二 次除冰，进而造成航班延误。 因此，本文优先考虑位于起飞跑道端头的除冰机位。如果等待时间过长， 可能导致航班延误，则选择等待时间最短的除冰机位。该规则一方面保证了航 班能在保持时间之内起飞这个安全指标，另一方面保证了延误时间较短i 还可 以均衡除冰资源的任务负荷。 该规则主要考虑除冰等待时间最短、跑道的分配、机型与机位的匹配等约 束，下面进行具体的描述： 保持作用时间 在第二节对于除冰调度问题需要考虑的约束条件的描述中，已经介绍了保 持时间的概念。保持作用时间约束即h o t ，它是指在除冰结束之后，防冰液能 阻止飞机表面再结冰的估计时间，这个时间与一定的天气情况有关，极端天气 情况时，如温度极低，或大雪天情况下，其保持作用时间会缩短。出于安全方 面的需要，飞机需要在防冰液的保持作用时间内起飞。 根据实际操作经验，飞机在除冰结束之后可以直接滑上跑道起飞，因此， 本文在保持作用时间的约束条件上做了一定的简化。暂不考虑航班在其他跑道 的除冰位进行除冰之后滑向其起飞跑道的时间约束，假设飞机除冰完成之后可 以立即起飞。 除冰时间 不同型号飞机的除冰时间有所不同，由于不同天气情况下，飞机霜、雪的 凝结程度不同，因此，对除冰时间也有一定的影响。本文主要考虑机场常用的 c 、d 、e 三种型号的飞机，及其一般情况下的除冰时间。即c 型飞机7 分钟；d 型飞机1 0 分钟；e 型飞机1 5 分钟。 跑道分配 不同目的地的航班被分配的跑道有所不同，每个航班在起飞前已经进行了 跑道的分配，实际中存在以下情况：假如在一号跑道的除冰坪除冰，需要在二 号跑道起飞，在从一号跑道的除冰坪滑n - 号跑道的过程中，就有可能因为时 间问题造成二次除冰的可能性。因此为了尽量避免进行二次除冰，在实际的调 度过程中，每个航班分配到哪个除冰坪，需要考虑其跑道的分配情况，尽量分 配位于起飞跑道端头的除冰坪。 综上，在该方面调度的原则是优先选择起飞跑道端头的除冰坪，在不满足 其他约束条件的情况下再选择其他除冰坪。 机型与机位的匹配 原则上，为了不造成资源的浪费，大型飞机分配大型除冰位，小型飞机分 配小型除冰位，尽量避免容纳大机型的除冰位分配给小机型；特殊情况下，当 大型机除冰位无空闲而有相邻小型机的除冰位空闲时，可以合并小型机除冰位。 根据实际情况，本文假设在满足其等待时间最短的情况下小型机可以分配 大型机的除冰机位，简化考虑每个除冰坪有c 、d 、e 型除冰机位各一个。 等待时间较短 由实际操作中的除冰业务可知，飞机在进行除冰之前，需要在等待区域排 队等待，我们将等待时间设为t ，此约束条件定义了最小的等待时间。本文将 此约束条件作为次要选择指标。在航班不能分配到其起飞跑道端头的除冰位时， 分配到等待时间最短的适合的除冰位。 3 6 本章小结 本章主要通过分析飞机除冰调度业务的流程以及实际情况，主要从调度效 率的角度出发，制定了启发式规则。为下一章的算法设计提供依据。 本章首先介绍了飞机除冰调度业务的具体流程，并建立了除冰调度的理论 模型。根据实际情况分析了在除冰调度过程中可能考虑到的约束条件，并结合 实际的运行要求，选择了符合实际需求的主要约束条件：航班时问的约束、各 航空公司的利益均衡、机型与除冰机位的匹配、等待时间最短等。然后主要从 航班除冰任务的需求度，以及除冰位的争用度两方面建立了启发式规则。另外， 给出了调度过程中可能采用的具体参数，为第五章的实例分析提供了依据。 第4 章除冰调度算法的描述 4 1 基于规则的启发式算法的描述 前两章已经对启发式搜索算法的概念进行了详细的介绍，下面重点介绍本 文针对飞机除冰调度问题所设计的基于第三章所设计启发式规则的启发式搜索 算法。 1 ) 初始化调度所需变量。操作如下： a 建立一个航班队列l i s t ，航班起飞时间早的排在前面，航班起飞 时间晚的排在后面。 b 初始化代表每个航班所属的航空公司的值只七，曰詹：l ，2 3 。 c 初始化每个航班的机型号j ，只j = 1 ，2 ，3 。 d 初始化每个航班的起飞时间t 。 e 初始化各航空公司的均衡值吼( k = 1 ，2 ，3 ) ，初始值均为o 。 f 每个除冰位设置变量1 一，记录第m 号跑道的第n 号除冰位最后一个 除冰任务结束的时间，初始值设置为o 。 g 每个除冰位设置一个任务列表“盯一，按照先后顺序存放安排到每 个除冰位上的任务集合，初始化时该列表为空。 h 设置最长延迟时间o 。 i 初始化各航班的等待时间吼，初始值均为0 。 2 ) 笋j j 断各航班除冰任务的需求度，选择航班列表中优先级最高的一个航班。 在t 时刻时，遍历列表l i s t 巧是否为空，若为空，转第七步。 若不为空，判断各航班所属的航空公司的均衡值，选择均衡值最小的一 个。若均衡值相同，则任选一个航班。 所属的航班均衡值吼加1 。 3 ) 判断上一步所选航班起飞跑道端头的除冰位的等待时间，若不会造成延 误则转第5 步，若可能造成航班延误则转下一步。 4 ) 判断适合第二步所选航班机型的其他除冰位的等待时间，选择等待时间 最小的除冰位。 5 ) 将第二步所选航班加入到所选除冰位的队列血盯= f m 一中，更新该列表，更 m 新1 m n 。 6 ) 删除 ，更新航班列表l i s t ( 。 2 8 7 ) 算法结束。 飞机除冰调度的流程如图4 1 所示： 计算所有待安 j 除冰航班的需求度，并从 中挑选需求度相对最高的航班，有多个相 同时选择所属航空公司均衡值最小的一 个，若均衡值相等，任选一个 否 4 2f c f s 算法 是 图4 - l 飞机除冰调度的启发式搜索算法流程图 先来先服务( f c f s ，f i r s tc o m ef i r s ts e r v e ) 是最简单的调度算法，按 先后顺序进行调度。无论任务的大小、特点和所需的完成时间，对先到的任务 总是先处理，后到的任务总是后处理。 本文假设每个航班除冰位均安排其起飞跑道的除冰位，不考虑不同除冰机 位的选择情况，设计最简单的飞机除冰调度的f c f s 算法如下： 1 ) 初始化调度所需变量。操作如下： a 建立一个航班队列l i s t ，航班起飞时间早的排在前面，航班起飞 时间晚的排在后面。 b 初始化每个航班的机型 j ， j = l ，2 ，3 。 c 初始化每个航班的起飞时间t 。 d 初始化代表每个航班所属的航空公司的值只七，曰忌= 1 ，2 3 。 e 每个除冰位设置变量1 m n ，记录第m 号跑道的第n 号除冰位最后一个 除冰任务结束的时间，初始值设置为0 。 f 每个除冰位设置一个任务列表l i s t l 一，按照先后顺序存放安排到每 个除冰位上的任务集合，初始化时该列表为空。 g 初始化各航班的等待时间觋，初始值均为0 。 2 ) 选择要进行除冰的航班。 在t 时刻时，遍历列表l i s t 巧是否为空，若为空，转第五步。 若不为空，总是优先选择起飞时间最早的航班。 3 ) 判断上一步所选航班起飞跑道端头的除冰位，将所选航班加入到所选除 冰位的队列l 坫“一中，更新该列表，更新l m 一。 4 ) 删除号，更新航班列表l i s t 毋。 5 ) 算法结束。 算法流程图如下： i 磊赢一 j 4 3 本章小结 否 是 l 得到除冰调度方案 图4 2 飞机除冰调度的f c f s 算法流程图 本章是论文的次重点。在第三章启发式规则设计的基础上，为飞机除冰调 度的理论模型设计了搜索算法。 本章首先介绍了现有的除冰算法，然后依据第三章的启发式规则设计了启 发式搜索算法，另外，设计了飞机除冰的f c f s 算法，便于第五章进行实例验证 及结果的对比分析。 5 1 实例描述 第5 章实例及结果分析 某大型国际机场共有三条跑道。每条跑道一个除冰坪，每个除冰坪有三个 除冰机位，分别适合c 、d 、e 三种型号的飞机进行除冰，编号分别为o 、l 、2 。 为了使验证结果简洁明了，把该机场一段时间内的航班时刻表的间隔缩短， 并结合其跑道分配及航班的各个属性得到如下等待进行除冰调度的航班表。航 班的主要属性包括航班号、所属的航空公司、航班的机型、航班的起飞时间以 及航班的起飞跑道。航空公司的主要属性包括i d ( 用0 、l 、2 来表示) 以及均 衡值。t i j 表示i 号跑道的第j 号除冰机位当前任务完成的时间。 航班信息列表如下： 3 1 表5 - 1待进行除冰调度的航班列表 航班i d航班号所属的航空公司i d航班机型i d航班的起匕时间航班的起飞跑道i d lm u5 6 2 0 o 01 2 ：0 0o 2z h9 8 1 l l 0 1 2 ：0 2l 3m u7 3 0ol1 2 ：0 5l 4n w 9 1 3o21 2 ：1 02 5 c z 6 7 5 3l 01 2 ：1 l0 6c a 4 5 0 3121 2 ：1 12 7c z 6 7 5 5l21 2 ：1 ll 8c a l 2 1 5l11 2 ：1 3o 9 e z3 0 7 0 01 2 ：1 50 1 0n h9 1 9221 2 ：1 52 l lj l 7 9 3o21 2 ：1 62 1 2c z 6 5 3 3221 2 ：1 8l 1 3k a 8 7 6 101 2 ：2 0 2 1 4o z3 7 72o1 2 ：2 2o 1 5f m9 1 9 2ol1 2 ：2 41 1 6j l 7 9 1ol1 2 ：2 52 1 7 m u 2 1 5 1 21 1 2 ：2 5l 1 8 l ( e8 9 7 2l1 2 ：2 60 1 9 s q8 2 6 ol1 2 ：2 91 2 0m u5 0 3 3121 2 ：3 l0 2 l z h9 8 1 2 001 2 ：3 3 o 2 2m u5 6 0 50 0 1 2 ：3 52 2 3n w 9 1 0201 2 ：3 82 2 4c z3 5 1 62o1 2 ：4 3l 2 5c a 4 5 0 4021 2 ：4 5 0 2 6c z6 7 5 5 l01 2 ：4 5 l 2 7c a1 2 1 60l1 2 ：5 02 2 8e z8 2 82o1 2 ：5 10 2 9n h9 2 0 2 01 2 ：5 1 l 3 0j l 7 9 4l11 2 ：5 32 3 1c z6 5 3 4ol1 2 ：5 42 3 2k a8 7 7121 2 ：5 4l 3 3o z3 7 8l l1 2 ：5 6l