引用本文:应圣钢,孙富春,胡来红,刘华平,张学军.基于多目标动态规划的多跑道进港排序[J].控制理论与应用,2010,27(7):827~835.[点击复制]
YING Sheng-gang,SUN Fu-chun,HU Lai-hong,LIU Hua-ping,ZHANG Xue-jun.Multi-objective dynamic programming algorithm for aircraft arrival sequencing and runway scheduling[J].Control Theory and Technology,2010,27(7):827~835.[点击复制]
基于多目标动态规划的多跑道进港排序
Multi-objective dynamic programming algorithm for aircraft arrival sequencing and runway scheduling
摘要点击 2460  全文点击 1970  投稿时间：2009-06-07  修订日期：2009-12-20
查看全文  查看/发表评论  下载PDF阅读器
DOI编号  10.7641/j.issn.1000-8152.2010.7.CCTA090722
  2010,27(7):827-835
中文关键词  进港排序  多跑道调度  多目标优化
英文关键词  aircraft arrival sequencing  multi-runway scheduling  multi-object optimization
基金项目  国家杰出青年科学基金资助项目(60625304); 国家自然科学基金面上项目资助项目(60572178).
作者单位E-mail
应圣钢 清华大学 智能技术与系统国家重点实验室  
孙富春 清华大学 智能技术与系统国家重点实验室  
胡来红* 清华大学 智能技术与系统国家重点实验室
第二炮兵工程学院 		hulh06@mails.tsinghua.edu.cn 
刘华平 清华大学 智能技术与系统国家重点实验室  
张学军 北京航空航天大学 电子信息工程学院  
中文摘要
      随着航空运输的高速增长, 航班延误日益严重, 而对飞机进行进港排序和跑道调度能有效提高机场吞吐量、减少飞机燃油花费, 从而减轻航班延误, 提升经济效益. 由于大量飞机的多跑道进港优化调度问题是一个非确定型多项式完全(NP-C)问题, 该问题一直没有得到有效解决. 本文针对已有的基于位置交换束缚的单跑道动态规划算法运算量大、运算效率低的不足, 采用优化解空间的措施并运用贪心策略, 同时将其推广到双跑道调度, 从而解 决大量飞机的双跑道、多目标进港排序优化问题. 大量仿真实验表明, 该算法复杂度与飞机数量呈近似线性关系,能在较短时间内对吞吐量和降落花费同时实现优化.
英文摘要
      Optimization of runway scheduling for aircraft landings plays an important role in modern air traffic control, by maximizing throughput of an airport and minimizing fuel cost of aircrafts. As a nondeterministic polynomialcomplete( NP-C) problem, the runway scheduling of a considerable number of aircrafts in a multirunway airport hasn’t been effectively solved. Because of considerable computation required by the traditional dynamic programming algorithm under constrained position shifting(CPS), we can only sequence aircrafts and schedule the time of arrival in a single-runway airport. This paper presents a new dynamic programming algorithm by changing the way of recurrence and combining the traditional one with several other methods including a greedy algorithm. Our algorithm can solve the problem of multirunway scheduling with multi-object efficiently and effectively. A large number of experiments show that the complexity of the algorithm is almost linearly proportional to the number of aircrafts, and the algorithm can optimize both throughput and landing cost simultaneously in a short period of time.