基于效率性和公平性的GDP时隙分配研究

李永庆，田 勇

(南京航空航天大学 民航学院，江苏 南京 210016)

近几年来，随着我国航空运输业的迅猛发展，空中交通量大幅增长，机场拥堵问题越来越突出.地面延误程序(GDP-Ground Delay Program)是空中交通流量管理中解决机场拥堵问题的一种有效措施.如何有效、合理、公平地分配时隙是GDP中的核心问题.国外对时隙分配已有一定研究，如RBS(Ration-By-Schedule)[1]算法、RBD(Ration-By-Distance)[2]算法等，国内也有学者对时隙分配问题提出了基于公平性或效率性的时隙分配模型，但很少有人提出同时兼顾效率和公平的时隙分配机制与方法[3].

若仅考虑时隙分配的效率性，虽然能减少机场总的延误成本，但航空公司承担的延误成本不能公平地分配，航空公司难以接受时隙分配的结果；若仅考虑时隙分配的公平性，虽然能保证各航空公司的时隙分配的公平性，但不能保证时隙分配的整体效率性.本文对效率性和公平性均衡的时隙分配方法进行了研究，通过建立均衡化数学模型实现时隙分配的总体最优性.

1 时隙分配模型

本文研究的地面等待策略旨在寻找效率性和公平性均衡的时隙分配方案，使时隙分配更趋合理.时隙分配的效率性是指时隙分配能高效的利用时隙资源，减少机场总的延误成本，公平性是指航空公司之间公平合理地分配时隙资源[4].

数学模型可表示为：

(1)

约束条件：

(2)

(3)

tj

(4)

(5)

主要参数说明如下：

F={f1，f2,…,fn}为参与地面等待的航班，f1∈F；S={s1,s2,…,sm}为机场执行GDP期间的可用时隙，由GDP执行期间机场单位每小时可接受的着陆航班数量(Arrival Acceptance Rate, AAR)来确定，sj∈S；tj为时隙sj的起始时间；ostai为表示航班fi的时刻表初始计划着陆的时间；xij为二进制决策变量，当航班fi选择了时隙sj时为1，否则为0；cij为航班fi分配到时隙sj时所引发的航班延误成本.

约束条件主要是对时隙分配的有效性进行约束，式(2)表示每个航班必须分配到一个时隙；式(3)表示一个时隙最多只能被一个航班使用；式(4)表示航班实际的着陆时间不能早于初始时刻表中计划的着陆时间.

2 公平性约束

时隙分配的公平性问题不能忽略，但公平性与效率性往往互为矛盾，追求公平往往会带来效率的下降[6].为实现时隙分配在效率和公平性上的均衡，本文在总体目标函数中引入了公平性指标.

(6)

相关的，同时定义协作效率函数Pα(xij)∈[0,1]，同样也是二进制决策变量xij的线性函数.当dα(xij)=1时，Pα(xij)=1，表示效率性最好；当dα(xij)=dmax时，Pα(xij)=0，表示效率性最差.可以定义协作效率函数为：

(7)

(8)

机场总体的公平性指标可以表示为各航空公司协作公平性指标的线性加权，结合式(8)可得：

(9)

综上所述，式(1)中的公平性决策目标可以表示为

(10)

(11)

3 遗传算法求解

上述模型为典型的整数规划模型，遗传算法是基于空间搜索的算法，适用于大规模并行计算，并能够以较大的概率寻找到最优解，对本文的整数模型能够较快地寻找到最优解.算法采用式(12)所示的适应度函数，式中Tmax为航班的延误最大估计值，f(x)为模型的目标函数.

(12)

3.1 编码策略

给每个参与GDP的航班分配时隙，构成染色体个体.航班所分配到的时隙为染色体的基因值，其值根据航班可用时隙随机产生，每个时隙只允许被分配一次，这种方式得到的编码是时隙元素的一个组合排列.

采用赌盘法(基于适应度比例)选择个体，个体i被选中的概率为：

(13)

其中：Fi为个体的适应度值；N为种群个体数目.

3.2 交叉

交叉操作是指从种群中随机选择两个个体，通过两个染色体的交换组合，把父个体的优秀特征遗传给子个体，从而产生新的优秀个体.为使新个体保留两个父个体的优良模式，本文采用单点、大片断基因保留、小片断基因保序的交叉方法[8]，即对于父个体1和2，随机地选择一个交叉位置，两个父体的基因分成了两部分，较长的一部分基因分别直接遗传给它们的子个体1和2，父体1中较短一部分基因按照在父个体2中的顺序重新排列后，作为子个体1的另一部分基因.同理，父体2中较短一部分基因按照在父个体1中的顺序重新排列后，作为子个体2的另一部分基因.此外，为了得到可行的个体，需要判断新个体是否满足约束条件，如果不满足则需重新进行交叉操作.

3.3 变异

变异操作使遗传算法具有局部的随机搜索能力，并可以加快算法速度.具体操作是：在染色体基因串中随机选择两个交换变异点，如果两位置处的时隙均是对应两航班的可用时隙，则交换它们，否则重新选择交换位置.

4 仿真验证

为验证理论的正确性，本文运用广州白云国际机场的航班时刻数据进行仿真验证.并将本文提出的时隙分配方法与现有的RBS算法相比较.原始数据和RBS算法分配结果如表1所示.

表1 原始数据和RBS算法分配结果

在计算航班延误成本时，延误成本等于延误时间与延误成本系数的乘积.在计算航班的延误成本系数时，重型、中型和轻型航班的单位延误运营成本分别设定为4 167元/h、2 916元/h和208元/h；国内、国际(要客)航班中每名旅客的平均延误成本分别为50元/h和100元/h.在用遗传算法求解时，选取种群规模为50，世代数为150，交叉率为0.7，变异率为0.1.见表2.

表2 本文方法与RBS算法效率性对比

本文所研究的时隙分配方法和RBS算法的公平性指标如表3所示.

表3 本文方法与RBS算法公平性指标对比

由表1、2可知，与RBS算法相比，本文所提方法的总延误时间与RBS算法相同，但总延误成本减少了10 869.5元，减少了近的33.4%.因此，该时隙交换方法有效的减少机场总延误成本，体现了优越的效率性.

由表3可以看出，本文提出的方法与RBS算法在时隙分配的公平性上有较大的提升，RBS算法总体公平性指标为0.28，而时隙交换后总体公平性指标为0.15，公平性指标越小，时隙分配越公平.

综合以上数据，可以看出本文的时隙分配方法不但减少了机场总延误成本，而且兼顾航空公司时隙分配的公平性，达到了预期的效果.

5 结 语

本文对地面等待中的效率性和公平性问题分别进行了定量分析，提出了基于效率性和公平性的地面等待数学模型，所研究的模型可以在减少机场总的延误成本的同时兼顾航空公司之间时隙分配的公平性.

参考文献：

[1] HOFFMAN R L, HALL W, BALL M O,etal. Collaborative decision making in air traffic flow management[R]. NEXTER Research Report, RR-99-2, UC Berkeley, 1999.

[2] BALL M O, HOFFMAN R. Ground Delay Program Planning Under Uncertainty Based on the Ration-by-Distance Principle[J]. Transportation Science, 2010, 22(1): 1-14.

[3] 张洪海，胡明华，陈世林. 基于3E均衡的CDM GDP机场时隙分配[J].人类工效学, 2010,16(3):49-52

[4] 徐肖豪，王 飞. 地面等待策略中的时隙分配模型与算法研究[J]. 航空学报，2010，31(10): 1993-2001.

[5] 徐肖豪，李 雄. 航班地面等待模型中的延误成本分析与仿真[J].南京航空航天大学学报, 2006, 38(1): 115-120.

[6] SHERALI H D, STAATS R W, TRANI A A. An airspace planning and collaborative decision-making model: Part I—Probabilistic conflicts, workload, and equity considerations[J].Transportation Science, 2003, 37(4): 434-456.

[7] SHERALI H D, STAATS R W, TRANI A A. An airspace planning and collaborative decision-making model: Part II—Cost model, data considerations, and computations[J].Transportation Science, 2006, 40(2): 147-164.

[8] 陶世群, 浦保兴. 基于遗传算法的多级目标非平衡指派问题求解[J].系统工程理论与实践, 2004, 8(4): 80-85.