基于复合分派规则的进场航班排序方法

张军峰; 郑志祥; 葛腾腾

基于复合分派规则的进场航班排序方法

南京航空航天大学民航学院, 江苏南京 210016

基金项目:

国家自然科学基金项目 71401072

江苏省自然科学基金项目 BK20130814

详细信息

作者简介:
张军峰(1979-), 男, 江苏建湖人, 南京航空航天大学副教授, 工学博士, 从事空管研究

中图分类号: V355.2
计量
- 文章访问数: 670
- HTML全文浏览量: 140
- PDF下载量: 511
- 被引次数: 0
出版历程
- 收稿日期: 2017-02-23
- 刊出日期: 2017-06-25

Sequencing approach of arrival aircrafts based on composite dispatching rules

School of Civil Aviation, Nanjing University of Aeronautics and Astronauticss, Nanjing 210016, Jiangsu, China

More Information

Author Bio:
ZHANG Jun-feng(1979-), male, associate professor, PhD, +86-25-84893421, zhangjunfeng@nuaa.edu.cn

摘要

摘要: 为解决航班延误问题, 提出了基于复合分派规则的进场航班排序方法。基于机器调度理论, 将最小化加权总延误为目标的进场航班排序问题等效为最小化加权总滞后的机器调度问题; 考虑顺序决定的准备时间约束、提交时间约束与最后期限约束, 构建了进场航班排序模型; 引入加权最短加工时间因子、松弛因子、准备时间因子、提交时间因子与最后期限因子, 提出了进场航班排序的复合分派规则, 设计了进场航班排序的启发式算法; 基于实际案例, 对比了采用提出的排序方法、先到先服务规则与Lingo软件得到的进场加权总延误、总延误与最大延误。计算结果表明: 提出的排序方法在30架次航班数值仿真中, 加权总延误比先到先服务规则缩短了31min, 延误航班数量减少了6架次; 在以上海浦东机场北向运行为场景的实际案例验证中, 基于排序方法的优化降落时间与Lingo软件的仿真结果相同, 与实际降落时间相比, 平均每架次航班提前了2.4min降落。
- 航空运输 /
- 进场航班排序 /
- 机器调度 /
- 复合分派规则 /
- 启发式算法
Abstract: To alleviate the flight delay problem, a sequencing approach of arrival aircrafts was proposed based on composite dispatching rules. Based on the machine scheduling theory, the sequencing problem of arrival aircrafts with the target of minimizing weighted total delay was transformed into the machine scheduling problem with the target of minimizing weighted total tardiness. The order-depended time constraint, submitted time constraint and deadline constraint were considered, and the sequencing model of arrival aircrafts was constructed. Through introducing the weighted shortest processing time factor, slack term factor, setup time factor, release time factor and deadline factor, the composite dispatching rule for the sequencing was presented, and a heuristic algorithm for the sequencing was developed. Based on real case, the weighted total delays, total delays and maximum delays of arrival aircrafts computed by using the proposed sequencing approach, first-come-first-service rule and Lingo software were compared. Computation result shows that in the numerical simulation with 30 arrival aircrafts, when the proposed method was compared with the first-come-first-service rule, the weighted total delay reduces by 31 min, and the number of delayed aircrafts decreases by 6. In the northbound operations of Shanghai Pudong Airport, when the proposed method was compared with Lingosoftware, the optimized landing times are same, but 2.4 min per aircraft is saved compared with the actual landing time.
- air transportation /
- arrival aircraft sequencing /
- machine scheduling /
- composite dispatching rule /
- heuristic algorithm

HTML全文

图 1 延长”三边”雷达引导

Figure 1. Radar vectoring through extending downwind leg

下载: 全尺寸图片幻灯片

图 2 进场航班排序情形A的松弛因子

Figure 2. Slack term factor of arrival aircraft sequencing under condition A

下载: 全尺寸图片幻灯片

图 3 进场航班排序情形B的松弛因子

Figure 3. Slack term factor of arrival aircraft sequencing under condition B

下载: 全尺寸图片幻灯片

图 4 进场航班排序情形C的松弛因子

Figure 4. Slack term factor of arrival aircraft sequencing under condition C

下载: 全尺寸图片幻灯片

图 5 进场航班排序启发式算法流程

Figure 5. Heuristic algorithm flowchart of arrival aircraft sequencing

下载: 全尺寸图片幻灯片

图 6 30架次航班的仿真场景

Figure 6. Simulation scenario of 30aircrafts

下载: 全尺寸图片幻灯片

图 7 30架次航班的仿真结果

Figure 7. Simulation results of 30aircrafts

下载: 全尺寸图片幻灯片

图 8 σ为250s时30架次航班的仿真结果

Figure 8. Simulation results of 30aircrafts whenσis 250

下载: 全尺寸图片幻灯片

图 9 σ为350s时30架次航班的仿真结果

Figure 9. Simulation results of 30aircrafts whenσis 350

下载: 全尺寸图片幻灯片

图 10 上海浦东机场北向运行场景

Figure 10. Northbound operation scenario in Shanghai Pudong Airport

下载: 全尺寸图片幻灯片

图 11 西北向进场飞行时间分布

Figure 11. Arrival flight time distribution from Northwest

下载: 全尺寸图片幻灯片

图 12 南向进场飞行时间分布

Figure 12. Arrival flight time distribution from South

下载: 全尺寸图片幻灯片

图 13 上海浦东机场北向运行验证场景

Figure 13. Validation scenario of Northbound operation in Shanghai Pudong Airport

下载: 全尺寸图片幻灯片

表 1 变量描述

Table 1. Variable descriptions

下载: 导出CSV

表 2 尾流间隔标准

Table 2. Wake vortex separation standards

下载: 导出CSV

表 3 复合分派规则

Table 3. Composite dispatching rules

下载: 导出CSV

表 4 仿真结果对比

Table 4. Comparison of simulation results

下载: 导出CSV

表 5 验证结果对比

Table 5. Comparison validation results

下载: 导出CSV

参考文献(25)

[1]	BENELL J A, MESGARPOUR M, POTTS C N. Airport runway scheduling[J]. Quarterly Journal of Operations Research, 2011, 9 (2): 115-138.
[2]	BEASLEY J E, KRISHNAMOORTHY M, SHARAIHA Y M, et. al. Scheduling aircraft landings-the static case[J]. Transportation Science, 2000, 34 (2): 180-197. doi: 10.1287/trsc.34.2.180.12302
[3]	LEE H, BALAKRISHNAN H. A study of tradeoffs in scheduling terminal-area operations[J]. Proceedings of the IEEE, 2008, 96 (12): 2081-2095. doi: 10.1109/JPROC.2008.2006145
[4]	BALAKRISHNAN H, CHANDRAN B G. Algorithm for scheduling runway operations under constrained position shifting[J]. Operation Research, 2010, 58 (6): 1650-1665. doi: 10.1287/opre.1100.0869
[5]	EUN Y, HWANG I, BANG H. Optimal arrival flight sequencing and scheduling using discrete airborne delays[J]. IEEE Transaction on Intelligent Transportation Systems, 2010, 11 (2): 359-373. doi: 10.1109/TITS.2010.2044791
[6]	D'ARIANO A, PISTELLI M, PACCIARELLI D. Aircraft retiming and rerouting in vicinity of airports[J]. IET Intelligent Transport Systems, 2012, 6 (4): 433-443. doi: 10.1049/iet-its.2011.0182
[7]	SAMA M, D'ARIANO A, PACCIARELLI D. Rolling horizon approach for aircraft scheduling in the terminal control area of busy airports[J]. Transportation Research Part E: Logistics and Transportation Review, 2013, 60: 140-155. doi: 10.1016/j.tre.2013.05.006
[8]	TESFAY Y Y. Modified panel data regression model and its applications to the airline industry: modeling the load factor of Europe North and Europe Mid Atlantic flights[J]. Journal of Traffic and Transportation Engineering: English Edition, 2016, 3 (4): 283-295. doi: 10.1016/j.jtte.2016.01.006
[9]	张军峰, 王菲, 葛腾腾. 基于分支定界法的进场航空器动态排序与调度[J]. 系统仿真学报, 2016, 28 (8): 1909-1914. https://www.cnki.com.cn/Article/CJFDTOTAL-XTFZ201608029.htm ZHANG Jun-feng, WANG Fei, GE Teng-teng. Dynamic arrival sequencing and scheduling based on branch and bound algorithm[J]. Journal of System Simulation, 2016, 28 (8): 1909-1914. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-XTFZ201608029.htm
[10]	HU Xiao-bing, PAOLO E D. Binary-representation-based genetic algorithm for arrival sequencing and scheduling[J]. IEEE Transaction on Intelligent Transportation Systems, 2008, 9 (2): 301-310. doi: 10.1109/TITS.2008.922884
[11]	HU Xiao-bing, PAOLO E D. An efficient genetic algorithm with uniform crossover for air traffic control[J]. Computers and Operations Research, 2009, 36 (1): 245-259. doi: 10.1016/j.cor.2007.09.005
[12]	张启钱, 胡明华, 张洪海. 基于RHC-GA的多跑道进离场航班多目标动态优化模型[J]. 交通运输工程学报, 2015, 15 (2): 70-78. doi: 10.3969/j.issn.1671-1637.2015.02.010 ZHANG Qi-qian, HU Ming-hua, ZHANG Hong-hai. Dynamic multi-objective optimization model of arrival and departure flights on multiple runways based on RHC-GA[J]. Journal of Traffic and Transportation Engineering, 2015, 15 (2): 70-78. (in Chinese). doi: 10.3969/j.issn.1671-1637.2015.02.010
[13]	ZHAN Zhi-hui, ZHANG Jun, LI Yun, et al. An efficient ant colony system based on receding horizon control for the aircraft arrival sequencing and scheduling problem[J]. IEEE Transactions on Intelligent Transportation Systems, 2010, 11 (2): 399-412. doi: 10.1109/TITS.2010.2044793
[14]	YU Sheng-peng, CAO Xian-bin, ZHANG Jun. A real-time schedule method for aircraft landing scheduling problem based on cellular automation[J]. Applied Soft Computing, 2011, 11 (4): 3485-3493. doi: 10.1016/j.asoc.2011.01.022
[15]	CAO Yi, RATHINAM S, SUN Deng-feng. Greedy-heuristicaided mixed-integer linear programming approach for arrival scheduling[J]. Journal of Aerospace Information Systems, 2013, 10 (7): 323-336. doi: 10.2514/1.I010030
[16]	SALEHIPOUR A, MODARRES M, NAENI L M. An efficient hybrid meta-heuristic for aircraft landing problem[J]. Computers and Operations Research, 2013, 40 (1): 207-213. doi: 10.1016/j.cor.2012.06.004
[17]	ANDREEVA-MORI A, SUZUKI S, ITOH E. Rule derivation for arrival aircraft sequencing[J]. Aerospace Science and Technology, 2013, 30 (1): 200-209. doi: 10.1016/j.ast.2013.08.004
[18]	MAERE G D, ATKIN J A D. Pruning rules for optimal runway sequencing with airline preferences[J]. Lecture Notes in Management Science, 2015, 7: 76-82.
[19]	FAYE A. Solving the aircraft landing problem with time discretization approach[J]. European Journal of Operational Research, 2015, 242 (3): 1028-1038. doi: 10.1016/j.ejor.2014.10.064
[20]	XU Bo. An efficient ant colony algorithm based on wake-vortex modeling method for aircraft scheduling problem[J]. Journal of Computational and Applied Mathematics, 2017, 317: 157-170. doi: 10.1016/j.cam.2016.11.043
[21]	HANCERLIOGULLARI G, RABADI G, AL-SALEM A H, et al. Greedy algorithms and metaheuristics for a multiple runway combined arrival-departure aircraft sequencing problem[J]. Journal of Air Transport Management, 2013, 32: 39-48. doi: 10.1016/j.jairtraman.2013.06.001
[22]	ALLAHVERDI A. The third comprehensive survey on scheduling problems with setup times/costs[J]. European Journal of Operational Research, 2015, 246 (2): 345-378.
[23]	KAPLAN S, RABADI G. Exact and heuristic algorithms for the aerial refueling parallel machine scheduling with due dateto-deadline window and ready times[J]. Computers and Industrial Engineering, 2012, 62 (1): 276-285.
[24]	CHEN Jing-fang. Scheduling on unrelated parallel machines with sequence-and machine-dependent setup times and duedate constraints[J]. The International Journal of Advanced Manufacturing Technology, 2009, 44 (11/12): 1204-1212.
[25]	PFUND M, FOWLER J W, GADKARI A, et al. Scheduling jobs on parallel machines with setup times and ready times[J]. Computers and Industrial Engineering, 2008, 54 (4): 764-782.