空中交通短期流量优化调度的动态网络流模型

空中交通短期流量优化调度的动态网络流模型

自20世纪80年代以来，该学院的航空流量管理取得了以下主要进展：1987年，odoni首次提出了一个问题，即如何实时规划和降低飞机的成本。1993年Terrab和Odoni对单机场地面等待策略问题(SAGHP)进行了研究;1994年Vranas、Bertsimas和Odoni提出多机场地面等待问题(MAGHP),把地面等待策略推广到整个机场网络。Vranas还研究了欧洲空中交通流量管理的最优时隙分配问题(OptimalSlotAllocation)。1997年Stock-Patterson进一步研究了飞机在机场网络中的最优速度调整以及航班为绕开恶劣气象条件的空域而重新选择飞行路线的问题,提出了空中交通流量管理问题(TFMP)和空中交通流量管理再寻径问题(TFMRP)。目前我国的空域尚未完全对民航开放,虽然总体飞行流量远小于发达国家,但分布不平衡,局部空域(如京、沪、穗3大机场的终端区)或繁忙航线成为空中交通网络的“瓶颈”。我国目前尚未设立中央流量管理机构,各大管制区分散实施流量管理和控制功能,管制区之间需相互协调。因此,现阶段我国空中交通流量管理的重点是研究面向管制区的短期流量管理的模型、算法和决策支持技术,而短期流量管理优化模型的研究在国内外文献还未见报导。1飞行流量的速度根据“效益最优”原则,空中交通短期流量管理问题可表达为:在未来有限时间内,当管制区内的某个或部分容量限制单元的容量发生变化时,制定出最优的飞行流量控制方案,使因流量控制而造成的总经济损失最小(或使总等待成本最小)。直观上,管制区内不同航向和不同高度层的航路构成了一个复杂的立体网络G(N,A),网络的每条弧(航路段)是容量限制单元,飞行流量在网络中从源点向汇点有序流动。我们作如下假设:1)空中交通流最小单位是单架飞机且不可再分。2)正常情况下飞行流量从源点传送到汇点的过程中总流量值没有损耗。3)空中交通网络中的弧都是有向弧,把双向航路定义为具有相同端点的一对方向相反的有向弧。4)假设每条弧的流量传送时间是恒定的,即假设不同型号的飞机飞越同一航路段的时间相等,当飞机类型相同(如都为喷气式客机)的情况下是近似成立的。5)由于未来两、三个小时内的各航路段容量可以准确预测,因此设未来时间区间T内弧(i,j)的容量估计值cij(t),t∈T是确定的。6)把时间区间T采样为n+1个彼此等距的时刻t0,t1,…,tn;弧容量cij(ti),i=0,1,…,n表示弧(i,j)在时刻ti和ti+1之间允许进入的流量上限。7)每个管制区通常划分为几个管制扇区,设任意时刻管制扇区内的总飞行流量存在确定上界,即不得超过管制员所能承受的最大工作负荷,并因管制员和扇区的不同而异。基于上述讨论,下面分别对空中交通管制区各组成环节以及空中交通流的动态行为进行建模。1管制移交点的建模为区别源点和汇点,我们把机场和与双向航路相连的管制移交点建模为一对源点和汇点,把与单向航路相连的管制移交点建模为单个源点或者单个汇点,如图1。区域空中交通网络通常具有多个源点和汇点。2主航台导航台是航路段之间的连接点,建模为网络中连接弧与弧的中间节点(非源点、非汇点)。3点的有序对i,j来表示把每一段航路(或进近走廊)建模为有向弧,用网络节点的有序对(i,j)来表示,如图2。每条弧有允许流量率cij(t)和传送时间aij两个参数;根据前面的假设,cij(t)是确定的,aij为常数。4空中等待把飞机的空中等待飞行建模为飞行流量在某个中间节点的自环上流动。设此自环的传送时间等于单位时间,流量率等于最大允许等待飞机数。5地面等待和管理系统区域外的等待在每个源点添加一段自环,表示地面等待或滞留等待过程,设此自环的流量率为+∞,传送时间等于单位时间。6有向弧集合飞行航班在管制区内的飞行路径可以表示为网络中从某一源点到某一汇点的相互连接的有向弧集合,即链。考虑到航班飞行通常要选择一、两个备降机场,则到达流量至少有两、三条可行链路。定义航班所有可行链路的集合为该航班的飞行计划;定义到达航班除正常飞行链路之外的所有可行链路的集合为该航班的备降飞行计划。7流量生产定义具有相同飞行计划的流量属于同一“品种”。显然在管制区内飞行的航班分属多种飞行计划,因此空中交通流是多品种的动态网络流。8源点到汇点的流量为确保问题有可行解,在模型中为每一“品种”的流添加一条从源点到汇点的虚拟弧,设其最大流量率为∞,传送时间为0。虚拟弧可保证所有从源点发出的流量在问题讨论的时间区间内都能到达汇点,但经过虚拟弧的流量要付出高昂惩罚费用。2st-dtmp数学模型2.1机场集合的计算设N=(I,A)表示管制区空中交通网络,i,j∈I表示网络中的节点,节点对(i,j)∈A表示网络中的弧;k∈K表示空中交通流的品种类型,s∈S表示管制区内的工作扇区序号;用T表示问题所考虑的时间区间集合,其中每个元素是均匀采样后的时刻。以下是所有符号定义和输入数据的列表:t时刻序号,t∈T={0,1,…,T}i,j顶点标号,i,j∈IIdep起飞机场集合Iarr降落机场集合Itpi有进入流量的管制移交点集合Itpo有流出流量的管制移交点集合Isrc源点集合,Isrc={Idep∪Itpi}⊂IIsink汇点集合,Isink={Iarr∪Itpo}⊂I且Isink∩Isrc=ØInod中间顶点集,Inod=IIsrc∪Isink}(i,j)弧序号,i,j∈I,(i,j)∈Ak空中交通流品种序号,k∈K={1,…,K}s管制扇区序号,s∈S={1,…,S}cij(t)航路段(i,j)在时刻t的最大允许流量率aij飞机经过航路段(i,j)的飞行时间(流的传送时间)r单位油耗费用系数cgi机场i的地面等待费用系数Ws管制扇区s的管制员工作负荷上限Pki(t)第k品种空中交通流t时刻计划从源点i发出的流量Hk(i,j)第k品种流的可行航路段集合(包括正常飞行计划和备用飞行计划),Gk(i,j)⊂K×AB(k)第k品种流的备降机场集合Ap从源点到汇点的虚拟弧集合(供不可行流使用)2.2交通流进入流量把网络流模型中的流变量定义为:fki,j(t)等于从t时刻到t+1时刻第k品种空中交通流在弧(i,j)上的实际进入流量(当且仅当(k,i,j)∈Hk(i,j)时有定义),t∈T。2.3运行费用bfki短期流量管理的目标是最小化总的飞行成本费用,目标函数由4项组成:Ζ=∑{t,k,(i,j):(k,i,j)∈Ηk(i,j)}r⋅aijfki,j(t)+∑{t,i∈Ιdep∪Ιtpi}Ci(t)di(t)+∑{t,k,(i,j):i∈B(k),(k,i,j)∈Ηk(i,j)}Μbfki,j(t)+∑{t,k,(i,j):(i,j)∈Ap}Μpfki,j(t).(1)第一项表示在实施流量管理期间所有飞机的飞行油耗费用。第二项表示由于实施流量控制而导致的地面等待费用和飞行流量在管制区外的滞留费用。当i∈Idep时,Ci(t)=cgi,即机场i的单位地面等待费用;当i∈Itpi时,Ci(t)表示滞留在上游管制区的流量的单位等待费用;而di(t)表示t时刻源点i处的滞留流量。di(t)=∑{τ:0≤τ≤t}∑k(Ρki(τ)-∑{j:(i,j)∈A}fki,j(τ))‚∀t,i∈Ιsrc(2)第三项表示所有因流量控制被调配到备降机场着陆的航班的额外备降费用,Mb为在备降机场降落一架次的费用系数。第四项是一项虚拟的惩罚项,表示任何从源点经虚拟弧到达汇点的流量所要付出的惩罚费用;通常选惩罚系数Mp为一充分大的正数,可保证在优化结果中流经虚拟弧的不可行流量尽可能少。2.4合同规定1ki,it-fkit-kit构成∑{j:(i,j)∈A,j≠i}fki,j(t)+fki,i(t)-fki,k(t-1)-Ρki(t)=0‚∀i∈Ιsrc‚k,t.(3)2[2]由来:“b表达[nd],t,nd,k,t,t,nod;k,t,t,t,k,t,t,t,t,k,t,t,k,t,t,nod,k,k,t,t,t,nod,k,k,t,t,t,nod,k,k,t,t,nd,k,k,t,nod,k,k,t,nod,k,k,k,k,k,t,k,k,k,t,k,k,k,t,k,k,t,k,k∑{j:(i,j)∈A}fki,j(t)-∑{j:(i,j)∈A}fkj,i(t-aji)=0‚∀i∈Inod,k,t.(4)3江阴高速a,i,t为例,k,t为v,t,v则v,t则v,t,v则v,tk,kit∑t,k∑i∈Ιsink∑{j:(j,i)∈A}-fkj,i(t)+V=0,(5)其中,V=∑t∑k∑i∈ΙsrcΡki(t).(6)42高速公路容量限制∑kfki,j(t)≤ci,j(t)‚∀t,∀(i,j)∈A.(7)52管理人员的工作量∑k∑{i,j:(i,j)∈As}∑{τ:t-aij<τ≤t}fki,j(τ)≤Ws‚∀s,t.(8)6网络流变量满足了团结条件fki,j(t)≥0,fki,j(t)∈Ζ‚∀i,j,k,t.(9)3k品种流的约束条件ST-TFMP的输出是在时间区间T内进入管制区的流量的最优控制方案。如果考虑在0时刻已经存在于管制区内的飞行流量的疏散问题(TFEP),则需对ST-TFMP模型作一些改进。设0时刻在管制区空域内的飞机总数为N;设任意一架需要疏散的飞机为α∈{α1,α2,…,αN},0时刻它在管制区空域内的位置可用一个四元组来表示:(α,i,j,tf),其意义为:在流量控制措施开始的0时刻,飞机α处于航路段(i,j)上,且距j点的飞行时间为tf。引入新的空中交通流品种:k′∈K′,其源点为j(j在ST-TFMP模型中为中间节点),汇点与原来飞行计划中的汇点相同(机场或管制移交点);对于源点j在tf时刻发送一个单位的k′品种流的行为,我们构造一个集合L={(j,tf,k′)|j∈Inod,tf≤max(aij),k′∈K′}来表示。当然对k′品种流也要规定可行路径集合:Hk′(i,j)={(k′,i,j)|(i,j)为k′品种流可行路径上的航路段}。设疏散流变量为:gk′i,j(t)等于从t时刻到t+1时刻k′品种流在航路段上的实际流量,且当(k′,i,j)∈Hk′(i,j)时有意义,t<maxTk′。新增疏散流约束条件如下:1)疏散流源点动态流量守恒∑{j:(i,j)∈Ak′}gk′i,j(t)=Qk′i(t)‚∀(i,t,k′)∈L.(10)方程右边的Qk′i表示在t时刻从中间节点i发出的第k′品种的疏散流的流量值。2)疏散流中间节点动态流量守恒方程∑{j:(k′,i,j)∈Ηk′(i,j)}gk′i,j(t)-∑{j:(k′,j,i)∈Ηk′(j,i)}gk′j,i(t-aji)=0‚∀i∈Inod,k′,t.(11)并且,原问题(ST-TFMP)的几个约束修改为:∑t,k,i∈Ιsink∑{j:(j,i)∈A}-fkj,i(t)+∑t,k′,i∈Ιsink∑{j:(j,i)∈A}-gk′j,i(t)+V+Ν=0.(5a)∑kfki,j(t)+∑k′gk′i,j(t)≤cij(t)‚∀t,∀(i,j)∈A.(7a)∑k∑{i,j:(i,j)∈As}∑{τ:t-aij<τ≤t}fki,j(τ)+∑k′∑{i,j:(i,j)∈As}∑{τ:t-aij<τ≤t}gk′i,j(τ)≤Ws‚∀s,t.(8a)此外,对于疏散问题,增加了新的目标函数Ζ′=∑{t,k′,i,j:(i,t,k′)∈L‚(k′,i,j)∈Ηk′(i,j)}r⋅aijgk′i,j(t)+∑{(t,k′,i,j):i∈B(k′)‚(k′,i,j)∈Ηk′(i,j)}Μbgk′j,i.(12)综上,考虑了管制区内初始飞行流量的疏散问题后的短期流量管理问题描述为:ST-TFMP1:MinZ+Z′s.t.(3)、(4)、(5a)、(6)、(7a)、(8a)、(10)、(11),且fki,j≥0,fki,j≥0,fki,j,gki,j∈Ζ‚∀i,j,k,k′,t.4模型计算性能分析本节采用中国民航华北空中交通管理局的实际数据来检验ST-TFMP模型的计算性能。原始数据选自1998年11月21日10∶30到13∶30期间的北京首都机场到达航班计划。根据第2节的方法,构建北京管制区空域的网络模型,如图3。其中Isrc={WXI,EPGAM,P07,ANRAT,ANDIN,BEDOG,ZN,ISGOD};Isink={ZBAA,ZBTJ};其余节点为中间节点,其中有6个空中等待点,它们的容量分别为:HG(11架),VYK(21架),LR(19架),OB(14架),以及降落跑道的两个头远台(4架)。流的品种数k=8。北京管制区空域被划分为3个区调扇区和2个进近扇区;到达流工作负荷上限为:区调东扇区为6架,其他4个扇区为4架。设Mp=1000,Mb=100,Ci(t)=10,r=1。时间采样以min为单位。为检验不同情况下ST-TFMP模型的计算性能,我们构建了4种典型场景。场景一:模拟首都机场正常运行(双跑道),降落容量为3架/5min;场景二:模拟首都机场单跑道运行,降落容量减小为1架/3min;场景三:模拟首都机场因恶劣天气原因从10∶30到13∶30期间关闭,降落容量0;场景四:模拟北京管制区受冷锋天气影响,航路段(ZN,KM)、(ISGOD,VYK)和(HG,VYK)在特定时间区间内临时关闭。我们采用GAMS2.50作为优化建模工具,采用Cplex6.0作为线性规划(LP)和混合整数规划(MIP)的求解工具;MIP的求解采用分支定界法,其中求解LP子问题采用修正单纯形法。求解用计算机的软硬件配置为:350MHz主频的AMD-K6-2CPU,128M内存,操作系统为WindowsNT4.0(整数运算性能为770.3MIPS,浮点运算性能为423.2MFLOPS)1。求解结