基于离散事件的地面等待模型算法研究与仿真

1、基于离散事件的地面等待模型算法研究与仿真第24卷第5期计算机仿真2007年5月文章编号:10069348(2007)05-0238-03基于离散事件的地面等待模型算法研究与仿真张学军,刘钊(北京航空航天大学电子信息工程学院,北京1o0o83)摘要:考虑大型机场拥塞问题日益严重,从航空公司的利益出发,采用推迟飞机起飞时问的方式,将成本较高的空中等待转化成地面等待.基于离散事件系统的地面等待模型就是针对此类问题而提出的.通过对模型求解进行研究,针对遗传算法的速度无法满足目前要求的问题,提出使用0.618算法完成求解过程,通过对计算过程进行改进保持了计算结果的准确性并且提高了速度.实验结果表明,0.

2、618算法的结果与遗传算法相差2.5%,但在速度上提高l1.9%,验证了此方法的有效性与实用性.关键词:地面等待;离散事件;算法;遗传算法中图分类号:v355.1文献标识码:aresearchandsimulationofgroundholdingmodelalgorithmbasedondiscreteeventzhangxueiui1,liuzhao(schoolofelectronicinformationengineering,beihanguniversity,beijing100083,china)abstract:consideringtheoverloadingandserio

3、uscongestionofsomelargeairpos,accordingtoairlineinter-est,certaindelaysareimposedonsomeaircraftsattakeoffinordertoavoidmoreexpensiveairdelay.thismethodcanchangetheexpensiveairholdingtogrounddelay.groundholdingmodelbasedondiscreteeventisjustpro-posedforsolvingthisproblem.afterresearchingonmodelcalcul

4、ation,0.618algorithmisproposedtofinishmodelcalculation,aimingatthatthegeneticalgorithmcannotmeettheperformancerequirement,andsomeimprovementareappliedtokeepaccurateresultandfastcalculation.theexperimentshowsthattheresultof0.618algorithmisdifferentfromgeneticalgorithmby2.5%.hut0.618algorithmisfasterb

5、y11.9%k,whichhasverifiedtheeffective-nessandpracticabilityofthemodelandalgorithm.keywords:groundholding;discreteevent;algorithm;geneticalgorithms1引言目前大型机场都不堪重负,出现了不同程度的空中交通拥塞问题,导致了飞机的空中等待,而终端区(机场)拥塞是飞机空中等待的一个主要原因.由于飞机空中等待成本远远高于地面等待成本,从航空公司的利益出发,采用推迟飞机起飞时间以减少其在航路上或目的机场上空的空中等待策略是解决这类问题的有效途径.基于离散事件系统的地

6、面等待模型是处理此类问题的主要理论模型.针对地面等待模型的求解过程中计算量大导致仿真周期较长的情况,在文献1的基础上提出新的模型计算方法.仿真结果表明计算方法是在保持结果的接近最优的情况下显着提高计算速度.基金项目:自然科学基金项目(60572178)收稿el期:20060327修回el期:20060414-238-2模型定义对某一机场而言,当天气晴朗时,飞机可以按预定时间依次准时降落.但如果天气状况突然变差(如出现大雾,雷雨等天气),使飞机的服务时间(即降落时间)延长,从而导致后续航班的延误.而如何使延误成本降到最低,就是一个急需解决的问题.为简单起见,给出几个基本假设:1)机场只有一个跑道

7、;2)机场管制中心按照先到先服务的原则对到港航班实行管制服务;3)只考虑机场的降落容量而不考虑起飞容量,即起飞容量是无限的.这样,一架飞机只有等前一架飞机落地之后才能开始降落.因此,如果第i架飞机的服务时间由于天气影响而延长,按预定时刻到达的第i+1架飞机就不得不在空中盘旋,等第i架飞机落地后才能开始降落.基于离散事件的地面等待模型的详细定义可参考文献1,下面主要对模型的求解问题进行讨论.由于天气变化,飞机从空中到跑道的降落时间d不固定,它随着天气的变好而缩短,随天气的恶劣而变长.这就说明第i架飞机的降落时间是由第i一1架飞机的降落时间和第架飞机降落时由天气影响的降落时间共同决定.此外,当推迟

8、第i架飞机降落时间后,延误将扩展到后面的所有飞机,即第i+1,i+2架飞机都会被至少推迟同样时间.相邻飞机降落时间的强相关性是模型求解过程中主要难点.即先找到第i架飞机的最优等待时间d后再计算第i+1架飞机的最优等待时间d.首先对符号进行定义.通过航空气象观测部门对气象的观测结果,再考虑到历史同期天气数据,综合起来对当天的天气进行预测,可得到当天的天气情有q(q=1,2,3,q)个天气样本,每个样本的概率分别为p.,p,p.a:第k架飞机的预计到达时间:第架飞机的落地的时间c:飞机地面延误成本c.:飞机空中延误成本,<c.(d2)是在第q个天气样本下第二架飞机总的成本,该成本包括地面等待

9、成本和空中等待成本.为飞机i的地面等待时间,为飞机i的空中等待时间.模型求解过程如下:第一步:由于第一架飞机不需要地面等待,因此d:=d=d7=0(1)=d3=(2)第二步:求(q=1,2,q),令d=maxd,1qq(3)di=rain,1qq(4)显然等待时间d应该在两者之间,这就可能使某些飞机在一些天气样本下有了空中等待,因此求解的目的是在区间d,d之间找到一个d=d使得总代价c最小,即:qpmkc=c(d2)=p(蠼+)+】qq3j=2(5)第三步:令a=a+第四步:此时可能a3,a,al<a,则要推迟这些航班到a时刻到达,即对于航班=2,3,4,令=蠼+d(6)d=d+max0

10、,a2一aj2(7)a,=maxa2,ai(8)第五步:对于第i航班(i>2),按照同第二步同样的方法,计算理想等待时间d.这样按照上述第二步至第五步的方法,依次可计算决定第三架,第四架直到最后一架飞机的理想等待时间d(1i).3模型求解对模型求解过程中最重要的环节就是在区间d,d之问找到一个d2=(空中等待)使得总代价c最小.由于式(5)是一个关于时间的连续有界函数,因此存在最小值.这是一个无约束优化问题,可以采用很多方法在dd内搜索.文献1中使用遗传算法计算第二架飞机的理想等待时间.遗传算法从一组随机产生的初始解,称为种群,开始搜索过程.种群中的每个个体是问题的一个解,称为染色体.染

11、色体是一串符号,比如一个二进制字符串.这些染色体在后续迭代中不断进化,称为遗传.在每一代中用适值来测量染色体的好坏.生成的下一代染色体,称为后代.后代是由前一代染色体通过交叉或者变异运算形成的.新一代形成中,根据适值的大小选择部分后代,淘汰部分后代,从而保持种群大小是常数.适值高的染色体被选中的概率较高.这样,经过若干代之后,算法收敛于最好的染色体,它很可能就是问题的最优解.遗传算法比较复杂,虽然全局搜索效果很好,但局部搜索过程收敛不稳定,有可能遗漏一些值.在实际仿真实验过程中,遗传算法确实能产生很好的结果,但由于它的通用性,对所解的优化问题也没有过多的数学要求,因此计算过程费时,达不到期望要

12、求.考虑到遗传算法本身比较复杂,而且仿真过程中都是使用仿真软件自带的实现模块,针对特定问题对其进行改进比较困难.故欲采用0.618法(又称为黄金分割法)替代遗传算法实现最优值的求解.0.618法收敛速度快,实现比较简单,计算速度快.在了解待解决问题的内在性质后容易进行改进,期望在尽量保持结果精确性的前提下显着提供运行速度.实现考虑如下改进:1)根据0.618算法要求在运行初期需要选取两个初始比较点,初始点的选取对计算速度和最后的结果都会有一定影响.通过对遗传算法产生的结果进行分析,发现最优延误时间出现在天气样本中概率最高的两种情况决定的延误时间的区间内的概率非常高.因此以d,d区间内出现概率最

13、高的两个点最为算法运行的初始比较点.2)根据中国民用航空空中交通管理规则,航空器机型种类按航空器最大允许其飞全重分为三类:重型机(等于或大于136000千克);中型机(大于70000千克,小于136000千克);轻型机(小于70000千克).按照航班所使用的飞机不同将航班分成三类:a,b和c,降落时间比为:35:30:21,由此看出相同时间内降落的小型飞机数目更多.大型飞机油耗大,因此单位时间空中延误成本大于小飞机,考虑总体延误成本没有标准计算方法,所以在此计算过程中使用飞机的载客数作为航班单位等待时间造成延误成本的权重,这样就相当于给了大型飞机优先降落权.根据实际经验数据,由于地面服务等其它

14、配套服务的原因,大部分飞机的降落时间基本都在2.2min,2.5min区间内,因此在使用0.618算法进行求解时不考虑由机型造成的降落时间差异,即大型飞机优先降落.4仿真结果与分析arena是rockwell公司推出的一个面向流事件的商业决策仿真软件,它提供对面向对象设计的支持,允许用户创建?-239?-和运行针对自己研究内容的模块,根据仿真结果分析决策的正确性.arena支持使用c/c+编写的代码,具有较强的通用性.图1是仿真过程中动画区起始状态.planewaitingtolanding是等待降落的航班;signal是信号灯,初始时跑道上没有飞机滑行所以显示绿色;变量valueofrele

15、asesignal显示降落逻辑值;nq显示正在等待降落的航班数量;systernrtmtlme是系统的运行时间;arriva1.numberout是产生的实体,即已经到达的航班数量;totalcost是总的等待成本.图1仿真运行界面在进行地面等待决策仿真的过程中,数据的来源很重要,这直接关系到决策的效果.所以,此地面等待决策系统所应用的数据是通过民航总局每年两次的飞行航班时刻表转化而来的,具有绝对的权威性.第一次运行时完全按照航班时刻表来仿真,不存在地面等待优化问题,所以求得的全部等待成本完全是空中等待成本,结果如图2.thentunber,thetimeandthetotalcost图2无优

16、化仿真结果使用0.618算法实现对(5)式中最优值d兰p的求解过程,仿真结果如图3.从仿真结果中可以看出,航班等待时间,等待的航班数,总的等待都有明显下降,同时等待的航班数量最大值为2,达到了减少飞机在机场上空盘旋等待的目的,大大减少了机场的空中拥塞情况,等待降落航班的空中等待时间也很小,仿真总用时5:52:17,总的等待成本是为470.42单位.图4给出了使用遗传算法实现对(5)式中d兰p最优值求解的仿真结果,仿真中使用了arena软件中自带的遗传算法实现模块.从仿真结果中可以看出,总的等待成本是为458.48单位,优于前者,仿真总用时6:39:59,与前者相比稍慢.一240一图3基于0.6

17、18算法的仿真结果图4基于遗传算法的仿真结果5结论基于des单机场流量模型仿真研究利用有效的算法对等待降落的航班进行优先级排队和等待优化是绝对可行的.通过对求解过程的改进,使用0.618算法替代遗传算法,在基本保持结果的最优性前提下(与遗传算法差2.5%),计算速度提高11.9%.参考文献:1罗喜伶.空中交通流量管理系统中关键技术研究d.北京航空航天大学博士论文,2002.2gandreatta,gromaninjacur.aircraftflowmanagementundercongestionj.transportationscience,1987,21(4).3wdavidkeltonrandall,psadowskideborah,asadowski.simulonwitharenam.mcgrawhill,2002,no.2edition.4mos