（航空宇航制造工程专业论文）民航机场停机位分配与优化技术研究.pdf

西北工业大学博士学位论文 民航机场停机位分配与优化技术研究 摘要 民航机场是航空运输链中旅客、货物和邮件的起始点、转接点和终结点， 也是一个国家和地区最重要的基础设施之一。机场关注的焦点一直是航空安全、 优质服务和经营效益三个方面，面临的主要压力是设施容量不足，保障能力难以 适应航空运输业的快速发展。因此，如何在保证地面飞行安全的前提下，通过生 产资源的合理调度与优化配置，提高服务水平，提高设施资源利用率，从而提高 经营效益，已经成为机场运营迫切需要深入研究和尽快解决的关键问题。 本文利用系统优化和系统仿真，以及人工智能的理论与方法，对机场生产 调度的核心环节停机位分配( r c r a f ls i a n 凼加s i g n m e n t ，简称a s a ) 及其 优化技术进行了研究，以期为机场生产调度提供理论和方法支持。 本文的主要研究工作及创新点如下： 1 深入考察了民航机场生产调度过程，论述了a s a 方法及其优化技术研究 的重大意义，分析了国内外a s a 问题的研究现状和存在的问题，探讨了a s a 问 题的研究策略； 2 分析了实际a s a 过程的约束条件和目标要求，引进建模假设和简化条 件，将a s a 过程中的基本约束形式化地表述为一组约束函数，以旅客在机场移 动距离最短和机场设施设备利用率最高作为目标函数，建立了a s a 问题的多目 标二次整数规划模型，为a s a 优化算法研究奠定了基础； 3 根据禁忌搜索算法的基本理论和方法，提出了a s a 优化求解算法，并对 该算法的能行性进行了分析。在算法设计中，引进了解集元素之间距离的概念， 提出了“蜘蛛型”和“蝌蚪型”侯选解集结构以及相应的邻域搜索方法，较好地 实现了集中搜索和分散搜索策略； 4 采用基于随机事件模型的系统仿真技术，建立了a s a 仿真与优化实验平 台，对a s a 实际过程进行计算机仿真，在此基础上进行计算实验，对a s a 优化 模型和算法进行验证研究，证明了本文提出的a s a 优化模型和算法的可行性与 有效性； 5 利用基于规则的推理机制处理附加约束，以弥补模型和算法对描述和处 一i 一 摘要 。 理复杂约束的能力的不足，进而探讨了a s a 知识库和推理机的实现技术： 6 分析了实际a s a 过程中的突发事件及其影响，提出了a s a 应急管理的 策略与目标，以及动态约束的处理机制，探讨了a s a 优化调度的鲁棒性和受扰 恢复技术，提出了将a s a 静态优化提升为动态优化的技术途径。 关键词：机场生产调度，停机位分配，优化模型，多目标规划，禁忌搜索算法 西北工业大学博士学位论文 r e s e a r c ho na i r c r a f ts t a n d sa s s i g n m e ma n do p t i m i z a t i o n i nc i v i la i 叩o r t ( p h d d i s s e f t 砒i o n ) n o n h w e s t e r np o l y t e c h n i c a lu i l i v e f s i t y ，x i 卸，pr c h i n a a b s t r a c t c i v i la 呻o r t sa r en o to 山yt h es o u r c e ，c x c i l a i l g ea i l dt a r g 毗n o d e so fa j r t r a n s p o r t a t i o nn e t w o r k s ，b u ta l s ot h ei m p o r t a n ti n 疗a s t m c t u r e so fj l a t i o n sa n da r e a s e v e nu n d e rt h eh e a v yp r e s s u r eo ft h e i rs m a l lc a p a d t i e sa n dp o o re q u i p m e n t sw h i c h c a n i a r d l ye n s u r et h er a p i dg f o 叭ho fc i v i l 州a t i o n ，a i r p o r t sa o v e rt h ew o r l dh a v et o f o c u so nt h es t e a d ya v i a t i o ns a f 毛g u a r d ，b e t t e r 辩r v i c ea n dr e a s o n a b l eo p e r a t i 彻b e n e m t h ei s s u eo fh o wa i la j r p o r tc a j li m p r o v ei t ss e r v i c e sa 1 1 dg c tm o r ci 玎c o m e sb ym e a n s o fo p t i m i z i n gt h er e s o u r c es c h e d u l i n gm u s tb ed e e p l yi n v e s t i g a t e da f l d u 唱e n t l y r e s o i v e d t op r o v i d et h ea i r p o r to p e r a t i o ns c h e d u l i n g 、析t ht h e o d ，a n dm e t h o ds u p p o n s ， t h em a l no p e r a t i o nw o r k n o w so fa na i r p o nh a sb e e nf 嘶e w e di nt h i sd i s s e r t a t i o n ，a n d t h ek e yp r o c e s so f t h eo p e r a t i o ns c h e d u l i n g ，t h a ti s ，r c r 蚯s t a n d sa 5 s i g 舯e n t ( a s a ) 锄do p t i m i z a t i o nt e c h n o l o g y ，h a sb e e ns t u d i e d b a s e do ns y s t e m0 p t i m i z a t i o n ，s y s t e m s i m u l a t i o na n da n i f i c i a li n t e l l j g e n c e t h em a nc o n t e n t sa n dc o n t r i b u t i o n so f t h ed i s s e r t a t i o na r ea sf o l l o w s ： 1 a r e rr e v i e 谢n go nt h el i t e r a t u r e so fa i r p o r to p e f a t i o ns c h e d u l i n t h ec u r r e n t s j t u a t i o n sa n ds o m el i m i t a t i o n so ft h ep r e v i o u s r e s e a r c h i n g r e s u l t so na s a o p t i i n i z a t i o nh a v eb e e na n a l y z e d ，a n dt h u sm em a i nr e s e a r c ht o p i c so ft h ed i s s e r t a t i o n h a v eb e e ni n t r o d u c e d 2 b ye x a m i 西n gt h ec o n s t r a i n sa n do b j e c t i v e so fa i la c t u a la s ap r o c e s s ，a 1 1 a s a o p t i m i z a t i o nm o d e lw i t hs i m p l i f i e dh ) r p o t h e s e si sg i v e nt h em o d e ii sb a s e do n m u l t i o b j e c tq u a d r i ci n t e g e rp f o g r a r n n l j n gw j t ht h e 盯i i n i m i z a t l o no ft o t a lw a 】“n g d i s t a n c e so fa l lp a s s e n g e r si nt h ea i r p o r ta st h ef i r s to b j e c t i v e ，a n dt h em a x i m i z a t i o no f t h ea 主p o f ti n c o m ef o me q u i p m e n tu s a g ea st h es e c o n do n e 3 a c c o r d j n gt ot h eb a s i ct h e o r ya n dm e t h o do ft u b as e a r c ha na s a o p t i m i z a t i o na l g o r i t h mh a sb e e np r o p o s e d ，f o rw h i c ha n e wc o n c e p to ft h ed i s t a n c e b 前w e e nt w or e s o l u t i sh a sb e e nb t r o d u c e d ，a sw e l la st h e “s p i d e r a n d “t a d p o l e ， a b s t r a c t c a n d i d a t es o l u t i o ns e ts t n j c t u r e sw i t h r e l a t i n g s e a r c hm e t h o d sh “ea i s ob e e n p r e s e n t e dw h i c hc a j le 塌c i e n t l ye x e c u t eb o t hi m e n s i f i c a t i o ns e a r c ha n dd i v 盯s 墒c a t i o n s e a r c h 4 t oe s t a b l i s hap i a t f b 肿o fa s as i m u i a t i o na 1 1 do p t j m i z a t i o n ，as v s t e m s i m u l a t i o nb a s e do nr a n d o me v e n tm o d e i1 1 a sb e e ni n t f o d u c e dt h ec o m p u t j n g e x p e r i m e n t a t i o n sh a v eb e e nc a r e do u to nt h ep j a t f o n nw h i c hs h o w st h ef e a s i b i l i t v a n de 衢c i e n c ) ，o f t h ea s a o p t i m i z a t i o nm o d e la n da l g o r i t h mp r o p o s e da b o v e 5 ad e d u c i n gm e c h a n i c sb a s e do nr u i e r sh a sb e e ns e tu pa sa na i d e dm e t h o dt o m a n a g et h ea d d i t i o n a lc o n s t f a i n s f u r t h e rm o r e ，t h ei m p l e m e n t a t i o nt e c h n 0 1 0 9 yo f a s ak n o w l e d g em a n a g e m e n ta 1 1 dd e d u c i n gm a c h i n eh a sa l s ob e e nd j s c u s s e d 6t h es c m f e 舀e sa f i do b j e c t i v e so fa s ad i s r u p tm a l l a g e m e n ti l a v eb e e n p m p o s e d 谢t ht h ee m e r g e n c i e sa n dt h e i ri n n u e n c e st ot h ea c t u a ia s ap r o c e s st ob e a j l a l y z e d ， f o rw 1 1 i c ht h ea s ar 0 b u s ts c h e d u l i n ga n dr e c o v e r ys t m t e g yh a sb e e n d i s c u s s e da sw e l lf i n a l i y ，t h et e c h l l i c a lr o u t e sf o ru p g r a d i n gt h es t a t i co p t i m i z a t i o no f a s at od y n a m i c0 p t i m i z a i i o na r ea l s op r e s e n t e d k e y w o r d s ： a i f p o no p e r a t i o ns c h e d u l i n g ，r c r a f ls t a n d sa s s i g 栅e n t ，o p t i f i l i z a t i o nm o d e l ， m u l t i o b j e c t i v ep r o g r 砌蕊n g ，t a b us e a r c ha l g o r i t h m 一 西北工业大学 学位论文知识产权声明书 本入完全了解学校有关保护知识产权的规定，即：研究生在校攻读 学位期间论文工作的知识产权单位属于西北工业大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被查 阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 同时本人保证，毕业后结合学位论文研究课题再撰写的文章一德注明作 者单位为西北工业大学。 保密论文待解密后适用本声明。 学位论文作者签名： 五护驴6 年4 月功日 西北工业大学 学位论文原创性声明 秉承学校严谨的学风和优良的科学道德，本人郑重声明：所呈交的 学位论文，是本人在导师的指导下进行研究工作所取得的成果。尽我所 知，除文中已经注明引用的内容和致谢的地方外，本论文不包含任何其 他个人或集体已经公开发表或撰写过的研究成果，不包含率人或他人已 申请学位或其它用途使用过的成果。对本文的研究做出重要贡献的个人 和集体，均已在文中_ | 2 王明确方式标明。 本人学位论文与资料若有不实，愿意承担一切相关的法律责任。 学位论文作者签名： 2 d 此年4 月2 口目 西北工业大学博士学位论文 第一章绪论 民航机场是航空运输链中旅客、货物和邮件的起始点、转接点和终结点， 也是一个国家和地区最重要的基础设施之一。机场业是一个资本密集、运营风险 高的行业。从全世界范围来看，各个机场关注的焦点一直是航空安全、优质服务 和经营效益三个方面，面临的主要压力是容量不足，保障能力难以适应肮空运输 业的快速发展【1 l ，并且基础设施建设投资巨大，其改扩建或新建工程动辄需要投 资数十亿元到数百亿元【2 j 。大量的基本建设投入，经常使机场承担巨额债务而陷 入经营困境。因此，如何在保证地面飞行安全的前提下通过生产资源的合理调 度与优化配置，提高服务水平，提高资源利用率，从而提高经营效益，已经成为 民航机场运营迫切需要深入研究和尽快解决的关键问题。为此，本文深入考察了 机场运营的主要流程，利用系统优化和系统仿真，以及人工智能的理论与方法， 对机场生产调度的核心环节机位分配方法及其优化技术展开了研究。 1 1 机场运营与停机位分配 民航机场的主要功能是利用自身所具有的各种资源，为航空公司提供飞行 地面保障服务，为旅客、货物和邮件提供航空运输必须的各种地面服务。机场收 入的主要来源是旅客过港费和资源使用费，合理地调度和利用自身的各种保障和 服务资源是机场运营的核心。这些资源包括人力资源( 各种保障人员和服务人 员) 、保障设施( 跑道、机坪等) 以及各种各样的保障设备( 廊桥、客梯车等) 。 站坪是机场空侧毗邻航站楼的区域，由若干个停机位及其间通道组成，是停泊飞 机、实现旅客和货物在机场转接的场所，也是机场进行各种地面保障活动的主要 场所。站坪控制是合理调配机场站坪设施和设备，为飞机和旅客提供保障服务的 过程，是机场安全生产的关键环节。由于这些资源的调度都以停机位分配为依据， 因而停机位分配是站坪控制的核心。 所谓停机位分配( a i r c r a f 【s t a n d sa s s i g n m e n t ，简称a s a ) ，就是在满足一 定的约束条件和目标要求的前提下，为执行每个航班的飞机分配适当的停机位的 过程。 在机场实际运营中，生产调度人员在每个工作日开始，根据当时日航班计 划和机场设施状况统筹安排，制定飞机停机位分配计划，据此安排飞机进出港地 第章绪论 面滑行路线，组织各项地面保障活动，确保不同航班在空间和时间上不发生冲突， 并且达到地面飞行安全所要求的空间距离和时间间隔。在停机位分配计划的执行 过程中，生产调度人员还要根据一些突发事件，如航班延误、航班取消等，随时 采取适当的应急处理措施，动态调整停机位分配计划，保持机场运营正常进行。 在此过程中，生产调度人员必须综合考虑站坪、场道、廊桥等机场保障设施的制 约，考虑飞机加油、机务检修等生产环节有序衔接。流程顺畅，还要考虑旅客中 转、要客迎送仪式等服务过程的要求。一般来说飞机对机位的占用必须满足一 系列复杂的约束条件。在整个站坪控制过程中，前一个状态将对后续各个状态产 生传递性影响。由上述可见，机场停机位分配过程非常复杂，是一个动态的多目 标、多约束的决策过程，从系统论的观点考察，这个过程可以看作是一个复杂的 离散动态系统口】。 目前，各大中型机场的机位分配基本上还是生产调度人员根据个人经验， 以手工方式或者简单的计算机辅助方式进行，难以保证生产现场流程顺畅，更不 能充分利用机场已有资源。在规模较大、而且日益繁忙的干线机场和中枢机场， 这种方式已经成为机场运营的薄弱环节，不能适应民航业整体发展的要求。比如 文献时国内某国际机场2 0 0 2 年航班延误因素统计结果表明，机场调度所引起 的航班延误占所有航班延误的1 5 4 5 ，占由于机场原因引起的航班延误的7 0 以上。这组统计数据仅揭示了机场调度对本机场航班正常率的影响。由于机场是 民航运输网络上的节点，如果考虑一个机场的航班延误对相关航空公司的飞机调 度，以及其它机场生产调度的连锁式传递性影响，则可以断言，机场调度对民航 运输业的正常运行发挥着难以估量的巨大作用。因此，机场甚至整个民航运输业， 都迫切需要借助计算机仿真技术，利用系统优化和人工智能的理论与方法，为机 场机位分配过程规划和优化提供先进的方法和手段。 现代化机场管理，实际上是不断采用先进的技术手段，提高机场安全保障 能力，改善服务质量，最终提升机场效益的过程p 】。机位分配过程的合理规划和 优化，对保证飞行安全和航班正点，提高服务质量，尤其对充分发挥已有保障设 施的效用，减少或延缓机场建设投入，从而提高机场经营效益具有重要作用。 1 2a s a 的研究现状 a s a 的规划和优化是机场运营的关键和薄弱环节，对机场运营，甚至对整 个民航运输业都有及其重大的影响。从文献检索情况来看，国外在二十多年前就 西北工业大学博士学位论文 开始了这方面的研究，已经取得了一定的理论成果。国内在这方面的研究起步较 晚，也不够深入。 机场的停机位和登机门经常具有一定的关联关系，因而a s a 问题在国外的 相关研究中经常被称作登机门分配问题( a i r c r a f tg 诬t ea s s i g n j n e n tp r o b l e m ，简称 a g a p ) 。国内外这些不同的a s a 问题研究的侧重点不同，因而采用的模型和 算法的也就各不相同，可以将这些研究大致分为以下四个方面。 1 2 1a s a 优化技术研究 a s a 优化技术研究，就是根据实际a s a 过程的约束条件和目标要求，建立 优化模型和优化算法，求解a s a 问题的最优解。 这类研究具有代表性的有b r a a k s m 在1 9 7 7 年1 6 】，b a b i ce ta 1 在1 9 8 4 年州， m a n g o u b i 和m a t h a i s e l 在1 9 8 5 年【s l ，v 卸d e r s t r a e t a i l 和b e r g e r o n 在1 9 8 8 年b i h r 在1 9 9 0 年1 1 们，z h a n g 在1 9 9 4 年川，c h e n g 在1 9 9 7 年f 1 2 】，h a g l a l l i 和c h e n 在1 9 9 8 年叫，以及b o l t a 在1 9 9 9 年“l 2 0 0 0 年期间，提出的基于整数规划( 线性整 数规划或者二次整数规划、o 1 整数规划或者混合整数规划) 分析模型。这些模 型的目标函数选择为全部旅客走过的路程、登机门关闭的次数、登机门使用时间 和空闲时间的最小化，或者上述几种目标的组合。这些模型或者使用精确解法， 或者使用启发式( h e u s t i c s ) 算法，比如单纯形法( s i m p i e xm e d t o d ) 、分枝界 定法( b r a n c ha 1 1 db a n d ) 、拉格朗日松弛算法( l a g f 锄百a nr d a x a t i o n - b a s em e t h o d ) 以及其它启发式搜索算法。在同类研究中，相对而言模型较为完备、研究较为深 入还要算j i e f e n g x u 和hd i n g 等人。j j e f b n g x u 和g l e n n b a i l e y 在2 0 0 1 年【1 6 l ， 把a g a p 问题构造成为一个混合o 一1 二次整数规划问题，然后将其转换为具有线 性目标函数和约束条件的o 1 整数规划问题，设计了一种简单的启发式禁忌搜索 算法来进行问题求解，最后，还进行了计算实验，提供了计算结果，并对这些结 果进行了分析。hd i n g ，al i m 和br o d r i g u e s 等分别在2 0 0 4 年1 刀和2 0 0 5 年 先用贪婪算法( g r e e 曲g o f i t h m ) 使得未分配机位的航班数量达到最少，然后 使用启发式优化算法，使得旅客行走路程最短。田晨和熊桂喜在2 0 0 5 年1 19 】通过 对大型机场机位分配所受约束和最终目标的分析研究，将其模型化，提出使用遗 传算法来解决机场a s a 问题。华克强，蔡毓峰等在2 0 0 5 年1 2 0 j 用极大代数理论研 究了航班调度优化问冠。文军和孙宏等在2 0 0 4 年【2j l 通过分析航班占用停机位的 特性，建立a s a 问题的排序模型，然后考虑“先到先服务”的规则并通过引入机 第一章绪论 位标号函数和航班标号函数设计种求解模型的标号算法。文军和李冰等在 2 0 0 5 年【捌把停机位的分配转化为图着色，建立a s a 问题的图着色模型并引入 时间片算法确定航班使用机位的时间冲突集合，根据“先到先服务”的原则给出 了a s a 问题的顶点序列着色算法。 1 2 2a s a 仿真技术研究 a s a 仿真技术研究，就是通过建立和运行a s a 问题的仿真系统，来研究 a s a 问题的有关特性。 这类研究具有代表性的有y u c h e n g 在1 9 9 8 年认为，在日益繁忙的机场， 由于许多不确定性因素的影响，飞机在机场空侧经常会发生停放位置和运动轨迹 的冲突，对于这个问题，人工控制难以解决，必须采用仿真技术来解决这个问题。 为此，y uc h e n g 分析了飞机起飞和降落、进港和出港、登机门分配等活动及其 控制过程。在此基础上，提出了基于规则和网络技术的a g a p 仿真模型，来 解决飞机在停机位上的冲突控制问题。随后，又提出了基于网络技术的仿真模型， 模拟飞机的起飞和降落过程及其约束条件，以避免飞机在跑道上的冲突犯”。利 用网络技术进行a g a p 研究，具有代表性的还有y a n 和c b a n g 等人。y a n 和 c h a n g 在1 9 9 8 年俐，y 卸和h u o 在2 0 0 1 年2 6 1 利用网络技术建立起了a g a p 的 分析模型，并对利用这个模型处理航班延误等突发事件的实现策略进行了讨论。 陶冶、白存儒等在2 0 0 5 年f 2 7 】讨论了空中交通流量管理中终端区航班的排序规划 问题。何智、高超等在2 0 0 5 年【2 ”也进行了类似的研究。倪桂明、杨东援等人在 2 0 0 1 年】从机场设计和建设的观点出发，探讨了机场系统计算机仿真问题，并 在2 0 0 2 年训通过对航站楼客流特性进行分析，利用面向对象方法，建立了航站 楼客流仿真系统的对象模型、动态模型以及功能模型。“y u 和d u a nz h e n 曲u a 在2 0 0 2 年1 对机场工作流系统进行了分析，并提出了机场自动化控制系统的设 计原则。徐肖豪、杨攀等在2 0 0 1 年【”1 研究了机场站坪控制的三维模拟系统的实 项方法。 1 2 3a s a 人工智能技术研究 a s a 的人工智能研究，就是利用人工智能的技术，建立a s a 专家系统，以 实现a s a 过程的自动化。 这类研究具有代表性的有y uc h e n g 在1 9 9 8 年”1 为了解决飞机在停机位上 西北工业大学博士学位论文 的冲突控制问题，实现a g a p 过程的自动化，提出了基于规则的a g a p 仿真模 型。y uc h e n g 利用知识工程的原理，把a g a p 的约束条件抽象为规则，然后利 用面向对象设计和编码技术探讨了该模型的实现策略。s o i h o il 锄和j i a m e n g c a o 等在2 0 0 2 年州认为a g a p 是一种n p h a r d 问题( n o n d e t e r f n i n i s t i c p o l o m i a l t i m eh a r dp r o b l e m ) l ，为了便于仿真系统或者实用系统输入初始条 件，有必要利用知识工程的原理，开发前置智能处理机，将自然语言描述的各种 约束自动转化为形式化的规则，为后置优化求解做好准备。张学民、施法中在 2 0 0 0 年3 5 1 研究了机场机位分配专家系统的实现技术，并开发了一个简单的停机 位自动分配系统。周至、孟波在2 0 0 4 年口蜘引入知识库，并且用拆分规则的形式 化方法表示知识，研究停机位自动分配问题。 1 2 4a s a 相关领域研究 除上述三类a s a 研究外，还有其它a s a 相关领域的研究，对本文的研究 有较大的借鉴作用。 h hh e s s e l i n k 等在1 9 9 8 年【2 】为了更好地发挥机场基础设施的效用，减轻指 挥调度人员的工作负担，研究了跑道、滑行道等资源调配的约束条件和决策问题。 该项研究仅仅从简单的应用实际出发，一般性探讨了一些主要的约束条件和决策 依据。dep i t f i e l d 等在19 9 8 年【3 7 1 采用m o m e c 砌。仿真，对一个新建机场在高 峰小时( 在一个工作日内，飞机起降架次最多的一个小时) 产生冲突的数量和持 续时间进行了研究和评估。该项研究从统计学的观点出发，为机场容量设计和容 量评估提供了依据，未涉及机场站坪控制实际过程的规划和优化问题。d o u l o n g 等在1 9 9 9 年【3 8 1 专题研究了全美航空系统运输管理的建模技术。该项研究的重点 在于一个较大区域内机场分布和航线配置的建模技术，对机场站坪控制实际过程 的规划和优化研究具有一定的借鉴作用，尤其是在把一个机场群的站坪控制过程 作为一个由不同航线联结成的有机整体进行考察时，该项研究将具有较大的指导 意义。v i c t o rh l c h e n g 等在2 0 0 1 年【3 9 】，试图通过提高地面调度精确度来减少飞 机跑道占用和滑行道等待的间隔时间，解决大型机场由于指挥调度而引起的飞机 进出港效率低下问题，并采用非线性控制的方法，对地面指挥自动化系统进行了 初步研究。该项研究所采用的非线性控制方法，其决策和优化求解非常困难。王 占伟、王洋2 0 0 1 年1 4 0 1 为了解决多机场航班队列的拥塞问题，研究了多机场航班 队列的优化问题，建立了多机场开放式非实时流量管理的数学模型。马正平、崔 第一章绪论 德光在2 0 0 4 年j 针对空中交通日益严重的航班延误，给出了一种机场航班延误 优化模型并利用遗传算法对模型进行了验证。 1 3 a s a 研究存在的问题 。 综上所述，虽然国内外对a s a 己经进行了一定深度的研究，但目前仍然存 在着机场实际运营的强烈需要和理论与方法支持相对不足的矛盾，主要表现在以 下几个方面： 1 a s a 问题本身是一个多目标、多约束的决策过程，业务规程非常复杂。 以往研究对a s a 的约束条件和目标要求研究不够全面深入，还不能提供套完 备和可行的业务规则； 2 以往研究者根据所研究a s a 问题的侧重点的不同，提出了不同的a s a 模型，这些模型过于简约，只适用于a s a 问题某个侧面的研究，不能为进一步 全面深入地研究a s a 问题提供支持； 3 a s a 问题属于较大规模调度问题，具有n p - h a r d 特性。a s a 优化求解方 法的研究仍然不充分。在合理的时间内求出适当规模条件下的满意解的数学方法 还有待于进一步研究； 4 以往研究的工作重点在于a s a 问题的静态过程，即停机位分配计划的制 定和优化上面，而对a s a 问题的动态过程，即应对各种突发事件，进行及时调 整的实时过程研究不够，不能适应机场实际运营的要求； 5由于a s a 问题本身的复杂性及其实际过程的不可重复性，难以通过简单 数理分析，或者与实际系统对比的方法进行模型和算法验证评估。因而通过建立 仿真系统，来对a s a 模型和算法进行验证评估的问题也需要进一步研究。 1 4a s a 问题的研究策略 生产调度问题是各类生产组织活动的关键环节，也是生产管理研究的个 热点问题，其任务就是根据生产组织活动的目标，制定出可行的或者最优的资源 分配计划以及作业流程。 a s a 问题是一类复杂的生产调度问题，其它行业生产调度问题的研究思路 和方法对a s a 问题研究具有借鉴意义。 1 4 1 系统优化的方法 目前，研究一般生产调度问题，尤其是在对资源分配优化要求比较高的情 西北工业大学博士学位论文 况下，通常要以系统优化的理论与方法作为主要的技术手段，借助于电子计算机 仿真技术，借鉴知识工程以及工作流等理论与方法，建立系统模型，设计求解算 法，从而求出问题的最优解或者满意解。 根据系统优化的理论与方法，开展a s a 研究的技术途径大致分为以下几个 阶段【4 2 l ： l系统认识阶段考察实际生产过程，获得先验知识，找出生产调度的 关键问题，研究分析约束条件和目标要求，界定研究对象。 2 系统建模阶段根据研究对象的约束条件和目标要求，进行提炼和抽 象，引进必要的假设，进行必要的简化，形成形式化表述，建立研究对象的系统 模型1 2 ”。 3 模型求解阶段根据系统模型的特点，结合应用领域要求，对模型进 行分析和优化，设计出求解算法和验证方法。 4 模型检验阶段利用计算机仿真技术，对模型和算法进行编码实现， 建立原型系统，并通过运行原型系统进行算例试验和计算结果分析，对模型与实 际情况的符合性以及算法的可计算性与运行效率进行验证评估，形成研究结论。 在上述几个阶段中，系统建模和模型求解是整个研究过程的重点和难点。 1 4 2 建模和求解技术 由于客观事物的复杂性，为了便于研究事物的本质属性和内在联系，经常 需要对所研究的客观对象进行概括和抽象，也就是要建立客观对象的模型。简单 地说，模型就是对客观对象的抽象表示，它为人们研究客观事物提供了一个能够 反映客观对象本质属性和内在联系的抽象框架。模型通常都应该包括一个完整的 概念集合、一套相应的表示方法，以及必要的规则约束1 1 2 引。一般而言，不同形 态的模型经常和相应的求解方法密切相关。对于典型的数学模型，经常具有一整 套的数学求解方法与之相适应。因而，可以说，建立模型的主要目的，就是要利 用相应的数学方法对研究对象进行数学求解。 调度问题作为一类复杂的组合优化问题，具有多目标、多约束的特点，绝大 多数生产调度问题都属于n p 完全问题( n 0 n p o l ”o i n i a lc o m p l e t ep r o b l e m s ) ， 其求解过程的计算量随问题规模呈指数增长。从系统优化的观点来看，调度问题 又属于离散系统的优化问题，因而从理论上说，求解离散系统优化问题的各种算 法都可以用来求解生产调度问题。 第一章绪论 优化算法实质上是一种从有限或者无限个解构成的解空间中寻找出一个或 者多个满意解或者最优解的搜索过程，它一般基于某种思想和机制，通过一定的 途径或者规则来得到被求解问题的满意解或者最优解。 文献j 根据算法的优化机制，把目前常用的优化算法分为：经典算法、构 造算法、邻域搜索算法、系统动态演化算法和混合型算法等。 1 经典算法。这类算法包括线性规划、动态规划、整数规划和分枝界定等 运筹学中的传统算法。经典算法在求解离散系统优化问题时，计算复杂度一般都 很大，只适用于求解小规模问题。 2 构造算法。这类算法用构造的方法快速建立起问题的解，通常算法的优 化质量较差，难以满足应用需要。比如调度问题中的j o h n s o n 法4 习等。 3 邻域搜索算法。这类算法从任意一个解出发，对其邻域不断搜索，用搜 索到的优于当前解的邻域解替代当前解来获得最优解。根据搜索机制的不同，这 类算法又可以分为局部搜索算法和指导性搜索算法。 ( 1 ) 局部搜索算法。局部搜索算法按局部最优化策略在当前解的邻域中搜索 最优解。局部搜索算法一般只能求出局部最优解，不能保证求出全局最优解。比 如爬山法等。 ( 2 ) 指导性搜索算法。指导性搜索法利用一些指导原则来指导整个解空间中 最优解的搜索。指导性搜索算法是在局部搜索算法的基础上发展起来的全局性优 化算法，这类算法以人类、生物的行为方式或者物质运动形态为背景，经过数学 抽象建立算法模型，借助于计算机来求解离散系统优化问题。比如模拟物体退火 过程的模拟退火算法4 ”，模拟自然界生物遗传和变异现象的遗传算法m 4 9 - 驯、 模拟人类智能的禁忌搜索算法”5 2 - 1 6 1 。 4 系统动态演化算法。这类算法将优化过程转化为系统动态演化的过程， 通过系统的动态演化来实现系统优化。比如神经网络p 3 5 q 和混沌搜索算法等。 5 混合型算法。这类算法是指把上述各类算法从结构或者操作上相混合而 衍生出各种新的算法。 优化算法还可以根据算法的其它特性划分为不同的类别，如精确算法和近似 算法【 ，5 “、确定性算法和随机算法、局部优化算法和全局优化算法等。 1 4 3 系统仿真技术 系统仿真技术作为分析、综合各类系统的一种有力的工具和手段，已经被广 西北工业大学博士学位论文 泛地应用于几乎所有的科学技术领域 ”。 系统仿真的基本定义是：设计一个实际系统的模型，对它进行实验，以便理 解和评判系统的各种运行策略，其基础是建立在系统的数学模型上，并以计算机 为工具对系统进行试验研究的方法。系统仿真的基本原理是相似原理，用系统仿 真技术研究生产调度问题，必须要保证环境相似和性能相似。 利用系统仿真技术可以模拟实际a s a 过程1 5 毗，这样，一是可以为a s a 优 化研究产生必要的、而且比实际数据更具代表性的初始数据，便于研究工作的深 入展开；二是由于实际a s a 过程具有复杂性和不可重复性，因而经常难以通过 简单的数理分析，或者通过与实际过程进行比较来对模型和算法进行验证评估， 采用系统仿真技术进行模型和算法的验证评估就成为一种非常有效的研究手段。 此外，计算机仿真系统的构造技术还对原型系统或者实用系统的实现具有重要的 指导意义。 1 5 研究内容与章节安排 1 5 1 主要研究内容 本文进行a s a 问题研究的目的就是要通过对a s a 过程的条件、步骤和目 标进行分析，建立相应的数学模型，并研究优化求解的数学方法，进而对模型和 算法进行验证评估，以期为机场机位分配提供方法论指导，解决机场运营的关键 问题。针对上述以往a s a 研究中存在的问题，本文的主要研究内容简述如下： l深入机场生产实际，分析机位分配及其相关活动业务流程，将实际系统 的约束条件和目标要求，归纳抽象为一组完备可行的业务规则，提出假设和简化 条件，采用多目标规划的方法构造约束函数和目标函数，从而建立起a s a 优化 模型； 2 探讨采用现代智能算法求解组合优化问题的技术途径，根据禁忌搜索算 法的基本理论和方法，针对a s a 优化模型特点，提出基于禁忌搜索算法的a s a 优化模型求解算法，并对该算法的可计算性进行分析： 3 采用系统仿真技术和随机事件模型，模拟a s a 实际过程，建立a s a 优 化测试平台，对a s a 优化模型和求解算法进行计算实验，分析实验结果，评估 模型和求解算法的可行性与有效性； 4 引进专家系统和应急管理技术，研究a s a 复杂约束的处理机制，分析实 第一章绪论 时a s a 系统中出现的突发事件及其影响，提出a s a 鲁棒性调度和受扰恢复策略 探讨a s a 动态优化技术及其实现技术。 1 5 2 主要技术路线 根据本文提出的a s a 问题研究策略和研究内容，确定研究路线如图1 1 所 示。 检索资料，分析研究领域，形 成研究思路，开始研究工作 分析业务流程， 明确目标约束， 提炼业务规则 建立优化模型 针对优化模型，构造优化算 法，并对算法进行可行性分析 1 5 3 章节安排 模拟a s a 实际过程，通过计算实 验对模型和算法进行验证评估 分析a s a 复杂约束，提出基于专 家系统的a s a 约束处理机制 分析a s a 突发事件，提出应急管 理和动态优化及系统实现策略 图卜l 主要研究技术路线 本文共分为六章，其主体部分又划分为理论研究、验证研究和应用研究三 部分，总体框架如图1 2 所示，各章内容简述如下： 第一章绪论：初步考察民航机场生产调度过程，简要论述进行停机位分配 方法及其优化技术研究的重大意义，较深入地分析国内外a s a 问题的研究现状 和存在的问题，在此基础上探索a s a 问题的研究策略，明确本文的研究内容和 技术路线，最后对全文的章节划分和内容组织进行统筹安排。 第二章a s a 过程分析与优化建模技术：深入考察机场生产调度过程。分 析停机位分配及其相关活动的业务流程，将实际系统的约束条件和目标要求，归 纳抽象为一组完备可行的业务规则，引进a s a 建模假设和简化条件，在此基础 西北工业大学博士学位论文 上，从一般的多目标规划向量模型出发，构造出a s a 优化问题的约束函数和目 标函数，从而建立起a s a 优化模型，并对该模型求解的可计算性进行初步分析。 i第一章绪论 + 理论研究 第二章a s a 过程分析 第三章基于禁忌搜索 与优化建模技术 的a s a 优化求解技术 王、 z 一一! ，ll 禁禁 a 提建思忌 算 s 出立搜搜 法 a 建优 索 索 复 过杂 程 模 化算算 分 假模法法 性 设型理设 分 析析 论计 验证研究 第四章a s a 优化模型和算法验证 1 a s a 仿真与优 a s a 过程仿真 a s a 优化模型 化试验平台和算法验证 应用研究 第五章智能a s a 优化系统的实现技术 1 基于规则的a s a 应急管理a s a 优化系统 a s a 推理机制与动态优化集成技术 士 第六章总结与展望 图卜2 论文总体框架 第一章绪论 第三章基于禁忌搜索的a s a 优化求解技术：针对a s a 优化模型，对几 种主要的现代智能算法进行比较分析，论述禁忌搜索算法的一般理论和关键技 术，引进解集元素之间距离的概念，提出“蝌蚪形”复合侯选解集结构以及相应 的邻域搜索方法，设计出基于禁忌搜索算法的a s a 优化求解算法，并对该算法 的性能和计算复杂性进行分析。 第四章a s a 优化模型与算法验证评估：引入系统仿真技术，利用随机事 件模型建立a s a 仿真与优化试验平台，随机生成相关参数，对a s a 实际过程进 行环境仿真和方法仿真，并对仿真结果进行分析。然后在该优化试验平台上对 a s a 优化模型和算法进行编码实现，并进行计算实验，对模型和算法的可行性 和有效性进行验证评估。 第五章智能a s a 优化系统的实现技术：引进基于规则的推理技术，来描 述和处理复杂约束条件，设计出a s a 的规则库，探讨a s a 推理机的实现技术。 分析实际a s a 过程中的突发事件及其影响，提出a s