（产业经济学专业论文）基于遗传算法的机场除冰服务资源优化配置研究.pdf

摘要 随着我国民航机场规模的扩大和旅客运输量的增加，如何提高民航飞机运行 安全与运行效率成为我国民航发展中必须解决的问题。近几年来，航空器除冰雪 问题已经酿成多起空难，并成为冬季影响航班正点率的重要因素之一。在飞机除 冰设备改造更新完成后，如何对飞机除冰过程进行科学合理的调度和规划成为提 高飞机除冰质量和效率的关键问题。本文对具有多块除冰坪条件下的机场除冰服 务资源调度问题进行深入研究，以期最大程度提高机场除冰服务资源调度的质量 和效率。 本文主要做了以下工作：首先，描述了机场除冰方式的现状与关键流程。然 后归纳总结了除冰服务资源调度建模的考虑因素；其次，对除冰服务资源调度的 约束条件和优化目标进行分类和总结，建立了一个以所有需要除冰服务的航班总 延误时间最短和延误时间较均衡为目标的机场除冰服务资源调度模型；然后，为 此模型设计了遗传算法。实例计算的结果表明这个算法能在规定的迭代次数内找 到可行且较优的解。 关键词：除冰服务，资源调度，遗传算法 a b s t r a c t w i t ht h ee x p a n s i o no fc i v i la i r p o r ta n dt h ei n c r e a s i n g p a s s e n g e r s ，h o wt o i m p r o v et h eo p e r a t i o n a ls a f e t ya n de f f i c i e n c yo fc i v i la i r p o r th a sb e c o m eap r o b l e m t h a tm u s tb es o l v e df o rt h ed e v e l o p m e n to fc i v i la v i a t i o n i nr e c e n ty e a r s ，p r o b l e m s c a u s e db yd e i c i n ga n ds n o w - s w e e p i n gh a v el e dt om a n yt r a g e d i e s ，a n dh a v eb e c o m e o n eo ft h ei m p o r t a n tf a c t o r sa f f e c t i n gf l i g h tp u n c t u a l i t yo fw i n t e rs e a s o n s i n c et h e d e i c i n ge q u i p m e n to fa i r c r a f t sh a v er e n o v a t e dh o wt os c h e d u l ea n dp l a nt h ed e i c i n g p r o c e s ss c i e n t i f i c a l l ya n dr e a s o n a b l yb e c o m e sk e yi s s u e st oi m p r o v ea i r c r a f t - d e i c i n g q u a l i t ya n de f f i c i e n c y t h i sp a p e r w i l lc o n d u c ti n - d e p t hs t u d i e sf o rt h ed e i c i n gs e r v i c e r e s o u r c e s c h e d u l i n gp r o b l e mo nc o n d i t i o nt h a tm u l t i - b l o c kd e i c i n gb l o c k sa r e a v a i l a b l ef o r t h ea i r p o r t ，w i t l lt h ee x p e c t a t i o no fi m p r o v i n gt h eq u a l i t ya n de f f i c i e n c y o ft h ed e i c i n gs e r v i c er e s o u r c es c h e d u l i n gt oal a r g ee x t e n t t h em a i nc o n t e n t sa r ea sf o l l o w s f i r s to fa l l ，t h ep a p e rd e s c r i b e sm e t h o d sa n d k e yf l o w so fa i r p o r td e i c i n g s e c o n d l y , i ts u m m a r i z e sc o n s i d e r a t i o n sf o rt h ed e i c i n g s e r v i c er e s o u r c es c h e d u l i n gm o d e l i n g t h i r d l y ，t h ep a p e rc l a s s i f i e sa n ds u m m a r i z e s c o n s t r a i n t sa n do p t i m i z a t i o no b j e c t i v e so ft h ed e i c i n gs e r v i c er e s o u r c es c h e d u l i n g , e s t a b l i s h i n gt h ea i r p o r td e i c i n gs e r v i c er e s o u r c es c h e d u l i n gm o d e lw i t ht h eo b j e c t i v e o fm i n i m i z i n gt o t a ld e l a yt i m ef o ra l lf l i g h t sa n db a l a n c i n gd e l a yt i m ef o re v e r yf i g h t a tl a s t ，i td e s i g n st h eg e n e t i ca l g o r i t h mt or e a l i z et h em o d e l 1 1 1 ee x e c u t i n gr e s u l t so f e x a m p l e ss h o wt h a tt h ea l g o r i t h mc a nf i n df e a s i b l ea n db e t t e rs o l u t i o n su n d e rt h e s p e c i f i e di t e r a t i o nt i m e s k e y w o r d s ：d e i c i n gs e r v i c e s ，r e s o u r c es c h e d u l i n g ，g e n e t i ca l g o r i t h m 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容 外，本论文不含任何其他个人或集体已经发表或撰写过的作品成 果。对本文所涉及的研究工作做出重要贡献的个人和集体，均已 在文中以明确方式标明。本人完全意识到本声明的法律责任由本 人承担。 特此声明 学位论文作者签名：柱水 沙邯年岁月i e l 学位论文版权使用授权书 本人完全了解对外经济贸易大学关于收集、保存、使用学位 论文的规定，同意如下各项内容：按照学校要求提交学位论文的 印刷本和电子版本；学校有权保存学位论文的印刷本和电子版， 并采用影印、缩印、扫描、数字化或其它手段保存论文；学校有 权提供目录检索以及提供本学位论文全文或部分的阅览服务；学 校有权按照有关规定向国家有关部门或者机构送交论文；在以不 以赢利为目的的前提下，学校可以适当复制论文的部分或全部内 容用于学术活动。保密的学位论文在解密后遵守此规定。 学位论文作者签名：袖犯 导师签名： 笼彳场 弘气年5 = 其引日 1 年f 月y ) 日 1 1 研究背景与意义 第一章绪论 本文依托于国家自然科学基金项目( 6 0 8 7 9 0 2 0 ，项目名称：面向高效安全的 飞机除冰过程控制的理论和方法研究( 2 0 0 8 ) ) ，以北京首都国际机场飞机除冰为 背景，利用现有的飞机集中除冰系统装备，对具有多块除冰坪条件下的飞机除冰 调度进行深入研究，以期最大程度提高机场除冰服务资源调度的质量和效率。 飞机除冰是影响民航飞机冬季运行安全和效率的关键因素之一。飞机除冰是 指去除飞机大翼及机身表面的冰、雪、霜的过程。由于附着在飞机表面的冰雪霜 等污染物会直接导致飞机的空气动力学特性的改变，如升力下降、失速迎角改变 等，这种动力学特性的改变也是造成空难的主要原因之一。此外，聚集在飞机表 面的冰块在飞机起飞后容易脱落并吸入发动机，造成发动机损坏，从而引发空难。 据统计，在过去2 5 年里，由于飞机除冰问题已经造成了1 8 起空难，其中包括我 国包头“1 1 2 1 空难、美国“1 1 2 9 ”科多拉州空难、英国“1 4 ”伯明翰空难等， 导致千余人罹难。因此，冬季飞机除冰问题已经成为影响飞机飞行安全的隐患之 一。同时，飞机除冰问题也是造成冬季冰雪天气条件下航班大面积延误的主要原 因之一，特别是对大型枢纽机场的影响尤为严重。近几年，我国的北京首都国际 机场、上海虹桥机场均发生过由于飞机除冰导致的航班大面积延误，由此影响到 全国航班的正常运行，造成巨额的经济损失。 我国受冰雪影响的民航机场较多，据统计，在过去两年里，在我国年吞吐量 超过5 0 万的机场中，有降雪报告的机场达到3 3 个。而目前我国1 4 4 个运行机场 中，有冰雪天气的机场达到9 7 个。2 0 0 8 年冬季，共有7 2 个机场运行受到冰雪 天气的影响，占运行机场总数的5 0 7 ，造成航班延误2 0 7 4 架次，取消航班8 3 7 架次，1 5 个机场被迫关闭5 8 次，给机场、航空公司的工作造成很大的被动。2 0 0 8 年冰雪天气的影响范围波及到了部分南方机场，导致全国范围内大部分机场均不 同程度受到了冰雪的影响。因此，针对飞机除冰问题进行研究，对于提高我国民 航机场的冬季运行保障能力和运行效率具有重要的现实意义。 增加现有飞机除冰装备的数量、改进除冰装备的性能是提高飞机除冰质量和 除冰效率的途径之一。为此，2 0 0 5 年，民航总局对全国机场的飞机除冰雪状况 进行了调研，并根据各机场的情况进行了设备的更新和改进，在大型枢纽机场建 立飞机集中除冰系统，以最大程度提高飞机除冰质量和效率。在飞机除冰设备改 造更新完成后，如何对飞机除冰过程进行科学合理的调度和规划则成为提高飞机 除冰质量和效率的关键问题，研究面向高效、安全的飞机除冰过程调度与过程控 制的理论和方法也成为我国民航机场未来提高冰雪天气飞机运行安全和运行效 率的重要途径之一。 本文对机场除冰服务资源优化配置问题进行研究，着重研究机场除冰服务资 源调度问题，通过资源调度计划合理地配置关键资源。本文首先将建立机场除冰 服务资源调度的模型，然后根据模型设计合适的遗传算法来求解模型，得出“最 优的资源调度计划，根据资源调度计划合理地分配除冰服务相关资源，提高机 场除冰服务的质量和效率。本文的研究对提高枢纽机场冬季冰雪天气条件下的运 行保障能力具有重要的理论和现实意义。 1 2 国内外的研究现状及发展趋势 由于冰雪霜天气具备一定的偶然性和突发性，导致多数条件下飞机除冰过程 并非机场正常运行规划调度的组成部分，要求离港、空管等其他部门的运行调度 根据天气情况进行短期的动态调整。同时飞机除冰过程具有一定的时效性，而不 同类型的飞机除冰过程时间也在很大范围内变化，因此，飞机除冰过程表现为一 定程度的不确定性，需要机场其他系统根据飞机除冰过程要求进行动态的调整和 调度。而机场内运行的飞机隶属于多家航空公司，每个飞机个体代表着本公司的 利益，在冰雪天气条件下，单体飞机均以减少延误，减少公司运行损失为目的， 在飞机除冰过程中，整体表现具有趋同性，在某一时间段内，也会给除冰过程带 来很大的不确定性和动态性。因此，飞机除冰过程调度问题是一类典型的不完整 信息条件下动态资源调度问题。 目前，国内外对机场除冰调度的研究还非常少，因此对机场除冰服务资源调 度进行研究是非常有意义的探索。而存在环境变化和不完整信息条件下的资源调 度问题一直是学术界的研究热点，形成了若干理论研究成果，并在生产过程、医 疗、港e l 和机场资源调度等领域有着广泛的应用。如b i s p 0 1 和r o s e 2 等使用仿真 与优化相结合的方法研究可重入生产系统的能力分配、库存管理和生产控制等方 面问题；m a s o n 3 、刘民和吴澄等4 提出了基于启发式规则的动态生产系统调度方 案；于海滨等5 针对制造企业工件的交货期不同，提出了对提前拖期工件进行惩 1 b i s p ocf ，t a y u rs ，m a n a g i n gs i m p l er e - e n t r a n tf l o wl i n e st h e o r e t i c a lf o u n d a t i o na n de x p e r i m e n t a lr e s u l t s ， t e c h n i c a lr e p o r t ，c a r n e g i em e l l o nu n i v e r s i t y ，p o t t s b u r g h 。19 9 7 6 r o s eo ，e s t i m a t i o no ft h ec y c l et i m ed i s t r i b u t i o no faw a f e rf a bb yas i m p l es i m u l a t i o nm o d e l ，p r o c e e d i n g so f t h ei n t e m a t i o n a lc o n f e r e n c eo ns e m i c o n d u c t o rm a n u f a c t u r i n go p e r a t i o n a lm o d e l i n ga n ds i m u l a t i o n f o w l e r , w c o r c h r a n ，j a n dh i l t o n 。c ( e d s ) ，s a nf r a n c i s c o ，c a p pl3 3 - l3 8 ，l9 9 9 m a s o nsj ，k a s i no ，s c h e d u l i n gc o m p l e x j o bs h o p su s i n gd i s j u n c t i v eg r a p h s ：ac y c l ee l i m i n a t i o np r o c e d u r e ， i n t e r n a t i o n a lj o u r n a lo fp r o d u c t i o nr e s e a r c h ，4l ( 5 ) ，p p 9 8 卜9 9 4 ，2 0 0 3 l i um ，w uc ，g e n e t i ca l g o r i t h mu s i n gs e q u e n c er u l ec h a i nf o rm u l t i o b j e c t i v eo p t i m i z a t i o ni nr e - e n t r a n t m i c r o - e l e c t r o n i cp r o d u c t i o nl i n e ，r o b o t i c sa n dc o m p u t e r - i n t e g r a t e dm a n u f a c t u r i n g ，2 0 ( 3 ) ，p p 2 2 5 - 2 3 6 ，2 0 0 4 于海斌，上浩波，基十遗传算法的单机提前拖期调度方法研究，控制理论j 应用，2 0 0 7 年，2 0 9 2 1 4 页。 厶 罚的一类单机调度问题，并给出了基于遗传算法的优化方案；姚韵等6 对机场航 班过站的地面服务调度问题进行研究，给出考虑了不同设备加工能力的设备能力 差分配算法等。 以上关于动态调度的研究主要是采用集中调度的方法来进行研究，随着分布 式人工智能的发展，多利益主体构成的复杂系统中资源动态优化调度问题开始得 到有效解决。尤其是多a g e n t 技术在这方面有很大的优越性。随着多a g e n t 技术 的日益发展成熟，该技术已被广泛应用于各个领域，并被认为是研究分布式智能 系统的最重要的方法。目前，相当多的研究人员将该技术应用于制造业和现代服 务业的各个方面，如制造企业集成，供应链管理，制造规划、调度及控制，物料 管理及应急响应等等。 本文将在上述研究成果的基础上，对机场除冰服务资源优化配置问题进行有 意义的探索与研究。 1 3 研究内容与方法 1 3 1 研究内容 机场除冰服务的资源配置问题是一个非常复杂的问题。涉及的资源包括除冰 坪机位、除冰车及相关设备、工作人员、跑道等。以除冰坪为例，首先，除冰坪 的分配必须适合除冰坪的物理特性。这种适合体现在两个方面：一个是必须适合 除冰坪的容量特性；一个是在长时段内减少除冰坪冲突。在实际运营时，根据飞 机的型号来分配除冰坪，这是除冰坪容量特性的要求。即使除冰坪总量是足够的， 却可能在某些时段出现除冰坪冲突：飞机来了，却找不到合适自己停放的除冰坪。 如果分配不太合适，就会加剧这些冲突：例如把太多的小飞机放到了大除冰坪， 当大飞机来的时候就找不到空的大除冰坪了，但这时却可能还有空闲的小除冰 坪。这就要求除冰坪分配计划必须在较长的时段内减少甚至消除这些冲突。因此， 需要考虑航班密度、航班量、机型数量、除冰坪数量、时间段等因素的约束。 其次，飞机除冰过程具有一定的时效性，根据天气情况的不同，其保持时间 会有所变化，根据飞机除冰液标准，最长的保持时间不超过1 8 分钟，超过保持 时间，会增加已完成除冰飞机的二次结冰概率，从而给飞行安全带来隐患，而不 同类型的飞机除冰过程时间也在很大范围内变化。因此，飞机除冰过程需要机场 其他系统根据飞机除冰过程要求进行动态的调整和调度。比如需要考虑与离港系 统过程、滑行道调度系统、泊位分配过程等过程的耦合。 6 姚韵，朱金福，柏明国，航班过站地面服务的优化调度算法，信息与控制，2 0 0 7 年，3 6 ( 4 ) ，4 8 6 - 4 9 2 页。 3 再次，分配除冰坪更要考虑与机场整体实际运营以及经营管理之间的深刻影 响。机场内运行的飞机隶属于多家航空公司，每个飞机个体代表着本公司的利益， 在冰雪天气条件下，单体飞机均以减少延误，减少公司运行损失为目的。而除冰 调度应是所有航空公司的利益平衡结果。 本文对机场除冰服务的资源优化配置问题进行初步探索，着重研究了机场除 冰服务资源调度问题，通过资源调度计划合理地配置关键资源。本文首先分析了 国内外机场除冰调度的研究现状，探讨机场除冰调度的研究方法与研究意义。随 后给出实际调研结果，归纳出机场除冰方式与除冰流程。在实际调研的基础上， 对实际过程进行必要的简化、规范和抽象，总结出除冰服务的关键资源约束。本 文建立了一个以所有需要除冰服务的航班总延误时间最短和航班的延误时间较 均衡为目标的机场除冰调度模型，主要约束资源是除冰坪数量、类型等。然后结 合这个除冰服务资源调度的模型，本文研究了适合于求解此问题的遗传算法，通 过遗传算法的结果得到调度计划并对关键资源进行优化配置。最后运用机场的实 际业务数据，使用v i s u a lc + + 6 0 进行仿真实验，对除冰服务资源优化配置问题 进行实证研究。 1 3 2 研究方法 本文以能力约束、决策分析、并行机调度以及现代优化算法等基本理论为依 据，以定量分析为主，结合定性分析，通过理论分析、实际调查、对比分析、模 型建立与求解、实例论证等对机场除冰服务资源优化配置问题进行探讨。课题的 研究工作依据如下步骤进行： ( 1 ) 充分利用现有研究成果，继承与创新相结合。 ( 2 ) 在认真收集、挖掘、整理数据信息和研究问题特点的基础上，构建模 型，提炼算法。 ( 3 ) 数学模型的建立遵循因素分析、指标量化、优化建模的步骤。 ( 4 ) 验证算法的合理性、实用性和有效性。 ( 5 ) 认真总结所提出的模型的优点及不足，明确所面临的挑战，以及进一 步的研究方向。 本文采用遗传算法求解模型。遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 是一种 借鉴生物学的新达尔文主义，基于自然选择原理和自然遗传机制的随机、高度并 行、自适应的全局优化搜索算法。因其高效的优化性能、无需问题特殊信息等优 点，已广泛用于计算机科学、优化调度、运输问题、组合优化、工程优化等领域。 目前它已发展成一种白组织、自适应的综合技术。因为遗传算法可以搜索大范围 的可行解空间( f e a s i b l es o l u t i o ns p a c e ) ，避免陷入局部最优解，并且可针对问 4 题的特点设计不同的进化方式，对于解决实际问题拥有相当大的弹性7 ，所以本 文的除冰服务资源调度模型使用遗传算法求解。 本文最后利用v i s u a lc + + 6 0 进行编程实现。通过整数编码方式得到个体， 然后确定遗传算法进化机制及其进化参数，具体包括：群体数量、交叉方式、交 叉概率、变异概率、选择方式、终止条件等。最后对运行结果进行分析。 1 4 本文的创新之处 目前，国内对机场除冰服务资源调度的研究非常少，还没有建立起高效的机 场除冰调度模型。本文将结合机场的实际业务要求，对机场除冰服务资源调度进 行研究，建立机场除冰调度模型；并设计适合机场除冰调度模型的遗传算法，用 以求解模型；通过求解出的调度计划对关键资源进行合理配置。这是优化技术在 现代服务业中的具体应用。 1 5 本文的结构 本文以机场除冰服务资源优化配置问题为主要研究内容，着重研究机场除冰 服务资源调度问题。建立了一个以所有需要除冰服务的航班总延误时间最短和航 班的延误时间较均衡为目标的机场除冰调度模型，并设计了适合本模型的遗传算 法，通过求解出的调度计划对关键资源进行合理配置。并用实例说明此模型和算 法有一定的优越性和可行性。 第一章概述课题的研究背景和意义，阐述了除冰服务资源优化配置问题的研 究进展和研究方法。 第二章首先描述了机场除冰方式的现状与关键流程。然后归纳总结了除冰服 务资源调度建模的考虑因素，并对除冰调度模型的约束条件和优化目标进行分类 和总结。最后总结归纳出除冰服务资源调度模型，建立了一个以所有需要除冰服 务的航班总延误时间最短和航班的延误时间较均衡为目标的机场除冰调度模型。 第三章为除冰服务资源调度模型设计遗传算法。首先陈述传统遗传算法的搜 索流程，然后设计机场除冰调度模型的遗传算法搜索流程，最后选择合适的遗传 算法进化机制及遗传参数。 第四章运用v i s u a lc + + 6 0 进行仿真实验，用实例说明本文的机场除冰调度 模型和算法较优。首先用遗传算法求解本文的模型，然后分析比较本文得到的调 度方案和传统的先到先服务f c f s 调度方案，说明本文模型和算法得到的调度方 7 玄光男，程润伟，遗传算法与i t 程优化，清华大学出版社，2 0 0 4 年。 5 案可行且更优。 第五章对论文研究工作进行总结，并对今后的研究方向进行了展望。 1 6 本章小结 本章主要介绍了除冰服务资源优化配置研究提出的背景与意义，以及国内外 的研究现状与发展趋势。国内外学者在动态资源调度方面的研究是本文的重要借 鉴与基础。本章也说明了本文的主要研究内容与方法。由于国内对机场除冰服务 资源调度的研究非常少，本文所做的研究是非常有意义的探索。最后，本章还概 括了本文的结构与各章主要内容。 6 第二章机场除冰服务资源优化配置问题的建模探讨 2 1 机场实际调研结果描述 2 1 1 机场除冰方式现状 在飞机起飞前，必须除去飞机所有冰冻层，这种方法称为除冰。 我国民航机场传统上采用机位除冰，机位除冰是指飞机在停机位等待，除冰 车等设备到各个停机位为飞机除冰。 这种除冰方式的核心设备是飞机除冰车，工艺流程如图2 1 所示： 图2 1 机位除冰工艺流程 这种分散的除冰作业方式存在诸多问题，主要表现在： 除冰过程缺乏统一的指挥和协调，整个除冰过程处于无序状态，除冰后 无法保证飞机在除冰液有效保持时间内及时起飞，容易造成二次除冰问 题，不仅增加了除冰成本，也给飞行安全带来极大的隐患。 降低了机位资源的利用率，从而使得整个机场容量和运行效率受到影响 除冰车的往返加液过程浪费了大量的时问，不仅降低了除冰设备资源的 使用效率，还增加了与飞机及地面运行车辆发生碰撞的几率，进一步降 低了机场容量和运行效率。 由于冻融效应，机位除冰方式会导致停机位道面的大面积损坏，导致巨 额损失，这种情况在北方机场尤为突出。 除冰液是乙二醇基的毒性液体，其直接排放会给周围生态带来不可逆转 的破坏，由此将引发环境问题。 综上，机位除冰会给造成更多的航班延误，并导致机场整体运作秩序的混乱， 也使航空公司、机场、空管的运行成本和安全风险提高。随着民航机队规模的扩 大，机位除冰方式已经无法保证冬季运行效率和安全需求，飞机集中除冰已经成 7 为国际上通用的作业方式。 飞机集中除冰是指每条跑道两端配有专门的除冰坪，所有需要除冰的飞机在 起飞之前，集中到除冰坪进行除冰。 与机位除冰方式相比，集中除冰作业方式具有下述优势： 保证飞行安全。集中除冰实现了飞机除冰过程的统一指挥和协调，可以 杜绝二次除冰问题，从根本上消除了飞机的飞行安全隐患； 提高除冰作业效率，减少延误。集中除冰方式可实现除冰液的就地供给， 减少除冰车往返所消耗的辅助时间，从而提高除冰作业效率，减少延误； 提高除冰车除冰作业能力。集中除冰作业在一定温度下进行除冰液的配 比作业，并配备自动搅拌系统，可保证除冰液的充分混合，提高除冰液 的除冰效果； 缩短除冰车除冰准备时间。集中除冰系统可以减少除冰液预热时间和燃 油加注频率，从而可大幅缩短除冰车作业准备时间； 减少除冰过程的刮蹭事故。集中除冰作业方式避免了除冰车在狭小的机 位空间与飞机发生碰撞的几率； 减少机坪道面破坏。集中除冰实现了除冰液的快速集中回收，避免了因 冻融效应导致的机坪大面积损坏； 保护环境和生态。除冰液的集中回收处理最大程度减少除冰液对机场周 围环境和生态的破坏。 飞机集中除冰是国际民航机场航空器除冰的发展趋势，对保证飞机的飞行安 全、提高除冰作业效率以及减少环境污染方面具有重要作用。 2 1 2 集中除冰方式的除冰坪设计 首都国际机场率先采用集中除冰方式，已稳定运行三年，并且已开始在全国 推广。 除冰坪是集中除冰方式的重要资源。集中除冰方式的除冰坪典型布局如下： 除冰坪设计为可以同时为一架d 类和一架c 类飞机进行集中除冰作业的空间， 如图2 2 所示，飞机翼尖之间距离为1 6 米，翼尖之间的区域作为除冰车作业区， 整个集中除冰坪的占地面积为1 3 4 8 0m 2 。可以看出，在进行除冰调度时，不同 类型的飞机需要分配不同类型的除冰坪机位。 (y i 按照正常程序完成各项保障作业，飞机关闭舱门后申请推出开车； 按照塔台指令滑出至除冰等待点等待； 按照引导车、入位引导员及机务人员信号操纵飞机进入除冰位进行除冰 工作； 得到机务许可后，联系塔台并按照塔台指令离开除冰位前往起飞跑道。 ( 2 ) 塔台： 指挥飞机前往除冰等待点； 飞机到达除冰等待点后，指挥机组跟随引导车及入位引导员信号进入除 冰位； 接到机组飞机除冰完毕报告后，指挥机组滑出； 指挥飞机滑至起飞跑道起飞。 ( 3 ) 机务： 飞机进入除冰位后及时放置轮挡； 通过耳麦与机组对话，确认机组刹车并关闭发动机和防撞灯； 向除冰人员给出“可以进行除冰 信号； 对飞机除冰作业进行现场监控； 除冰完毕后指示除冰车辆人员回到安全区域； 进行除冰检查并向机组通报除冰液使用情况； 指示机组丌车并联系塔台。 9 ( 4 ) 引导车： 按照现场指挥指令引导除冰等待点的飞机进入指定的除冰位； 向塔台通报要求控制等待除冰的排队飞机数量。 ( 5 ) 现场指挥 安排引导车引导飞机进入指定除冰位： 总体监控除冰现场秩序： 指挥调度现场除冰设备及人员； 与塔台保持联系，以及突发情况的通报； 除冰工作现场记录。 ( 6 ) 除冰车 按机务人员给出的“可以进行除冰信号开始除冰作业； 除冰完毕后退至安全区域。 除冰作业过程流程图如图2 3 所示。 l o 驰姆爿世若笾导涨nn匝 从图2 3 的流程可以看出，根据塔台的指令，需要除冰的飞机从机位出发， 到达除冰等待区，在除冰等待区等待，当除冰坪有空闲的机位时，再进入除冰 坪除冰。除冰工作完成之后，进入滑行道等待起飞。 2 2 机场除冰服务资源优化配置问题 2 2 1 问题的相关概念 本文研究机场除冰服务资源优化配置问题，主要是研究机场除冰服务资源 调度问题，根据调度计划对关键资源进行合理配置。机场除冰服务资源优化配 置问题的关键资源之一是除冰坪，除冰坪上有不同类型的停机位。首先，明确 停机位、航班和除冰坪机位分配等基本概念。 1 停机位( a i r c r a f ts t a n d ) 停机位是指民航机场站坪上用来停放特定型号飞机的特定位置和区域。停 机位简称机位或者泊位。 在除冰流程中，飞机从停靠的机位出发，到达除冰坪，会被分配一个特定 的机位。本文主要研究如何分配除冰坪的机位，以实现优化目标。除冰坪机位 与普通的停机位一样，具有以下几个主要的属性： ( 1 ) 规范标识：一般来说，停机位的方位、区域都是按照一定的规则确定 的，而且每个停机位都有一个唯一的编号用于标识该停机位； ( 2 ) 允许机型：不同的停机位，允许停放的机型是不同的。停机位的允许 机型用该停机位可以停放的最大机型表示； ( 3 ) 可用状态：可用状态表示停机位在某个时段能否使用的状态。这个属 性与时间紧密相关。 此外，停机位还具有以下重要的特性： ( 1 ) 瞬时独占性：一个停机位在任何时刻最多只能被一架飞机所独占。停 机位的这个属性说明，飞机对停机位的占用具有排它性； ( 2 ) 分时共享性：一个停机位可以在不相重叠的不同时段内被多架飞机分 别占用。停机位的这种特性称为停机位的分时共享性； ( 3 ) 可叠加性：两个相邻而且只能停放较小型号飞机的停机位，可以拼接 起来，形成一个可以停放较大型号飞机的另一个停机位。停机位的这种特性称 为停机位的可叠加性。 2 航班( f l i g h t ) 航班是指按照预先制定的计划，在特定时间执行特定航空运输任务的飞机 1 2 及航线的总和。 根据航班的定义，结合民航运输业航班管理和运营的特点，这里的航班具 有以下属性： ( 1 ) 航班号：航班号是指该航班的唯一标识代码；同时，航班号也标识着 这个航班属于哪家航空公司； ( 2 ) 飞机：执行一个航班的飞机标识和机型构成该航班的飞机属性。这里 的机型经常根据飞机的外形尺寸进行分类；机型的大小影响分配的除冰坪机位 的类型； ( 3 ) 起降时间：起降时间是指执行该航班的飞机在航线上各个机场起飞和 降落的时间序列。 此外，航班还具有如下特性： ( 1 ) 计划性：航班在执行前，其各个属性一般都是确定的，并且形成计划， 通报到各相关机构。航班的这种特性称为航班的计划性； ( 2 ) 时序性：航班属性中的起降时间，具有严格的时序要求，比如对于经 停机场来说，其降落时间必须小于起飞时间。此外，在航班计划中，航班经常 按照进港出港时间的升序排列。航班的这种特性称为航班的时序性； ( 3 ) 专一性：在正常情况下，一个航班只能而且必须占用一个停机位。航 班的这种特性称为航班的停机位专一性； ( 4 ) 随机性：航班虽然具有计划性，但是由于众多不可预测和不可控制因 素的影响，航班的实际执行情况经常会发生随机变化，比如由于天气原因引起 的航班取消、由于迫降原因引起的航班增加等。航班的这种特性称为航班的随 机性。 还有两个与航班紧密相关的概念：航班计划和航班动态。航班计划是在每 个工作同开始以前，由航空运输管理机构下达到机场的一个航班保障计划，这 个保障计划实质上是一个当同预计要执行的航班的集合；航班动态是机场在运 营过程中，根据其实际运作中的各种随机因素，对航班计划进行调整、修改和 充实相关信息后形成的动态航班计划。因而，航班动态是己经执行的航班、正 在执行的航班以及未执行的航班的集合。简单地说，航班动态是正在执行的航 班计划。 3 除冰坪机位分配 根据航班计划和资源占用状态，综合考虑飞机地面保障、旅客服务和航空 公司利益等因素，按照一定的规则和要求，为执行某个航班的飞机分配一个适 当的除冰坪机位的决策过程称为一次除冰坪机位分配。 1 3 在本文对机场除冰服务资源优化配置问题的研究中，关键是研究除冰服务 资源调度的方案，而关键资源即是除冰坪的机位，需要将除冰坪的机位合理的 分配给航班，以实现优化目标。 停机位分配一般具有以下特性： ( 1 ) 多目标性：停机位分配的基本任务是为执行特定航班的飞机分配适当 的停机位，但其目标经常呈现多样性。在不同情况下对这些目标强调的侧重点 不同，并且这些目标有时还存在冲突，因而在决策中经常要对不同目标要求进 行统筹考虑； ( 2 ) 多约束性：停机位分配过程的决策约束条件主要包括保障资源方面的 约束，飞机和航空公司方面的约束，天气等随机因素构成的约束等，并且这些 约束条件经常相互影响，呈现复杂的非线性关系； ( 3 ) 多态性：一次停机位分配，经常具有多个可选择的决策。一个时段内 的连续多次的停机位分配，经常可以形成多个可行策略。 2 2 2 问题的描述 本文研究机场除冰服务资源优化配置问题，主要是研究除冰服务资源调度 模型，并求解出模型的最优解，进而对资源进行合理的配置。涉及的资源包括 除冰等待区和除冰坪机位、除冰车、除冰人员、除冰相关设备、跑道等。除冰 调度的目的就是要合理分配上述资源，以实现优化目标。 建立除冰调度模型就是对实际过程进行抽象描述，为了使得模型既能刻画 所研究问题的本质，又便于讨论和处理，同时也为了进一步明确求解问题的条 件，本文通过引进假设条件的方式，对实际过程进行必要的简化、规范和抽象。 ( 1 ) 有限时段假设 在冰雪天气条件下，除冰调度对除冰等待区和除冰坪的机位进行分配具有 延续性，不存在明确的初始状态和终止状态。从这个意义上讲，停机位分配问 题属于无限离散系统问题。在实际调度过程中，前一个状态对后一个状态具有 传递性影响，从理论上讲不可能求出全局最优解，因而也就失去了研究这个问 题的现实意义。但在确定的考察时段内，除冰调度所涉及的状态是有限的，并 且存在最优解。为此，这里引进有限时段假设： ( 2 ) 容量满足假设 假设机场需要进行除冰服务的航班量和航班时间分布保持在除冰设旌容量 许可的范围内，也就是说机场所具有的各种除冰设施设备资源足够为当日航班 提供保障服务。 ( 3 ) 信息完备性假设 1 4 在冰雪天气条件下，假设在每个工作日开始以前，包括航班计划、机场资 源相关信息等当日除冰服务资源调度所必须的基本信息是完备的、确定的和已 知的。 在上述假设的基础上，除冰服务资源调度的关键约束只考虑除冰等待区和 除冰坪的机位。除冰等待区是飞机等待进行除冰服务的缓冲地带，通常即为滑 行道，一般并不存在机位约束的问题。除冰坪的机位有大小的区分，不同的机 型需要分配不同的机位。因此，本文的除冰服务资源调度计划主要对除冰坪机 位这个关键约束进行合理配置。 2 3 机场除冰服务资源调度问题的建模 2 3 1 问题的约束条件 除冰服务资源调度模型必须满足的约束包括： ( 1 ) 航班停靠在除冰坪时，必须被分配且仅能被分配到一个停机位； ( 2 ) 同一时间段，同一个停机位最多能停靠一个航班； ( 3 ) 机型与除冰坪机位相互匹配约束。即大型航班只能停靠大型停机位， 不能停靠到中型或小型停机位；中型航班可以停靠中型和大型机位；小型航班 可以停靠所有的机位； ( 4 ) 航班停靠时间段小于除冰坪机位的空闲时间段约束。即航班进入除冰 坪的时间大于该机位的空闲开始时间，航班离开除冰坪的时间小于该机位的空 闲结束时间。 2 3 2 问题的优化目标 机场除冰服务资源配置涉及到航空公司的经济利益、机场资源的利用和工 作人员等因素。机场内运行的飞机隶属于多家航空公司，每个飞机个体代表着 本公司的利益，在冰雪天气条件下，单体飞机均以减少延误，减少公司运行损 失为目的。从不同的角度考虑可以得到不同的优化模型。就优化的目标而言， 可以从以下几方面考虑： ( 1 ) 从减少航班延误的角度考虑：可以从两个角度来优化，一是以所有航 班总延误时间最短为优化目标，二是以所有航班的延误时间较均衡为优化目标， 也有将这两种优化目标相结合同时考虑的，结合后的优化模型比前面两种独立 的优化模型，结果都更优但耗时更长； ( 2 ) 从方便旅客的角度考虑：以旅客等待时间最短为优化目标； 1 5 ( 3 ) 从航空公司的角度考虑：以航空公司的经济利益最大为优化目标，这 需要对不同的航空公司设置不同的优先级别。 ( 4 ) 从地面服务公司的角度考虑，以设备利用率最大为优化目标。 本文从减少航班延误的角度考虑，以所有航班总延误时间最短和延误时间 较均衡为优化目标，从而提高旅客的服务质量，增加旅客的满意度，更好的响 应机场“以人为本”的经营服务理念。 2 3 3 问题的模型 塔台按照调度计划指示飞机在除冰等待区等待及进入除冰坪除冰，主要延 误时间为排队等待时间和除冰时间。飞机进行除冰所延误的时间与飞机除冰的 先后次序有关。为某个飞机分配好除冰坪后，单个飞机的延误时间为除冰完成 时间与预计离港时间之差。 假设在时间段丁内有，l 架需要除冰服务的航班，要把这些飞机分配m 个除 冰坪的机位上进行除冰，并确定各除冰坪机位的飞机除冰顺序和除冰完成时间 t c i 。飞机的预计离港时间t d i 已知，则t c i 与t d f 之差即为航班f 的延误时间。 首先对输入数据进行定义和说明，根据信息完备性假设，这些数据都是确 定和已知的。 ：为时间段r 内需要进行除冰的航班的集合，并且为非空集合，即l | o 。 一( fif - 1 ，2 ，3 ，1 1 ) ；变量i 代表航班。 厶：为航班f 的机型大小。 t d f ：表示航班f 的预计离港时间。 劬：航班i 的除冰时间，不同型号飞机的除冰时间不一样。 m ：为除冰坪停机位的集合，并且m 为非空集合，即i m o 。胙( 七ik = - i ， 2 ，3 ，脚) ；变量k 代表除冰坪机位。除冰坪有不同大小的机位，以适应不同 大小的飞机。 级：为除冰坪停机位k 的大小。 模型的形式化描述如下： 假设变量t c i ，表示航班f 的除冰完成时间。需要根据航班所分配的除冰坪 机位及航班除冰的顺序来计算t c i 。 优化目标为： ( 1 ) 所有需要进行除冰服务的航班总延误时间最短 f t = m i n ( t cf 一叻，) 1 6 ( 2 ) 所有需要进行除冰服务的航班的延误时间较均衡 f 2 = m i n ( t d i 一生) 2 约束条件为： 旭 刀 ( 1 ) 引入0 1 变量y 腩，当且仅当航班i 分配到除冰坪的k 机位时为1 ，否 则为o ；即 y 萨 o ，1 ，v i n , 、k m ( 2 ) 由于除冰坪机位具有瞬时独占性，需要除冰的航班必须且只能分配一 个除冰坪机位约束，即 yy 】 k = l ，v i e n ( 3 ) 同一时间段，同一个停机位最多能停靠一个航班约束，引入变量翻f 表示航班i 到达除冰坪的时间，t a f = t c r0 i 。对于航班i 和航班，v ( i ，) 玩= 取= j 当且仅当( t a i r c j ) ( 巩一t g ) q k ，则将航班f 分配给另一除冰坪机位，直至满足此约 束条件。若第一个航班i 分配到除冰坪机位k ，贝j j t c i = 仍f + 侥，并记录除冰坪机位 七的空闲开始时间t v k ，孤= t c i 。将航班i 放入集合风中，b k j j h l ； ( 3 ) 对于后面的航班，与第一个航班类似，在该航班可以停靠的除冰坪机 位的集合中( 满足o k l f ) ，选择飞机最少即巩最小( 可以维持除冰坪之间的平 衡) 的除冰坪机位k ，将航班i 放入集合凰。 a 如果b k = 0 ，n t g = 册f + 拜，t v k = t c i ，b k 加l ； b 如果b k 0 ，需要考虑如果矾t d i 0 ，则= 矾+ a ；否则，即矾t d i 0 ，n r g = t d z + a 。更新t v , 和b k ，t v k = t c i ，b k 加l 。 ( 4 ) 所有染色体中所有基因位计算完毕后，得到每个航班的除冰次序、除 冰坪机位和除冰完成时间t c i ，并以此计算适应度函数的值。 3 5 2 适应度函数评价 在遗传算法中使用适应度( f i t n e s s ) 这个概念来度量群体中各个个体在优 化计算中能达到或者接近于或者有助于找到最优解的优良程度。适应度高的个 体遗传到下一代的概率比较大；而适应度较低的个体遗传到下一代的概率就相 对小一些。度量个体适应度的函数称为适应度函数( f i t n e s sf u n c t i o n ) 。 适应度函数也称为评价函数，是根据目标函数确定的用于区分群体中个体 好坏的标准，是算法演化过程的驱动力，也是进行自然选择的唯一依据。适应 度函数总是非负的，任何情况下都希望其值越大越好。而目标函数可能有正有 负，即有时求最大值，有时求最小值，因此需要在目标函数与适应度函数之间 进行变换。为了变更选择压力，也需要对适应度函数进行变换。 评