基于混合动态规划算法的进场航班排序-论文.pdf

《基于混合动态规划算法的进场航班排序-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第32卷第1期广西师范大学学报：自然科学版Vo1．32No．12014年3月JournalofGuangx[NormalUniversity：NaturalScienceEditionMar．2O14基于混合动态规划算法的进场航班排序梁曼，马兰，邹飞(1中国民航大学天津市空管运行规划与安全技术重点实验室，天津300300；2南京航空航天大学民航学院，江苏南京21O0163中国民用航空西南地区空中交通管理局云南分局，云南昆明650200)摘要：在遵循优化并可行的算法设计理念下，为了更好解决终端区航班进场排序问题，本文提出一种混合动态规划算法。该算法在动态规划的基础上结合约束

2、位置交换算法与滑动窗算法，将进场航空器合理分组、分阶段进行排序，综合考虑短期排序预测的灵活性和计算规模的适度，提高了算法的计算速度、灵活性和鲁棒性。仿真结果表明：与传统先到先服务算法相比，改进后的混合算法不仅能减少延误11．6，计算速度快，而且还避免了与原次序的较大变化，便于管制策略的实施。关键词：空中交通管理；航空器排序；动态规划中图分类号：V355．2文献标识码：A文章编号：10016600(2014)O1—0044—07随着我国航空运输业的迅猛发展，空中交通流量日益增长。但由于交通流量的分布不均匀，以北京、上海和广东为主的三大枢纽机场占据了我国较大的交通流量，航班延

3、误问题较为严重。据2012年民航行业发展统计公报统计L1]：2012年，航空公司计划航班250．2万班次，其中正常航班187．2万班次，不正常航班63．0万班次，平均航班正常率为74．83。航班延误不仅给航空器运营商以及机场当局带来较大的经济损失，也容易引发社会问题。进场航空器的排序主要发生在终端管制区内，是造成航班延误的一个重要环节。在终端管制区内，航空器从不同的方向，以不同的高度汇聚进近，必须将他们以规定的安全间隔、一定的顺序安排到进港航路上。管制员一般根据航空器预计到达时间的先后来决定着陆的次序，即按照先到先服务(firstcomefirstserve，FCFS)算

4、法对终端区航班进行排序，这个算法虽然易于操作，但容易造成航班的延误过度。合理的进港航班排序能提高机场跑道和终端区内空域的利用率，减少终端区的流量堵塞，减少航班的延误，降低管制员的工作负荷。终端区航班进场排序的研究一直以来都受到研究人员的普遍关注E36J。考虑到航班排序是一个动态的过程，Psaraftis早在1978年就开始运用简单的动态规划方法来研究该问题¨7]，但随着进场航空器数量的增加，计算规模会呈现出指数化增长的趋势，解决这样一个巨大的多项式计算问题目前是不现实的，其工作量巨大。Balakrishnan和Chandran将Psaraftis的动态规划模型进行改进，运

5、用约束位置交换算法(constrainedpositionshift，CPS)来减少计算量]，虽然优化结果较好，但是优化策略却不被管制员所接受，与实际运行相差较大。鉴于航空器进场是一个动态过程，遵循优化并可行的算法设计理念，本文将在动态规划的基础上采用CPS与滑动窗算法进行优化，形成混合优化算法，将进场航空器分阶段、分组进行排序，以达到既避免航空器与原次序产生较大变化，减少与先到先服务的冲突，减少计算量，同时也便于管制策略实施的目的。收稿日期：2013—09—03基金项目：国家自然科学基金资助项目(U1333116)；国家科技支撑计划资助项目(2011BAH24B10)；

6、中央高校基本科研业务费中国民航大学专项基金资助项目(ZXH2013DO13)；天津市空管运行规划与安全技术重点实验室开放基金资助项目通信联系人：马兰(1966一)，女，甘肃武威人，中国民航大学副教授。E—mail：malan66@263．net第1期梁曼等：基于混合动态规划算法的进场航班排序45动态规划基础理论动态规划的理论是多阶段决策过程最优化的基本理论，是由R．Bellman等人在2O世纪5O年代初提出的。贝尔曼最优性原理指最优策略具有一种性质：无论初始状态和初始决策如何，相对于第一个决策所形成的状态来说，余下的决策需要构成最优策略。动态规划是针对多阶段决策问题的特点

7、，来解决这类问题的最优化原理，其成功解决了生产管理等方面的实际问题，成为了运筹学的新分支。动态规划模型的基本概念：①阶段。将决策过程分解成若干个阶段，按次序求每阶段的解，用k表示阶段变量；②状态。各个阶段开始时的条件叫状态，系统在第k(1≤志≤)阶段的状态变量，记为S；③决策。当各个阶段和状态确定以后，就可以通过不同的决策，来确定下一阶段的状态，这称为决策。而表示决策的变量叫决策变量，用U(S)表示第点阶段，状态为S时的决策变量；④状态转移方程。在动态规划中本阶段的状态是上一阶段状态和决策的结果，因此知道第k阶段的状态S和决策