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

吕双回, 胡明华

(南京航空航天大学民航学院，江苏 南京 210016)

0 引 言

多机场系统的离场放行策略是协同流量管理问题的子问题.同一终端区内的多个机场构成多机场系统，使用多个公共离场定位点，相应的标准离场航路因此形成耦合.尽管各国学者在离场排序问题方面进行了大量研究，但以往的研究多集中于单机场离场航班排序策略问题，协调同一终端区内多机场系统的离场放行策略研究才刚刚起步，多机场系统航班离场排序问题是NP难题.已有的单机场航班排序相关研究表明：先到先服务(First come first served)排队方法整体效率较低[1]；滑动时间窗动态排序方法的局部最优解与全局最优解差异较大[2-3]；作为一种群智能多点并行随机搜索方法，粒子群算法在进行大规模搜索时收敛速度有待提高[4]；考虑实际地理因素限制的离场排序模型在采用退火、禁忌搜索和陡峭下降搜索等算法时，某些情况下结果差异很大[5]；遗传算法的适应度和交叉算子参数较难确定[6]；基于动态理论的排序算法的特征系数得出的排序位置对实际改动太大[7].

考虑地面等待策略，并基于多机场系统具有公共离场定位点的空域结构特点，建立多机场系统的航班放行策略模型.在此基础上提出启发式隐枚举算法(HLEA)，通过引入机场优先级，并协调经由公共离场定位点的各机场航班比例，优化各机场航班的放行时刻，使多机场系统的航班总体延误最小.

1 多机场系统航班放行策略模型

模型的目标函数为

(1)

表示研究时段内所有机场离场航班的总延误时间最小.

模型约束为：

(2)

(3)

(4)

(5)

∀f∈Fk,∀f′∈Fk,∀k∈K

(6)

∀f∈Fk,∀f′∈Fk,∀k∈K

(7)

∀t∈T,∀f∈Fk,∀k∈K

(8)

2 启发式隐枚举算法

由于多机场系统的航班放行策略模型是NP难问题，因此考虑用启发式方法进行求解，本文采用隐枚举算法.起飞机场的离场容量和离场航路的各定位点容量是确定的.

图1 启发式隐枚举法流程图

隐枚举算法首先通过对有共同离场定位点的各机场航班放行序列算法求出初始可行解，再通过机场优先级的设定，以及公共离场定位点各机场航班流的比例调节，进行放行时刻的最优化求解.算法中，航班的优先级根据延误时段数动态提高，当预计到达离场定位点的时刻相同时，航班流量大的起飞机场拥有更高的优先级.

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

由表2可知：对于航班预计起飞时间分布不紧凑的珠海机场来说，航班能按时起飞，不涉及地面等待，两种算法对其航班的离场时刻影响不大；对航班预计起飞时间分布紧凑的广州机场来说，HLEA较之FCFS算法使其平均延误减少了34.84%、最大延误时间减少17.95%，放行时刻配置获得了较好的优化.

HLEA较之FCFS算法使两机场的总延误减少了26.35%、两机场的平均延误减少了26.37%，因此可以较大幅度提高多机场系统的整体运行效率.

表2 两种时刻表的统计比较 min

4 结 语

以上对多机场系统的协调放行策略进行了探索性的研究，基于地面等待策略提出了多机场系统的航班放行策略模型，并采用启发式隐枚举算法对该模型进行了求解.与基于FCFS的算法相比较，隐枚举算法不仅算法简捷，还考虑了机场优先级和机场通过耦合定位点的流量比例，可以大幅度减少离场延误和地面等待时间.其他协同决策的影响因素、多机场多跑道的使用、不同SID的相互影响因素等对离场放行的效应更加复杂，也是今后需要进一步探索和研究的课题.

参考文献：

[1]孙霞林，曾华，熊德之，杨建华.基于排队的服务系统的最小成本[J]．武汉工程大学学报，2008，30(1)：125-126.

[2]张兆宁，王莉莉．基于流量和滑动窗的空中交通管理动态排序法[J]．交通运输工程与信息学报，2004，2(3)：22-25.

[3]胡雄鹰，熊茜，黎伟东.基于结点的网络最大流算法[J].武汉工程大学学报，2009，31(12)：7-69.

[4]高海超，胡明华．基于最小延误成本的进港航班公平排序[J]．交通运输工程与信息学报，2008，6(4)：57-62.

[5]Atkin JAD，Burke EK， Greenwood JS, et al. Hybrid metaheuristics to aid runway scheduling at London Heathrow airport[J]，Transportation Science，2007，41(1)，90-106.

[6]陶冶，白存儒，由嘉．基于遗传算法的起降航班动态排序模型的研究[J]．中国民航学院院报，2005，23(4) ：6-9.

[7]胡明华，李丹阳，韩松臣．被动空中交通流量管理中的动态排序算法[J]．南京航空航天大学学报，2000，32(1)：85-90.

[8]张培林，刘清，丁涛,等．交通运输专业虚拟实习平台的建设[J]．武汉工程大学学报，2009，31(9)：72-77.