民航需求日益增大，延误航班日益增多。航班延误往往导致停机位预指派计划无法正常实施。同时停机位指派结果的改变将影响滑行调度的起讫点，进一步增加了其复杂度，对停机位和滑行道联合调度提出了更高的要求。
国内外****已经对停机位与滑行道的联合调度进行了大量研究，研究成果颇为丰富。目前，研究成果主要分为单资源系统调度和多资源系统调度2类。在单资源系统调度方面，国内外****建立了考虑滑行调度影响的停机位指派模型^[1]，部分****采用车间调度^[2]、预测^[3-4]等手段得到航空器滑行时间，并以滑行时间作为停机位指派模型的输入变量，建立考虑停机位指派影响的滑行道调度模型^[5-6]，或是引入停机位推出时间控制策略建立滑行道调度模型进一步提升滑行道运行效率^[7-8]。在多资源系统调度方面，则主要建立分步骤的滑行道与停机位多系统调度模型^[9-10]，按照先进行停机位指派再进行滑行道调度的顺序进行场面优化^[11]，并在此基础上允许路径选择^[12-13]。部分****尝试在滑行道调度采用固定路径的基础上进行停机位指派最终实现航空器无冲突滑行^[14]。此外，部分****采用仿真软件进行相关研究，如采用CPN Tools仿真航班过站时跑道与停机位的利用情况，探索如何提高场面资源利用率^[15]，基于JADF(Java Agent Development Framework)平台开发机场空侧仿真系统，对跑道入侵与滑行冲突进行风险控制^[16]等。
纵观国内外研究成果，单资源系统调度对滑行调度或是停机位指派有较大简化，侧重于对单一资源系统深入的研究。现有的多资源系统调度则主要采用先进行停机位指派再进行滑行道调度的分步骤的建模方式，难以体现停机位指派与滑行道调度之间的反馈作用。如何在保障滑行道和停机位指派质量的基础上实现联合调度这一问题亟待研究。
本文以滑行道调度为上层规划，停机位再指派为下层规划，建立滑行道和停机位联合调度双层规划模型。在提高停机位和滑行道运行效率的同时减少航空器整体等待时间和停机位受扰动影响，并设计遗传算法结合MATLAB对所建双层规划模型进行验证。
1 滑行道和停机位再指派双层规划模型建模 本文采用无向图G(V, E)对机场场面网络进行建模，其中V为节点集合，E为边的集合，并以航空器在无向图中的运行过程为研究对象建立停机位和滑行道双层规划模型。
1.1 基于滑行道调度的上层模型 上层模型为滑行道调度模型，滑行道调度基于停机位再指派结果，是场面调度规划的上层模型。地面管制员将离场航空器由停机坪出口点经滑行道滑行引导至跑道入口点排队，将进场航空器由跑道出口点引导至停机坪入口点。具体模型如下：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

目标式(1)航空器在非停机坪区域与停机坪区域的总体平均滑行时间最短，其中s_{n, n－1}为边(n, n－1)的长度；u^t为非停机坪区域平均滑行速度；T_ni为在节点n附近航空器i避免交叉点冲突，超越冲突和对头冲突而产生的等待时间；F_A为进场航空器集合；F_D为离场航空器集合；R为路径集合，R_i为航空器i的路径；(s_{n, n－1}/u^t+T_ni)为航空器在非停机坪区域的滑行总时间；(T_βi+T_i^β)为航空器在停机坪区域的滑行总时间，其中T_βi为等待进入停机坪的时间, T_i^β为航空器i在停机坪β内的滑行时间；AP为停机坪集合。
式(2)~式(4)表示滑行路径应连续有效且每节点遍历不超过一次，其中V为机场网络图中节点集合；d_mni为判断航空器i是否依次经过节点m和n的布尔变量；d_nli为判断航空器i是否依次经过节点n和l的布尔变量。式(5)为交叉点约束，保证依次通过同一交叉点的航空器之间留有最小安全间隔。其中t_ni为航空器i滑行至节点n的时刻；t_nj为航空器j滑行至节点n的时刻；b_nij为判断航空器i、j是否依次经过节点n的布尔变量；s_f为航空器滑行时需保持的安全距离。式(6)和式(7)为边约束，保证先后通过相同滑行道边的航空器不会出现超越冲突或对头冲突。式(8)和式(9)为一架航空器至多在一个机坪活动与一个机坪至多允许一架航空器同时活动，其中y_iβ为判断航空器是否在该停机坪活动的布尔变量；t_βi为航空器i进入停机坪β的时刻；T_i^β由停机坪与停机位的物理信息与停机坪区域的平均滑行速度u_f共同确定；t_s为连续两架航空器占用同一停机坪的最小安全间隔；H为足够大的常数。式(10)约束最大滑行时间为T_max，其中n₀为起始节点。
1.2 基于停机位再指派的下层模型 下层模型为停机位再指派模型。下层模型确定待调度航空器的具体停机位及其所属停机坪，由此确定上层模型航空器滑行道调度中的起点和终点。下层模型目标函数如下：

(11)

(12)

(13)

(14)

(15)

目标函数式(11)表示最小化远(G_C)和近机位(G_R)更换扰动v_ik和w_ik，以及航空器进入停机坪的等待时间T_βτ最小。η为等待时间的权重，为常数，可由仿真得到；T_βτ来自上层模型求解结果, 体现了上层模型向下层的数据传输；M_i为航空器i的机型；y_iβτ为判断航空器i是否在τ时段进入停机坪β的布尔变量；x_ik为判断航空器i是否分配至停机位k的布尔变量。
式(12)和式(13)表示航空器必须指派至一个停机位且同一航班对的进离场航班被指派至同一停机位。其中ε_ij为判断两航空器是否为同一航班对的布尔变量。式(14)为停机位独占约束，其中t_i^g和T_i^g分别为航空器i的停机位占用起始时刻与占用时间，其中占用时间包括航空器推入停机位时间T_ent，地面保障时间和航空器推出停机位时间T_push；t′_s为同一个停机位连续停放航空器的最小安全间隔。式(15)为机型匹配约束，其中N_k为停机位k的类型。
2 算法实现 遗传算法具有算法参数少、流程简洁、编程易实现、求解效率高、计算量小等特点, 在组合优化问题上有独特优势。本文采用遗传算法对模型进行求解，首先采用整数编码的方式，对从机场采集的数据按照时间顺序排序并进行编码。染色体结构如图 1所示。

图 1 染色体结构 Fig. 1 Structure of a chromosome

图选项

图 1为滑行道调度染色体结构，每个染色体由F_A+F_D个基因组成。基因在染色体的位置代表航空器序号，基因的数值代表该航空器选取的路径编号。如第1个基因位置序号为1，值为R₁，代表1号航空器的滑行路径编号为R₁。停机位再指派模型中染色体结构与此相同，不再赘述。
本文结合双层规划模型在传统遗传算法基础上引入单点交叉与循环嵌套的迭代方式如下：
因基本交叉可能产生停机位指派与滑行道调度的不可行解, 本文采用单点交叉的方式进行交叉操作。即随机选取染色体n₁、n₂片段n₃∈[1, size]，概率p∈(0, 1)，如果p < p_c，则对n₁、n₁两染色体在n₁片段执行交叉操作，p_c为交叉概率。
本文采取循环嵌套的迭代方式以契合双层规划模型。即本文算法先进行i_g次停机位再指派迭代并在此基础上对滑行道调度模型进行i_t次迭代，此为1次联立迭代，总计进行i_G次联立迭代。其中每次联立迭代初始解均包含上一次联立迭代最优解。
本文设置适宜度为各模型目标函数，其余诸如选择与变异等操作原理均与传统遗传算法相同，此处不再赘述。
3 仿真验证 本文以中国华东某大型机场为例进行仿真实验。本文依据该机场提供的2016年3月11日8:00—12:00的机位预指派计划表，对40个航班对及其对应的80架进离场航空器进行停机位再指派和滑行道调度。
本文将G1~G34共34个停机位归类在C1~C8共8个停机坪中，形成如图 2所示的机场场面网络无向图。图中R1、R2为跑道节点，A1~A16为非停机坪区域滑行道节点，B1~B9为停机坪区域的滑行道节点。B1~B3、B4~B6、B9~B7及停机坪区域内的滑行道为停机坪区域滑行道。C1~C5的出入口分别为B1~B5；C6的出入口为B6；C7的入口为B7，出口为B8；C8的入口为B9，出口为B8。根据各停机坪距离跑道出入口的距离设置C1~C6为近机位停机坪，C7和C8为远机位停机坪。

图 2 机场场面网络无向图 Fig. 2 Undirected graph of airport surface network

图选项

停机位信息及预指派计划如表 1和表 2所示。
表 1 机场停机位信息 Table 1 Airport gate information

停机位号	停机坪号	机型
G1	C1	D
G2	C1	C
G3	C1	C
G4	C1	D
G5	C2	C
G6	C2	C
G7	C2	C
G8	C2	D
G9	C3	D
G10	C3	C
G11	C4	C
G12	C4	D
G13	C4	C
G14	C4	C
G15	C5	C
G16	C5	C
G17	C5	C
G18	C5	D
G19	C6	C
G20	C6	C
G21	C6	C
G22	C6	C
G23	C6	C
G24	C7	D
G25	C7	D
G26	C7	D
G27	C7	D
G28	C7	C
G29	C8	C
G30	C8	C
G31	C8	C
G32	C8	C
G33	C8	C
G34	C8	C

表选项






表 2 停机位预指派计划 Table 2 Gate pre-assignment plan

序号	机型	预指派机位	ETA	ETD
1	C	10	08:21	09:35
2	C	5	08:35	09:36
3	D	9	08:51	09:44
4	C	6	09:05	10:38
5	C	2	09:09	10:37
6	C	4	09:19	10:33
7	C	11	09:26	10:54
8	C	18	09:30	11:06
9	C	13	09:30	11:25
10	B	15	09:33	11:19
11	C	19	09:38	10:59
12	D	8	09:45	11:13
13	C	3	09:51	10:46
14	C	10	10:00	11:28
15	C	5	10:08	11:23
16	B	20	10:13	11:30
17	D	1	10:24	11:46
18	C	16	10:28	11:59
19	C	17	10:35	12:03
20	C	6	10:41	12:15
21	D	4	10:43	12:07
22	C	7	10:47	11:44
23	C	8	10:55	12:22
24	D	9	10:59	12:29
25	C	2	11:00	12:02
26	C	11	11:04	12:24
27	C	14	11:05	12:51
28	C	15	11:12	12:20
29	C	19	11:16	12:31
30	B	13	11:18	12:41
31	C	18	11:20	12:10
32	C	3	11:22	12:22
33	C	5	11:28	13:45
34	C	10	11:42	12:49
35	D	1	11:53	13:39
36	C	2	11:54	13:17
37	C	16	12:04	13:11
38	B	20	12:07	13:29
39	C	7	12:09	13:13
40	C	17	12:13	13:20

表选项






表 2中, ETA(Estimated Time of Arrivals)为预计进场时刻，ETD(Estimated Time of Departures)为预计离场时刻。仿真测试中算法参数为：滑行道调度种群数目设为50，停机位再指派问题种群数目为100，突变概率0.02。对上层模型滑行道调度问题迭代100次，下层模型停机位再指派问题迭代150次，联立迭代次数为20次。依据实际运行情况设置:u^t=15 m/s，u^g=10 m/s，T_ent=60 s，T_push=300 s，u_f=50 m，T_max=250 s。
停机位仿真结果如图 3所示，滑行道仿真结果如图 4所示，停机位再指派模型前15代进化程度剧烈。随着迭代代数的增加，目标函数逐渐降低，扰动值逐渐升高最终在一个合理的范围。滑行道调度前30代收敛速度较快，80代后趋于稳定，这说明本文所取迭代代数是足够的。

图 3 停机位再指派迭代趋势 Fig. 3 Iteration trend of gate re-assignment

图选项

图 4 滑行道调度趋势 Fig. 4 Trend of taxiway scheduling

图选项

本文采用2种方式进行联立迭代：每次迭代时仅参考前一次迭代结果的反馈和参考历次累积迭代结果的反馈。仿真结果如图 5和图 6所示。

图 5 仅考虑前一次迭代结果的仿真结果 Fig. 5 Simulation results only considering the last iterative result

图选项

图 6 考虑历次累积迭代结果的仿真结果 Fig. 6 Simulation results considering all previous cumulative iteration results

图选项

图 5显示，仅考虑前一次迭代结果的反馈方式不具有稳定性，而考虑历次累积迭代结果的反馈方式具有明显的趋势性(见图 6)，可见考虑历次累积反馈方式具有较好的反馈效果。因此本文采取该迭代方式进行仿真。
迭代后期的双层模型求解结果，基于人工停机位再指派的双层模型求解结果和采用理论最短滑行路径的双层模型求解结果的对比如表 3所示。
表 3 3种调度策略的求解结果 Table 3 Solving results of three scheduling strategies

调度策略	扰动值	远机位数目	平均滑行时间/s	冲突次数	路径锁死
迭代后期	325	2	91.86	4	0
人工指派	441	5	121.65	7	0
最短路径	441	5	1000000	49	1

表选项






可见，在人工指派将较多的航空器指派至远机位，导致平均滑行时间增长, 航空器平均滑行时间高于迭代后期的结果, 冲突增加达75%，严重影响场面运行效率。相比于人工指派，双层规划策略停机位扰动值由441降至325，降低了26.3%，平均滑行时间由121.65 s降低至91.86 s，降低了24.49%，优化效果明显。在滑行道调度使用最短路径的情况下，不仅产生49次冲突，还产生滑行路径锁死的情况，远高于其他类型的仿真结果, 不能应用于实际调度。
对迭代后期的实验结果进行分析，结果如表 4和图 7所示，表 4中记录不同指派方案受扰动航空器被指派至的停机位序号。
表 4 受扰动航空器的停机位再指派结果 Table 4 Gate re-assignment result of affected aircraft

航空器序号	预指派机位	迭代后期
10	15	24
12	8	4
30	13	34
31	18	23
36	2	12
37	16	18

表选项

图 7 各航班滑行时间 Fig. 7 Taxiing time of each flight

图选项

迭代后期的停机位再分配共影响6架航空器，其中30号航空器被指派至远机位34，其余5架航空器再指派与预指派间隔8.625个停机位，处于旅客可接受的范围。更换的停机位与原停机位处于不同的停机坪，减少了停机坪冲突发生的可能性。迭代后期的仿真结果显示滑行道调度过程中，大部分航空器滑行时间在150 s以内。经统计，最短路A1~A11使用频率最高，而远机位停机坪C8仅有1架航空器经过，多数航空器的滑行路径较短。总计27架航空器选取最短路径，占总航空器数的33.75%；有8架航空器选取了迂回的路径，占总航空器数的10%，其他航空器均选取了较短的路径。迂回路径和较短路径的选择有效避免了滑行路径冲突，减少了冲突时间。滑行道冲突情况如表 5所示。
表 5 滑行道冲突情况 Table 5 Taxiway conflict

航班序号	进离场状态	冲突节点	延误时间/s	冲突原因
9	进场	16	14.3	节点冲突
27	进场	3	57.9	对头冲突
30	进场	5	42.1	对头冲突
41	离场	10	20.3	对头冲突

表选项






由表 5可知，仿真过程中出现的滑行道冲突以进场航班对头冲突为主。离场航班中仅41号航班即1号航空器承载的离场航班发生冲突，同时平均冲突解脱时间为33.65 s，滑行道总体运行较高。接近最大滑行时间的航空器仅有3架，说明设置最大滑行时间250 s是合适的。
4 结论 1) 本文构建停机位再指派与滑行道调度的双层模型，通过上下层模型的反复联立迭代实现模型间的相互影响和作用，并设计改进遗传算法求解。
2) 仿真结果显示，该双层模型较好地体现了上下层模型的影响关系，联立迭代有明显趋势性。停机位扰动值降低26.3%，平均滑行时间降低24.79%，对场面运行效率有明显提高。
3) 在本文的研究基础上，未来有关机场场面调度的研究应考虑滑行道动态调度，以及将场面各资源子系统进行联合调度以实现机场整体调度。

参考文献

[1]	NEUMAN U M, ATKIN J A D. Airport gate assignment considering ground movement[M]. Berlin: Springer, 2013: 184-198.
[2]	BEHRENDS J A, USHER J M. Aircraft gate assignment:Using a deterministic approach for integrating freight movement and aircraft taxiing[J]. Computers & Industrial Engineering, 2016, 102(5): 44-57.
[3]	MURCA M C R. A robust optimization approach for airport departure metering under uncertain taxi-out time predictions[J]. Aerospace Science & Technology, 2017, 68(9): 269-277.
[4]	GUEPET J, BRIANT O, GAYON J P, et al. Integration of aircraft ground movements and runway operations[J]. Transportation Research Part E Logistics & Transportation Review, 2017, 104(8): 131-149.
[5]	WANG J, SHORTLR J F, WANG J, et al.Analysis of gate-waiting delays at major US airports[C]//9th AIAA Aviation Technology, Integration, and Operations Conference(ATIO)and AIAA/AAAF Aircraft Noise and Emissions Reduction Symposium(ANERS).Reston: AIAA, 2009: 1-20. https://catsr.vse.gmu.edu/pubs/9thATIO_GateAnalysis.pdf
[6]	QIN Q, YU H. A statistic analysis of flight delays of major US airports:Illustrated by the example of the JFK airport[M]. Berlin: Springer, 2015: 469-474.
[7]	STEFAN R, JASON A D, EDMUND K B. A more realistic approach for airport ground movement optimisation with stand holding[J]. Journal of Scheduling, 2014, 17(5): 507-520. DOI:10.1007/s10951-013-0323-3
[8]	SIMAIAKIS I, KHADILKAR H, BALAKRISHNAN H, et al. Demonstration of reduced airport congestion through pushback rate control[J]. Transportation Research Part A Policy & Practice, 2014, 66(1): 251-267.
[9]	LEE H.Airport surface traffic optimization and simulation in the presence of uncertainties[D].Boston: Massachusetts Institute of Technology, 2010. https://dspace.mit.edu/handle/1721.1/87480
[10]	CLARE G, RICHARDS A G. Optimization of taxiway routing and runway scheduling[J]. IEEE Transactions on Intelligent Transportation Systems, 2011, 12(4): 1000-1013. DOI:10.1109/TITS.2011.2131650
[11]	杨磊.机场场面运行优化技术研究[D].南京: 南京航空航天大学, 2012. YANG L.Research on optimization techniques of airport surface operation[D].Nanjing: Nanjing University of Aeronautics and Astronautics, 2012(in Chinese). http://cdmd.cnki.com.cn/Article/CDMD-10287-1012042207.htm
[12]	冯程.机场场面运行优化及容量评估技术研究[D].南京: 南京航空航天大学, 2013. FENG C.Research on optimization techniques of airport surface operation and capacity evaluation[D].Nanjing: Nanjing University of Aeronautics and Astronautics, 2013(in Chinese). http://cdmd.cnki.com.cn/Article/CDMD-10287-1014006074.htm
[13]	MALIK W, GUPTA G, JUNG Y. Managing departure aircraft release for efficient airport surface operations[J]. Journal of Air Transport Management, 2013, 46(3): 406-422.
[14]	YU C, ZHANG D, LAU H Y K H, et al. A heuristic approach for solving an integrated gate reassignment and taxi scheduling problem[J]. Journal of Air Transport Management, 2017, 62(1): 189-196.
[15]	徐涛, 曾进进, 吕宗磊. 基于CPN Tools的机场主要资源调度研究[J]. 中国民航大学学报, 2013, 31(2): 36-39. XU T, ZENG J J, LU Z L. Study on scheduling of main resources in airport based on CPN Tools[J]. Journal of Civil Cviation University of China, 2013, 31(2): 36-39. DOI:10.3969/j.issn.1674-5590.2013.02.008 (in Chinese)
[16]	汤淼.基于MAS(Multi-agent System)的机场空侧管制运行仿真系统研究[D].南京: 南京航空航天大学, 2016. TANG M.Research on simulation system of airport airside operation based on MAS (Multi-agent System)[D].Nanjing: Nanjing University of Aeronautics and Astronautics, 2016(in Chinese). http://cdmd.cnki.com.cn/Article/CDMD-10287-1016791935.htm