﻿ 不确定容量下时隙分配问题两阶段规划模型<sup>*</sup>
 文章快速检索 高级检索

1. 空军工程大学 装备管理与无人机工程学院, 西安 710043;
2. 空军研究院, 北京 100089;
3. 国家空域管理中心, 北京 100091

Two-stage programming model for time slot allocation problem under uncertain capacity
QI Yao1, WANG Ying1, LIANG Ying2, YAO Di3
1. Equipment Management and UAV Engineering College, Air Force Engineering University, Xi'an 710043, China;
2. Air Force Research Institute, Beijing 100089, China;
3. National Flight Flow Monitoring Center, Beijing 100091, China
Received: 2018-12-25; Accepted: 2019-02-02; Published online: 2019-02-26 09:26
Foundation item: National Natural Science Foundation of China (71601183)
Corresponding author. WANG Ying, E-mail:yingwangkgd@163.com
Abstract: In uncertain environment such as bad weather, it is easy to cause a large number of flight delays by the traditional time slot allocation method. To solve this problem, the time slot allocation process is first analyzed. Then a two-stage programming model for time slot allocation under uncertain capacity based on the uncertainty theory is proposed, including a single-airport model and a multi-airport model. The models highlight the tradeoff between the schedule slot/request slot discrepancies and operation slot/schedule slot discrepancies. According to the characteristics of the model, a progressive binary heuristic calculation method based on artificial bee colony (ABC) algorithm is designed to improve the efficiency of the solution. The validity of the model and algorithm is verified by the case study, and the model parameter setting is analyzed.
Keywords: time slot allocation     two-stage programming     uncertainty theory     artificial bee colony (ABC) algorithm     heuristic calculation

1 问题描述与建模 1.1 问题定义

 图 1 时隙分配的2个阶段 Fig. 1 Two stages of time slot allocation

1.2 单机场模型

 (1)

 (2)
 (3)
 (4)
 (5)
 (6)
 (7)
 (8)

 (9)

 (10)
 (11)
 (12)
 (13)
 (14)
 (15)
 (16)

1.3 多机场模型

 (17)

 (18)
 (19)
 (20)
 (21)
 (22)
 (23)
 (24)
 (25)

 (26)

 (27)
 (28)
 (29)
 (30)
 (31)
 (32)
 (33)
 (34)

2 方法设计

2.1 渐进二元启发式方法框架

2.2 基于ABC算法的求解器设计

2.1节提出了求解两阶段0-1整数规划模型的渐进二元启发式方法，从方法框架中可以看出，步骤2和步骤7都要进行问题求解，考虑到时隙分配问题特别是多机场时隙分配问题规模大的特点，本文将ABC算法引入到渐进二元启发式方法框架，作为求解器用于步骤2和步骤7的求解。

ABC算法是2005年Karaboga[30]通过模拟工蜂采蜜的整个过程提出的一种新型智能优化算法，与其他智能优化算法相比，其具有结构简单、易于实现、参数较少、鲁棒性强等优点[31]

 图 2 基于ABC算法的渐进二元启发式方法计算框架 Fig. 2 Progressive binary heuristic method computation framework based on ABC algorithm
3 算例验证

3.1 单机场模型算例验证

3.1.1 初始数据

 (a)进场航班 航班 时隙 航班 时隙 A1 10:00 A16 11:05 A2 10:05 A17 11:10 A3 10:10 A18 11:15 A4 10:15 A19 11:20 A5 10:20 A20 11:20 A6 10:25 A21 11:25 A7 10:35 A22 11:30 A8 10:35 A23 11:35 A9 10:40 A24 11:40 A10 10:50 A25 11:40 A11 10:50 A26 11:40 A12 10:55 A27 11:40 A13 11:00 A28 11:50 A14 11:00 A29 11:55 A15 11:00 A30 11:55 (b)离场航班 航班 时隙 航班 时隙 D1 10:00 D21 10:50 D2 10:00 D22 10:55 D3 10:05 D23 10:55 D4 10:05 D24 11:00 D5 10:10 D25 11:00 D6 10:10 D26 11:00 D7 10:15 D27 11:05 D8 10:15 D28 11:10 D9 10:15 D29 11:15 D10 10:20 D30 11:20 D11 10:20 D31 11:20 D12 10:20 D32 11:25 D13 10:25 D33 11:30 D14 10:25 D34 11:30 D15 10:30 D35 11:30 D16 10:30 D36 11:35 D17 10:30 D37 11:45 D18 10:35 D38 11:45 D19 10:40 D39 11:50 D20 10:45 D40 11:55

 联程航班对 最小周转时间/min A1, D12 25 A4, D18 25 A7, D20 30 A10, D27 30 A15, D28 20 A16, D30 20 A20, D38 30 A22, D40 25

 时段 第1阶段不确定容量分布 第2阶段容量实现值 进场 离场 机场 进场 离场 机场 10:00—10:30 4 7 10 10:30—11:00 3 6 8 11:00—11:30 2 5 6 11:30—12:00 4 6 9

3.1.2 仿真结果

 控制参数 取值 种群规模 100 最大循环次数 1 000 最大限制搜索次数 50 观察蜂数量 种群规模的一半 采蜜蜂数量 种群规模的一半 侦察蜂数量 1

 时段 两阶段模型 传统模型 请求时隙-计划时隙差 计划时隙-运行时隙差 合计 请求时隙-计划时隙差 计划时隙-运行时隙差 合计 10:00—10:15 0 0 0 0 0 0 10:15—10:30 1 0 1 0 1 1 10:30—10:45 0 0 0 0 1 1 10:45—11:00 0 0 0 0 0 0 11:00—11:15 3 1 4 0 4 4 11:15—11:30 3 2 5 0 6 6 11:30—11:45 4 2 6 0 7 7 11:45—12:00 2 2 4 0 5 5 总计 13 7 20 0 24 24

3.1.3 结果分析

3.2 多机场模型算例验证

1) 京津冀。北京首都国际机场(ZBAA)、天津滨海国际机场(ZBTJ)、石家庄正定国际机场(ZBSJ)。

2) 长三角。上海浦东国际机场(ZSPD)、上海虹桥国际机场(ZSSS)、南京禄口国际机场(ZSNJ)、杭州萧山国际机场(ZSHC)、合肥新桥国际机场(ZSOF)。

3) 珠三角。广州白云国际机场(ZGGG)、深圳宝安国际机场(ZGSZ)、珠海金湾机场(ZGSD)。

3.2.1 初始数据及仿真结果

 机场群 航班数量 进场航班数量 离场航班数量 京津冀 248 82 166 长三角 372 137 235 珠三角 309 84 225

 机场群 权重系数 与传统模型对比 请求时隙-计划时隙差增加值 运行延误减少值 时隙分配优化百分比 京津冀 1 36 51 15.3 3 67 176 66.9 长三角 1 63 91 10.3 3 102 516 62.5 珠三角 1 75 139 62.7 3 81 445 71.3

 图 3 时隙分配优化百分比示意图 Fig. 3 Schematic diagram of time slot allocation optimization percentage

3.2.2 结果分析

4 结论

1) 本文提出的不确定容量下时隙分配两阶段规划单机场模型和多机场模型符合时隙分配两阶段过程，以航班而不是航班数为变量，将两阶段规划模型从单机场推广到多机场，与传统时隙分配模型相比，能够有效地对时隙分配结果进行优化。

2) 本文设计的基于ABC算法的渐进二元启发式方法，充分考虑了模型的二进制特点，从原问题的松弛问题出发，渐进增加二进制约束，降低了模型求解复杂度；利用ABC算法结构简单、易于实现、参数较少、鲁棒性强的优点，将ABC算法设计为启发式计算求解器，算例证明，方法可以有效地对模型进行求解。

3) 算例对模型和方法进行了可行性和有效性验证。算例结果显示，在单机场和多机场情况下，本文模型均体现了较大优势；同时，模型权重系数越大，本文模型优势越大，对时隙分配结果提升效果越大。

 [1] 中国民用航空局.2015年民航行业发展统计公报[EB/OL].(2016-05-30)[2018-12-24].http://www.caac.gov.cn/XXGK/XXGK/TJSJ/201605/t20160530_37643.html. Civil Aviation Administration of China. 2015 civil aviation industry development statistics bulletin[EB/OL].(2016-05-30)[2018-12-24].http://www.caac.gov.cn/XXGK/XXGK/TJSJ/201605/t20160530_37643.html (in Chinese). [2] 中国民用航空局, 国家发展和改革委, 交通运输部.中国民用航空发展第十三个五年规划[EB/OL].(2017-02-15)[2018-12-24].http://www.caac.gov.cn/XXGK/XXGK/FZGH/201704/t20170405_43502.html. Civil Aviation Administration of China, National Development and Reform Commission, Ministry of Transport. The Thirteenth Five-Year Plan for the development of civil aviation in China[EB/OL].(2017-02-15)[2018-12-24].http://www.caac.gov.cn/XXGK/XXGK/FZGH/201704/t20170405_43502.html(in Chinese). [3] 中国民用航空局运行监控中心.2017年全国民航航班运行效率报告[EB/OL].(2018-03-01)[2018-12-24].http://www.caac.gov.cn/XWZX/MHYW/201803/t20180328_56080.html. Operation Monitoring Center of Civil Aviation Administration of China. 2017 national civil aviation flight operation efficiency report[EB/OL].(2018-03-01)[2018-12-24].http://www.caac.gov.cn/XWZX/MHYW/201803/t20180328_56080.html(in Chinese). [4] HOFFMAN R L.Integer programming models for ground-holding in air traffic flow management[D].City of College Park: University of Maryland, 1997. [5] HOFFMAN R L, HALL W, BALL M O, et al.Collaborative decision making in air traffic flow management[R].Berkeley: University of California, Berkeley, 1999. [6] VOSSEN T W.Fair allocation methods in air traffic management[D].City of College Park: University of Maryland, 2002. [7] BALL M O, HOFFMAN R L, VOSSEN T. An analysis of resource rationing methods for collaborative decision making[C]//Proceeding of ATM 2002-System Architectures and CNS Technologies Needed to Cope with the Air Traffic Capacity Problem and Related Evaluation Tools, 2002: 64-70. [8] MADAS M A, ZOGRAFOS K G. Airport slot allocation:From instruments to strategies[J]. Journal of Air Transport Management, 2006, 12(2): 53-62. DOI:10.1016/j.jairtraman.2005.08.001 [9] ODONI A R.The flow management problem in air traffic control[M]//ODONI A R, BIANCO L, GIORGIO S.Flow control of congested networks.Berlin: Springer, 1987: 269-288. [10] TERRAB M, ODONI A, DEUTSCH O.Ground-holding strategies for ATC flow control[C]//AIAA Guidance, Navigation and Control Conference.Reston: AIAA, 1989: 1635-1646. [11] GILBO E P. Optimizing airport capacity utilization in air traffic flow management subject to constraints at arrival and departure fixes[J]. IEEE Transactions on Control Systems Technology, 1997, 5(5): 490-503. DOI:10.1109/87.623035 [12] OUSSEDIK S, DELAHAYE D.Reduction of air traffic congestion by genetic algorithms[C]//International Conference on Parallel Problem Solving from Nature.Berlin: Springer, 1998: 855-864. [13] PULUGURTHA S S, NAMBISAN S S. Using genetic algorithms to evaluate aircraft ground holding policy in real time[J]. Journal of Transportation Engineering, 2001, 127(5): 442-448. DOI:10.1061/(ASCE)0733-947X(2001)127:5(442) [14] MADAS M A, ZOGRAFOS K G. Airport slot allocation:A time for change?[J]. Transport Policy, 2010, 17(4): 274-285. DOI:10.1016/j.tranpol.2010.02.002 [15] 胡明华, 徐肖豪. 空中交通流量控制的地面保持策略[J]. 南京航空航天大学学报, 1994, 26(增刊): 26-30. HU M H, XU X H. Ground-holding strategies for ATC flow control[J]. Journal of Nanjing University of Aeronautics and Astronautics, 1994, 26(S): 26-30. (in Chinese) [16] 周茜, 张学军, 柳重堪. 时隙分配算法在CDM GDP程序中的应用[J]. 北京航空航天大学学报, 2006, 32(9): 1043-1045. ZHOU Q, ZHANG X J, LIU Z K. Slots allocation in CDM GDP[J]. Journal of Beijing University of Aeronautics and Astronautics, 2006, 32(9): 1043-1045. DOI:10.3969/j.issn.1001-5965.2006.09.011 (in Chinese) [17] 徐肖豪, 王飞. 地面等待策略中的时隙分配模型与算法研究[J]. 航空学报, 2010, 31(10): 1993-2003. XU X H, WANG F. Research on slot allocation models and algorithms in ground holding policy[J]. Acta Aeronautica et Astronautica Sinica, 2010, 31(10): 1993-2003. (in Chinese) [18] 张洪海, 胡明华. CDM ADGDP机场容量与时隙协同配置[J]. 系统工程理论与实践, 2010, 30(10): 1901-1908. ZHANG H H, HU M H. Collaborative allocation of capacity and slot in CDM ADGDP airport[J]. Systems Engineering-Theory & Practice, 2010, 30(10): 1901-1908. (in Chinese) [19] 田勇, 李永庆, 万莉莉, 等. 基于市场机制的地面等待时隙分配方法[J]. 系统工程理论与实践, 2014, 34(6): 1614-1619. TIAN Y, LI Y Q, WAN L L, et al. Slot allocation based on market mechanism in ground holding policy[J]. Systems Engineering-Theory & Practice, 2014, 34(6): 1614-1619. (in Chinese) [20] 刘丽华.市场机制下飞机推出时隙分配模型与算法研究[D].哈尔滨: 哈尔滨工业大学, 2017. LIU L H.Research on model and algorithm for aircraft pushback slot allocation under market mechanism[D].Harbin: Harbin Institute of Technology, 2017(in Chinese). [21] ANDREATTA G, ROMANIN-JACUR G. Aircraft flow management under congestion[J]. Transportation Science, 1987, 21(4): 249-253. DOI:10.1287/trsc.21.4.249 [22] RICHETTA O, ODONI A R. Solving optimally the static ground-holding policy problem in air traffic control[J]. Transportation Science, 1993, 27(3): 228-238. DOI:10.1287/trsc.27.3.228 [23] MUKHERJEE A, HANSEN M M. A dynamic stochastic model for the single airport ground holding problem[J]. Transportation Science, 2007, 41(4): 444-456. DOI:10.1287/trsc.1070.0210 [24] 杨尚文, 胡明华, 张洪海. 随机型协同时隙分配模型[J]. 系统工程理论与实践, 2014, 34(1): 153-157. YANG S W, HU M H, ZHANG H H. Stochastic collaborative slot allocation models[J]. Systems Engineering-Theory & Practice, 2014, 34(1): 153-157. (in Chinese) [25] 乐美龙, 李星灿, 高金敏. 机场到达时刻数量决策随机模型[J]. 系统工程理论与实践, 2017, 37(11): 2948-2954. LE M L, LI X C, GAO J M. Stochastic model of determining airport arrival slots number[J]. Systems Engineering-Theory & Practice, 2017, 37(11): 2948-2954. DOI:10.12011/1000-6788(2017)11-2948-07 (in Chinese) [26] COROLLI L, LULLI G, NTAIMO L. The time slot allocation problem under uncertain capacity[J]. Transportation Research Part C:Emerging Technologies, 2014, 46: 16-29. DOI:10.1016/j.trc.2014.05.004 [27] 岳仁田, 赵胖胖, 赵嶷飞. 带补偿的两阶段随机规划航班时隙分配研究[J]. 航空计算技术, 2018, 48(1): 4-8. YUE R T, ZHAO P P, ZHAO Y F. Study on slot allocation based on two-stage stochastic programming with recourse[J]. Aeronautical Computing Technique, 2018, 48(1): 4-8. DOI:10.3969/j.issn.1671-654X.2018.01.002 (in Chinese) [28] LIU B. Uncertainty theory[M]. 4th ed. Berlin: Springer, 2015: 111-130. [29] ZHENG M F, YUAN Y, WANG Z T, et al. Study on two-stage uncertain programming based on uncertainty theory[J]. Journal of Intelligent Manufacturing, 2017, 28(3): 633-642. DOI:10.1007/s10845-014-1012-6 [30] KARABOGA D.An idea based on honey bee swarm for numerical optimization[R].Kayseri: Erciyes University, 2005. [31] 江铭炎, 袁东风. 人工蜂群算法及其应用[M]. 北京: 科学出版社, 2014: 47-55. JIANG M Y, YUAN D F. Artificial bee colony algorithm and its application[M]. Beijing: Science Press, 2014: 47-55. (in Chinese)

#### 文章信息

QI Yao, WANG Ying, LIANG Ying, YAO Di

Two-stage programming model for time slot allocation problem under uncertain capacity

Journal of Beijing University of Aeronautics and Astronsutics, 2019, 45(9): 1747-1756
http://dx.doi.org/10.13700/j.bh.1001-5965.2018.0757