基于多目标时隙优化模型在地面等待策略上的研究

张 虹， 熊 静， 张文成， 严 宇

(上海工程技术大学 航空运输学院，上海 201620)

0 引 言

现如今随着经济的发展，航空运输需求不断增长，航班延误也时有发生。航班延误不仅给旅客带来不便，也给航空公司等带来巨大的损失，而当目的机场产生容量不足这一情况时，将空中等待转化为地面等待，实行地面等待策略是如今的一大研究热点，地面等待策略的核心是时隙分配，时下国内外对时隙分配的研究主要局限于对时隙的公平性进行考虑，在充分考虑公平性的情况下忽视了时隙的效率性。

1987 年， Odoni[1]首次系统地阐述了空中交通流量问题的研究领域、基本概念和主要问题，提出了重新安排飞机起飞时间以使拥挤成本最小化的思想。1989 年， Terrab等人[2]将单机场确定型模型转化成了网络流模型，提出用最小费用流来求解模型。1994年Odoni等人[3]，Varanas等人[4]对地面等待的实时性问题和多机场受限的地面等待问题进行了研究，建立了著名的VBO模型。

20世纪90年代，胡明华等人[5]针对中国空域情况首次对地面等待策略进行研究。稍后，胡明华等人[6]还对多元地面等待策略下时隙分配进行研究，建立了以降低延误成本为决策目标的数学模型。接下来，胡明华等人[7]又在简单网络规划模型的基础上改进成本函数构造了改进的网络流规划模型。此后，董云龙[8]剖析了地面等待程序中公平性的重要性，改进了初始分配算法，提出了PRA算法、也就是二次整数规划算法。

综上论述可知，目前对时隙分配的研究主要集中在对时隙的初次分配，对于时隙的初次分配多是考虑时隙的公平性或效率性，鲜少有文献基于时隙的公平性和效率性建立多目标优化模型，对时隙的公平性和效率性同时加以考量，让时隙在初次分配时初步达到时隙的公平性和效率性。本文即在此基础上建立了基于公平性和效率性的多目标优化模型,并运用模拟退火算法进行求解，可以让优化目标初次达到时隙的效率性和公平性。

1 多目标时隙优化模型

本文主要建立基于航班总延误成本最低和航空公司平均延误成本最低的多目标优化模型，其中求解多目标优化模型的方法有很多，但本文主要使用权重法将多目标模型转化为单目标优化模型进行求解，如下所示：

minT(X)=λ1f1(x)+λ2f2(x),

(1)

λ1+λ2=1,

(2)

其中，λ1和λ2表示2个目标函数的系数权重，本文为了保证两模型的公平性，分别将两权重系数都设置为0.5。

式(1)中，f1(x)指的是航班总延误最低，主要模型可表示为：

(3)

(4)

(5)

(6)

xij∈(0,1)，

(7)

相应地，式(1)中的f2(x)指的是航空公司平均延误成本最低，主要模型如下所示：

(8)

(9)

(10)

xij∈(0,1),

(11)

研究可知，式(8)主要是利用方差最小化来体现航空公司的公平性。方差公式为：

D(X)=E{[X-E(X)]^2}.

(12)

方差是用来衡量一组数据离散程度的统计量，方差越大，离散程度越大；方差越小，离散程度越小。所以用方差来衡量公平性的话，方差越大，数据越离散，各航空公司的平均延误时间越不接近总航空公司延误时间，公平性差；方差越小，数据的离散程度小，各航空公司的平均延误时间越接近总航空公司延误时间，公平性越好。

2 模拟退火算法研究与应用

模拟退火算法是模仿自然界退火现象而得，利用了物理中固体物质的退火过程与一般优化问题的相似性，就是从某一初始温度开始，伴随温度的不断下降，为了避免陷入局部最优采用了Metropolis准则，最终使得算法收敛于全局最优。模拟退火算法的计算步骤可做设计表述如下：

Step 1初始化。任选初始解，i∈S,给定初始温度T0,终止温度Tf，令迭代指标k=0,Tk=T0。

Step 2随机产生一个领域解，j∈N(i)，(N(i)表示的领域)计算目标值增量Δf=f(j)-f(i)。

Step 3Δf<0,令i=j转Step4(j比i好,无条件转移)；否则产生ε∈(0,1)，若exp(-Δf/Tk)>ε,则令i=j(j比i好，有条件转移)。需特别指出，Tk高时，广域搜索;Tk低时，局域搜索。

Step 4若达到热平衡(内循环次数大于n(Tk)), 转Step 5，否则转Step 2。

Step 5k=k+1, 降低Tk，若Tk

上述是模拟退火算法的基本步骤，但模拟退火算法的地面等待策略时隙分配的运用中，研究推得的设计步骤可详述如下：

Step 1输入一个n*n的成本矩阵(n和参与的时隙数量相同)。

Step 2由于算法在时隙分配的应用中生成的解是一个向量，因此领域的产生，是通过随机调换这个向量中的任意两个位置，从而得到可行解。

Step 3解的接受与淘汰。在得到一个新解时，将新的解与当前解作比较，相减得到Δf，若Δf<0(本文是以最小化为例)，说明得到的新解相对于原始的解是更优化的，则当前值将被新解所取代；相反若Δf>=0，首先看新解所得出的适应度函数值的接收概率是否大于一个0～1之间的随机数。若大于则接收该并不是最优的新解，若小于则舍弃该解，重新生成新解。

Step 4终止条件。在内循环中设置一个Metropolis链，当内循环次数达到Metropolis链所设置的次数时则跳出，外循环通过降低初始温度，当最终的温度小于设置的最低温度值时则跳出外循环，循环结束。

3 算例验证

本文研究拟运用上海虹桥机场某天上午航班进场的航班时刻表的原始数据作为仿真数据，其中主要涉及到2个航空公司的11个航班，仿真数据见表1。

表1 数据验证表

由表1可知航班时刻表从进场的2:00开始直到2:40结束，当流量下降为10 min/架次时，利用RBS算法得到时隙的初次分配结果，详见表2。

研究中，根据前文求得的RBS算法下航班时刻表，利用上述建立的多目标优化模型求解航班的总延误成本、各航空公司平均延误成本，得到结果见表3。

由表3可知在RBS算法的基础上，总的延误成本较高，因此RBS算法的时隙排序方案并不是最佳排序方案。接下来，研究中将利用模拟退火算法对上述多目标优化模型进行求解。最终求得的结果见表4。

表2 RBS算法下时隙分配表

表3 RBS算法下航班延误损失表

由表4可知，利用模拟退火算法对多目标优化模型进行求解后得到总的延误成本为82 872。CZ航空公司和MU航空公司的延误成本分别为37 450和45 422，相对于RBS算法对时隙分配得到的延误成本都有所下降。最终运算结果见表5，研究对比结果绘制如图1所示。

表4 模拟退火算法下的多目标时隙分配表

Tab. 4 Multi-target time slot allocation table under simulated annealing algorithm

序号航班号航空公司OSTD类型最大载客人数模拟退火算法OSTD延误成本1MU4762MU2:00H2362:0002MU4413MU2:05M1623:3017 4993CZ6981CZ2:05H2233:0015 7274MU5805MU2:10M1892:1005CZ9343CZ2:15H2362:407 4646MU2386MU2:15M1503:1010 6827CZ9062CZ2:20H2502:2008CZ3539CZ2:25H2422:301 5229MU9514MU2:30M1623:4014 41110CZ3557CZ2:35H2203:2012 73711MU722MU2:40H2202:502 830总延误成本82 872CZ延误成本37 450MU延误成本45 422CZ平均延误成本7 490MU平均延误成本7 570

表5 计算结果对比

图1 结果对比图

由表5和图1分析可知，利用模拟退火算法对多目标优化模型进行求解，相比RBS算法的求解在总延误成本上减少了11.1%；在MU航空公司总延误成本上减少了15.10%；在CZ航空公司的总延误成本上减少了5.7%。并且2家航空公司的延误成本相对于RBS算法求得的延误成本更加平均。因此采用模拟退火算法对多目标优化模型进行求解在时隙的效率性上和公平性上都可以取得一定的优化效果。

4 结束语

本文主要研究了地面等待策略下基于时隙的公平性和效率性，建立了时隙多目标优化模型，并利用模拟退火算法对模型进行智能求解，最终结果相对于利用RBS算法求得的结果不仅是在总的延误成本上、还是各航空公司的平均延误成本上都有一定的优化。因此在时隙的初次分配上,利用模拟退火算法可以使得时隙初次分配达到效率性和公平性。