[word格式] 机场进离场流量协同分配策略

[word格式] 机场进离场流量协同分配策略 机场进离场流量协同分配策略 第4O卷第5期 2008年10月 南京航 JournalofNanjing 空航天大学 UniversityofAeronautics&Astronautics Vo1.40No.5 0ct.2008 机场进离场流量协同分配策略 张洪海胡明华陈世林 (南京航空航天大学民航学院,南京,210016) 摘要:为充分利用机场容量,减少航班延误,把进离场视为互相影响的两个过程,研究机场流量与容量匹配问题, 给出了一种进离场流量协同分配模型.基于机场容量动态限制,模型以最小化进离场航班总延误损失为目标,协 同优化进离场流量分配策略;通过引入航班延误损失系数,作为航空公司协同决策的偏好信息以兼顾其利益.针 对模型特点设计了遗传算法予以实现.实例仿真结果表明,模型不仅能使流量与容量协调匹配,而且能够使延误 损失降到最小且能兼顾航空公司的利益,验证了所提策略的有效性. 关键词:空中交通;流量分配;遗传算法;协同优化 中图分类号:V355.1文献标识码:A文章编 号:1005—2615(2008)05-0641—05 CollaborativeDistributionStrategyofAirportArrival andDepartureTrafficFlow ZhangHonghai,HuMinghua,ChenShilin (CollegeofCivilAviation,NanjingUniversityofAeronautics&Astronautics,Naniing,210016,China) Abstract:Touseairportcapabilityandreducefrightdelay,anoptimizationmodelfortheflow distributionisproposed.Themodeltakesarrivalsanddeparturesastwointerdependentprocesses.The modelminimizesthetotaldelaycosttofindoptimalflowdistributionstrategy.Italsointroducesdelay costcoefficientsasdecision—preferentialinformationtoconsidertheairlinesinterest.Agenetic algorithmsisdesignedforthemode1.Experimentalresultsshowthatthemodelhasabalancebetween airportflowsandcapabilities,andminimizesthedelaycostwithairlinepreferences.Sothedistribution strategyiSverifiedtobeeffective. Keywords:airtraffic;flowdistribution;geneticalgorithms;CO—optimizati on 引目 空中交通流量管理的根本目的在于调整交通需 求与供给,使之协调匹配.随着航空运输的蓬勃发 展,不断增长的空中交通需求与供给之间的矛盾日 益突出,由机场容量的限制带来的交通拥挤,航班延 误问题已日益严峻,机场成了空中交通管制的瓶 颈[】_3J.航班延误不仅会造成巨大的经济损失,而且 还会直接影响航空公司的信誉.因此,合理分配机场 流量,优化利用容量,使之协调匹配,对于减缓空中 等待和地面延误,提高航空公司信誉等,既具有经济 价值又具有现实意义. 机场流量分进场流量和离场流量,与之相应的 机场容量分别为进场容量和离场容量.目前大多数 流量管理,优化决策的研究都将进离场视为相互独 立的两个过程,而且将机场容量视为一个恒定值. 然而,由于国内大多数机场只有一条跑道,进离场 实际上是互相影响制约的两个过程.研究表明,机 场进场容量和离场容量一般表现为如图1所示的 机场容量曲线L4]. 基金项目:国家”八六三”高技术发展计划(20060AA12A105)重点资 助项目. 收稿日期:2007—06—13;修订日期:2007—10—11 作者简介:张洪海,男,博士研究生,1979年9月生;胡明华(联系人),男, 教授,博士生导师,E—mail:minghuahu@263. net. 642南京航空航天大学第4O卷 图1机场容量曲线(VFR条件下) 显然,机场容量不是恒定的,而且随机场天气 的变化而显着变化,甚至与飞机类别,组合比例及 顺序都直接相关.一般情况下机场按两种运 行:目视飞行规则(VFR)和仪表飞行规则(IFR), 前者在天气较好时使用,容量较大;后者在天气较 差时使用,容量较小.本文主要研究VFR条件下的 流量与容量匹配问题.此外,机场还有一些调度规 则,如停机坪,滑行道等的使用,后勤服务等.研究 表明这些因素对延误影响较tJ,c引,因此本文暂不考 虑这些因素. 机场终端区流量分配或容量配置问题的研究 已受到国内外学者的日益关注.Gilbo,余江,马正 平等人通过最小化机场进离场列队中延误的航班 量建立优化模型,配置容量,分配流量.;Gilbo又 基于CDM(Collaborativedecisionmaking)研究了 机场进离场流量管理协同优化策略[8],通过加入优 先级队列使具有优先权的航班免遭延误,考虑了航 空公司的利益;DellOlmo通过最小化航班延误时 间建立优化模型,并采用动态规划的方法研究容量 配置问题[g].然而由于航班类型,重要程度等性质 不同,其延误损失也会不同.因此无论延误航班的 数量最小,还是延误时间最小,延误损失未必达到 最小.因此,本文在上述研究的基础上,提出一种进 离场流量协同分配优化策略,通过以最小化进离场 航班总延误损失为目标,并借鉴CDM思想,结合航 班类型,重要程度等因素,引入航班延误损失系数 作为决策偏好信息,建立优化模型寻求最佳的流量 分配.所求方案既能使延误损失到达最小又能 兼顾航空公司的利益,因而更趋合理. 1协同分配策略 1.1流量分配原理 机场交通流量分配的根本在于平衡航班需求 和机场供给,需求与供给失衡势必造成航班延误. 机场供给一般表现为如图1所示的容量曲线,图中 的点称为进离场航班需求点.当需求小于或等于供 给,即图中需求点处于容量曲线内或上(如d点), 则进离场需求均被满足,无航班延误;当需求大于 供给,即图中需求点处于容量曲线之外(如P点), 则造成某些航班延误,此时须合理分配进离场流 量,使之与容量协调匹配,即在容量曲线上寻求 Pareto最优的容量配置点(称为最优流量分配点), 使延误损失降到最小. 本文提出的分配策略是把要进行流量分配的 时间区间划分为若干时段,根据每时段的初始交通 需求和动态容量限制,在实现容量最优利用的基础 上,寻求进场和离场航班的总延误损失最小,协同 优化配置进离场容量,为每时段分配最优的进离场 流量;通过引入航班延误损失系数作为决策偏好信 息,使航班所属的航空公司能够协同决策,最小化 航班延误的同时尽可能地满足航空公司的利益,使 流量分配策略更趋合理. 1.2已知与假设 为实现上述分配策略,需要给出以下几点假 设: (1)预分配流量的时间区间的航班需求及容量 曲线已知,所有航班的地面或空中的单位时间延误 损失已知,这是策略得以实现的先决条件. (2)在时间区间内无法分配的需求,都可在下 一 个额外的时段内完成,即假设该时段容量无限; 该条件用以确保所有航班都可以实现进或离场,即 确保所研究问题具有可行解. (3)所有航班不能在其预计离场(进场)时间之 前离场(进场),即航班不能提前起飞(降落).该条 件使研究问题线性化,可以简化模型,在实际应用 中也是合理的. 1.3数学模型描述 模型参数及其符号意义: 7?:预分配流量的时间区间,由若干时段组成, 一 {t,t,…,t,t+),时段为一定长时间(如 15min),定义t+为额外时段,其容量无限,tET D:丁时间内的离场航班d集合,dED. A:丁时间内的进场航班a集合,a?A. F:71时间内的所有航班厂集合,F—DUA,厂 ?F. e,:航班厂预计最早进场或离场时间. 71,:航班厂可能的进场或离场时段集合,Ts= {t?丁l,?P,},T,cT. e,():航班/在t时间进场或离场的延误损失 函数,C,(f)一c,?(f一,)H.其中c,指航班厂的延 误损失系数,是由其机型,重要程度或优先级等因 素决定,代表单位时间的航班延误损失或延误程 度,作为决策偏好信息调整最优策略;参数e用来 第5期张洪海,等:机场进离场流量协同分配策略643 表示航班延误成本的缓慢超线性增长,它是协同决 策公平原则的体现,能避免过多地延误某一航 班..,O<e<1. ,,『1航班a在t时间离场 „/o否则 ,, f1航班n在t时问进场 d {o否则 “:机场在t时段内的离场流量 Ut一 ?37(f)VtET :机场在t时段内的进场流量 ,一 ?Y.(,)vtET 【,,分别为t时段的最大离场容量和进场容 量. 目标函数 厂(,)一min??Cs(t)?.27/-(f)一,?FtErs:t?” min??(f一)e?lz(,)+d?DtETd:t>~ed ??(,一ea),?(,)(1) d?Atqrd:t>~eo 约束条件 0??U,0??V,tET,t?tN+1(2) 口?”+?73?y,tET,t?t?+1(3) zd(f)一{0,1},>z(,)一1,d?D(4) t „ ~:.?T. a ()一{0,1),(f)一1,日?A(5) t „ E.T a 约束条件(2,3)为容量限制约束,它们构成容 量限制下的流量分配点域(容量曲线以内或上),在 点域内寻求最优分配点,从而确保容量与流量协调 匹配;其中,,为容量曲线系数,如图1中,由0 ?%?8,O??7,+2v?18和玩+7Jt?12构成 流量分配点域.约束条件(4,5)为流量分配约束,用 以确保每个航班有且仅有一个进场或离场时段. 2遗传算法求解 模型实际决策变量为二进制值,属于O一1整数 规划.由于在流量分配及调度中,通常要配置几个 小时的流量及其调度,航班需求量较大,传统的O一1 整数规划算法较难求解.本文采用遗传算法寻求模 型最优解. 2.1编码 本文遗传算法中个体的染色体表示采用矩阵描 述,构成如图2中所示的染色体个体.x扎的矩阵 Y一[.y](=1,…,m,一1,…,,其中m为机场需 求中进离场航班总量,为每个航班可能的进场或 离场时段集合T),Y表示航班i在时段J内的进场 雉场 时间段n 图2染色体编码及遗传操作示例 或离场情况(若Y.一1,则航班i在时段内的进场或 离场;若Y严0,则不在该时段内进场或离场).Y值 随机产生,所有Y,取值后,行和列都有相应的约束, 矩阵行要满足流量分配约束,矩阵列要满足容量限 制约束.满足约束的个体代表一种可行的流量分配 方案.随机编码生成一个可行解的步骤如下: (1)为离场航班初始编码.初始化离场航班i 的所有元素,令.j=0;然后在丁r内随机选择一个 时段,令Y—1. (2)最大离场容量约束修正.离场航班编码若 满足约束条件(2)中的前者则进行步骤(3);否则转 至步骤1. (3)为进场航班初始编码.初始化进场航班i 的所有元素,令,一0;然后在7?内随机选择一个 时段,令Y=1. (4)最大进场容量约束修正.进场航班编码若 满足约束条件(2)中的后者则进行步骤(5);否则转 至步骤(3). (5)进离场容量曲线约束修正.个体编码若满 足约束条件式(3)则该个体编码完毕;否则转至步 骤(1)重新编码. 2.2选择 采用基于最优保留策略的排序选择方法:首先 计算种群中的每个个体的适应度,并将个体按其适 应度值降序排列;然后根据预先设定的淘汰率,淘 汰适应度值较小的个体,并复制相同比例的最优个 体(适应度值较大的个体),以保证种群大小不变. 2.3交叉 采用单点交叉方式对两个体进行交叉(图2中 的父个体1和2).首先在1,…,的时段列中,随机 选择一列位置作为交叉点,如选择图2中加黑直线 的位置作为交叉点,则把染色体矩阵分成左右两部 分;然后交换父个体1和2的染色体矩阵右侧部分 的Y值,从而生成子个体1和2. 由于代表个体的矩阵在行和列上均有相应的 约束,采用单点交叉方式,交叉后的子个体可以满 644南京航空航天大学第4O卷 足列约束(容量限制约束),但行约束(流量分配约 束)或多或少不能满足,因此,再对交叉后的子个体 约束修正处理. 约束修正处理方法.行约束不满足时会出现两 种情况:(1)行中有两个进场或离场时段,(2)行中 没有进场或离场时段.若某行出现前者情况,则随 机去掉一个(仍然满足列约束);若出现后者情况, 则在该行可能的进场或离场时段集合中随机选择 一 个作为进场或离场时段,此时该时段对应的列约 束可能不再满足,若不满足则在集合中重新随机选 择.如果选择完该集合中所有时段后仍不满足列约 束,则该子个体存在致死的遗传基因,应给予淘汰, 为保证群体大小不变,保留该子个体对应的父个 体. 2.4变异 采用随机选择两列互换产生新个体的方式.互 换操作可以满足行约束,但可能不满足列约束,若 不满足列约束,则重新随机选择其他两列互换,直 至满足列约束为止. 3实例及分析 以国内某机场12:O0,14:oo时间段内的交通 流量分配为例,交通初始需求中共有92架次航班 (其中离场49,进场43),交通需求及其与机场容量 的匹配情况如图3所示.显然,其中有若干时段的 进场或离场需求超出了其最大容量,且相互影响的 进离场需求也超出了机场容量(图3中有4个需求 点在容量曲线之外),这种与容量不相匹配的需求 势必造成航班延误.为减小或消除延误,应对需求 再分配,使之与容量协调匹配. 针对该机场的交通需求及其容量曲线,应用遗 传算法协同优化进离场流量分配方案.仿真优化之 前,先确定延误损失系数值.根据国际民航组织 (ICAO)的,按照飞机的尾流强弱将飞机分为 重型,中型和轻型3类[1,文献[1O]中对延误成本 的分析,设定普通航班各类型飞机的延误损失系数 见表1;此外,有关研究表明,进场航班的单位时间延 误损失是离场航班的3倍[11],因此可设定同等类型 的具有优先权的航班(包括进场和重要离场航班)的 延误损失系数是普通航班的3倍.遗传操作时,选取 种群规模为100,最大世代数为400,选择淘汰率为 0.2,交叉率为0.9,变异率为0.1.经计算得到该问题 的最优解,即最佳的流量分配方案.优化后各时段的 流量及其与容量的匹配情况如图4所示. 表1普通航班各类飞机的延误损失 机型代表符号成,延失 /I.J 8 d 黾6 4厂]\ 2 0 12:O0f12:15ll2:3ol1245I3:0(}l13:l5I133oIl3:45 口进场航班5l8I4I7I7l4I4l4 臼离场航班36978637 时间区间 图3交通初始需求及其与机场容量的匹配情况 lu 8 a 蚕6 r4IN 2 0 l2O0121512:30l2:4513:OO13.15l3:3O134514:O0 口进场航班57566554O 口离场航班347667682 8 d „吾6 4 翥z O 时间区间 图4优化后的流量及其与机场容量的匹配情况 离场(架/15min) 246810 离场(架/15min) 第5期张洪海,等:机场进离场流量协同分配策略645 显然,优化后的流量与容量能较好地协调匹配 (所有分配点都处于容量曲线上或内,其中内点(3, 5)是由于属于第1个时段且其初始需求小于容量 所致,(6,5)是由于整数约束所致).虽然造成了2 个离场航班延误到该时间区间外,但能最大限度地 减小具有优先权的所有进场航班的延误,使该时间 区间内的总延误损失达到最小.以12:15,12:3O 时段为例分析说明,优化前(图3)虽然该时段的离 场需求6小于其最大容量8,但进场需求8超过其最 大容量7,而且进离场需求点偏离容量曲线之外,航 表2所示,从中看出:具有优先权的所有进场航班 几乎都能在本时段内进场,由于最大进场容量约 束,因A7航班属于轻型机且最早进场时间较晚,而 被分配到以后的时段;虽然离场需求小于其最大容 量,但为了尽量减小损失较重的进场航班的延误 (仅1架被延误到以后的时段),致使2架离场航班 (D4,D5)被分配到以后的时段,最早离场时间相对 较晚的D6航班由于具有优先权而被保留.显然,这 种分配不仅能尽量减小总延误损失,而且满足了航 空公司的利益,因为航空公司可能宁愿以延误某些 班延误不可避免.该时段优化后的流量分配方案如次等航班为代价换取其重要航班的准时进离场. 表212:l5,12:30时段的进离场流量分配方案 4结束语 本文把进离场视为互相影响的两过程,在其容 量互相转换和动态约束的条件下,研究流量与容量 的协调匹配问题.论文提出了一种进离场流量协同 分配策略,给出了分配模型,并采用遗传算法予以 实现.模型不仅考虑了总延误损失,而且通过引入 航班延误损失系数作为决策的偏好信息,优化的同 时兼顾了航空公司的利益,使流量分配具有一定的 灵活性和自主性.实例分析表明所提的分配策略切 实可行.如果结合跑道构型,滑行道,停机坪及飞机 安全间隔等因素,可进一步研究进离场航班的协同 调度,时隙分配等问题. 参考文献: [1]胡明华,钱爱东,苏兰根.基于地面等待策略的航班时 刻规划方法EJ].航空,2001,23(3):262—264. [2]胡明华,钱爱东,苏兰根.多机场地面等待问题模型研 究[J].南京航空航天大学,200O,32(5):586— 590. [3]马正平,崔德光.机场航班延误优化模型I-J].清华大 学:自然科学版,2004,44(4):474—477. [4]GilboEP.Airportcapacity:representation,esti— mation,optimizationrJ].IEEETransactionson ControlSystemsTechnology,1993,1(3):144—154. [5]GilboEP.Optimizingairportcapacityutilizationin airtrafficflowmanagementsubjecttOconstraintsat arrivalanddeparturefixes[J].IEEETransactionson ControlSystemsTechnology,1997,5(5):490—503. [6]余江,王大海,浦云.终端区起飞着陆的协同优化[J]. 系统工程,2003,18(5):462—465. [7]马正平,崔德光,谢玉兰.机场终端区流量分配及优化 调度[J].清华大学:自然科学版,2003,43(7): 876—879. [8]GilboEP,HowardKW.Collaborativeoptimization ofairportarrivalanddeparturetrafficflow managementstrategiesforCDM[C]//3rdUSA/ EuropeAirTrafficManagementR&DSeminar. Napoli:s.n.],2000:1-11. [9]DellOlmoP,LulliG.Adynamicprogramming approachfortheairportcapacityallocationproblem [J].IMAJournalofManagementMathematics, 2003,14(3):235—249. [1O]徐肖豪,李雄.航班地面等待模型中的延误成本分析 与仿真[J].南京航空航天大学,2006,38(1): ll5—12O. [11]DelahayeD,SofianeO,PuechmorelS.Airspace objectivegenetic congestionsmoothingbymulti— algorithm[c]//ACMSymposiumonApplied Computing,SantaFe:s.n.],2005:907—912.