确定性空域容量约束下的区域流量管理优化模型.doc

确定性空域容量约束下的区域流量管理优化模型第47卷第2期2012年4月西南交通大学journalofsouthwestjiaotonguniversityvo1.47no.2apr.2012文章编号:0258-2724(2012)02-0348-07doi:10.3969/j.issn.02582724.2012.02.028确定性空域容量约束下的区域流量管理优化模型张颖,谢华,胡明华(南京航空航天大学民航学院,江苏南京210016)摘要:为解决区域内空中交通拥挤问题,以最小化总权重延误和最小化区域外权重延误为优化目标,通过决策偏好参数关联两个优化目标,在确定性扇区容量约束的基础上,增加了流量尾随间隔限制约束和扇区最大允许延误时间约束,构建了满足区域性流量管理实际运行约束条件的基于时间计量的流量管理整数规划模型.选取中南区域的实际空域和航班计划数据,采用cplex优化软件求解模型.结果表明:目标函数中的决策偏好参数能调节两个优化目标;新增的约束条件能满足实际运行需求和保证策略的可实施性,即在实施生成的策略时不产生额外的管制员工作负荷.关键词:区域流量管理;数学规划模型;确定性空域容量;尾随间隔;时间计量中图分类号:v355.1文献标志码:aoptimizationmodelforareatrafficflowmanagementunderconstraintofdeterministicairspacecapacityzhangying,xiehua,huminghua(civilaviationcollege,nanjinguniversityofaeronauticsandastronautics,nanjing210016,china)abstract:tosolveareaairtrafficcongestionproblems,anintegerprogrammingmodelbasedontimebasedmeteringforareatrafficflowmanagementwasbuilt.theoptimizationobjectivesofthemodelaremi.nimizingthetotalweighteddelayandminimizingtheweighteddelayoutofthearea,andthetwoobjectivesarecorrelatedthroughadecisionpreferenceparameter.inadditiontothedeterministicsectorcapacityconstraint,twonewconstraints,includingthemilesintrailrestrictionforthetrafficflowandthemaximumallowabledelaytimeforflightsinthesector,areaddedtothemodeltosatisfythepracticaloperationconstraintsofareatrafficflowmanagement.themodelwasthensolvedwiththesoftwarecplexthroughanumericalexampleusingtherealoperationalairspacedataandflightdatafromthemiddlesouthareacontrolcenter.theresultsshowthatthedecisionpreferenceparametercanadjustthetwoobjectives,andthatthenewlyaddedconstraintscansatisfythepracticalneedsandensurethefeasibilityofthestrategyimplementation,thatisproduceadditionalworkloadforthecontrollerswhenimplementingtheresultingstrategy.keywords:areatrafficflowmanagement;mathematicalprogrammingmodel;deterministicairspacecapacity;milesin?trail;timebasedmetering空中management,交通流量管理(airtrafficflow量的重要作用,根据问题的复杂性及计划的时间范atfm)起着平衡空中交通流量和容围,可以将空中交通流量管理问题分为全局性战略收稿日期:基金项目:作者简介:通讯作者:2010123国家863计划资助项目(2006aa12a105)张颖(1978一),女,讲师,博士研究生,研究方向为空中交通运输与管理,e-mail:胡明华(1962一),男,教授,博士,博士生导师,研究方向为空中交通运输与管理,e-mail:第2期张颖等:确定性空域容量约束下的区域流量管理优化模型349流量管理问题和区域性战术流量管理问题.全局性战略流量管理提前124h对全国范围内的流量进行管理,而区域性流量管理提前20120min对区域内交通流量进行管理.区域性战术流量管理基于更为准确和实时的交通和气象信息,主要通过尾随距离间隔限制(milesin-trail,mit)或区域内机场起飞航班申请放行许可的方式,对本区域内不能解决的拥挤,需要扩散到上游的相邻区域进行流量限制.在我国当前的实际管制运行中,将区域流量管理分为主动管理和被动管理,主动管理是对本区域空域拥挤进行管理;被动管理则是根据相邻区域对本区域施加的mit流量限制条件实施相应的管理.由于缺乏流量管理单位的统一协调,主要依赖管理者的经验,更多采用的是被动控制方式,实施流量限制的区域并不知道该限制会对相邻上游区域造成多大影响,是否会加剧拥挤.限制流量的方式也主要采用粗放但较易于执行的mit方式.通常利用线性或非线性优化技术解决空中交通流量管理决策问题_4.文献4建立了计算效率较高的整数规划模型.文献5中给出的确定性优化模型可以看作是文献4模型的宏观形式,该模型忽略了文献4模型的一些细节,用于研究欧洲空中交通流量管理问题.文献6中通过确定性优化模型求得航班优化的离场延误时间,并根据延误时间计算区域边界管制移交点的mit流量限制值.优化方法有时候不一定能满足计算时间要求,为了在允许的时间范围内求得合适的解需要使用启发式方法.文献7提出了两种启发式方法以及一种启发式方法与优化算法相结合的方法,并进行了比较.文献8在管制区短期空中交通流量管理问题中引入了流量控制事件概念和相应约束条件.本文研究采用时间计量(time-basedmetering,tbm)方式进行区域流量管理,tbm方式是mit的有效替代方式.区别于mit限制对特定航班流执行固定的时间间隔或距离间隔,tbm采用为各航班分配过点时间的方式实施流量控制.mit限制通常对主要交通流产生的影响较大,tbm方式则针对各航班进行优化控制.本文以文献4的优化模型为基础,建立区域流量管理模型,模型增加了相邻区域对本区域施加的mit流量限制约束和本区域各个扇区内最大允许延误时间约束,并在目标函数中增加了反映决策者偏好的参数,考虑流量控制策略的可执行性及决策者决策偏好因素,使该模型更适用于生成优化的区域流量管理策略,为区域流量管理决策提供支持.1区域流量管理模型1.1问题描述本文区域流量管理模型的目标是通过调整飞机的起飞时刻或进入本区域时刻,以及航班在区域内的飞行时间,满足本区域内扇区容量约束和相邻区域的mit流量控制约束,使航班延误时间或延误成本最小化.航班在区域的各个扇区内通过调速或变更航迹消耗需吸收的延误时间,为保证策略的可执行性,模型中增加了航班在扇区内最大允许延误时间限制,该限制值与扇区的地理范围,空域结构等因素相关,当航班需要吸收的延误时间超出扇区内最大允许延误时间时,在地面或区域外发生延误.1.2模型假设模型基于以下假设条件:(1)离散化的时间段.将时间划分为离散且等长度的连续时问片段.(2)确定的飞行流量.航班途经各航路点的时刻为确定值.(3)确定的空域容量.空域容量为确定值.(4)延误的发生地.本区域内起飞航班的延误为地面延误和在本区域内空中延误;非本区域机场起飞航班的延误为进入本区域之前的空中延误和在本区域内的空中延误.(5)扇区容量.扇区容量为一定时段内允许通过扇区的航班架次.1.3模型描述1.3.1目标函数mln(wara.utf+wata,)+j(wgtgf+warr)efgmin(watat.iai+wata.tt.【aj+wgtg【nt1),(1)式中:f为经过区域的航班.厂的集合,包括在本区域内机场起降的航班和飞越航班;f为在本区域内机场起飞的航班集合,fgcf;w为地面延误的权重系数;为空中延误的权重系数;f.,为本区域内机场起飞航班_厂的地面延误;t.,为非本区域内机场起飞航班厂在区域外350西南交通大学第47卷的空中延误;t,为航班/区域内的空中延误;t.为本区域内机场起飞航班地面总延误;t.为所有航班区域内空中总延误;t为非本区域内机场起飞航班区域外空中总延误.式(1)中,(t.,+watainf)表示非本|f,f区域内机场起飞航班的空中及地面总权重延误;(.t.,+t,)表示本区域内机场起飞航班e的空中及地面总权重延误,目标函数为最小化所有航班的总权重延误.令决策变量为:1,航班门生t或t之前已到达空域;ujr【0,航班.厂在t或t之前尚未到达空域定义如下变量:为航班.厂沿飞行路径在本区域内经过的受限空域单元数量,受限空域单元包括航班途经的扇区和航班从本区域进入相邻区域的移交点.将航班从本区域进入相邻区域的移交点作为一个独立的受限空域单元,是为了表示相邻区域对本区域施加的mit流量约束;p(f,i)=r航班经过本区域内扇区,1<,【航班从本区域进入相邻区域的移交点,i=,p,=(p(f,i):1i,);tj.=tt,r为航班fn达空域单元的可行飞行时间段,1,;tenterf为航班_厂预计进入本区域时刻;t,为航班厂预计离开本区域时刻.则式(1)中各量均可表示为决策变量dm的函数,t,=(d一d一1)一t,tekf,(,1)ff/f,t(,=t(o一d一1)一t.rl,tetk,u,i)fef,taji1,=t(o一d一1)一titoutfff/f,tai1,=t(o一d一1)一t_ll一tc,ffg,tl=tg,j:jetaintotal=t,nfal=taoutff.,/ef/f对本区域内机场起飞航班的区域性流量管理,可以通过在本区域内部进行起飞申请协调;对区域外机场起飞航班的限制,需要与相邻上游管制区域进行协调,管理者需要在减小本区域内航班延误的同时,考虑对上游管制区域航班的影响,为此引入优化目标(2),即最小化区域外权重延误值,rain(ata0uit0la1).(2)对于该多目标优化问题,可以采用线性加权方法转化为如下单目标优化问题:min(wgtg【0tl+atait.lal+wata.tt.)+pwatanijt1=rainwgtg【0ll+atait.t1+a(1+p)ta【lut眦1,(3)式中:p为决策偏好系数,表示减少单位区域外权重延误对应的总权重延误增加量,可以根据管理者的决策偏好设定.式(3)对地面延误,区域内空中延误,区域外空中延误分别赋予了不同的权重.1.3.2约束条件(1)扇区容量约束.定义为待优化时段内的时间片集合,js为区域内的容量受限扇区集合,对于s,tt,5,(t)表示扇区在时间片t的容量值.(,一ll,f)jttp,)|,p(f+11j,1fs(t),ves,tt,ff.(4)式(4)表示各个扇区内航班流量满足扇区容量约束.(2)相邻区域对本区域的mit流量控制约束.相邻区域对本区域施加的mit流量控制约束条件是:指定时段内符合特定筛选条件的航班之间的时间间隔必须不小于指定的时间间隔,才可通过本区域进入相邻区域的移交点.ffmit,gfmjt,fg,tmith.,tmilrpnd,it(o一d一)一t:ttkf,krutf)i(d一df_1)ifminit,(5)式中:f为符合相邻区域mit流量控制规定的航班流筛选条件的航班集合(下文称该类航班为mit受控航班);第2期张颖等:确定性空域容量约束下的区域流量管理优化模型351tminit为与相邻区域mit流量控制距离间隔值相对应的时间间隔值(minutesintrail,minit),等于mit距离间隔值与航班通过流量控制点的平均速度之比;tmitbegin为相邻区域mit流量控制开始时刻;t为相邻区域mit流量控制结束时刻.式(5)为非线性约束,表示任意两架mit受控航班离开本区域的时间间隔满足流量控制时间间隔要求.为减少计算复杂性,将间隔约束转化为滑动窗口内通过的航班架次约束,其近似等价于以下的线性约束条件:(d,-d,)umit,vn,1nm,(6)f.jefmit:(ftmitbegin)/jmitdize+1=n,k=p(f,式中:jmitwindowsize为滑动窗口的直径;.为在.,出时段内通过的航班架次.将间隔值转化为时段内通过的航班架次的计算公式为:umitca.a=jmitwind.wsietslot/tminit,其中:f1.为时间片的大小,min;是滑动步长为1个时间片时从t晒到tmitend流量控制时段内的滑动时间窗口数量,m=tmltendtmitbegin一.,mitwid.wsize+2.(3)航班依次经过各个受限空域单元的连续性约束为:.,f+fm一,0,厂f,=p(f,i),=p(f,i+1),1i<,t,t+tminfjtjf(7)该约束条件表示航班按照各个受限空域单元到达次序依次经过的各个空域单元.(4)时间连续性约束为:djftdift一1>10,fef,p(f,i,1,t,t一1广(8)该约束条件表示航班经过空域单元在时间上是连续的,如果时刻t一1航班已经过空域单元./,即dj,c_=1,则在时刻t及t之后的时刻,也必然都为1.(5)扇区内最大允许延误时间约束为:t(.,ll,l一.)一:0,t(,一,f_1)一ti,jtaxd.lt:te*jrff,j:=p(f,),=p(f,i+1),1i<,(9)式中:t.为扇区内允许的航班最大延误时间;ti,航班厂在扇区中需要的最短飞行时间.该约束条件表示航班在扇区内的最大允许飞行时间不能超过在该扇区内的所需最短飞行时间与在该扇区内的最大允许延误时间之和.1.4cplex求解采用cplex优化软件求解该整数规划模型.设航班总数为fl,航班最多经过个扇区,航班在各个扇区内可行飞行时间集合的元素个数(即时间范围集合内包含的时间片个数,称为时间片集合的势)最大值为:d,mjaxl,扇区集合中扇区数为1s1,则变量总数的上限为ifld(+1),约束条件个数的上限为:l5lll+2lfldn+lfl.2实例分析2.1实验参数设置选取2010年8月26日10:o011:30时段内位于中南区域的478架航班进行仿真,以5min为一个时间片,478架航班最早进入中南区域的时刻作为待优化时段的开始时间,单个航班最大总延误为120rain,478架航班中最晚离开中南区域时刻加上120min作为待优化时段的结束时刻,则fl=80,每个航班最多经过8个扇区,单个扇区内可行飞行时问最大可能跨度为2.5h,则d=30,该算例变量总数的上限为129060,约束条件总数上限为233984,在不同参数值下采用cplex的求解时间为23min.基本参数如下:tl.t=5min;地面延误权重系数w=1;空中延误权重系数w=2;各个扇区的容量值均为10架次.相邻区域mit流量控制采用中南管制区域较常见352西南交通大学第47卷的与之相邻的郑州区域在移交点oblik导航台施加的流量控制,受控流量为经oblik点离开中南区域进入郑州区域的所有航班.为研究模型中新增约束条件及目标函数中偏好参数对航班延误的影响,改变模型中的参数值进行实验.(1)令t.在15min范围取值,使_,为t的最小公倍数,计算相应的值,通过式(6)中u值的变化研究约束条件式(2)对航班延误的影响;(2)令tdelay分别取5,10,15rain,通过式(9)中t值的变化,研究约束条件式(5)对航班延误的影响;(3)令目标函数中决策偏好参数p分别取0.o0和0.25,研究p值的变化对航班延误的影响.2.2实验结果及分析航班延误时问随mit流量控制时间间隔值的变化情况见图1.仅考虑扇区容量时扇区内最大延误时间约束对航班延误的影响见图2.同时考虑扇区容量和mit限制时扇区内最大允许延误时问约束对航班延误的影响见图3.参数p分别取0.o0和0.25时,不同扇区内最大允许延误时间下的延误变化趋势见图4.一口一mit受控航班总权重延误1不同mit限制值下航班总权重延误的变化fig.1changeoftotalweighteddelayfordifferentmitvalues(1)相邻区域mit流量控制约束对航班延误情况的影响如图1所示,随着mit流量控制时问间隔值的增大,所有航班的总权重延误时间也增大,其中mit受控航班权重延误增加,而非mit受控航班的权重延误反而减小,这是因为相邻区域流量控制约束必然影响mit受控航班,使得这些航班构成的航班流密集程度下降,区域内空域资源就可以更多的分配给非mit受控航班,非mit受控航班的权重延误因此相应减小0量色一匠蕾捌i厦曾图2仅有扇区容量约束时不同扇区内最大允许延误时间下的航班延误变化fig.2changeofflightdelayfordifferentmaximumallowedsectordelaysonlyunderthesectorcapacityconstraint图3扇区容量及mit限制约束条件下不同扇区内最大允许延误时问下的航班延误变化fig.3changeofflightdelayfordifferentmaximumallowedsectordelaysundersectorcapacityconstraintandmitconstraint舍g一厘曹趔图4不同扇区内最大允许延误时间下区域外权重延误及总权重延误的变化fig.4changeofweighteddelayoutofthezoneandtotalweighteddelayfordifferentmaximumalloweddelaysinthesector(2)扇区内最大延误时间约束的影响当对扇区内最大允许延误时间不加限制时,在仅考虑扇区容量约束和同时考虑扇区容量及mit限制约束两种情况下,航班在单个扇区内延误时间第2期张颖等:确定性空域容量约束下的区域流量管理优化模型353的最大值分别达到30和35min,该延误只能通过空中等待航线飞行来消耗,会增加管制员的工作负荷.为使生成的流量控制策略具有较强的可实施性,扇区内最大允许延误时间约束是必要的,延误时间随扇区内最大允许延误时间的变化情况见图2及图3,随着扇区内最大允许延误时间的增大,区域内延误时间增大,地面延误时间和区域外延误时间减小,总权重延误时间也减小.(3)参数p对优化目标的影响从图4中可见,p=0.25与p=0.00相比,区域外权重延误时间减小,总权重延误时间增大.决策者可以通过调整p值获得不同的总权重延误与区域外权重延误的组合,参数p起到了调节区域外权重延误与总权重延误的作用.但随着区域内最大允许延误时间限制条件的增强(即从不限制到最大允许延误时间为5min的最严格限制),区域外权重延误时间的减少量呈递减趋势,总权重延误时间的增加量呈递增趋势,表示当存在较严格的区域内最大延误时间限制时,少量区域外权重延误时间的减少会导致较大的总权重延误时间增加,参数p对减少区域外延误的调节作用减弱.通过上述分析可见,与文献4中模型相比,本文模型增加外区域mit流量控制约束,使模型更符合区域性流量管理的实际需求,优化目标函数的调整也更能体现区域流量管理者的决策偏好,扇区内最大允许延误时问约束使管制员在实施生成策略时更便于控制,不会因此产生额外的工作负荷.3结束语本文建立的模型考虑了实际管制运行的需求和管理者的决策偏好,该模型可以为制定区域流量管理策略提供决策支持.通过对模型中约束条件和优化目标函数的参数进行灵敏度分析,进一步揭示了该模型生成的区域流量管理策略的特性.本文模型的目标函数采用了线性的航班权重延误时间,为了体现不同类型航班延误成本的不同,可以选用幂函数或指数函数表示的航班延误成本作为优化目标,此时采用cplex求解将不能满足实时性要求,为了提高求解速度,需要进一步研究使用遗传算法或模拟退火算法等人工智能算法进行快速求解.参考文献:f1sridharb,grabbes,mukherjeea.modelingandoptimizationintrafficflowmanagementj.proceedingsoftheieee,2008,96(12):20602080.2kopardekarp,greens,rohertyt,eta1.milesin.trailoperations:aperspectivecaiaas3rdannualaviationtechnology,integration,andoperationsforum.denve:aiaa,2003:1.113赵嶷飞,金长江.区域空中交通流量控制研究j.飞行力学,2002,20(2):6770.zhaoyifei,jinchangjiang.anapproachtoareatrafficflowcontrolresearchj.flightdynamics,2002,20(2):67-70.4bertismasd,patiersonss.theairtrafficmanagementproblemwithenroutecapacitiesj.operationsresearch,1998,46(3):406-422.5lullig,odonia.theeuropeanairtrafficflowmanagementproblemj.transportationscience,20o7,41(4):431443.6mukherieea,grabbes,sridharb,alleviatingairspacerestrictionsthroughstrategiccontrolcaiaaguidance,navigation,andcontrolconference.honolulu:aiaa,2008:111.7jakobovitsr,kopardekarp,burkej,eta1.algorithmsformanagingsectorcongestionusingtheairspacerestrictionplannercproc.ofthe7thusa/europeatmr&dseminar.barcelona:eurocontrol2007:1.10.8赵嶷飞.管制区短期空中交通流量管理的时隙一航线分配模型及算法j.航空,2009,30(1):121126.zhaoyifei.timerouteassignmentmodelandalgorithmforshorttermareatrafficflowmanagementj.actaaeronauticaetastronauticasinica,2009,30(1):121126.9synnestvedtrg,swensonh,erzbergerh.schedulinglogicformiles-in-trailtrafficmanage?mentr.washingtond.c.:nasatechnicalmemorandum,1995.10grabbes,sridharb.modelingandevaluationofmiles.in.trailrestrictionsinthenationalairspacecaiaaguidance,navigation,andcontrolconference.austin:aiaa,2003:ll3.11landrysj,farleyt,hoangt.expandingtheuseoftimebasedmetering:multicentertrafficmanagementadvisorcproceedingsofthe6thusa/europeatm2005r&dseminar.baltimore:faa,2005:110.12krozelj,jakobovitsr,pennys.analgorithmicapproachforairspaceflowprogramsj.354西南交通大学第47卷(上接第340页)8高阳,詹沙磊.基于第三方物流的多周期多目标产品回收网络设计j.控制与决策,2010,25(8):1164-l168.gaoyang,zhanshalei.designformulti-periodmultiobjectiveproductrecoverynetworksbasedonthirdpartylog