留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

亓尧 王瑛 梁颖 姚頔

亓尧, 王瑛, 梁颖, 等 . 不确定容量下时隙分配问题两阶段规划模型[J]. 北京航空航天大学学报, 2019, 45(9): 1747-1756. doi: 10.13700/j.bh.1001-5965.2018.0757
引用本文: 亓尧, 王瑛, 梁颖, 等 . 不确定容量下时隙分配问题两阶段规划模型[J]. 北京航空航天大学学报, 2019, 45(9): 1747-1756. doi: 10.13700/j.bh.1001-5965.2018.0757
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)

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

doi: 10.13700/j.bh.1001-5965.2018.0757
基金项目: 

国家自然科学基金 71601183

详细信息
    作者简介:

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

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

    通讯作者:

    王瑛, E-mail: yingwangkgd@163.com

  • 中图分类号: V355

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

Funds: 

National Natural Science Foundation of China 71601183

More Information
  • 摘要:

    恶劣天气等不确定环境下,传统时隙分配方法易造成航班大量延误现象,为解决这一问题,分析了时隙分配过程,基于不确定理论,从权衡"请求时隙-计划时隙差"和"计划时隙-运行时隙差"的角度,提出了不确定容量下的时隙分配两阶段规划模型,分别构建了单机场模型和多机场模型。根据模型特点,设计了基于人工蜂群(ABC)算法的渐进二元启发式方法,提升了求解效率。通过算例分析,验证了所提模型和方法的有效性,同时对模型参数设置进行了分析。

     

  • 图 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
  • [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).
  • 加载中
图(3) / 表(7)
计量
  • 文章访问数:  428
  • HTML全文浏览量:  6
  • PDF下载量:  223
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-12-25
  • 录用日期:  2019-02-02
  • 刊出日期:  2019-09-20

目录

    /

    返回文章
    返回
    常见问答