不确定容量下时隙分配问题两阶段规划模型

亓尧; 王瑛; 梁颖; 姚頔

doi:10.13700/j.bh.1001-5965.2018.0757

不确定容量下时隙分配问题两阶段规划模型

doi: 10.13700/j.bh.1001-5965.2018.0757

亓尧¹,
王瑛^1, ,,
梁颖²,
姚頔³

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

基金项目:

国家自然科学基金 71601183

详细信息

作者简介:
亓尧男, 博士研究生。主要研究方向:不确定理论、空域资源规划

王瑛女，博士，教授，博士生导师。主要研究方向：装备系统工程、不确定理论

通讯作者:
王瑛, E-mail: yingwangkgd@163.com

中图分类号: V355
计量
- 文章访问数: 626
- HTML全文浏览量: 77
- PDF下载量: 230
- 被引次数: 0
出版历程
- 收稿日期: 2018-12-25
- 录用日期: 2019-02-02
- 网络出版日期: 2019-09-20

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

QI Yao¹,
WANG Ying^{1
, ,},
LIANG Ying²,
YAO Di³

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

Funds:

National Natural Science Foundation of China 71601183

More Information

Corresponding author: WANG Ying, E-mail:yingwangkgd@163.com

摘要

摘要:
恶劣天气等不确定环境下，传统时隙分配方法易造成航班大量延误现象，为解决这一问题，分析了时隙分配过程，基于不确定理论，从权衡"请求时隙-计划时隙差"和"计划时隙-运行时隙差"的角度，提出了不确定容量下的时隙分配两阶段规划模型，分别构建了单机场模型和多机场模型。根据模型特点，设计了基于人工蜂群（ABC）算法的渐进二元启发式方法，提升了求解效率。通过算例分析，验证了所提模型和方法的有效性，同时对模型参数设置进行了分析。
- 时隙分配 /
- 两阶段规划 /
- 不确定理论 /
- 人工蜂群(ABC)算法 /
- 启发式计算
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.
- time slot allocation /
- two-stage programming /
- uncertainty theory /
- artificial bee colony (ABC) algorithm /
- heuristic calculation

HTML全文

图 1 时隙分配的2个阶段

Figure 1. Two stages of time slot allocation

下载: 全尺寸图片幻灯片

图 2 基于ABC算法的渐进二元启发式方法计算框架

Figure 2. Progressive binary heuristic method computation framework based on ABC algorithm

下载: 全尺寸图片幻灯片

图 3 时隙分配优化百分比示意图

Figure 3. Schematic diagram of time slot allocation optimization percentage

下载: 全尺寸图片幻灯片

表 1 航班时隙请求

Table 1. Request of flight time slot

(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

下载: 导出CSV

表 2 联程航班

Table 2. Connecting flights

联程航班对	最小周转时间/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

下载: 导出CSV

表 3 机场两阶段容量

Table 3. Airport capacity in two stages

时段	第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

下载: 导出CSV

表 4 ABC算法控制参数设置

Table 4. Control parameter setting of ABC algorithm

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

下载: 导出CSV

表 5 时隙分配结果

Table 5. Results of time slot allocation

时段	两阶段模型			传统模型
时段	请求时隙-计划时隙差	计划时隙-运行时隙差	合计	请求时隙-计划时隙差	计划时隙-运行时隙差	合计
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

下载: 导出CSV

表 6 算例规模

Table 6. Scale of computation samples

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

下载: 导出CSV

表 7 模型结果对比

Table 7. Model result comparison

机场群	权重系数	与传统模型对比
机场群	权重系数	请求时隙-计划时隙差增加值	运行延误减少值	时隙分配优化百分比
京津冀	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

下载: 导出CSV

参考文献(31)

[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. http://www.cnki.com.cn/Article/CJFDTotal-NJHK4S1.004.htm 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). http://www.cnki.com.cn/Article/CJFDTotal-NJHK4S1.004.htm
[16]	周茜, 张学军, 柳重堪.时隙分配算法在CDM GDP程序中的应用[J].北京航空航天大学学报, 2006, 32(9):1043-1045. doi: 10.3969/j.issn.1001-5965.2006.09.011 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(in Chinese). doi: 10.3969/j.issn.1001-5965.2006.09.011
[17]	徐肖豪, 王飞.地面等待策略中的时隙分配模型与算法研究[J].航空学报, 2010, 31(10):1993-2003. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=hkxb201010013 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). http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=hkxb201010013
[18]	张洪海, 胡明华.CDM ADGDP机场容量与时隙协同配置[J].系统工程理论与实践, 2010, 30(10):1901-1908. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=xtgcllysj201010022 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). http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=xtgcllysj201010022
[19]	田勇, 李永庆, 万莉莉, 等.基于市场机制的地面等待时隙分配方法[J].系统工程理论与实践, 2014, 34(6):1614-1619. http://d.old.wanfangdata.com.cn/Periodical/xtgcllysj201406030 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). http://d.old.wanfangdata.com.cn/Periodical/xtgcllysj201406030
[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. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=48385055 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). http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=48385055
[25]	乐美龙, 李星灿, 高金敏.机场到达时刻数量决策随机模型[J].系统工程理论与实践, 2017, 37(11):2948-2954. doi: 10.12011/1000-6788(2017)11-2948-07 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(in Chinese). doi: 10.12011/1000-6788(2017)11-2948-07
[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. doi: 10.3969/j.issn.1671-654X.2018.01.002 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(in Chinese). doi: 10.3969/j.issn.1671-654X.2018.01.002
[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).