基于混合整数规划的停机位优化调度研究

doi:10.11896/jsjkx.190400154

计算机科学 ›› 2020, Vol. 47 ›› Issue (8): 278-283.doi: 10.11896/jsjkx.190400154

基于混合整数规划的停机位优化调度研究

张红颖¹, 申荣苗¹, 罗谦²

1 中国民航大学电子信息与自动化学院天津 300300
2 中国民用航空总局第二研究所成都 610041

出版日期:2020-08-15 发布日期:2020-08-10
通讯作者: 张红颖(carole_zhang0716@163.com)
基金资助:
国家自然科学基金民航联合研究基金重点项目(U1533203)

Study on Optimal Scheduling of Gate Based on Mixed Integer Programming

ZHANG Hong-ying¹, SHEN Rong-miao¹, LUO Qian²

1 College of Electronic Information and Automation, Civil Aviation University of China, Tianjin 300300, China
2 The Second Research Institute of Civil Aviation Administration of China, Chengdu 610041, China

Online:2020-08-15 Published:2020-08-10
About author:ZHANG Hong-ying, born in 1978, Ph.D, professor, postgraduate supervisor.Her main research interests include airport intelligence and automation technology.
Supported by:
This work was supported by the Key Projects of the Civil Aviation Joint Fund of the National Natural Science Foundation of China(U1533203).

摘要/Abstract

摘要： 为有效缓解机场航空器延误现状, 系统地研究了机场停机位优化调度问题。通过深入剖析机场地面运行特性, 综合考虑航空器机型匹配、缓冲时间和航空器冲突等约束限制, 科学合理地权衡机场各种利益需求, 提出优化停机位调度问题的混合整数规划模型, 主要目标是在确保航空器安全运行的前提下, 使得航班延误的总时间最短。该模型引入了概率分布函数, 以避免航空器冲突的发生, 结合多目标优化及分支界定算法的基本理论, 寻求最优的分配方案。仿真实验表明, 模型对机场预计进港航空器时间进行优化排序, 通过优化调度方案调整停机位分配冲突, 得到最优的分配方案。该算法能够缩小搜索空间, 提高求解效率, 显著减低延误总时间, 提高机场停机位的资源利用率。与启发式算法相比, 所提算法可使航空器延误减少2.4%, 因此该方法能够有效降低机场地面航班延误率。

关键词: 分支界定算法, 概率分布函数, 航班延误, 混合整数规划, 停机位调度

Abstract: In order to alleviate effectively the current situation of airport aircraft delay, the optimal scheduling of airport gate is studied.By deeply analyzing the characteristics of airport ground operation, considering the constraint restrictions such as aircraft model matching, buffer time and aircraft conflict, scientifically and reasonably weighing the various interest needs of the airport, this paper proposes a mixed integer programming model to optimize the gate scheduling problem, the main goal is to ensure the safe operation of the aircraft under the premise, so that the total flight delay time is the shortest.The probability distribution function is introduced to avoid the occurrence of aircraft conflict.Combining with the basic theory of multi-objective optimization and branching definition algorithm, the optimal assignment schemeis sought.The simulation results show that the model optimizes the timing of the expected inbound aircraft in the airport, adjusts the position allocation conflict by optimizing the scheduling scheme, and gets the optimal allocation scheme.The algorithm can reduce the search space, improve the efficiency of the solution, significantly reduce the total delay time, and improve the utilization rate of airport gate resources.Compared with heuristic algorithm, the aircraft delay is reduced by 2.4%, and the proposed method caneffectively reduce the delay rate of airport ground flight.

Key words: Branch-and-cut method, Flightdelay, Gate scheduling, Mixed integer programming, Probability distribution function

中图分类号:

TP391.9

张红颖, 申荣苗, 罗谦. 基于混合整数规划的停机位优化调度研究[J]. 计算机科学, 2020, 47(8): 278-283. https://doi.org/10.11896/jsjkx.190400154

ZHANG Hong-ying, SHEN Rong-miao, LUO Qian. Study on Optimal Scheduling of Gate Based on Mixed Integer Programming[J]. Computer Science, 2020, 47(8): 278-283. https://doi.org/10.11896/jsjkx.190400154

参考文献

[1]DENG W, SUN M, ZHAO H, et al.Study on an airport gate assignment method based on improved ACOalgorithm[J].Kybernetes, 2018, 47(1):20-43.
[2]LIU L H, ZHANG Y P, XING Z W, et al.Optimization of aircraft pushback decision based on discrete differential evolution[J].Journal of Transportation Systems Engineering and information technology, 2016, 16(6):196-203.
[3]ZHANG J R, WANG G, TONG S Y.Research on Flight First Service Model and Algorithms for the Gate Assignment Problem[J].CMC-Computers, Materials & Continua, 2019, 61(3):1091-1104.
[4]ZHAO J M, WU W J, LIU Z M, et al.Airport gate assignment problem with deep reinforcement learning[J].High Technology Letters, 2020, 26(1):102-107.
[5]LI Z, WANG Z X, SUI H.Research on the Evaluation IndexSystem of Operational Support Effectiveness of Military Airport Facilities[J].Journal of Chongqing University of Technology (Natural Science), 2018, 32(9):209-216.

[6]DORNDORF U, JAEHN F, PESCH E.Flight gate assignment and recovery strategies with stochastic arrival and departure times[J].Or Spectrum, 2016, 39(1):1-29.
[7]BOURAS A, GHALEB M A, SURYAHATMAJA U S, et al.The airport gate assignment problem:a survey[J].Scientific World Journal, 2014, 2014(6):9165-9172.
[8]CHENG C H, HO S C, KWAN C L.The use of meta-heuristics for airport gate assignment[J].Expert Systems with Applications, 2012, 39(16):12430-12437.
[9]YU C, ZHANG D, LAU H Y K.An adaptive large neighborhoodsearch heuristic for solving a robust gate assignmentproblem[J].Expert Systems with Applications, 2017, 84:143-154.
[10]ZHANG J, CHEN Q, SUN G, et al.Disruption Scheduling ofAirport Gate Based on Tabu Search Algorithm[C]∥Control Conference, 2014(CCC).IEEE, 2014:84-88.
[11]NEUMAN U M, ATKIN J A D.Airport Gate Assignment Considering Ground Movement[J].Lecture Notes in Computer Science, 2013, 8197:184-198.
[12]LI D.Research on batch scheduling problem with non-identical job sizes using ant colony optimization algorithm[D].Hefei:Anhui University, 2014.
[13]LI Y L, LI Y.Aircraft stands assignment optimization based on variable tabu length[J].Journal of Computer Applications, 2016, 36(10):2940-2944.
[14]WANG Y H, ZHU J F, ZHU B, et al.Mixed collection planning method for seat allocation in busy airports[J].Journal of Wuhan University of Technology(Information & Management Engineering), 2015, 37(4):427-431.
[15]BOURAS A, GHALEB M A, SURYAHATMAJA U S, et al.The Airport Gate Assignment Problem:A Survey[J].Scientific World Journal, 2014, 27(6):9165-9172.
[16]PANG M B, ZHANG S L, LI C X.Bi-level programming of urban bus stop locating[J].Journal of Highway and Transportation Research and Development, 2013, 30(3):118-124.
[17]PREM KUMAR V, BIERLAIRE M.Multi-objective airportgate assignment problem in planning and operations[J].Journal of Advanced Transportation, 2015, 48(7):902-926.
[18]SANG H K, FERON E.Impact of Gate Assignment on Departure Metering[J].IEEE Transactions on Intelligent Transportation Systems, 2014, 15(2):699-709.
[19]GUPET J, ACUNA-AGOST R, BRIANT O, et al.Exact and Heuristic Approaches to the Airport Stand Allocation Problem[J].European Journal of Operational Research, 2015, 246(2):597-608.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于混合整数规划的停机位优化调度研究

Study on Optimal Scheduling of Gate Based on Mixed Integer Programming

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

Metrics

本文评价

推荐阅读 0

[1]	郑斐峰, 蒋娟, 梅启煌. 最小化集装箱运输成本的配载优化 Study on Stowage Optimization in Minimum Container Transportation Cost 计算机科学, 2019, 46(6): 239-245. https://doi.org/10.11896/j.issn.1002-137X.2019.06.036
[2]	罗凤娥,张成伟,刘安. 基于数据挖掘的航班延误预警管理分析 Flight Delays Early Warning Management and Analysis Based on Data Mining 计算机科学, 2016, 43(Z6): 542-546. https://doi.org/10.11896/j.issn.1002-137X.2016.6A.129
[3]	赵晔，周畅，王昌. 一种随机采样的特征保持的网格简化算法 Feature Preserved Mesh Simplification Algorithm Based on Stochastic Sampling 计算机科学, 2011, 38(5): 249-251.
[4]	徐涛,荣耀,王建东. 基于SOA的民航航班延误波及分析与预警系统 Flight Delay Propagation Analyzing and Predicting System of Civil Aviation of China Based on SOA 计算机科学, 2009, 36(7): 157-160. https://doi.org/10.11896/j.issn.1002-137X.2009.07.037
[5]	. 航班延误波及链的有色出现网模型计算机科学, 2009, 36(2): 241-244.