《武汉工程大学学报》  2010年01期 97-99   出版日期：2010-01-31   ISSN:1674-2869   CN:42-1779/TQ

---

基于启发式隐枚举算法的多机场GDP放行策略


引言多机场系统的离场放行策略是协同流量管理问题的子问题.同一终端区内的多个机场构成多机场系统，使用多个公共离场定位点，相应的标准离场航路因此形成耦合.尽管各国学者在离场排序问题方面进行了大量研究，但以往的研究多集中于单机场离场航班排序策略问题，协调同一终端区内多机场系统的离场放行策略研究才刚刚起步，多机场系统航班离场排序问题是NP难题.已有的单机场航班排序相关研究表明：先到先服务（First come first served）排队方法整体效率较低［1］；滑动时间窗动态排序方法的局部最优解与全局最优解差异较大［23］；作为一种群智能多点并行随机搜索方法，粒子群算法在进行大规模搜索时收敛速度有待提高［4］；考虑实际地理因素限制的离场排序模型在采用退火、禁忌搜索和陡峭下降搜索等算法时，某些情况下结果差异很大［5］；遗传算法的适应度和交叉算子参数较难确定［6］；基于动态理论的排序算法的特征系数得出的排序位置对实际改动太大［7］.考虑地面等待策略，并基于多机场系统具有公共离场定位点的空域结构特点，建立多机场系统的航班放行策略模型.在此基础上提出启发式隐枚举算法（HLEA），通过引入机场优先级，并协调经由公共离场定位点的各机场航班比例，优化各机场航班的放行时刻，使多机场系统的航班总体延误最小.1多机场系统航班放行策略模型模型的目标函数为Min∑k∈K∑f∈Fk∑t∈T（tfdc-tfde）·xft（1）
表示研究时段内所有机场离场航班的总延误时间最小.其中，xft是决策变量，若航班f能在时段t内起飞，xft为1，否则为0；K为所有起飞机场k的集合；k为航班f的起飞机场；Fk为在机场k起飞的所有航班的集合；T为航班起飞时刻集合；tfde为航班f的预定离场时刻；tfdc为航班f的控制离场时刻，即航班f实际分配到的起飞离场时刻.模型约束为：∑t∈Txf1=1f∈Fk,k∈K(2)∑f∈Fk,k∈KxftDk(t)t∈T,k∈K(3)∑k∈Kσ(f)∑f∈Fk：p∈P(f)xft-ftpfCp(t)∑k∈Kσ(f)=1,t∈T,k∈K(4)tfdetfdc,f∈Fk,k∈K,t∈T(5)tfdc+wtf′dcf∈Fk,f′∈Fk,k∈K(6)ftpf+MITftpff∈Fk,f′∈Fk,k∈K(7)xft={0,1},t∈T,f∈Fk,k∈K(8)其中，式（2）确保航班在起飞时刻所在的时间片只起飞一次；式（3）表示起飞机场容量约束，Dk(t)为在时段t内机场k的离场容量，k∈K；式（4）表示有公共离场定位点的各机场的航班流比例不超过定位点容量限制，σ(f)是航班f起飞机场k的优先级因子，P(f)为航班f在航路中经由离场定位点的集合，Cp(t)为在时段t内离场定位点的容量,p∈P，ftpf是航班f由起飞机场到达各离场定位点的飞行时间，p∈P(f)；式（5）表示航班控制起飞时间不早于航班预计起飞时间；式（6）是尾流间隔限制，w为航班f的尾流间隔，f′表示相继f的航班；式（7）是航迹间隔（MilesInTrail）限制，MIT(t)是在时段t内离场定位点的限制间隔；式（8）表示决策变量只能取0或1.第1期吕双回，等：基于启发式隐枚举算法的多机场GDP放行策略
武汉工程大学学报第32卷
2启发式隐枚举算法由于多机场系统的航班放行策略模型是NP难问题，因此考虑用启发式方法进行求解，本文采用隐枚举算法.起飞机场的离场容量和离场航路的各定位点容量是确定的.图1启发式隐枚举法流程图
Fig.1The heuristic latent enumerate algorithm flow chart隐枚举算法首先通过对有共同离场定位点的各机场航班放行序列算法求出初始可行解，再通过机场优先级的设定，以及公共离场定位点各机场航班流的比例调节，进行放行时刻的最优化求解.算法中，航班的优先级根据延误时段数动态提高，当预计到达离场定位点的时刻相同时，航班流量大的起飞机场拥有更高的优先级.3算例分析交通运输是一门实践性非常强的学科［8］.因此仿真采用VC++编写仿真程序，原始数据选自2008年3月5日18∶00~19∶00广州白云机场(CAN)和珠海三灶机场(ZUH)的航班数据，包括39个航班，离场跑道占用时间为2分钟一个时隙.两机场共同离场定位点LMN点有流量控制，流控限制时间从18∶00至19∶00，经过LMN点的航路时间间隔为8分钟，即航迹间隔（MilesInTrail）.19∶00后，流控消除，过LMN点航班只要满足安全间隔即可.其他航路点没有流量限制.广州白云机场比珠海三灶机场的优先级高.表1显示了不同机场流量比例因子下对应机场的总延误时间（CAN是广州机场的三字代码，ZUH是珠海机场的三字代码）.可以看出，经由LMN离场定位点的航班架数较多的起飞机场，其航班延误的总时间较少，机场航班延误总量与其经由公共离场定位点的航班流量呈现此消彼长的关系.因此，可以调整两个机场通过LMN点的航班架次比例，优化空域资源配置，使多机场系统的延误总量最小，提高空域使用的效率.
表1优先级比例因子不同时机场延误时间min
Table 1The delay time when different priority rate factors
流控架次比例关系CAN ZUH 合计CAN=3,ZUH=321125236CAN=4,ZUH=214672218CAN=5,ZUH=1130114244CAN=6,ZUH=0106178284由表2可知：对于航班预计起飞时间分布不紧凑的珠海机场来说，航班能按时起飞，不涉及地面等待，两种算法对其航班的离场时刻影响不大；对航班预计起飞时间分布紧凑的广州机场来说，HLEA较之FCFS算法使其平均延误减少了34.84%、最大延误时间减少17.95%，放行时刻配置获得了较好的优化.HLEA较之FCFS算法使两机场的总延误减少了26.35%、两机场的平均延误减少了26.37%，因此可以较大幅度提高多机场系统的整体运行效率.表2两种时刻表的统计比较min
Table 2Compared two schedule time
延误指标HLEAFCFS减少延误两机场总延误21829678两机场平均延误5.8982.11广州平均延误5.037.722.69珠海平均延误990广州最大延误32397珠海最大延误535304结语以上对多机场系统的协调放行策略进行了探索性的研究，基于地面等待策略提出了多机场系统的航班放行策略模型，并采用启发式隐枚举算法对该模型进行了求解.与基于FCFS的算法相比较，隐枚举算法不仅算法简捷，还考虑了机场优先级和机场通过耦合定位点的流量比例，可以大幅度减少离场延误和地面等待时间.其他协同决策的影响因素、多机场多跑道的使用、不同SID的相互影响因素等对离场放行的效应更加复杂，也是今后需要进一步探索和研究的课题.