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

QI Yao; WANG Ying; LIANG Ying; YAO Di

doi:10.13700/j.bh.1001-5965.2018.0757

Volume 45 Issue 9

Sep. 2019

Turn off MathJax

Article Contents

Journal of Beijing University of Aeronautics and Astronautics > 2019 > 45(9): 1747-1756.

QI Yao, WANG Ying, LIANG Ying, et al. Two-stage programming model for time slot allocation problem under uncertain capacity[J]. Journal of Beijing University of Aeronautics and Astronautics, 2019, 45(9): 1747-1756. doi: 10.13700/j.bh.1001-5965.2018.0757(in Chinese)

Citation:

QI Yao, WANG Ying, LIANG Ying, et al. Two-stage programming model for time slot allocation problem under uncertain capacity[J]. Journal of Beijing University of Aeronautics and Astronautics, 2019, 45(9): 1747-1756. doi: 10.13700/j.bh.1001-5965.2018.0757(in Chinese)

Citation:

PDF( 2333 KB)

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

doi: 10.13700/j.bh.1001-5965.2018.0757

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
Received Date: 25 Dec 2018
Accepted Date: 02 Feb 2019
Publish Date: 20 Sep 2019

Abstract

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

FullText(HTML)

References(31)

References

[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).