到达航班排序与调度优化的遗传算法研究

《到达航班排序与调度优化的遗传算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第2卷第2期航空工程进展VoL2No．22011年5月ADVANCESINAERONAUTICALSCIENCEANDENGINEERINGMay201文章编号：1674—8190(2011)02—236—05到达航班排序与调度优化的遗传算法研究黄政，白存儒，张伟(西北工业大学航空学院，西安710072)摘要：解决机场到达航班的排序与调度(Ass)问题是保持空中交通通畅、减少航班延迟的主要途径。本文针对ASS问题的特点，建立了以航班总延误时间为目标函数的排序模型，提出了基于格里芬斯塔特编码和滚动时域优化策略的遗传算法，并对

2、排序模型进行了仿真分析。结果表明：与先到先服务算法相比，本文算法能显著减少航班总延迟，同时较常规遗传算法具有更好的求解性能。关键词：空中交通流量管理；终端区；遗传算法；优化策略中图分类号：V355文献标识码：A9eneticAlgorithmforArrivalSequencingandSchedulingOptimizationHuangZheng，BaiCunru，ZhangWei(SchoolofAeronautics，NorthwesternPolytechnicalUniversity，Xi’an710072，C

3、hina)Abstract：Todealwiththeproblemofarrivalschedulingandsequencing(ASS)isthemainwaytOkeepairtraf—fieunobstructedandreduceflightsdelay．AccordingtOthecharacteristicsofASSproblem，anobjectfunctionwithtotaldelayisdeveloped，animprovedgeneticalgorithmbasedonGrefenstettec

4、odingandrecedinghorizoncontrolstrategyisproposed，thentheschedulingmodelwithgeneticalgorithmissimulatedinthispaper．Theresultsofthesimulationshowthatcomparedwithfirstcomefirstserve(FCFS)algorithmthetotaldelayisgreatlyreducedandtheproposedalgorithmhasbetteroptimizati

5、onperformancethantraditionalgeneticalgo—rithm．Keywords：airtrafficflowmanagement；terminalarea；geneticalgorithm；optimizationstrategyO引言近年来我国民航业发展迅速，各机场年起降航班数逐年上升，在航班高峰期或恶劣天气等情况下，机场常产生交通拥堵，造成大面积的航班延误；缓解机场交通拥堵的方法之一是对降落的航班进行排序优化，以减少航班延误。机场常用的排序算法是先到先服务(FirstComeFirstSe

6、rved，FCFS)算法，FCFS算法按照航班的计划着陆时间(Pre—dietedLandingTime，PLT)安排航班的着陆顺序[1]，FCFS简单易行，但在排序时忽视了许多有用的信息，因此在机场繁忙时不能有效的减少航班延误。目前应用较多的排序算法是基于尾流间隔收稿13期：2011—04—12，修回日期：2011—05—06通信作者：黄政，sliing@mail．nwpu．edu．cn的位置调换法(PositionShifting，PS)。为了保证航空器飞行安全，民航总局规定了不同类型飞机间的最小尾流间隔距离，由于终端

7、区排序一般是基于时间进行的，将距离标准转化为时间标准得到着陆时间间隔(LandingTimeInterval，LTI)c2。，如表1所示。表1着陆时间间隔Table1Landingtimeintervals蟪轻中一重轻9874由13874重16711494从表1可以看出，对于不同类型飞机，着陆时第2期黄政等：到达航班排序与调度优化的遗传算法研究237间间隔是非对称的，位置调换法利用不同类型飞机间尾流间隔的不同，通过调换飞机位置以达到减少航班延迟的目的[3]。基于位置调换的航班排序问题是一个典型的旅行商(TravelingS

8、alemanProblem，TSP)问题，采用常规求解算法求解，随着航班数的增多计算量将急剧上升，难以满足机场排序实时性的要求。遗传算法是一种大规模并行搜索算法，与传统算法相比有着很高的求解效率，很适合用来解决航班排序问题[4]。对于应用遗传算法求解ASS问题，需要考虑选用何种编码以及如何满足机场排序的