多机场网络系统流量分配策略

多机场网络系统流量分配策略（精选3篇）

多机场网络系统流量分配策略 篇1

多机场网络系统流量分配策略

摘要：为有效减少机场交通拥挤、降低航班延误,从系统角度研究战略层面的机场交通供需平衡问题.通过考虑单机场进场和离场间的相关性以及多机场联程航班间的.关联性,提出了开放式多机场有向网络交通流系统;基于多元容量受限约束和联程航班约束,以最小化网络系统内所有航班的总延误为目标,建立了开放式多机场网络配流模型.结合国内三大机场的实际航班数据,对模型进行了仿真验证.仿真结果表明:所建模型可以对多机场网络系统流量与容量进行协调优化匹配,充分利用系统容量最小化系统航班延误;可为空管部门提供流量调配优化策略、为民航部门制定航班计划提供辅助决策依据. 作者： 姜雨张洪海夏洪山 Author： JIANG YuZHANG Hong-haiXIA Hong-shan 作者单位： 南京航空航天大学,民航学院,南京,210016 期 刊： 系统工程理论与实践 ISTICEIPKUCSSCI Journal： SYSTEMS ENGINEERING ―THEORY & PRACTICE 年，卷(期)： ,31(2) 分类号： V355.1 U8 关键词： 空中交通流量管理 网络系统 多机场 配流 优化 机标分类号： V35 TP3 机标关键词： 多机场有向网络系统流量分配策略networkstrategy航班延误最小化系统容量配流模型开放式交通拥挤战略层面约束优化匹配优化策略通流系统平衡问题流量调配决策依据 基金项目： 国家科技部基金

多机场网络系统流量分配策略 篇2

出行时用户或者自由竞争追求费用最短的路径, 或者所有用户都由某个中央部门控制, 前者选择路径的结果是用户均衡, 即没有人能够通过单方面改变路径进一步降低自身费用,后者分配流量的结果是系统最优,即所有用户花费的费用总和最小。当静态交通需求量分配中,Roughgarden证明当路阻函数为系数非负的线性函数时,用户均衡导致的效率损失最多为系统最优的1/3, 当路阻函数是系数非负、 度数最大为d的多项式函数时, 给出纳什均衡流总费用与系统最优流总费用比值的上界是(1-d·(d+1)-(d+1)d)-1, 说明用户均衡与系统最优之间差距较大[1,2];著名计算科学家Papadimitriou等对博弈均衡的复杂性、最劣的均衡以及如何计算均衡做了深入研究[3,4,5];动态的交通流量分配研究还很少,例如,当n次连续的交通需求依次到达出发点选择路径到目的地去, 由于先到的用户并不知道随后有多少流量到达就不得不做出决策选择路径,通常采用占线和竞争策略的方法解决这样的问题,Tobias Harks等[7,8,9,10]给出了用户均衡占线策略(SUE)分配流量,研究了流量任意可分和不可分时的情

形, 给出了与多项式路阻函数最高度数有关的竞争比上界和下界; 随后他研究了带有时间窗的占线交通流量分配问题, 给出了SEQ和SEQ2策略, 并做了相应的竞争分析, 给出了竞争比的上界和下界。在占线问题中, 如果以Con(R)表示采用占线策略分配完流量序列R后所有用户花费的费用总和, 类似地, 以Copt(R)表示离线最优费用, 则占线策略的竞争比可以用系数Con(R)/Copt(R)来度量[6]。对于任意的需求序列R, 如果存在常数c使得Con(R)≤cCopt(R)+β,此处β是与R无关的一个常数,则称占线策略是c竞争的。

在静态流量分配中,用户均衡策略会导致很差的交通状况,而系统最优策略可以使得交通状况达到理想的状况,考虑到以往研究的不足和系统最优策略的优点,本文重点研究在占线交通流量分配中系统最优策略的竞争性能。本文第2节给出占线交通流量分配的数学模型及基本假设;与已有的用户均衡分配策略(SUE)不同,第3节给出流量分配后能使得当前所有用户花费费用总和最小的系统最优策略;第4节先对路阻函数是非负、非递减凸函数的情形进行竞争分析,然后进行路阻函数分别是系数非负线性函数和系数非负多项式函数下的竞争分析并给出相应的竞争比;第5节通过算例给出系统最优策略竞争比的下界。

2 问题描述及基本假设

问题描述:n次连续的交通需求依次到达出发点选择路径到目的地去,第i次交通需求量是ri,由于缺乏信息,第i次交通需求到达时用户只知道需求量r1,r2,…,ri-1,ri,而对于未来的需求量ri+1,ri+2,…,rn无法预知,但此时必须做出决策把ri单位的交通需求分配到网络上去,那么如何分配流量能使得所有用户花费的费用总和尽可能小呢?

给定一个有向交通网络G(V,E), V表示网络的节点集合,E表示路段e的集合;le(x)表示流量为x时通过路段e的费用,它是该路段上流量x非负的、非递减的凸函数;当流量序列r1,r2,…,ri,…,rn依次通过该网络时,第i次分配使用节点κi={i1,i2,…,ini},其中ri={ri1,ri2,…,rini};Pij表示起点sij到迄点tij之间所有路径的集合,fijp≥0是路径p∈Pij上的流量;可行流x就是对于所有的点v∈V, 能使${\displaystyle \sum _{e\in \delta {}^{+}(v)}x}{}_e^{ij}-{\displaystyle \sum _{e\in \delta {}^{-}(v)}x}{}_e^{ij}=\gamma {}_{ij}(v)$成立的流,其中δ+(v),δ-(v)分别表示从节点v流出、流入流量的路段集合, 如果v=sij, 则γij(v)=rij, 若v=tij, 则γij(v)=-rij; 第i次分配通过第j个节点分配到路段e∈E上的流量为$f{}_e^{ij}={\displaystyle \sum _{e\in p}f}{}_p^{ij}$,第i次分配在路段e上累计的流量为$f{}_e^i={\displaystyle \sum _{ij\in \kappa {}_i}f}{}_e^{ij}$; n次分配在路段e上总共分配的流量为$f{}_e={\displaystyle \sum _{i=1}^{n}f}{}_e^i$,用户在网络上花费的总费用为:$C(f)={\displaystyle \sum _{e\in E}l}{}_e(f{}_e)f{}_e={\displaystyle \sum _{e\in E}l}{}_e\left({\displaystyle \sum _{i=1}^{n}f}{}_e^i\right)\left({\displaystyle \sum _{i=1}^{n}f}{}_e^i\right)$。

因为用户在出行时总是追求费用最小的路径,而不考虑其它用户如何选路,从而会导致很坏的交通状况,而系统最优可以使得交通状况达到最优,但是用户必须接受控制才能实现系统最优;用户要改变已经选择好的出行路径,要付出额外费用,如果这个费用很大的,则用户最好的策略还是坚持原来的路径不变。

根据上面的分析以及为了研究方便,本文给出如下假设:

①任何时刻,任何一个点对之间的用户都听从某个中央部门的安排;

②用户一旦被分配到网络上,它的出行路径就不能再改变;

③网络上所有路段的通行能力都没有限制;

④交通流量是无限任意可分的,也就是每个用户携带的流量是无限小的。

3 系统最优策略

实施交通管理,最终的目标就是想使得交通状况达到最好,如果流量分配是静态的过程,只要采用系统最优的分配方式就可以使得交通状况达到最好;如果交通状况是一个动态的过程,需求一个接一个到来,系统最优分配方式分配流量的效果如何呢,这是交通部门关注的一个问题,下面重点研究系统最优策略在动态流量分配过程中的效果。

系统最优策略:对实时到达的交通需求量每一次都按系统最优方式分配,即每次流量分配结束后,网络上所有用户所花费费用总和最小,且流量一旦分配到网络上其出行路径就不能再改变。

根据前面的模型可知,利用系统最优策略分配流量时,求解下面的最优化问题(P1)就可以得到第k次分配到路段上的流量,

$\begin{array}{l}\min C{}^k(f{}^k)\\ \text{s}.\text{t}.{\displaystyle \sum _{e\in \delta {}^{+}(v)}f}{}_e^{ij}-{\displaystyle \sum _{e\in \delta {}^{-}(v)}f}{}_e^{ij}=\gamma {}_{ij}(v),\forall v\in V\\ f{}_e^k\ge 0,\forall e\in E\end{array}(\text{Ρ}1)$

其中,$C{}^k(f{}^k)={\displaystyle \sum _{e\in E}l}{}_e\left({\displaystyle \sum _{i=1}^{k}f}{}_e^i\right)\left({\displaystyle \sum _{i=1}^{k}f}{}_e^i\right)$。由于路阻函数是凸函数,第一个约束条件是流量的线性函数,因此,该规划是一个凸规划,可以在多项式时间内求解。

根据Roughgarden[1]可知,求解下面的规划(P2)也可以得到系统最优流:

$\begin{array}{l}\min {\displaystyle \sum _{e\in E}{\displaystyle {\int }_0^{f{}_e^i}(l{}_e\left({\displaystyle \sum _{k=1}^{i-1}f}{}_e^k+z\right)}}\\ +\left({\displaystyle \sum _{k=1}^{i-1}f}{}_e^k+z\right)l^{\prime }{}_e\left({\displaystyle \sum _{k=1}^{i-1}f}{}_e^k+z\right))dz\\ \text{s}.\text{t}.{\displaystyle \sum _{e\in \delta {}^{+}(v)}f}{}_e^{ij}-{\displaystyle \sum _{e\in \delta {}^{-}(v)}f}{}_e^{ij}=\gamma {}_{ij}(v),\forall v\in V\\ f{}_e^k\ge 0,\forall e\in E\end{array}(\text{Ρ}2)$

由规划(P2)可知,当交通状况处于系统最优状态时,在边际费用的意义上来说,交通状况处于纳什均衡状态。

4 系统最优策略的竞争分析

衡量一个占线策略好坏的重要指标就是该策略的竞争比,竞争比越小策略就越好。下面重点研究系统最优策略的竞争性能。由于路段上的通行费用随着流量的增加而增加,因此,一般假设路段上的路阻函数是流量非负、非递减的函数。本节先研究一般情形,即路阻函数是非负、非递减凸函数时系统最优策略的竞争比, 然后研究路阻函数分别是系数非负的线性函数和系数非负多项式函数时该策略的竞争比。

为了便于进行竞争分析,特给出以下符号和定义:

定义1 对每一个路段e∈E及其上的路阻函数le,令

$\begin{array}{l}\begin{array}{l}\upsilon {}_e^n(l{}_e,f{}_e)\\ =l{}_e(f{}_e)f{}_e-{\displaystyle \sum _{i=1}^{n}l}{}_e\left({\displaystyle \sum _{k=1}^{i}f}{}_e^k\right)f{}_e^i\\ -{\displaystyle \sum _{i=1}^n\left({\displaystyle \sum _{k=1}^{i}f}{}_e^k\right)}{l}^{\prime }{}_e\left({\displaystyle \sum _{k=1}^{i}f}{}_e^k\right)f{}_e^i\end{array}\\ \begin{array}{l}\omega (l{}_e;n,\lambda )\\ =\underset{x{}_e,f{}_e>0}{{\displaystyle \sup }}\frac{(d+1)(l{}_e(f{}_e)-\lambda l{}_e(x{}_e))x{}_e+\upsilon {}_e^n(l{}_e,f{}_e)}{l{}_e(f{}_e)f{}_e}\end{array}\end{array}$

其中, xe,fe是非负向量,fie是路段e上第i次分配的流量,n是交通需求次数,实数λ>0, d是自然数。令ω(L;$n,\lambda )=\underset{l{}_e\in L}{{\displaystyle \sup }}\omega (l{}_e$;n,λ),其中L是非负、非递减的凸函数组成的集合。

定义2 参数λ的可行集是Γ(L,n)={λ>0|1-(d+1)ω(L;n,λ)>0}。

4.1 非负、非递减凸路阻函数时的竞争比

先研究路阻函数是非负、非递减凸路阻函数时系统最优策略的竞争比。下面的变分不等式是进行竞争分析的基础。

引理1(变分不等式) 假设有n次连续的交通需求占线到达路网出发点选择路径到目的地去,如果路段上的路阻函数le是非负、非递减凸函数,采用系统最优策略分配流量时,下面的变分不等式成立:

${\displaystyle \sum _{e\in E}\left(l{}_e\left({\displaystyle \sum _{i=1}^{k}f}{}_e^i\right)+\left({\displaystyle \sum _{i=1}^{k}f}{}_e^i\right)l^{\prime }{}_e\left({\displaystyle \sum _{i=1}^{k}f}{}_e^i\right)\right)}(f{}_e^k-x{}_e^k)\le 0$

其中, fke是规划问题(P1)的解,xke该规划的任意一个可行解。

定理1 假设有n次连续的交通需求占线到达路网出发点选择路径到目的地去,如果网络上的路阻函数le是非负、非递减的凸函数,且对于任意实数x≥0,d≥1, xl′(x)≤dl(x)成立,则系统最优策略的竞争比是:

$\underset{\lambda \in \Gamma (L,n)}{{\displaystyle \inf }}\left(\frac{(d+1)\lambda }{1-\omega (L;n,\lambda )}\right)$

其中, L是非负、非递减的凸函数组成的集合。

证明 令f是按系统最优策略分配时产生的交通流,x是任意一个可行流,则

$\begin{array}{l}C(f)\\ \le {\displaystyle \sum _{e}l}{}_e(f{}_e)f{}_e+{\displaystyle \sum _{i=1}^n{\displaystyle \sum _e(l{}_e\left({\displaystyle \sum _{k=1}^{i}f}{}_e^k\right)}}\\ +\left({\displaystyle \sum _{k=1}^{i}f}{}_e^k\right)l^{\prime }{}_e\left({\displaystyle \sum _{k=1}^{i}f}{}_e^k\right))(x{}_e^i-f{}_e^i)\\ \le {\displaystyle \sum _{e\in E}(}\upsilon {}_e^n(l{}_e,f{}_e)+(d+1)l{}_e(f{}_e)x{}_e)\\ \le \lambda (d+1)C(x)\\ +{\displaystyle \sum _{e\in E}(}(d+1)(l{}_e(f{}_e)-\lambda l{}_e(x{}_e))x{}_e+\upsilon {}_e^n(l{}_e,f{}_e))\\ \le \lambda (d+1)C(x)+\omega (L;n,\lambda )C(f)\end{array}$

第一个不等式是由于引理1,最后一个不等式是由于ω(L;n,λ)的定义及λ属于可行集Γ(L,n)。取x是最优离线解就可以得到定理中的结论。证毕。

该定理给出了计算系统最优策略竞争比的一般方法,如果路阻函数是一般的非负、非递减函数,竞争比是多少无法得知,下面给出系数非负多项式函数的竞争比。

4.2 系数非负线性路阻函数时的竞争比

系数非负的多项式路阻函数是最简单也是最基本的一种,研究这类路阻函数的竞争比具有很重要的意义,因为咱实际中经常会把一般的路阻函数近似为线性或多项式类的函数来研究,具有很强的可操作性,下面研究路阻函数l是系数非负线性函数时的竞争比,先看下面引理。

引理2 假设有n次连续的交通需求占线到达路网出发点选择路径到目的地去,如果路阻函数是系数非负的线性函数l(x)=ax+b,式子ω(L;n,1)的值至多是(n-2)/2n.

证明 由不等式$(f-x)x\le \frac{1}{4}f{}^2$及柯西-施瓦兹不等式$\left({\displaystyle \sum _{i=1}^{n}a}{}_{i}b{}_i\right){}^2\le {\displaystyle \sum _{i=1}^{n}a}{}_i^2{\displaystyle \sum _{i=1}^{n}b}{}_i^2$可得

$\begin{array}{l}\omega (l{}_e;n,\lambda )\\ =\underset{x{}_e,f{}_e>0}{{\displaystyle \sup }}\frac{(d+1)[l{}_e(f{}_e)-\lambda l{}_e(x{}_e))x{}_e+\upsilon {}_e^n(l{}_e,f{}_e]}{l{}_e(f{}_e)f{}_e}\\ =\underset{x{}_e,f{}_e>0}{{\displaystyle \sup }}\frac{(d+1)[l{}_e(f{}_e)-l{}_e(x{}_e))x{}_e+\upsilon {}_e^n(l{}_e,f{}_e]}{l{}_e(f{}_e)f{}_e}\\ \le \underset{x{}_e,f{}_e>0}{{\displaystyle \sup }}\frac{2\cdot \frac{1}{4}a{}_{e}f{}_e^2-\frac{1}{n}a{}_{e}f{}_e^2}{a{}_{e}f{}_e^2}\\ \le \frac{n-2}{2n}\end{array}$

其中,$\upsilon {}_e^n(l{}_e,f{}_e)=l{}_e(f{}_e)f{}_e-{\displaystyle \sum _{i=1}^{n}l}{}_e\left({\displaystyle \sum _{k=1}^{i}f}{}_e^k\right)f{}_e^i-{\displaystyle \sum _{i=1}^n\left({\displaystyle \sum _{k=1}^{i}f}{}_e^k\right)}{l}^{\prime }{}_e\left({\displaystyle \sum _{k=1}^{i}f}{}_e^k\right)f{}_e^i=-\frac{1}{n}a{}_{e}f{}_e^2$.证毕。

定理2 假设有n次连续的交通需求占线到达路网出发点选择路径到目的地去,如果路段上的路阻函数是线性函数l(x)=ax+b, a,b≥0, 则系统最优策略的竞争比是4。

4.3 系数非负多项式路阻函数时的竞争比

本节考虑路阻函数是系数非负且度数最大是d的多项式时的竞争比,即路阻函数l∈Ld={adxd+…+a1x+a0,as≥0,s=0,1,…,d}。

引理3 假设有n次连续的交通需求占线到达路网出发点选择路径到目的地去, 如果路阻函数l∈Md, 则ω(Md;$n,\lambda )=(d+1)\underset{\mu >0}{{\displaystyle \sup }}\mu -\lambda \mu {}^{d+1}$.其中Md是单项式asxs,0≤s≤d组成的集合,参数λ≥1, s,d是正整数且s∈[d]。

证明 令f是由系统最优策略产生的交通流, x是任意一个可行流。 因为${\displaystyle \sum _{e}l}{}_e(f{}_e)f{}_e\le (d+1){\displaystyle \sum _{k=1}^{n}l}{}_e\left({\displaystyle \sum _{i=1}^{k}f}{}_e^i\right)f{}^k$,结合υne(le,fe)的定义,可知υne(le,fe)≤0。因此

$\begin{array}{l}\omega (l{}_e;n,\lambda )\\ =\underset{x{}_e,f{}_e>0}{{\displaystyle \sup }}\frac{(d+1)[l{}_e(f{}_e)-\lambda l{}_e(x{}_e))x{}_e+\upsilon {}_e^n(l{}_e,f{}_e]}{l{}_e(f{}_e)f{}_e}\\ \le \underset{x{}_e,f{}_e>0}{{\displaystyle \sup }}\frac{(d+1)[l{}_e(f{}_e)-\lambda l{}_e(x{}_e)]x{}_e}{l{}_e(f{}_e)f{}_e}\end{array}$

令μ=xe/fe,可得

$\omega (l{}_e;n,\lambda )=\underset{\mu >0}{{\displaystyle \sup }}\frac{(d+1)[l{}_e(f{}_e)-\lambda l{}_e(\mu f{}_e)]\mu f{}_e}{l{}_e(f{}_e)f{}_e}$

现在考虑路阻函数是单项式函数le(x)=asxs,s∈[d]的情形,

$\begin{array}{l}\omega (l{}_e;n,\lambda )\\ =\underset{\mu \ge 0}{{\displaystyle \sup }}\frac{(d+1)(a{}_{s}f{}_e^s-a{}_s\lambda \mu {}^{s}f{}_e^s)\mu f{}_e}{a{}_{s}f{}_e^{s+1}}\\ =(d+1)\underset{\mu \ge 0}{{\displaystyle \max }}\mu -\lambda \mu {}^{s+1}\end{array}$

因为λ≥1,上式的最大值可以在μ≤1处得到。因为s∈[d],所以

$\begin{array}{l}\omega (l{}_e;n,\lambda )\\ =(d+1)\underset{\mu \ge 0}{{\displaystyle \max }}\mu -\lambda \mu {}^{s+1}\\ \le (d+1)\underset{\mu \ge 0}{{\displaystyle \max }}\mu -\lambda \mu {}^{d+1}\end{array}$

引理4 假设有n次连续的交通需求占线到达路网出发点选择路径到目的地去,如果路段上的路阻函数l∈Ld,则ω(le;n,λ)的值至多是d/(d+1),其中λ=(d+1)d-1.

证明 当λ=(d+1)d-1时, ω(le;n,λ)的最大值在μ=1/(d+1)处取得,代入得

$\begin{array}{l}\omega (l{}_e;n,\lambda )\\ =(d+1)\left[\frac{1}{d+1}-(d+1){}^{d-1}(d+1){}^{-d-1}\right]\\ =\frac{d}{d+1}\end{array}$

定理3 假设有n次连续的交通需求占线到达路网出发点选择路径到目的地去,如果路阻函数l是系数非负、度数最大是d的多项式函数时,则系统最优策略的竞争比是(d+1)d+1.

5 系统最优策略竞争比的下界

上一节研究了系统最优策略的竞争比,本节研究该策略竞争比的下界。通过下面的算例,在所给定的需求序列下,利用系统最优策略分配流量时所有用户花费的费用与最优费用的比值不小于5/3。

定理4 假设有n次连续的交通需求占线到达路网出发点选择路径到目的地去,如果网络上的路阻函数是系数非负的线性函数,则系统最优策略的竞争比不小于5/3。

证明 考虑下图中给出的网络,网络上的路阻函数分别是l(si,s)(x)=0, l(ti,t)(x)=0, l(si,t1)(x)=i, l(s,t)(x)=x.

需求σ={1,2,…,k,k+1}依次到达,在第i次需求中都有1单位的流量从si到ti(i=1,…,k),在第k+1次需求中有d单位的流量从s到t. 在每一次分流过程中,系统最优策略分给siti路径上的流量是$\frac{1}{2}$,另一半流分配到s,t路径上去,因此,系统最优策略产生的费用是$C{}_{SS{\rm O}}(\sigma )=\frac{1}{2}k(k+1)+\left(\frac{k}{2}+d\right){}^2$;最优的离线解在前k次分流中所产生的费用是${\displaystyle \sum _{i=1}^{k}i}=\frac{1}{2}k(k+1)$,第k+1次产生的费用是d2,因此,离线问题的最优费用是$C{}_{opt}(\sigma )=\frac{1}{2}k(k+1)+d{}^2$,令$k=n-1,d=\frac{n}{2}$可得$\frac{C{}_{SS{\rm O}}(\sigma )}{C{}_{opt}(\sigma )}=\frac{\frac{1}{2}k(k+1)+\left(\frac{k}{2}+d\right){}^2}{\frac{1}{2}k(k+1)+d{}^2}=\frac{5n{}^2-5n+1}{3n{}^2-2n}\le \frac{5}{3}$。

显然,当n=1时,定理2中给出的上界是一个紧界。通过对比可以发现系统最优策略分配流量之后,能够使得网络上流量所花费的费用是最优费用的5/3倍,而已有的用户均衡策略分配流量所产生的费用大于等于系统最优费用的3倍,从这个意义上来说,系统最优策略优于用户均衡策略。

6 结束语

当交通需求动态达到时,本文采用系统最优策略去分配交通需求量。对典型的变分不等式进行合理处理的基础上,得到了计算系统最优策略竞争比的计算方法,特别地,当路阻函数是系数非负的线性函数时,证明该策略是4-竞争的;当路阻函数是系数非负、度数至多是d的多项式函数时,该策略是(d+1)d+1-竞争的,并给出系统最优策略竞争比的下界是5/3;本文研究还有好多不足之处,比如目前还没有证明该策略是最优策略;国内外占线交通流量分配问题研究的还非常少,还有很多值得研究的方向,比如流量不可分的情形; Stacheklberg博弈中的占线交通流量分配问题等。

参考文献

[1]Roughgarden T,Tardos E.How bad is selfishrouting?[J].Journal of the ACM,2002,49(2):236~259.

[2]Roughgarden T.The price of anarchy isindependent of the network topology[J].Journalof Computer and System Science,2003,67:341~364.

[3]Koutsoupias E,Papadimitriou C H.Worst caseequilibria[A].Lecture Notes in Computer Science1563[C].Berlin:Springer,1999:404~413.

[4]Deng X,Papadimitriou C H,Safra S.On the complexity of equilibrium[J].Journal of Computer andSystem Sciences,2003,67(2):311~324.

[5]Papadimitriou C H,Roughgarden T.Computingequilibria in multi-player games[A].Proceedingsof SODA[C].Berlin:Springer,2005:82~91.

[6]Manasse M S,McGeoch L A,Sleator D D.Competitive algorithms for on2line problems[A].Proceedings 20th Annual ACM Symposium onTheory of Computing[C].1988:322~33.

[7]Harks T,et al.Nonadaptive selfish routing withonline demands[Z].CAAN 2007,LNCS 4852:27~45.

[8]Harks,Stefan.Online multicommodity routingwith time windows[Z].Berlin:Konrad-Zuse-Zentrum für Informationstechnik,2007-12-28.

[9]Harks T,Heinz S,Pfetsch M E.Competitiveonline multicommodity routing[Z].ZIB Report 07-16,Zuse Institute Berlin,2007.

多机场终端区联合放行策略优化 篇3

随着经济的不断发展,航空运输量大幅增加,机场终端空域的“瓶颈”现象越发突出,尤其是在空域拥塞地区出现第二、第三个机场之后,终端区的航线网络更加错综复杂,由终端空域引发的延误越来越多,同时潜在的不安全因素也大大增加。国家的“十二五”规划明确我国要建设北方、华东、中南、西南、西北五大机场群。届时,多机场系统将成为一种普遍现象,如何安全有效的利用多机场终端空域成为当代民航业备受关注的问题。解决终端区拥挤最常用的方法是航班排序,现在的排序方式主要依靠管制部门间的管制放行协议和管制员手工排序,为了提高多机场终端区的运行效率,有必要采取一种智能的离场航班排序方法。

单机场终端区离场航班放行问题的研究受到国内外学者的广泛关注[1,2,3],已有的研究大多是基于航班的地面操作。目前,针对多机场终端区离场航班联合放行问题的研究甚少。文献[4]研究了多机场系统的出现和系统内各机场之间的相互影响,文献[5]以最小化所有航班通过空域限制系统的时间为目标,研究了多机场终端区协同离场和协同进场的优化问题,文献[2]给出了多机场终端区公共离场定位点时段流量超出容量时容流协同优化方法,但其研究是基于时段总流量,没有分配航班的具体过点时刻。文献[6]研究了多机场GDP放行策略,但只考虑了多机场之间的公共离场定位点容量受限时对离场航班的影响,对机型差异、航班延误成本等影响因素未加考虑。

本文以多机场终端区空中单元受限为研究重点,综合航班离场时的各影响因素,以最小延误成本为目标,建立多机场的联合放行模型,并设计遗传算法对模型进行求解,同时给出了仿真算例。

1 多机场联合放行问题建模

1.1 问题描述

多机场终端区指同一终端区内包含多个机场。多机场终端区内来自不同机场的航班共享某些空域资源,当这些空域单元的流量大于容量时,部分航班需执行地面等待。为了充分利用多机场终端区内容量受限单元的时隙资源,本文从多机场系统的层面研究多机场的联合放行策略。

多机场终端区内离场容量受限单元一般包括跑道系统、离场定位点(DF)、扇区等。因此,本文对多机场联合放行策略的具体描述如下:已知给定时间区间内各机场的离场航班时刻表、各航班过离场定位点的时间以及各点的时间间隔限制,考虑机型、延误成本、机场优先级等因素,在充分利用定位点容量的基础上,合理分配各离场定位点的时隙资源,确定各离场航班的实际起飞时间,使各机场的离场航班过同一离场定位点时满足间隔限制,同时避免不必要的空中盘旋或是长时间地面开车等待,从而提高航班运行的安全性,降低航空公司的运营成本。为了区分不同机场航班延误损失的差异性,本文采用了当量延误成本的计算方法,即将单架航班实际延误成本与其所在机场的优先级的乘积作为此航班的当量延误成本。

根据模型需要本文作以下假设:

1) 终端区各空域元素在未来各时段的容量值已知。

2) 航班不能早于航班时刻表的时间起飞。

3) 同一机场不同机型航班从跑道起飞后到达同一离场定位点所用时间相同。

4) 所有航班的地面单位时间延误已知。

1.2 优化模型

目标函数为最小化离场航班总的延误损失:

$c(t)=\min {\displaystyle \sum _{m\in {\rm M}}{\displaystyle \sum _{f\in F{}_m}{\displaystyle \sum _{t\in {\rm T}}\alpha }}}{}_m(f)c{}_f(t{}_{dc}^f-t{}_{de}^f)x{}_t^f$

约束条件:

${\displaystyle \sum _{m\in {\rm M}}\alpha }{}_m=1$ (2)

${\displaystyle \sum _{t\in {\rm T}}x}{}_t^f=1$ (3)

pmt≤Dm(t) (4)

t${}_{de}^f$≤t${}_{dc}^f$∀f∈Fm (5)

t${}_{dc}^f$+ω≤t${}_{dc}^{f^{\prime }}$∀f∈Fm,f′∈Fm (6)

t${}_{dc}^f$+ft${}_f^p$+MIT≤t${}_{dc}^{f^{\prime }}$+ft${}_{f^{\prime }}^p$ (7)

模型参数及符号意义如下:

T为航班f可能的离场时段集合,由等长度的时间段t组成,t∈T;

M为终端区内机场个数,m∈M;

Fm为机场m的起飞航班集合;

t${}_{de}^f$为航班f的计划离场时刻;

t${}_{dc}^f$为航班f的实际离场时刻;

pmt为机场m在t时段的流量;

Dm(t)为时间段t内机场m的离场容量,∀m∈M,f∈Fm;

αm(f)为航班f起飞机场m的优先级因子;

P(f)为航班f在航路中经由的离场定位点集合;

ft${}_f^p$为航班f由起飞机场到达各离场定位点的飞行时间,p∈P(f);

ω为航班f的尾流间隔;

f′为航班f的后继航班;

MIT(t)为在时间段t内离场定位点的限制间隔;

cf为航班f的单位时间延误损失。

式(3)确保每个航班只分配一个离场时刻。式(4)起飞机场容量约束。式(5)限制航班不提前起飞。式(6)航空器的尾流间隔限制。式(7)航迹间隔限制。下面将设计遗传算法对模型求解,并用实例数据对模型进行仿真验证。

2 遗传优化设计

多机场联合放行问题的实质是重新排列经过公共离场点的航班顺序,使总的延误成本最小,属于组合优化问题。当问题规模增大时,组合优化问题的搜索空间将急剧增加,传统方法较难求解。遗传算法是求解这类问题的最佳工具之一,它同时处理群体中的多个个体,减少了陷入局部最优解的风险,因此本文应用遗传算法[3,7,8,9]求解,求解过程中适应度函数如式(8)所示。式中ε是一极小的常数,设为1,目的是防止c(t)为0时适应度函数无意义。

$F(c(t))=\frac{1}{c(t)+\epsilon }$ (8)

2.1 遗传编码设计

采用排列编码方式进行编码。排列编码也叫序列编码,是针对一些特殊问题的特定编码方式。该编码方式将有限集合内的元素进行排列,若集合内包含m个元素,则存在m!种排列方法,例如多机场终端区有A、B 2机场,则将两机场的离场航班按初始离场时刻表的起飞顺序进行编码,并在同一编码中同时包含A、B 2机场的离场航班。如A机场有20个航班,B机场有10个航班,则编码1,2,21,3,23,4,…20,30。编码中小于等于20的元素代表A机场的离场航班,大于20的元素代表B机场的离场航班,构成如图2所示的染色体个体。

2.2 种群个体初始化

初始种群的个体随机产生,但要确保每个航班编码在每条染色体中有且仅有1次。

2.3 选择操作

采用基于适应度选择的轮盘赌算法对初始种群进行选择操作,以预先设定的概率从种群中选择与初始种群数量相同的个体。适应度大的个体被选中的几率大,从而改善了种群质量。

2.4 交叉操作

交叉操作的目的是产生新的个体,模拟自然界的交叉变异过程。采用单点交叉的方式进行交叉操作,设计如下操作步骤:

步骤1。按照交叉概率从父代中随机选择2个个体;

步骤2。通过随机算法选择交叉点,确定交叉区域,如P1、P2 2个个体,交叉点选择为5,交叉区域如下划线所示:

P1=1 2 3 4 5 6 7 8 9 P2=2 1 3 5 8 7 9 4 6

步骤 3。为了防止交叉后某些航班编码染色体中的缺失,本文特别设计如下操作,即将P1的交叉区域添加到P2之前,将P2的交叉区域添加到P1之前,得到新的序列:

P1’=8 7 9 4 6 1 2 3 4 5 6 7 8 9

P2’=5 6 7 8 9 2 1 3 5 8 7 9 4 6

步骤 4。除去新序列中重新出现的元素,得到最终子代个体:

P1’’=8 7 9 4 6 1 2 3 5 P2’’=5 6 7 8 9 2 1 3 4

2.5 变异操作

采用多点变异方法,按照变异概率随机选择进行变异操作的个体,随机选择2个变异点,然后交换2点的编码值。

P1=1 2 3 4 5 6 7 8 9 P2=1 2 7 4 5 6 3 8 9

3 算例分析

假设某多机场终端区内有A、B 2个机场,DF1、DF2、DF3是2机场的公共离场定位点。某日09:00-09:30时段内,DF1点流量控制,过DF1的航空器时间间隔为5 min。机场A、B的初始离场航班时刻表见表1。2机场离场航班在过公共离场定位点时存在时刻冲突或不满足定位点的间隔限制,需要对2机场离场航班重新排序,确定各航班的实际起飞时刻,使之在满足公共离场定位点的间隔要求的同时最小化总的延误成本。

仿真优化时,按照国际民航组织( ICAO)的标准,根据飞机的尾流强弱将航班分为重型、中型和轻型类[9];根据文献[10]对延误成本的分析确定本文航班延误成本cf;根据多机场终端区内各机场流量大小、航班连续性等各因素确定各机场的优先级因子。本文假设机场A为终端区内的主要机场,它的优先级因子设为0.7,机场B的优先级因子设为0.3。由于2机场的优先级是相对值,所以本文中延误损失也是关于机场优先级的相对值。用Matlab编写遗传算法程序,种群规模50,最大进化代数300,交叉概率0.6,变异概率0.1。

优化后2机场的离场航班时刻表如表1所示,此时航班经过各管制单元的时间满足了各单元的间隔限制,同时,通过实施多机场的联合放行,减少了各管制部门的协调,减轻了管制员的负荷。多机场的联合放行使各航班提前确定了各自的实际起飞时间,避免了长时间的关舱门后的地面等待,机场和航空公司可以提前安排旅客在候机楼休息,提高了服务质量。与FCFS相比本文方法效率更高更经济,对比结果见表2。图2为遗传算法优化时得到的总成本曲线,由图可知,在计算过程中种群质量不断改善,总成本不断减小,最终趋于一个恒定值,这说明遗传算法运行良好。

4 结 论

研究了多机场联合放行问题,建立了多机场联合放行的优化模型。设计了求解模型的遗传算法程序。仿真结果表明,通过本文设计的优化模型求解多机场联合放行问题,可有效减少航班的延误成本,减轻管制员负荷,提高空域利用率。

参考文献

[1]王来军,史忠科.航班离场排序问题的遗传算法设计[J].系统工程理论与实践,2004(9):119-125.

[2]张洪海.机场终端区协同流量管理关键技术研究[D].南京:南京航空航天大学,2009.

[3]Capri S,Ignaccolo M.Genetic algorithms for solvingthe aircraft-sequencing problem:the introduction of de-partures into the dynamic model[J].Journal of AirTransport Management 2004,10(5):345-351.

[4]Bonnefoy P A,Hansman R J.Emergence and impactof secondary airports in the united states[C]∥Chicago:AIAA 4th Aviation Technology,Integration and Opera-tion and Operation Forum,2004:1-12.

[5]Husni Idris,Ph D.Queuing analysis of interdependen-cies between multiple-airport system operations[C]∥AIAA 9th Aviation Technology,Integration,and Cone-rence,2009:1-10.

[6]吕双回,胡明华.基于启发式隐枚举算法的多机场GDP放行策略[J].武汉工程大学学报,2010,32(1):97-99.

[7]Delahaye Daniel,Sofiane Oussedik,Stephane P.Air-space congestion smoothing by multi-objective geneticalgorithm[C]∥New York:ACM Symposium on Ap-plied Computing,Santa Fe,USA,2005.

[8]王小平,曹立明.遗传算法理论、应用与软件实现[M].西安:西安交通大学出版社,2002.

[9]张兆宁,王莉莉.空中交通流量管理理论与方法[M].北京:科学出版社,2009.