场面航空器滑行时空协同优化模型

姜雨; 王欢; 樊卫国; 陈丽丽; 蔡梦婷

doi:10.19818/j.cnki.1671-1637.2019.01.013

场面航空器滑行时空协同优化模型

doi: 10.19818/j.cnki.1671-1637.2019.01.013

姜雨^1,,
王欢¹,
樊卫国^{1, 2},
陈丽丽¹,
蔡梦婷¹

1.
南京航空航天大学民航学院，江苏南京 210016
2.
苏州农业职业技术学院智慧农业学院，江苏苏州 215008

基金项目:

国家自然科学基金项目 U1333117

详细信息

作者简介:
姜雨(1975-), 女, 山东烟台人, 南京航空航天大学副教授, 工学博士, 从事机场场面运行优化研究

中图分类号: V355.2
计量
- 文章访问数: 1652
- HTML全文浏览量: 278
- PDF下载量: 1178
- 被引次数: 0
出版历程
- 收稿日期: 2018-09-12
- 刊出日期: 2019-02-25

Spatio-temporal cooperative optimization model of surface aircraft taxiing

1.
College of Civil Aviation, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, Jiangsu, China
2.
School of Intelligent Agriculture, Suzhou Polytechnic Institute of Agriculture, Suzhou 215008, Jiangsu, China

More Information

Author Bio:
JIANG Yu(1975-), female, associate professor, PhD, jiangyu07@nuaa.edu.cn

摘要

摘要: 引入双层规划方法, 研究了场面航空器在滑行道系统中的滑行调度问题; 考虑了成本与冲突对场面航空器运行效率和安全的影响, 以航空器推出延迟时间与滑行路径作为决策变量, 以航空器在滑行道系统中滑行过程无冲突与场面航空器的总滑行距离最短为目标函数, 构建了场面航空器滑行时空协同优化模型; 针对航空器滑行道调度问题的特点, 设计了适用于航空器滑行时空协同优化模型的双层规划算法, 以降低场面航空器滑行距离和等待时间; 为了验证航空器滑行时空协同优化模型及算法的有效性, 对比了先到先服务调度方案的计算结果, 分析了滑行等待时间与滑行距离对场面航空器运行效率的影响。研究结果表明: 场面航空器滑行时空协同优化模型与先到先服务的航空器调度方案相比, 保证了航空器滑行过程无冲突, 将16架次航空器的总滑行距离从40 690 m降至37 700 m, 降低了8%;航空器平均运行时间为254 s, 提升了滑行道系统的整体运行效率; 在复制组数为100与变异概率为0.4的条件下, 采用场面航空器滑行时空协同优化模型能够在412 s内获得最优解, 求解效率与收敛性显著。可见, 采用场面航空器时空协同优化模型在保障航空器滑行安全的前提下, 能有效提高场面航空器滑行调度效率, 降低航空器运行成本, 能够为繁忙机场滑行道调度提供决策支持。
- 航空运输 /
- 飞机滑跑 /
- 双层规划模型 /
- 启发式算法 /
- 滑行调度 /
- 路径优化
Abstract: The taxiing schedule problem of surface aircraft at the airport was studied by introducing a bi-level programming method. The impacts of taxiing cost and conflict on the operation efficiency and safety of surface aircraft were considered. The spatio-temporal cooperative optimization model of surface aircraft taxiing was constructed by taking the pushout delay time and aircraft taxiing path as decision variables, and the minimum total taxiing distance of surface aircraft without conflict in the taxiway system as objective functions. According to the characteristics of aircraft taxiway schedule problem, a bi-level programming algorithm suitable for the aircraft taxiing spatio-temporal collaborative optimization model was designed to reduce the taxiing distance and waiting time of aircraft. In order to verify the validity of the model and algorithm, the result of the first-come-first-served scheduling plan was compared, and the impacts of waiting time and taxiing distance on the efficiency of surface aircraft were analyzed. Analysis result shows that compared with the first-come-first-serve scheme, the spatio-temporal cooperative optimization model can ensure zero-collision during the aircraft taxiing, and the total taxiing distance of 16 aircrafts reduces from 40 690 m to 37 700 m with a reduction of 8%. The average running time of aircraft is 254 s, which shows that the overall operating efficiency of taxiway system increases. Under the condition that the replication groups number is 100 and the mutation probability is 0.4, the optimal solution of spatio-temporal cooperative optimization model can be obtained within 412 s, and the model has significant efficiency and convergence. It can be seen that on the premise of guaranteeing the safety of aircraft taxiing, the spatio-temporal collaborative optimization model of surface aircraft can effectively improve the efficiency of aircraft taxiing scheduling, reduce the aircraft operation cost, and provide the decision support for the busy airport taxiway scheduling.
- air transportation /
- aircraft taxiing /
- bi-level programming model /
- heuristic algorithm /
- taxiing scheduling /
- path optimization

HTML全文

图 1 某大型机场滑行道系统构型

Figure 1. Structure of a large airport taxiway system

下载: 全尺寸图片幻灯片

图 2 模型最优解进化过程

Figure 2. Optimal solution evolution process of model

下载: 全尺寸图片幻灯片

图 3 航空器滑行冲突点数进化过程

Figure 3. Evolution process of aircraft taxiing conflict point number

下载: 全尺寸图片幻灯片

图 4 航空器的运行时间

Figure 4. Operation times of aircrafts

下载: 全尺寸图片幻灯片

图 5 复制组数对调度结果的影响

Figure 5. Influence of number of replication groups on scheduling result

下载: 全尺寸图片幻灯片

表 1 航空器滑行时刻表

Table 1. Aircraft taxiing timetable

航空器编号	开始滑行时间	滑行起点	滑行终点	分类
1	08:00	32	37	A
2	08:00	35	33	D
3	08:02	36	31	D
4	08:02	37	31	D
5	08:04	36	33	D
6	08:05	34	35	A
7	08:06	32	36	A
8	08:06	34	36	A
9	08:08	32	37	A
10	08:08	35	33	D
11	08:10	32	35	A
12	08:11	34	35	A
13	08:12	36	31	A
14	08:14	34	37	A
15	08:15	35	33	D
16	08:15	32	36	A

下载: 导出CSV

表 2 优化结果对比

Table 2. Comparison of optimization results

方法	FCFS	航空器滑行时空协同优化模型
总滑行距离/m	40 690	37 700
平均滑行距离/m	2 543	2 356
总等待时间/s	0	294
平均等待时间/s	0	18.4
冲突点数	9	0

下载: 导出CSV

表 3 变异概率对调度结果的影响

Table 3. Influence of mutation probability on scheduling result

变异概率	0.2	0.4	0.6
航空器平均滑行距离/m	2 368	2 356	2 418
航空器平均等待时间/s	14.8	18.3	19.3
程序运行时间/s	419	412	406
最优解出现的迭代次数	90	70	10

下载: 导出CSV

参考文献(30)

[1]	CHENG V H L. Airport surface operation collaborative automation concept[C]∥AIAA. AIAA Guidance, Navigation, and Control Conference and Exhibit 2003. Reston: AIAA, 2009: 1-14.
[2]	MARÍN A G. Airport management: taxi planning[J]. Operations Research, 2006, 143: 191-202. doi: 10.1007/s10479-006-7381-2
[3]	DEAU R, GOTTELAND J B, DURAND N. Airport surface management and runways scheduling[C]//ATM. 8th USA/Europe Air Traffic Management Research and Development Seminar. Toronto: Eurocontrol, 2009: 1-9.
[4]	JIANG Yu, LIAO Zhi-hua, ZHANG Hong-hai. A collaborative optimization model for ground taxi based on aircraft priority[J]. Mathematical Problems in Engineering, 2013, 2013: 1-9.
[5]	李睿馨, 徐国标. 一种航空器地面滑行路径决策优化算法[J]. 高师理科学刊, 2017, 37 (9): 14-19. doi: 10.3969/j.issn.1007-9831.2017.09.005 LI Rui-xin, XU Guo-biao. A calculation method on the optimization of aircraft taxi route decision[J]. Journal of Science of Teachers' College and University, 2017, 37 (9): 14-19. (in Chinese). doi: 10.3969/j.issn.1007-9831.2017.09.005
[6]	王艳军, 胡明华, 苏炜. 基于冲突回避的动态滑行路径算法[J]. 西南交通大学学报, 2009, 44 (6): 933-939. doi: 10.3969/j.issn.0258-2724.2009.06.023 WANG Yan-jun, HU Ming-hua, SU Wei. Dynamic taxiway routing algorithm based on conflict avoidance[J]. Journal of Southwest Jiaotong University, 2009, 44 (6): 933-939. (in Chinese). doi: 10.3969/j.issn.0258-2724.2009.06.023
[7]	TANCREDI U, ACCARDO D, FASANO G, et al. An algorithm for managing aircraft movement on an airport surface[J]. Algorithms, 2013, 6 (3): 494-511. doi: 10.3390/a6030494
[8]	ZANG Jing-nan, LIU Qing. Airport taxi scheduling strategy based on particle swarm optimization algorithm[C]//MCE. International Conference on Mechatronics. Control and Electronic Engineering. Paris: Atlantis Press, 2014: 118-121.
[9]	张亚平, 廉冠, 邢志伟, 等. 飞机推出控制停机位等待惩罚策略[J]. 哈尔滨工业大学学报, 2018, 50 (3): 39-45. https://www.cnki.com.cn/Article/CJFDTOTAL-HEBX201803005.htm ZHANG Ya-ping, LIAN Guan, XING Zhi-wei, et al. Aircraft departure pushback control strategy based on gate-hold penalty[J]. Journal of Harbin Institute of Technology, 2018, 50 (3): 39-45. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-HEBX201803005.htm
[10]	潘卫军, 杨磊, 朱新平, 等. 繁忙机场机坪运行过程着色Petri网建模[J]. 计算机仿真, 2018, 35 (1): 52-56, 97. doi: 10.3969/j.issn.1006-9348.2018.01.011 PAN Wei-jun, YANG Lei, ZHU Xin-ping, et al. Modeling of busy airport apron running processes based on color Petri net[J]. Computer Simulation, 2018, 35 (1): 52-56, 97. (in Chinese). doi: 10.3969/j.issn.1006-9348.2018.01.011
[11]	ROSA L P, FERREIRA D M, CRUCIOL L L B V, et al. Genetic algorithms for management of taxi scheduling[C]//IEEE. 2013 International Conference on Artificial Intelligence. New York: IEEE, 2013: 594-598.
[12]	NOGUEIRA K B, AGUIAR P H C, LI Wei-gang. Using ant algorithm to arrange taxiway sequencing in airport[J]. International Journal of Computer Theory and Engineering, 2014, 6 (4): 357-361. doi: 10.7763/IJCTE.2014.V6.889
[13]	丁建立, 李晓丽, 李全福. 基于改进蚁群协同算法的枢纽机场场面滑行道优化调度模型[J]. 计算机应用, 2010, 30 (4): 1000-1003, 1007. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJY201004045.htm DING Jian-li, LI Xiao-li, LI Quan-fu. Optimal scheduling model for hub airport taxi based on improved ant colony collaborative algorithm[J]. Journal of Computer Applications, 2010, 30 (4): 1000-1003, 1007. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSJY201004045.htm
[14]	LUO Xiao, TANG Yong, WU Hong-gang. Real-time adjustment strategy for conflict-free taxiing route of A-SMGCS aircraft on airport surface[C]//IEEE. 12th IEEE International Conference on Mechatronics and Automation. New York: IEEE, 2015: 929-934.
[15]	汤新民, 王玉婷, 韩松臣. 基于DEDS的A-SMGCS航空器动态滑行路径规划[J]. 系统工程与电子技术, 2010, 32 (12): 2669-2675. doi: 10.3969/j.issn.1001-506X.2010.12.36 TANG Xin-min, WANG Yu-ting, HAN Song-chen. Aircraft dynamic taxiway routes planning for A-SMGCS based on DEDS[J]. Systems Engineering and Electronics, 2010, 32 (12): 2669-2675. (in Chinese). doi: 10.3969/j.issn.1001-506X.2010.12.36
[16]	LIU Qing, LI Chun-ling, LUO Xiao-fei. Airport taxi scheduling strategy based on cooperate particle swarm optimization algorithm[J]. International Journal of Advancements in Computing Technology, 2011, 3 (9): 165-172. doi: 10.4156/ijact.vol3.issue9.21
[17]	SAMÀ M, D'ARIANO A, D'ARIANO P, et al. Optimal aircraft scheduling and routing at a terminal control area during disturbances[J]. Transportation Research Part C: Emerging Technologies, 2014, 47 (P1): 61-85.
[18]	ZHOU Hang, JIANG Xin-xin. Research on taxiway path optimization based on conflict detection[J]. Plos One, 2015, 10 (7): 1-17.
[19]	黄政, 白存儒, 张伟. 到达航班排序与调度优化的遗传算法研究[J]. 航空工程进展, 2011, 2 (2): 236-240. doi: 10.3969/j.issn.1674-8190.2011.02.019 HUANG Zheng, BAI Cun-ru, ZHANG Wei. Genetic algorithm for arrival sequencing and scheduling optimization[J]. Advances in Aeronautical Science and Engineering, 2011, 2 (2): 236-240. (in Chinese). doi: 10.3969/j.issn.1674-8190.2011.02.019
[20]	CHENG Xiao-hang, XUE Hui-feng, HONG Ding-song, et al. Design of adaptive genetic algorithm on single airport ground-holding policy[C]∥ASCE. International Conference on Transportation Engineering 2007. Reston: ASCE, 2007: 253-258.
[21]	FU A-li, LEI Xiu-juan, XIAO Xiao. The aircraft departure scheduling based on particle swarm optimization combined with simulated annealing algorithm[C]//IEEE. 2008 IEEE Congress on Evolutionary Computation. New York: IEEE, 2008: 1393-1398.
[22]	WEISZER M, CHEN Jun, LOCATELLI G. An integrated optimisation approach to airport ground operations to foster sustainability in the aviation sector[J]. Applied Energy, 2015, 157: 567-582. doi: 10.1016/j.apenergy.2015.04.039
[23]	ALONSO-AYUSO A, ESCUDERO L F, MARTÍN-CAMPO F J, et al. A VNS metaheuristic for solving the aircraft conflict detection and resolution problem by performing turn changes[J]. Journal of Global Optimization, 2015, 63 (3): 583-596. doi: 10.1007/s10898-014-0144-8
[24]	闫春望, 黄玮, 王劲松. 一种随机时变神经网络最短路径算法[J]. 天津理工大学学报, 2016, 32 (2): 40-44. https://www.cnki.com.cn/Article/CJFDTOTAL-TEAR201602010.htm YAN Chun-wang, HUANG Wei, WANG Jin-song. A stochastic time-varying neural network shortest path algorithm[J]. Journal of Tianjin University of Technology, 2016, 32 (2): 40-44. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-TEAR201602010.htm
[25]	付宇晓. 面向机坪管制移交的场面运行优化问题研究[D]. 南京: 南京航空航天大学, 2017. FU Yu-xiao. Research on the airport surface operation optimization problem of the transfer of the aprons control[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2017. (in Chinese).
[26]	李睿馨. 大型繁忙机场机坪管制工作中的滑行路径决策优化算法研究[D]. 广汉: 中国民用航空飞行学院, 2018. LI Rui-xin. Research on the optimization algorithm of taxiing path decision of the ramp control work in the busy airport[D]. Guanghan: Civil Aviation Flight University of China, 2018. (in Chinese).
[27]	BRACKEN J, MCGILL J T. Mathematical programs with optimization problems in the constraints[J]. Operations Research, 1973, 21 (1): 37-44.
[28]	BRACKEN J, FALK J E, MCGILL J T. Technical note—the equivalence of two mathematical programs with optimization problems in the constraints[J]. Operations Research, 1974, 22 (5): 1102-1104.
[29]	WEN U P, HSU S T. Linear bi-level programming problems—a review[J]. The Journal of the Operational Research Society, 1991, 42 (2): 125-133.
[30]	WHITE D J, ANANDALINGAM G. A penalty function approach for solving bi-level linear programs[J]. Journal of Global Optimization, 1993, 3: 397-419.