南京大学学报(自然科学版) ›› 2020, Vol. 56 ›› Issue (1): 132–141.doi: 10.13232/j.cnki.jnju.2020.01.015

• • 上一篇    下一篇

多跑道进离港地面等待问题建模及协同优化

张玉州(),张子为,江克勤   

  1. 安庆师范大学计算机与信息学院，安庆，246133
  • 收稿日期:2019-10-26 出版日期:2020-01-30 发布日期:2020-01-10
  • 通讯作者: 张玉州 E-mail:yzhzhang@mail.ustc.edu.cn
  • 基金资助:
    安徽省自然科学基金(1808085MF173);安徽省高校省级自然科学研究重点项目(KJ2016A438)

Multi⁃runway arrival⁃departure ground⁃holding problem modeling and collaborative optimization

Yuzhou Zhang(),Ziwei Zhang,Keqin Jiang   

  1. School of Computer and Information, Anqing Normal University, Anqing, 246133, China
  • Received:2019-10-26 Online:2020-01-30 Published:2020-01-10
  • Contact: Yuzhou Zhang E-mail:yzhzhang@mail.ustc.edu.cn

RichHTML

6

PDF (PC)

1044

摘要：

针对多跑道机场起降航班难以进行跑道合理分配，尤其是混合跑道的使用问题，以降低航班延误损失为目标，提出一种基于跑道的航班优先系数计算策略，建立了一种多跑道进离港地面等待问题优化模型，并实现进离港队列延误费用的合理分配.同时，设计了一种启发式局部搜索算子并嵌入遗传算法，形成一种混合遗传算法对问题模型求解.通过对代表性算例的计算，结果表明，所提出的模型及算法不仅可以减少航班的延误损失，还可以显著优化延误损失在进离港队列之间的合理分配.

关键词: 协同优化, 遗传算法, 进离港地面等待问题, 多跑道机场, 启发式局部搜索, 航班优先系数

Abstract:

Since it is difficult to allocate multi?runways to planes and use mixed runways reasonably in multi?runway airports,a strategy of computing flight priority coefficient based on runways is brought forward according to actual composition of arrival?departure flights and planed assignment of runways. Hence,an optimization model is proposed for multi?runway arrival?departure ground?holding problem (ADGHP) in order to minimize delay costs of flights and ensure reasonable distribution of delay costs between arrival queue and departure queue. Then,a local heuristic search operator is designed and integrated into genetic algorithm (GA) for the model. A hybrid GA is obtained for the model of multi?runway arrival?departure ground?holding problem. Finally,the simulation is implemented with typically examples and the results show apparent effects in reducing and reasonably distributing delay cost.

Key words: collaborative optimization, genetic algorithm, arrival?departure ground?holding problem, multi?runway airport, heuristic local search, flight priority coefficient

中图分类号: 

  • V355，TP18

表1

基于跑道的个体编码 (a) 航班的进离港类别"

1 2 3 4 5 6 7
进港 进港 离港 进港 离港 离港 进港
8 9 10 11 12 13
离港 进港 进港 离港 离港 进港

表1

基于跑道的个体编码 (b) 个体编码"

r0 1 2 7 9 13
r1 3 4 8 10
r2 5 6 11 12

表2

仿真算例航班数据"

航班 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
机型 S M H S M H H S H M M H S M S H M H
人数 68 133 365 42 120 160 377 45 220 175 165 335 82 180 55 423 132 279
类别 进港 进港 离港 进港 离港 进港 离港 进港 离港 进港 离港 进港 离港 进港 进港 离港 离港 进港
航班 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
机型 H S M S H M S H M M H H S M H S H
人数 525 90 115 78 339 189 82 430 112 125 239 458 68 158 255 42 160
类别 离港 离港 进港 进港 离港 进港 离港 离港 进港 进港 离港 离港 离港 进港 进港 离港 离港

表3

仿真实验排序结果"

航

班

 航班使用跑道计划时间 FCFS SGA SLSGA HLSGA
ET0 ET1 ET2 R STA GT GC R STA GT GC R STA GT GC R STA GT GC
1 00:01 00:10 00:18 0 00:01 0 0.0 0 00:01 0 0.0 0 00:01 0 0.0 0 00:01 0 0.0
2 00:36 00:28 00:50 1 00:28 0 0.0 1 00:28 0 0.0 1 00:28 0 0.0 1 00:28 0 0.0
3 01:15 01:35 01:27 2 01:27 0 0.0 2 01:27 0 0.0 2 01:27 0 0.0 2 01:27 0 0.0
4 02:55 03:10 02:41 0 02:55 0 0.0 0 02:55 0 0.0 0 02:55 0 0.0 0 02:55 0 0.0
5 03:04 03:43 03:15 2 03:21 6 16.5 2 03:21 6 16.5 2 03:21 6 16.5 2 03:21 6 16.5
6 04:35 04:00 03:47 1 04:00 0 0.0 1 04:00 0 0.0 1 04:00 0 0.0 1 04:00 0 0.0
7 05:38 04:40 05:09 2 05:09 0 0.0 2 05:09 0 0.0 2 05:09 0 0.0 2 05:09 0 0.0
8 06:40 06:15 05:52 0 06:40 0 0.0 1 06:47 32 25.1 0 06:40 0 0.0 0 06:40 0 0.0
9 07:15 07:09 06:20 2 06:43 23 108.5 2 06:43 23 108.5 1 07:09 0 0.0 1 07:09 0 0.0
10 08:15 08:00 07:31 1 08:00 0 0.0 0 08:15 0 0.0 0 08:15 0 0.0 0 08:15 0 0.0
11 08:20 08:30 07:59 2 08:37 38 219.3 2 08:37 38 219.3 2 07:59 0 0.0 2 07:59 0 0.0
12 09:25 08:52 08:48 1 09:14 22 144.7 1 08:52 0 0.0 1 08:52 0 0.0 1 08:52 0 0.0
13 10:28 10:10 09:53 2 10:55 62 85.8 2 10:55 62 85.8 2 10:17 24 33.2 2 10:17 24 33.2
14 10:38 10:45 09:55 0 10:38 0 0.0 0 10:38 0 0.0 1 10:46 1 3.7 1 10:46 1 3.7
15 11:40 11:31 11:50 1 12:01 30 28.4 1 11:39 8 7.6 0 11:40 0 0.0 0 11:40 0 0.0
16 12:35 12:04 12:23 2 12:23 0 0.0 2 12:23 0 0.0 2 12:23 0 0.0 2 12:23 0 0.0
17 13:10 13:05 13:31 1 13:15 10 29.5 1 13:05 0 0.0 1 13:05 0 0.0 1 13:05 0 0.0
18 13:52 13:30 13:45 0 13:52 0 0.0 0 13:52 0 0.0 0 13:52 0 0.0 0 13:52 0 0.0
19 14:25 14:03 13:59 2 13:59 0 0.0 2 13:59 0 0.0 2 13:59 0 0.0 2 13:59 0 0.0
20 15:00 15:23 14:49 1 15:33 10 15.1 1 15:23 0 0.0 1 18:13 170 257.4 1 15:23 0 0.0
21 15:12 15:55 15:05 0 15:46 34 90.8 0 15:46 34 90.8 1 15:55 0 0.0 0 15:46 34 90.8
22 16:06 16:38 16:03 1 17:11 33 43.6 1 17:01 23 30.4 0 16:39 33 43.6 1 17:01 23 30.4
23 16:37 17:46 16:25 2 16:25 0 0.0 2 16:25 0 0.0 2 16:25 0 0.0 2 16:25 0 0.0
24 18:05 18:20 17:52 0 18:05 0 0.0 0 18:05 0 0.0 0 18:05 0 0.0 0 18:05 0 0.0
25 18:42 19:29 18:42 2 19:12 30 41.5 2 19:12 30 41.5 1 19:51 22 30.5 1 19:29 0 0.0
26 19:32 20:00 20:12 1 20:00 0 0.0 1 20:00 0 0.0 2 20:12 0 0.0 2 20:12 0 0.0
27 20:05 21:03 21:06 0 20:05 0 0.0 0 20:05 0 0.0 0 20:05 0 0.0 0 20:05 0 0.0
28 20:55 21:18 21:40 0 21:19 24 109.6 0 21:19 24 109.6 1 21:18 0 0.0 0 21:19 24 109.6
29 21:23 21:36 22:06 1 21:36 0 0.0 1 21:36 0 0.0 2 22:06 0 0.0 1 21:36 0 0.0
30 21:52 22:33 23:06 2 23:06 0 0.0 2 23:06 0 0.0 1 22:33 0 0.0 2 23:06 0 0.0
31 23:01 23:15 23:20 1 24:23 68 78.7 1 24:23 68 78.7 1 26:57 222 257.1 1 27:42 267 309.2
32 23:15 23:41 23:56 0 23:15 0 0.0 0 23:15 0 0.0 0 23:15 0 0.0 1 23:41 0 0.0
33 23:42 24:10 24:25 0 24:29 47 414.8 0 24:29 47 414.8 1 24:10 0 0.0 0 23:42 0 0.0
34 24:13 24:39 24:26 2 25:53 87 64.2 1 26:01 82 60.5 1 28:35 236 174.0 2 25:53 87 64.2
35 24:46 24:55 24:58 1 25:37 42 157.3 2 24:58 0 0.0 2 24:58 0 0.0 1 24:55 0 0.0

表4

实验数据统计结果"

FCFS SGA SLSGA HLSGA
总延误成本 1648.5 1289.2 816.0 657.6
进港队列延误成本 831.9 678.3 47.3 234.5
离港队列延误成本 816.6 610.9 768.7 423.1
even(s,FAQ) 38.85 31.68 2.21 10.95
even(s, FDQ) 20.89 15.63 19.66 10.82
distance(s) 17.96 16.05 17.46 0.13

表5

FCFS各跑道航班序列"

r0 1 4 8 14 18 21 24 27 28 32 33
r1 2 6 10 12 15 17 20 22 26 29 31 35
进港 进港 进港 进港 进港 离港 离港 进港 离港 离港 离港 离港
r2 3 5 7 9 11 13 16 19 23 25 30 34

表6

HLSGA各跑道航班序列"

r0 1 4 8 10 15 18 21 24 27 28 33
r1 2 6 9 12 14 17 20 22 25 29 32 35 31
进港 进港 离港 进港 进港 离港 离港 进港 离港 离港 进港 离港 离港
r2 3 5 7 11 13 16 19 23 26 30 34

图1

延误费用曲线图"

图2

延误费用分配均匀度偏差曲线图"

1 吴薇薇，孟亭婷，张皓瑜 . 基于机场延误预测的航班计划优化研究. 交通运输系统工程与信息，2016，16(6)：189-195. (Wu W W，Meng T T，Zhang H Y. Flight plan optimization based on airport delay prediction. Journal of Transportation Systems Engineering and Information Technology，2016，16(6)：189-195.)
2 吴仁彪，赵婷，屈景怡 . 基于深度SE?DenseNet的航班延误预测模型. 电子与信息学报，2019，41(6)：1510-1517. (Wu R B，Zhao T，Qu J Y. Flight delay prediction model based on deep SE?DenseNet. Journal of Electronics and Information Technology，2019，41(6)：1510-1517.)
3 屈景怡，叶萌，渠星 . 基于区域残差和LSTM网络的机场延误预测模型. 通信学报，2019，40(4)：149-159. (Qu J Y，Ye M，Qu X. Airport delay prediction model based on regional residual and LSTM network. Journal on Communications，2019，40(4)：149-159.)
4 Cox J ， Kochenderfer M J . Optimization approaches to the single airport ground?holding problem. Journal of Guidance Control & Dynamics，2015，38(12)：1-8.
5 Cai K Q ， Zhang J ， Xiao M M ，et al . Simultaneous optimization of airspace congestion and flight delay in air traffic network flow management. IEEE Transactions on Intelligent Transportation Systems，2017，18(11)：3072-3082.
6 张洪海，胡明华 . CDM ADGDP机场容量与时隙协同配置. 系统工程理论与实践，2010，30(10)：1901- 1908. (Zhang H H，Hu M H. Collaborative allocation of capacity and slot in CDM ADGDP airport. Systems Engineering?Theory & Practice，2010，30(10)：1901-1908.)
7 张玉州，陈文莉，李锐 等 . 基于局部搜索机制MOGA的多目标ADGHP建模及优化. 系统仿真学报，2013，25(5)：962-968.
Zhang Y Z ， Chen W L ， Li R ，et al . Modeling and optimization for multi?objective ADGHP based on local search MOGA. Journal of System Simulation，2013，25(5)：962-968.
8 张玉州，李锐，江克勤 等 . 基于自适应多局部搜索memetic算法的多跑道地面等待问题求解. 系统工程理论与实践，2012，32(11)：2523-2532.
Zhang Y Z ， Li R ， Jiang K Q ，et al . Solution to multi?runway ground?holding problem based on adaptive multi?local search memetic algorithm. Systems Engineering ? Theory & Practice，2012，32(11)：2523-2532.
9 罗喜伶，张其善 . 起降容量受限的地面等待模型研究. 北京航空航天大学学报，2004，30(2)：127-130. (Luo X L，Zhang Q S. Research on GHP model with constrained departing and landing capacities. Journal of Beijing University of Aeronautics and Astronautics，2004，30(2)：127-130.)
10 魏云，王莉莉 . 多跑道机场离场航班推出时刻的优化研究. 交通运输工程与信息学报，2015，12(2)：70-73，79. (Wei Y，Wang L L. Research on the optimization of launch time of departure flights of multi?runway airport. Journal of Transportation Engineering and Information，2015，12(2)：70-73，79.)
11 吴家豪，彭志平，崔得龙 等 . 基于多Agent系统的粒子群遗传优化云工作流调度算法. 南京大学学报(自然科学)，2017，53(6)：1114-1124.
Wu J H ， Peng Z P ， Cui D L ，et al . Combining PSO and GA for workflow scheduling based on multi?agent system. Journal of Nanjing University (Natural Science)，2017，53(6)：1114-1124.
12 李二超，马玉泉 . 基于就近取值策略的离散多目标优化. 南京大学学报(自然科学)，2018，54(6)：1216-1224. (Li E C，Ma Y Q. Discrete multi?objective optimization based on the nearest value strategy. Journal of Nanjing University (Natural Science)，2018，54(6)：1216-1224.)
13 Donis?Díaz C A ， Muro A G ， Bello?Pérez R ，et al . A hybrid model of genetic algorithm with local search to discover linguistic data summaries from creep data. Expert Systems with Applications，2014，41(4)：2035-2042.
14 Eroglu D Y ， Ozmutlu H C ， Ozmutlu S . Genetic algorithm with local search for the unrelated parallel machine scheduling problem with sequence?dependent set?up times. International Journal of Production Research，2014，52(19)：5841-5856.
15 Hu X B ， Di Paolo E . An efficient genetic algorithm with uniform crossover for air traffic control. Computers & Operations Research，2009，36(1)：245-259.
16 徐肖豪，李雄 . 航班地面等待模型中的延误成本分析与仿真. 南京航空航天大学学报，2006，38(1)：115-120. (Xu X H，Li X. Cost analysis of flight delays and simulation in ground?holding model. Journal of Nanjing University of Aeronautics & Astronautics，2006，38(1)：115-120.)
[1] 信统昌,刘兆伟. 基于贝叶斯⁃遗传算法的多值无环CP⁃nets学习[J]. 南京大学学报(自然科学版), 2020, 56(1): 74-84.
[2] 李二超，马玉泉. 基于就近取值策略的离散多目标优化[J]. 南京大学学报(自然科学版), 2018, 54(6): 1216-1224.
[3] 吴家豪1，彭志平2*，崔得龙2，李启锐2，何杰光2. 基于多Agent系统的粒子群遗传优化云工作流调度算法[J]. 南京大学学报(自然科学版), 2017, 53(6): 1114-.
[4]  骆乾坤1，吴剑锋2*，杨　运2，3，吴吉春2，马淑芬4.  基于DREAM算法的含水层渗透系数空间变异特征识别[J]. 南京大学学报(自然科学版), 2016, 52(3): 448-455.
[5]  杨　蕴1，朱　琳2*，林　锦3，王锦国1.  考虑地面沉降约束的地下水模拟优化管理模型[J]. 南京大学学报(自然科学版), 2016, 52(3): 470-478.
[6] 周 涛1,2，陆惠玲1*，张艳宁2，马 苗2,3. 基于Rough Set的高维特征选择混合遗传算法研究[J]. 南京大学学报(自然科学版), 2015, 51(4): 880-893.
[7] 骆乾坤*，吴剑锋2，杨运3，钱家忠1. 渗透系数空间变异程度对进化算法优化结果影响评价[J]. 南京大学学报(自然科学版), 2015, 51(1): 60-66.
[8] 程春玲;李阳;张登银;. 基于遗传算法的层次化云资源监测方法[J]. 南京大学学报(自然科学版), 2013, 49(4): 491-499.
[9]  Markushev Dragan1，Rabasovic Mihailo1，Lukic Mladena2
Cojbasic Zarko3，Todorovic Dragan4
.  实时脉冲光声法用于分子弛豫时间的测定[J]. 南京大学学报(自然科学版), 2013, 49(1): 5-12.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 孙　玫，张　森，聂培尧，聂秀山. 基于朴素贝叶斯的网络查询日志session划分方法研究[J]. 南京大学学报(自然科学版), 2018, 54(6): 1132 -1140 .
[2] 周星星，张海平，吉根林. 具有时空特性的区域移动模式挖掘算法[J]. 南京大学学报(自然科学版), 2018, 54(6): 1171 -1182 .
[3] 韩明鸣, 郭虎升, 王文剑. 面向非平衡多分类问题的二次合成QSMOTE方法[J]. 南京大学学报(自然科学版), 2019, 55(1): 1 -13 .
[4] 刘　素, 刘惊雷. 基于特征选择的CP－nets结构学习[J]. 南京大学学报(自然科学版), 2019, 55(1): 14 -28 .
[5] 王伯伟, 聂秀山, 马林元, 尹义龙. 基于语义相似度的无监督图像哈希方法[J]. 南京大学学报(自然科学版), 2019, 55(1): 41 -48 .
[6] 孔　颉, 孙权森, 纪则轩, 刘亚洲. 基于仿射不变离散哈希的遥感图像快速目标检测新方法[J]. 南京大学学报(自然科学版), 2019, 55(1): 49 -60 .
[7] 贾海宁, 王士同. 面向重尾噪声的模糊规则模型[J]. 南京大学学报(自然科学版), 2019, 55(1): 61 -72 .
[8] 严云洋, 瞿学新, 朱全银, 李　翔, 赵　阳. 基于离群点检测的分类结果置信度的度量方法[J]. 南京大学学报(自然科学版), 2019, 55(1): 102 -109 .
[9] 阚　威, 李　云. 基于LSTM的脑电情绪识别模型[J]. 南京大学学报(自然科学版), 2019, 55(1): 110 -116 .
[10] 杨　蕴, 宋　健, 朱　琳, 吴剑锋, 王锦国. 基于KELM地面沉降替代模型的地下水多目标管理模型研究[J]. 南京大学学报(自然科学版), 2019, 55(3): 349 -360 .

版权所有 © 2021 《南京大学学报(自然科学)》

地址：江苏省南京市鼓楼区汉口路22号，南京大学学报编辑部，210093

电话：025-83592704 , 传真：025-83592704        技术支持：北京玛格泰克科技发展有限公司