基于多目標時隙優(yōu)化模型在地面等待策略上的研究

張 虹， 熊 靜， 張文成， 嚴 宇

(上海工程技術大學 航空運輸學院，上海 201620)

0 引 言

現如今隨著經濟的發(fā)展，航空運輸需求不斷增長，航班延誤也時有發(fā)生。航班延誤不僅給旅客帶來不便，也給航空公司等帶來巨大的損失，而當目的機場產生容量不足這一情況時，將空中等待轉化為地面等待，實行地面等待策略是如今的一大研究熱點，地面等待策略的核心是時隙分配，時下國內外對時隙分配的研究主要局限于對時隙的公平性進行考慮，在充分考慮公平性的情況下忽視了時隙的效率性。

1987 年， Odoni[1]首次系統地闡述了空中交通流量問題的研究領域、基本概念和主要問題，提出了重新安排飛機起飛時間以使擁擠成本最小化的思想。1989 年， Terrab等人[2]將單機場確定型模型轉化成了網絡流模型，提出用最小費用流來求解模型。1994年Odoni等人[3]，Varanas等人[4]對地面等待的實時性問題和多機場受限的地面等待問題進行了研究，建立了著名的VBO模型。

20世紀90年代，胡明華等人[5]針對中國空域情況首次對地面等待策略進行研究。稍后，胡明華等人[6]還對多元地面等待策略下時隙分配進行研究，建立了以降低延誤成本為決策目標的數學模型。接下來，胡明華等人[7]又在簡單網絡規(guī)劃模型的基礎上改進成本函數構造了改進的網絡流規(guī)劃模型。此后，董云龍[8]剖析了地面等待程序中公平性的重要性，改進了初始分配算法，提出了PRA算法、也就是二次整數規(guī)劃算法。

綜上論述可知，目前對時隙分配的研究主要集中在對時隙的初次分配，對于時隙的初次分配多是考慮時隙的公平性或效率性，鮮少有文獻基于時隙的公平性和效率性建立多目標優(yōu)化模型，對時隙的公平性和效率性同時加以考量，讓時隙在初次分配時初步達到時隙的公平性和效率性。本文即在此基礎上建立了基于公平性和效率性的多目標優(yōu)化模型,并運用模擬退火算法進行求解，可以讓優(yōu)化目標初次達到時隙的效率性和公平性。

1 多目標時隙優(yōu)化模型

本文主要建立基于航班總延誤成本最低和航空公司平均延誤成本最低的多目標優(yōu)化模型，其中求解多目標優(yōu)化模型的方法有很多，但本文主要使用權重法將多目標模型轉化為單目標優(yōu)化模型進行求解，如下所示：

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 模擬退火算法研究與應用

模擬退火算法是模仿自然界退火現象而得，利用了物理中固體物質的退火過程與一般優(yōu)化問題的相似性，就是從某一初始溫度開始，伴隨溫度的不斷下降，為了避免陷入局部最優(yōu)采用了Metropolis準則，最終使得算法收斂于全局最優(yōu)。模擬退火算法的計算步驟可做設計表述如下：

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若達到熱平衡(內循環(huán)次數大于n(Tk)), 轉Step 5，否則轉Step 2。

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

上述是模擬退火算法的基本步驟，但模擬退火算法的地面等待策略時隙分配的運用中，研究推得的設計步驟可詳述如下：

Step 1輸入一個n*n的成本矩陣(n和參與的時隙數量相同)。

Step 2由于算法在時隙分配的應用中生成的解是一個向量，因此領域的產生，是通過隨機調換這個向量中的任意兩個位置，從而得到可行解。

Step 3解的接受與淘汰。在得到一個新解時，將新的解與當前解作比較，相減得到Δf，若Δf<0(本文是以最小化為例)，說明得到的新解相對于原始的解是更優(yōu)化的，則當前值將被新解所取代；相反若Δf>=0，首先看新解所得出的適應度函數值的接收概率是否大于一個0～1之間的隨機數。若大于則接收該并不是最優(yōu)的新解，若小于則舍棄該解，重新生成新解。

Step 4終止條件。在內循環(huán)中設置一個Metropolis鏈，當內循環(huán)次數達到Metropolis鏈所設置的次數時則跳出，外循環(huán)通過降低初始溫度，當最終的溫度小于設置的最低溫度值時則跳出外循環(huán)，循環(huán)結束。

3 算例驗證

本文研究擬運用上海虹橋機場某天上午航班進場的航班時刻表的原始數據作為仿真數據，其中主要涉及到2個航空公司的11個航班，仿真數據見表1。

表1 數據驗證表

由表1可知航班時刻表從進場的2:00開始直到2:40結束，當流量下降為10 min/架次時，利用RBS算法得到時隙的初次分配結果，詳見表2。

研究中，根據前文求得的RBS算法下航班時刻表，利用上述建立的多目標優(yōu)化模型求解航班的總延誤成本、各航空公司平均延誤成本，得到結果見表3。

由表3可知在RBS算法的基礎上，總的延誤成本較高，因此RBS算法的時隙排序方案并不是最佳排序方案。接下來，研究中將利用模擬退火算法對上述多目標優(yōu)化模型進行求解。最終求得的結果見表4。

表2 RBS算法下時隙分配表

表3 RBS算法下航班延誤損失表

由表4可知，利用模擬退火算法對多目標優(yōu)化模型進行求解后得到總的延誤成本為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分析可知，利用模擬退火算法對多目標優(yōu)化模型進行求解，相比RBS算法的求解在總延誤成本上減少了11.1%；在MU航空公司總延誤成本上減少了15.10%；在CZ航空公司的總延誤成本上減少了5.7%。并且2家航空公司的延誤成本相對于RBS算法求得的延誤成本更加平均。因此采用模擬退火算法對多目標優(yōu)化模型進行求解在時隙的效率性上和公平性上都可以取得一定的優(yōu)化效果。

4 結束語

本文主要研究了地面等待策略下基于時隙的公平性和效率性，建立了時隙多目標優(yōu)化模型，并利用模擬退火算法對模型進行智能求解，最終結果相對于利用RBS算法求得的結果不僅是在總的延誤成本上、還是各航空公司的平均延誤成本上都有一定的優(yōu)化。因此在時隙的初次分配上,利用模擬退火算法可以使得時隙初次分配達到效率性和公平性。