机场调度

392华东理工大学学报(自然科学版)JournalofEastChinaUniversityofScienceandTechnology(NaturalScienceEdition)文章编号:1006-3080(2008)03-0392-07基于遗传算法的机场调度优化算法刘兆明，葛宏伟，钱锋(华东理工大学信息科学与工程学院，化学工程联合国家重点实验室，上海200237)Vol.34No.32008-06摘要:随着航班数量的不断增长，航空管理系统已不堪重负，机场容量将成为航空运输发展的瓶颈。为了解决机场容量不足问题，本文将机场调度问题分为机位分配和滑行道分配两个过程，设计了适合于求解机位分配和滑行道分配问题的遗传算法。对停机位分配问题，在遗传进化过程中为促进算法收敛，采用贪婪算法对种群进行优化，并引入模拟退火忠、想对适应度函数进行修正。对滑行道分配问题，为适合遗传算法求解，首先将问题转化为围的形式，并设计了相应的遗传编码方式。数位模拟实验表明所提算法能够比较有效地解决机位分自己和滑行道分配问题。关键词:遗传算法;贪婪算法;模拟退火;停机位分配;滑行道分配中图分类号:TP18文献标识码:AAirportSchedulingOptimizationAlgorithmßasedonGeneticAlgorithmLIUZhao-ming,GEHong-wei,QIANFeng(StateKeyLaboratoryofChemicalEngineering,SchoolofInformationScienceandEngineering,EastChinaUniversit:xofScienceandTechnology,Shanghai200237,China)Abstract:Withtheincreaseofairtraffic,thecapacityofairportsisbecomingamajorbottleneckinairtrafficcontroloperations.1nthispaper,inordertosolvethisproblem,theairportschedulingproblemisclassifiedintoairportgateschedulingproblemandtaxiwayschedulingproblem.Thispaperproposestwonovelschedulingalgorithmsforsolvingtheproblemsbasedongeneticalgorithm.Morespecifically,inordertoacceleratetheconvergencespeedoftheairportgateschedulingalgorithm,agreedyalgorithmisintroducedtooptimizethepopulationandthesimulatedannealingisusedtoadjustfitnessfunctionvalue.Besides,agraphmodelanditscorrespondingmatrixcodingarepresentedtopavethewayforthetaxiwayschedulingproblem.Experimentalresultsvalidatethefeasibilityoftheproposedmodelandalgorithms.Keywords:geneticalgorithm;greedyalgorithm;simulatedannealing;gatescheduling;taxiwayscheduling随着航空运输需求的日益增长，航班延误己成为普遍现象，并有不断增长的趋势。欧洲航空协会的一份报告指出1999年上半年超过37%欧洲内部收稿日期:2007-05-17航班延误超过15min，其中机场管理问题应对45%的启程延误和40%的晚点负责。汉莎航空公司1999年由于飞机等待降落而浪费了26000t燃料，基金项目z国家杰出青年科学基金(60625302);国家863计划项目(2006AA04Z168);国家自然科学基金面上项目(60704028);上海市基础研究重点项目(07JC14016);长江学者和创新团队发展计划资助ORT0721);高等学校学科创新引智计划(B08021);上海市重点学科建设项目资助(B504)作者简介::X'tJ兆明0984-)，男，江苏人，硕士生，研究方向z模式识别与智能系统。通讯联系人=钱锋，[e-mail]3931优化目标为:m+1m+1Minimize~~~~fu•Wkl•YikYjl+三Jh2·WOKE十三Jft0·wkzO约束条件为:m+l~Yik=l(叭，1~iζη)aidi(Vi,1ζl'三n)Yik•Yjk(dj-a,)(di-aj)ζ0，(Vi，j，lζi，j~n，k手m+1)(4)YikE{O,1}(Vi,1ζzζn，Vk，lζk~m十1)(5)目标函数是使旅客步行的总距离为最短;公式(2)确保所有的航班都必须分配到并且只能分配到一个停机位或停机坪;公式(3)指定每个航班的到达时间早于其出发时间;公式(4)确保分配到同一个机位上的飞机在时间上不能有重叠(停机坪时间可重叠);公式(5)表明变量h只能在0，1中取值。(1)(2)(3)刘兆明，等.基于遗传算法的机场调度优化算法联合航空公司每年因空中交通管理问题需多花费2.0X107美元。调查显示超过80%的航班晚点是由于机场容量的不足和机场管理系统问题。由于当前航空运输需求增长速度远远大于机场容量的增长速度，而且机场容量的增长十分困难，投资巨大，因此高效的机场管理对于现有系统资源的有效利用变得越来越重要[1-2J而机场调度是机场管理的核心。当前对于机场调度的研究主要集中在飞机在机场的单个过程，如到达[3J、离开[4J和静态分配[5J等，而把飞机在机场的整个运行过程结合起来研究的不多。机场调度优化主要分为两个方面z停机位分配优化[6-7]和滑行道分配优化山。当前许多关于滑行道分配的研究都是基于对滑行过程的仿真[9-10J或对滑行时间的估计[11叶飞本文将飞机在机场运作的整个过程结合起来，基于遗传算法提出了一种新的调度优化算法。停机位分配问题模型第3期基于遗传算法的停机位分配算法本文提出一种基于遗传算法的停机位分配算法，为避免随着航班数量增多编码长度急剧增长，采用实数编码方式。为简化说明，设机场共有3个停机位，待分配的航班有10个。假设航班2、3分配到1号停机位，1、4、5分配到2号停机位，9、8、10分配到3号停机位，6、7分配到停机坪，则基因编码如下:nuqa少6I7分配到不同停机位的航班之间用O隔开，每组代表不同的停机位。此外，在遗传算法执行过程中采用比例选择的方法。2.1初始种群计算采用随机生成种群的方法。考虑到在实际情况中，从人口到停机坪的距离远远大于入口到停机位的距离，因此停机位分配问题的首要任务就是使分配到停机坪的航班数目最少，这可以大大加快算法的收敛速度。所以本文利用贪婪算法进一步优化初始群体。基本原理如下:对所有的航班进行排序后，对分配到停机坪的航班依次进行调整，将每一个航班分配到空闲的并且开始空闲时间最接近该航班的进入停机位时间的停机位上，如不存在这样的机位，则该航班仍停留在停机坪上。2O9I8I105I041停机位分配优化的目标是将给定的航班分配到不同的机位，使得航班之间不产生冲突，并使旅客步行的距离为最短[13-叫。无法分配到停机位的飞机则分配到停机坪，由于人口到停机坪的距离远大于到其他机位的距离，因此应尽量将航班分配到停机位。所有的停机位在同一时间里只允许分配一个飞机(停机坪除外)。由于不同机位问题可以分解为几个相同的机位问题，故本文假设所有可提供的机位及飞机所需的机位置都是相同的。下面给出停机位分配问题的数学模型[15-17J。定义如下变量:N.飞机(到达或离开)集合FM:机场可用的机位数目;n.飞机的总数目;m:机位的总数pai:飞机i的到达时间;di:飞机i的离开时间;Wkl:旅客从机位h到机位t的距离;/;;:从航班i到1的旅客人数;gi:飞机i分配到的机位;加入两个虚拟停机位o代表机场的入口或出口，m+1代表无机位可用时，飞机分配到停机坪;二元变量Yi1=l表示航班i分配到入口k，否则为0;V(i,j)Yi1=Yjk=l(k手m十1)当且仅当(ai­dj)X(aj-di)O。394华东理工大学学报(自然科学版〉第34卷该算法的基本步骤如下:(1)对航班进行排序，用变量5记录当前空闲时间段的开始时间，变量f记录当前空闲时间段的结束时间，变量max记录最接近当前航班进入机位时间的空闲时间段的起始时间，变量index记录拥有当前最好空闲时间段的航班。开始时s=O，j=O，max=O，index=O。(2)对于分配在停机坪的每一架飞机l:①对于分配到停机位的每一个航班):(a)如果航班j是该机位上第一个航班，则s=O，j=鸟，如果满足条件jd;，maxs，则max=s，zηdex=j;(b)如果航班j是该机位上的最后一个航班，则s=坑，j=∞，如果满足条件sa;，maxs，则max=s,index=j;(c)如果航班j前面有航班，则s=dj一I，j=肉，如果满足条件s矶，jd;，maxs，则max=s，index=j;前;②如果index手0，则航班i插入到index之③如果index=O，则航班i仍分配到停机坪;(3)输出结果。2.2适应度函数直接采用目标函数作为适应度函数，对于不同的目标函数值区分度不大，会导致算法收敛较慢，影响计算时间。因此引入模拟退火思想，设计适应度函数为:jitness=e田tue叫-a)祷10n(6)Value表示目标函数值，n调整适应度函数值的区间，使之不至于过小。系数α决定了复制的强制性，a越小，适应度值的区分度越大。适应度函数与目标函数的单调性相反，当目标函数取到最大值时，适应度函数取值最小。2.3交叉算子采用两点交叉的方法，首先随机生成两个交叉点，两个交叉点之间的部分就是基因进行交换的部分。交换后形成的染色体可能存在这样的情况:同一个航班占用两个机位，停机位减少或增加了，分配到同一个停机位的航班在时间上冲突。具体处理过程如下:(1)处理停机位数目变化的情况。如果子染色体中停机位数目增加，则从后一个交叉点开始，到前→个交叉点结束，寻找编码为O的位置，一定存在这样的点，该位置的编码为0，在另一条子染色体中该位置的编码不为0，将两条染色体上该位置的编码互换;如果数目减少，则另一条子染色体的停机位数目必增加，处理这条子染色体即可。重复这样的过程直到停机位的数目没有变化。(2)处理同一个航班占用两个停机位的情况。从后一个交叉点开始到前一个交叉点结束，寻找该航班，将该航班所在的第一个位置换成当前没有在子染色体中出现的最小的航班，重复这样的过程直到每一个航班都分配到停机位。(3)处理同一个停机位上航班在时间上冲突的问题。对分配到每一个停机位的航班按进入停机位时间进行排序，按照约束条件(4)对每一个航班进行调整，将不满足约束条件的航班分配到停机坪，再用贪婪算法对航班进行优化，使分配到停机坪的航班数目最少。2.4变异算子随机在染色体挑选两个基因进行交换，对分配到每一个停机位的航班按进入停机位时间进行排序，按照约束条件(的对每一个航班进行调整，将不满足约束条件的航班分配到停机坪，再用贪婪算法对航班进行优化，使分配到停机坪的航班数目最少。3滑行道分配问题模型当飞机靠近机场后，首先降落在跑道上，然后在规定的滑行道上滑行并进入机场终端区域(停机坪)，并在那供乘客上下飞机和装卸货物，当一切准备妥当后，飞机离开停机坪通过规定的滑行道进入跑道起飞。滑行道连接着停机坪和跑道。每一条跑道都有一些出口和人口，这些出口和入口连接着跑道和滑行道。停机坪和滑行道之间也通过一些人口和出口相连。在规划飞机滑行路线时应避免