摘要
控制和减少航班延误是国内外民航管理工作的一个长期主要任务。通过航班数据分析,挖掘数据内在特征,并找出其中的延误与波及变化趋势,对航班延误问题的研究有重要指导意义。
本文采用定性分析和定量分析相结合的方法深入研究了航班延误的理论问题,应用贝叶斯网络理论建立实际航班数据的贝叶斯网络模型,分析航班延误影响因素之间的因果关系,给出不同条件下航班延误的概率分布情况。重点研究了贝叶斯网络结构学习的理论方法问题。
第一章概述,介绍了航班延误问题的提出,航班延误与波及问题特性分析,总结了国内外研究现状;描述了基于贝叶斯网络学习的知识发现过程;给出本文主要研究思路。
第二章介绍贝叶斯网络学习,描述贝叶斯网络学习的基本概念,讨论了贝叶斯网络参数学习、贝叶斯网络结构学习、评分模型以及模型优化的主要方法。
第三章提出了高评分优先遗传模拟退火贝叶斯网络结构学习算法,把解决组合优化问题的模拟退火搜索算法和遗传算法应用于贝叶斯网络的结构学习,有效避免高分个体误导种群发展方向所带来的早熟问题,以提高贝叶斯网络结构学习的精度。
第四章提出了基于遗传禁忌搜索的贝叶斯网络结构学习算法,将禁忌搜索算法的思想应用于基于遗传算法的贝叶斯网络结构学习中,进一步改进了遗传算法的交叉和变异操作过程,以提高贝叶斯网络结构学习的效率。
第五章采用数据挖掘典型数据集对本文提出的改进的贝叶斯网络结构学习算法HSPGSA和GATS进行实验分析,与传统的结构学习算法做了对比性研究,说明了方法的有效性和优越性。
第六章构建了航班数据的贝叶斯网络模型。
在以上理论研究的基础上,采集了实际民航航班数据,分别学习构建了大型枢纽机场航班离港延误模型,大型航空公司连续航班延误波及模型,进行了航班延误波及分析,分析结果有助于领导层进行航班延误相关问题管理决策。
To control and reduce flight delays is a long-term and major task of civil aviation management both at home and abroad. To analyze flight data, discover their inner features and find out the changing tendency of flight delay and propagation plays a guiding role in researching flight delays.
By an integrated quantitative and qualitative analysis, the theoretical problem of flight delay is studied in this dissertation. The Bayesian network theory is applied to establish a model with real flight data, to analyze the cause effect relationship of influencing factors in flight delays and to present the probability distribution of flight delays under different conditions.
In chapter 1, the problem of flight delays, the analysis of flight delay and delay propagation, the summary of present research conditions both at home and abroad are introduced. The process of knowledge discovery based on Bayesian networks learning is described and the main research method of this dissertation is presented.
In chapter 2, Bayesian networks learning and basic concepts are briefed. Main methods of parameter learning, structure learning, scoring model and model optimization of Bayesian networks are discussed.
In chapter 3, the algorithm of high score priority of genetic-simulated annealing (SA)of Bayesian networks structure leaning is proposed. SA search algorithm and genetic algorithm (GA) of the optimization problem are applied into the structure learning to effectively avoid the prematurity of population development brought by high-score individuals misleading and to improve the precision of Bayesian networks structure learning.
In chapter 4, the algorithm of Bayesian networks structure learning based on GA & TS (Taboo Search) is put forward. The method of TS algorithm is applied into the Bayesian networks structure learning based on GA to further improve the crossover and mutation processes so as to enhance the efficiency of Bayesian networks structure learning.
In chapter 5, the representative data set of datamining is utilized to make experimental analysis on HSPGSA and GATS of improved Bayesian networks structure learning. The comparative studies with the traditional structure learning algorithm are made to explain the effectiveness and superiority of the method.
In chapter 6, A Bayesian network model of flight data is established.
On the basis of aforesaid theoretical studies, real civil flight data were collected, the departing flight delay model of large hub airport and the sequence flight delay propagation model of large airline companies are composed respectively to make flight delay propagation analyses. The result is helpful for the executive level to make decisions on related problems of flight delays.
引文
[1]卢伟,范虹,借鉴国外解决航班延误的办法[J],国际航空,2004,(12):13~16
[2]中国航空传媒新闻中心“美国7月航班延误率近三成创历年同期最高值”http://www.airchinanews.com时间:2007-09-06 09:15:46来源:新华网
[3]C. Barnhart, A. Cohn, E. Johnson, D. Klabjan, G. Nemhauser, and P. Vance (2003) ,“Airline Crew Scheduling.”[M] Handbook of Transportation Science, second edition, Kluwer’s International Series,2003:279~279
[4]《民航航班正常统计办法》[S]中国民航总局文件民航发(2007)149号
[5]Mostafa Terrab,Saaju Paulose.Dynamic Srategic and Tactical Air Traffic Flow Control[A].Systems,Man and Cybernetics,1992,IEEE International Conference on 18-21 Oct 1992,1:243~248
[6]Jarrah, A.I.Z.,Yu,G.,Krishnamurthy,N.and Rakshit,A.,A decision support framework for airline flight cancellations and delays[J], Transportation Science,1993,27(3):266~280
[7]Peter F Kostiuk, Eric Gaier, Dou Long. The Economic Impacts of Air Traffic Congestion[EB/OL]. htp://www.boeing.com/commercial/caft/reference/documents/lmiecon. pdf, April 1998
[8]Roger Beatty,Rose Hsu,Lee Berry, and James Rome,Preliminary Evaluation of Flight Delay Propagation Through an Airline Schedule[J], Air Traffic Control Quarterly,1999,74(4):259~270
[9]S.S.Allan,J.A.Beesley,J.E.Evans,S.G.Gaddy Analysis of Delay Causality at Newark International Airport,4th USA/Europe Air Traffic Management R&D Seminar,Santa Fe,New Mexico,USA December 2001:1~11
[10]Schaefer,L. and D.Millner,Flight Delay Propagation Analysis with the Detailed Policy Assessment Tool[C],Proceedings of the 2001 IEEE Systems, Man, and Cybernetics Conference,Tucson,Arizona,Institute of Electrical and Electronics Engineers (IEEE).2001:1~5
[11]Mueller E.R. and Chatterji G.B.,Analysis of aircraft arrival and departure delay characteristics,Proceedings of Aircraft Technology Integration and Operations Technical Forum,Los Angeles,CA,2002
[12]Paul T.R.Wang,Lisa A.Schaefer,and Leonard A.Wojcik,Flight connection and their impacts on delay propagation,IEEE Xplore 2003:5.B.4-1~5.B.4-9
[13]Willy Vigneau,Flight Delay Propagation Synthesis of the Study[R], EUROCONTROL Agency M3 Systems,2003:1~45
[14]Dai,D.M. and Liou,J.S. Delay Prediction Models for Departure Flights, Journal of the Transportation Research Board.CR-ROM.2006
[15]Chaug-lng Hsu,Che-Chang Hsu,Hui-Chirh Li Flight Delay Propagation,allowing for behavioural response[J].Critical Infrastructure,2007,3(3/4):301~326
[16]Wu,C.L. and Caves,R.E.,Aircraft operational costs and turnaround efficiency at airports[J],Journal of Air Transport Management,2000, 6:201~208
[17]Hsu,C.I.Jong,H.T. and Huang,H.J. Flight delay propagation and control strategies[J],Transportation Planning Journal,2003, 32(3):447~478
[18]Ning Xu,George Donohue,Kathryn Blackmond Laskey,Chun-Hung Chen. Estimation of Delay Propagation in the National Aviation System Using Bayesian networks[J],Journal of the transportation Research Board. CR-ROM.2007
[19]Ning Xu,Kathryn B. Laskey,Chun-hung Chen,Shannon C. Williams,Lance Sherry Bayesian Network Analysis of Flight Delays,Journal of the Transportation Research Board TRB 2007 Annual Meeting CD-ROM
[20]程朋,崔德光,吴澄,一种基于优化的空中交通短期流量管理模型[J],清华大学学报(自然科学版),2001,41(4/5):163~166
[21]赵嶷飞,金长江,区域空中交通流量控制研究[J],飞行力学,2002,20(2): 68~70
[22]罗喜伶,空中交通流量管理系统中关键技术研究[D]:[博士论文],北京:北京航空航天大学,2002
[23]高海军,王健,陈龙,等,空中交通流量管理研究综述[J],控制工程, 2003,10(6):484~487
[24]马正平,催德光,机场航班延误优化模型[J],清华大学学报(自然科学版), 2004,44(4):474~477
[25]石丽娜,多等级模糊评价方法在航班延误中的应用[J],上海工程技术大学学报,2006,20(3):276~279
[26]陈炜炜,耿睿,崔德光,进近区域到达航班排序和调度的优化[J],清华大学学报(自然科学版),2006,46(1):157~160
[27]姜微微,崔德光,舒学智,空中交通流量管理中的多机场地面等待策略[J],清华大学学报(自然科学版),2006,46(1):137~140
[28]徐肖豪,李雄,航班地面等待模型中的延误成本分析与仿真[J],南京航空航天大学学报,2006,38(1):115~119
[29]D.Heckerman. Bayesian Networks for Data Mining. Data Mining and Knowledge Discovery,1997,1(1):79~89
[30]张连文,郭海鹏,贝叶斯网引论[M],北京:科学出版社,2006
[31]茆诗松,王静龙等,统计手册[M],北京:科学出版社,2003
[32]宫秀军,贝叶斯学习理论及其应用研究:[博士学位论文] ,北京:中国科学院计算技术研究所,2002
[33]王辉,用于预测的贝叶斯网络[J],东北师大学报(自然科学版),2002,34(1):9~14
[34]汪荣贵,张佑生,彭青松,分组样本下Bayes网络条件概率的学习算法[J],小型微型计算机系统,2002,23(6):687~690
[35]杨欣斌,孙京浩,黄道,基于Bayesian网络的缺损数据处理方法[J],华东理工大学学报,2002,28:41~45
[36]刘大有,王飞,卢奕南,薛万欣,王松昕,基于遗传算法的Bayesian网结构学习研究[J],计算机研究与发展,2001,38(8):916~922
[37]王双成,林士敏,用Bayesian网络处理具有不完整数据的问题分析[J],清华大学学报自然科学版,2000,40(9):65~68
[38]D.J.Spiegelhalter,S.L.Lauritzen.Sequential Updating of Probabilities on Directed Graphical Structures Networks.1990.20:579~605
[39]U.M.Fayyad,R.Uthurusamy,Data Mining and Knowledge Discovery in Databases (Introduction to the Special Section).CACM.1996.39(11):24-26
[40]慕春棣,戴剑彬,叶俊,用于数据挖掘的贝叶斯网络[J],软件学报,2000, 11(5):660~666
[41]史忠植,知识发现[M],北京:清华大学出版社,2005
[42]胡文斌,孟波,王少梅,基于贝叶斯网络的权重自学习方法研究[J],计算机集成制造系统,2005,11(12):1781~1784
[43]Cooper GF. A BayesianMethod for the induction of probabilistic networks from data [J].Machine Learning,1992,9(4):309~347
[44]SPIEGELHALTER DJ,LAURITZEN SL. Sequential Updating of Conditional Probabilities on Directed Graphical Structures[J]. Networks,1990, 20(5):579~605
[45]GOLMARD JL,MALLET A. Learning probabilities in causal trees from incomplete database[J].Artificial Intelligence,1991,5(1):93~106
[46]LAURITZEN SL. The EM algorithm for graphical association models with missing data[J].Computational Statistics and Data Analysis,1995,19(2):191~201
[47]THIESSON B,MEEK C,HECKERMAN D. MSR-TR-99-31,Accelerating EM for large databases[R].Microsoft Research,2001
[48]D.M. Chickering,D. Geiger,D. Heckerman. Learning Bayesian Networks is NP-Hard. Microsoft Research Technical Report MSR-TR-94-17.1994
[49]张少中,基于贝叶斯网络的知识发现与决策应用研究,大连理工大学,博士学位论文,2003
[50]Akaike H. Information Theory and an Extension of the Maximum Likelihood Principle.2nd Intrnat.Symp. on Information Theory(Petrov,B.N and Csaki,.F.,eds)267~281
[51]陈希孺,王松桂,近代回归分析-原理方法及应用,合肥:安徽教育出版社,1987
[52]Sakamoto Y,Ishiguro M and Kitagawa G.Akaike Information Criterion Statistics.KTK Scientific Publishers,Tokyo,1986
[53]李刚,知识发现的图模型方法:[博士学位论文],北京:中国科学院软件研究所, 2001
[54]D. Heckerman,D.Geiger,D.M. Chickering. Learning Bayesian Networks: The Combination of Knowledge and Statistical Data.Machine Learning.1995, 20(3):197~241
[55]Lam W,Bacchus F . Learning Bayesian belief networks: an approach based on the MDL principle [J].Computational Intelligence,1994,10(4):269~293
[56]G.E. Cooper,E. Herskovits. A Bayesian Method for the Induction of Probabilistic Networks from Data. Machine Learning.1992,9:309~347
[57]Kirkpatrick S,Gelatt C D and Vecchi M P.1983.Optimization by simulated annealing.Science,220:671~680
[58]Metropolis N,Rosenbluth A W and Rosenbluth M N,el al.1953.Equationas of state calculations by fast computing machines.J ChemPhys,21:1087~1091
[59]王凌,智能优化算法及其应用[M],北京:清华大学出版社,2004
[60]HOLLAND J H. Adaptation in Natural and Artificial Systems[M]. Ann Arbor:Michigan Univ Press,1975
[61]Bac F Q,Perov V L.1993.New evolutionary genetic algorithms for NP-complete combinatorial optimization problems. Biol. Cybern.,69:229~234
[62]RUDOLPH G. Convergence properties of canonical genetic algorithms[J] . IEEE Trans on Neural Networks,1994,5(1):96~101
[63]EIBEN A E,AARTS E H,VAN HEE K M. Global convergence of genetic algorithms:an infinite markov chain Analysis[C]// Parallet Problem Solving from Noture. Berlin; Springer-Verlag,1991:4~12
[64]恽为民,席裕庚,遗传算法的全局收敛性和计算效率分析[J],控制理论与应用,1996,13(4):455~460
[65]孟庆春,纪洪波,董浩,带有对称编码的基因算法中的优良个体成员选取和保存技术[J],计算机研究与发展,1997,34 (增刊):28~31
[66]徐川育,解决一类遗传算法早熟收敛的混合法及其推广[J],软件学报,1998,9(3):231~235
[67]张铃,张钱,佳点集遗传算法[J],计算机学报,2001,24(9):917~922
[68]何雄君,孙国正,刘刚,遗传算法的随机摄动法[J],武汉大学学报(理学版),2001,47(3):285~288
[69]席光,蔡永林,用改进遗传算法求取曲面间最小距离[J],计算机辅助设计与图形学学报,2002,14(3):209~213
[70]王蕾,沈庭芝,招杨,一种改进的自适应遗传算法[J],系统工程与电子技术,2002,24(5):75~78
[71]Glover F,Laguna M. Tabu search,In Modern Heuristic Techniques for Combinatorial Problems(Edited by C.Reeves).Oxford:Blackwell Scientific. 1993
[72]Mublenbein H.Parallel genetic algorithms in combinatorial optimization.Computer Science and Operations Research(Edited by Osman Balci) ,Oxford:Pergamon Press,1995
[73]Glover F,Kelly J. Laguna M. Genetic algorithms and tabu search:hybrids for optimizations.Computers Ops. Res.,1995,22(1):111~134