劉艷紅，高 林，李耀華

（中國民航大學(xué)航空工程學(xué)院，天津 300300）

基于經(jīng)濟損失的航班延誤恢復(fù)模型研究

劉艷紅，高 林，李耀華

（中國民航大學(xué)航空工程學(xué)院，天津 300300）

分析了航班延誤的恢復(fù)調(diào)度問題，并針對問題提出了一種機場大面積航班延誤恢復(fù)模型，模型考慮了航班延誤的延誤時間，還考慮了不同機型對航班延誤經(jīng)濟損失造成的影響。構(gòu)造了基于免疫機制的免疫遺傳算法來求解模型，此算法保留了標(biāo)準(zhǔn)遺傳算法隨機全局并行搜索的特點，又在相當(dāng)大的程度上避免了未成熟收斂。用實際的航班信息進行仿真研究結(jié)果表明，文中的模型和算法切實可行。

航班延誤經(jīng)濟損失；免疫機制；免疫遺傳算法

改革開放以來，隨著航空運輸業(yè)的迅速發(fā)展，空中交通網(wǎng)絡(luò)的擁塞現(xiàn)象日益嚴(yán)重。擁塞導(dǎo)致起飛航班的延遲，影響到達航班的順序，給用戶帶來不便，造成航空公司的巨大損失，甚至影響了飛行的安全性。據(jù)統(tǒng)計，美國在20世紀(jì)90年代初，每年因航班延誤造成的延誤損失就高達2.5億美元。近幾年美國每年的延誤損失甚至高達了30億美元[1]。本世紀(jì)初，Mark Hansen研究了延誤后如何盡快恢復(fù)的理論和模型，他以洛杉磯機場為例，使用線性和非線性回歸模型的方法分析了美國幾大機場的航班延誤及飛行時間正?；绦?，但對國內(nèi)大多數(shù)航空公司的航班恢復(fù)調(diào)度并不太適用[2]。

目前，中國在進行航班延誤恢復(fù)時的航班調(diào)度上基本采用先到先服務(wù)算法（FCFS），雖然對于管制員比較容易實施和操作，但是調(diào)度的效率低，因此建立合理的恢復(fù)模型已大勢所趨。徐肖豪等學(xué)者也對延誤恢復(fù)問題進行了全面研究，提出了各種地面等待模型，但這些模型多以延誤時間作為衡量地面等待策略的標(biāo)準(zhǔn)，沒考慮不同機型對航班延誤經(jīng)濟損失造成的影響[3]。文獻[4]針對延誤航班恢復(fù)模型定義了航班影響因子，考慮航班延誤的經(jīng)濟效益，但沒有考慮機場容量的限制。本文提出了一種機場大面積航班延誤恢復(fù)模型，該模型可以提供航班延誤恢復(fù)時機場出發(fā)航班的最優(yōu)分配方案，使延誤損失最小，大幅提高航空運輸?shù)慕?jīng)濟效益，并構(gòu)造了一種基于免疫機制的遺傳算法來求解此模型。

1 航班延誤恢復(fù)模型

1.1 問題描述

航班延誤是指航班由于某種原因沒有按照公布的時刻出發(fā)或到達，即屬于不正常航班。正常航班符合以下條件：

1）在班期時刻表公布的離站時間后15 min（北京、上海、廣州、深圳25 min）之內(nèi)正常起飛的航班；

2）在班期時刻公布的到達時間開艙門的航班。不正常航班：不符合正常航班全部條件的航班。造成航班延誤的因素很多，一是天氣等自然因素造成的延誤；二是航空公司自身的原因造成的延誤，如飛機出現(xiàn)機械故障、飛機調(diào)配、發(fā)行計劃安排出現(xiàn)問題等；三是空中流量飽和，空管對飛機起飛進行控制造成的延誤。其中天氣原因是主要原因。

航班延誤不僅給旅客帶來諸多不便，也使航空公司蒙受經(jīng)濟損失，而且嚴(yán)重威脅到機場及空域的安全。航空延誤所帶來的問題[1]包括：①導(dǎo)致運行成本上升0.9%～2.3%（因航空公司規(guī)模不同而不同）；②導(dǎo)致高價值商務(wù)旅客流失；③使航空公司在旅客面前失去誠信；④增加地面和客艙服務(wù)難度；⑤引發(fā)旅客投訴和法律糾紛；⑥飛機利用率下降、機組利用率下降；⑦對飛行安全不利。

1.2 航班延誤經(jīng)濟損失的構(gòu)成

航班延誤經(jīng)濟損失通常包括顯性損失和隱性損失兩部分。顯性損失包括航空公司經(jīng)濟損失和旅客經(jīng)濟損失，航空公司經(jīng)濟損失由延誤航班運營成本和延誤航班盈利損失兩部分組成。隱性損失主要指航空公司的形象和名譽的損失，由于這些隱性損失的不確定性，因此，本文在計算航班延誤經(jīng)濟損失的時候并沒有考慮這些隱性損失。

1.2.1 航空公司經(jīng)濟損失

1）延誤航班的運營成本

延誤航班的運營成本與延誤航班的機型有著直接聯(lián)系，起飛質(zhì)量越大的飛機，其停場費、起降費、旅客服務(wù)費等就越高，相應(yīng)的地面等待成本也就越高。本文根據(jù)國際民航組織（ICAO）的標(biāo)準(zhǔn)，按照飛機的尾流強弱將飛機分3類分別討論運營成本，如表1所示。以中型飛機B737－300為例，據(jù)計算，1架飛機每年花費的租賃費、稅金、停場費、飛機維護費用和相應(yīng)的航材費用等固定性費用為2 500萬元，按1年有365天計算，1天的成本約為7萬元。為了方便分析，本文假設(shè)重型機、中型機和輕型機延誤的運營成本分別為10萬元/天、7萬元/天和5 000元/天，各機型每小時延誤運營成本a0的值如表1所示。

對于不同的機型，其延誤運營成本c0（t）為

式中：t為延誤時間。

2）延誤航班的盈利損失

表1 各類飛機每小時延誤運營成本Tab.1 Operating costs of different aircraft per hour

航空器作為航空公司的主要生產(chǎn)工具，其目的除了要為旅客提供優(yōu)質(zhì)的服務(wù)外還要為航空公司創(chuàng)造利潤，因此，當(dāng)航班發(fā)生延誤時，航空公司的盈利也會受到直接影響，造成航空公司的經(jīng)濟損失。延誤航班的盈利損失與航班最大載客人數(shù)、航班客座率和航空公司的凈利潤率密切相關(guān)。根據(jù)2004年英國《商業(yè)航空》[2]的統(tǒng)計可得出中國航空公司的平均凈利潤率r約為2.98%。從中國實際情況出發(fā)，假設(shè)航班客座率s為75%，平均票價a為750元，平均飛行時間f為2 h，因此，令m表示航班最大載客人數(shù)，則各航空器每小時可為航空公司賺取的利潤an為

延誤航班的盈利損失為

1.2.2 旅客經(jīng)濟損失

航班延誤造成的旅客經(jīng)濟損失與飛行的等級相關(guān)。國外相關(guān)機構(gòu)就航班延誤對旅客造成的經(jīng)濟損失做過較為系統(tǒng)的分析（如表2所示），得到旅客的平均時間價值為 28.6$·h－1，其中最低時間價值為23.8$·h－1，最高時間價值為 35.6$·h－1。

表2 國外旅客延誤時間價值Tab.2 Delay time values of foreign passengers

根據(jù)國外旅客延誤時間價值并結(jié)合中國飛行的分類，中國民航運輸中對于普通國內(nèi)航班飛行每名旅客平均延誤經(jīng)濟損失約為50元·h－1，對于國際航班和重要客人的飛行每名旅客平均延誤經(jīng)濟損失約為100元·h－1。航班延誤造成的旅客經(jīng)濟損失cp（t）為

式中：ap為航班單位每名旅客的平均延誤經(jīng)濟損失。

1.3 航班延誤恢復(fù)模型建立

航班延誤恢復(fù)調(diào)度（recovery scheduling of flight delays，RSFD）是指由于某些原因造成了大面積的航班不能正常起飛，當(dāng)延誤恢復(fù)時，要重新調(diào)度這些延誤了的航班。調(diào)度的任務(wù)是給出一種航班調(diào)度方案，使所有延誤的航班在盡可能短的時間內(nèi)起飛，并使得延誤造成的經(jīng)濟損失盡可能小。在文獻[4]的研究成果基礎(chǔ)上，進行了深入研究，并對模型進行了改進，這樣，建立了如下航班延誤的恢復(fù)模型

式中：F為所有航班的總延誤經(jīng)濟損失；n為延誤航班總數(shù)；c（tj）為航班的總延誤經(jīng)濟損失；c0（tj）、cn（tj）、cp（tj）分別為航班fj的運營成本、盈利損失和旅客經(jīng)濟損失，具體計算已在前面提出；tj為航班fj的延誤時間，由實際起飛時刻和計劃起飛時刻決定，而實際起飛時刻由航班延誤恢復(fù)時刻和航班延誤恢復(fù)調(diào)度方案決定；將執(zhí)行航班恢復(fù)的時間平均分成若干段，每段用Δtj表示；aΔtj表示航班fj的預(yù)計降落時間所在的時間段值；dj表示航班fj降落后允許的最大延誤時間；lij=0表示航班fj未在Δtj時間段降落，等于1則表示航班fi在Δtj時間段降落；mΔtj表示在時間段Δtj的機場的容量值。

目標(biāo)函數(shù)（5）保證延誤造成的總經(jīng)濟損失最少；約束條件（6）即保證了航班fj在其預(yù)計降落時間之前的時間段不允許降落，又保證了航班延誤不能超過其最大延誤值；約束條件（7）保證了在時間段Δtj降落的航班不能超過其機場容量值。

目前，解決航班恢復(fù)調(diào)度問題主要采用的是順延的辦法，即先來先服務(wù)（FCFS）策略，其思路為延誤恢復(fù)時按照航班原來的起飛順序調(diào)度航班，該法雖然簡單，但沒有考慮航班、航空公司和旅客的各種因素，因此，往往不能令人滿意。本文嘗試采用免疫遺傳算法來求解該問題。

2 航班延誤恢復(fù)調(diào)度模型求解算法

2.1 抗體結(jié)構(gòu)

抗體編碼采用自然數(shù)編碼方式，所有延誤的航班按照時刻表中的順序設(shè)置標(biāo)號分別為1、2、3、…、n，即：X={1，2，3，…，n}。每個抗體基因為 M，M={a1，a2，a3，…，an}，其中 ai∈X 且 ai≠aj，即 M 表示航班恢復(fù)調(diào)度的一個排列序列；還定義輸出變量數(shù)k，k表示適應(yīng)值或聚合適應(yīng)值。如上所述，每個抗體均由一個（1×h）矩陣表示，其中h=n+k，其機構(gòu)如圖1所示。假設(shè)免疫系統(tǒng)由N個抗體組成（即群體規(guī)模為N），整個群體的數(shù)據(jù)結(jié)構(gòu)便是一個N×（n+k）的矩陣。

圖1 抗體的數(shù)據(jù)結(jié)構(gòu)Fig.1 Data structure of antibody

2.2 免疫遺傳算法

免疫遺傳算法是基于生物免疫機制提出的一種改進的遺傳算法[4]，其將實際求解問題的目標(biāo)函數(shù)對應(yīng)為抗原，而問題的解對應(yīng)為抗體。基于免疫原理的遺傳算法與標(biāo)準(zhǔn)遺傳算法相比，具有如下顯著特點：①具有免疫記憶功能，該功能可以加快搜索速度，提高遺傳算法的總體搜索能力；②具有抗體的多樣性保持功能，利用該功能可以提高遺傳算法的局部搜索能力；③具有自我調(diào)節(jié)功能，這種功能可用于提高遺傳算法的全局搜索能力，避免陷入局部解。免疫遺傳算法即包括標(biāo)準(zhǔn)遺傳算法中的選擇、交叉、變異等功能，又包括免疫機制的免疫記憶、多樣性保持、自我調(diào)節(jié)等功能，它們都是針對抗體進行的。

在本算法中定義了下列名詞：多樣度、親和度、濃度。多樣度是抗體的多樣性測度?？贵w基因座j的信息熵Hj（N）可定義為其中pij為第i個符號出現(xiàn)在基因座j上的概率，且可定義為：pij=在基因座j上出現(xiàn)第i個符號的總個數(shù)/N。由此可得平均熵H（N）

兩個抗體u和v之間的親和度定義為Au，v，則

Au，v取值范圍為 0～1，Au，v越大，表示 u、v 兩個抗體越親和，Au，v=1則表示u，v兩者基因完全一致，若將兩個抗體之間的親和度概念擴展到整個群體，則得到群體親和度A（N）?？贵w的濃度ci即群體中相似抗體所占的比重，即

ci=和抗體i具有很大親和度的抗體數(shù)/

抗體總數(shù)N （10）

2.3 算法步驟

1）初始化種群，根據(jù)所要求解的問題，隨機生成N個個體作為初始種群As。

2）計算當(dāng)前種群中所有個體的適應(yīng)值。

3）對當(dāng)前的種群Ak進行交叉操作，得到種群Bk，然后對種群Bk進行變異操作，得到種群Ck。

4）根據(jù)式（9）計算當(dāng)前種群Ck的抗體信息熵H和群體親和度A，與閥值A(chǔ)0比較。若A>A0，則轉(zhuǎn)至步驟5）；若不成立，則轉(zhuǎn)至步驟2），迭代代數(shù)加一。

5）隨機產(chǎn)生P個新抗體，與種群Ck結(jié)合，產(chǎn)生新種群 Dk，此時抗體總數(shù)為（P+N）；根據(jù)式（10）計算抗體濃度及聚合適應(yīng)度。

6）基于抗體濃度更新群體，并對記憶單元進行更新。

7）判斷當(dāng)前代數(shù)是否達到進化截止代數(shù)或當(dāng)前群體的抗體平均濃度是否達到穩(wěn)定，若達到截止代數(shù)或穩(wěn)定，則輸出最優(yōu)解，算法結(jié)束；否則轉(zhuǎn)至步驟2），迭代代數(shù)加一。

3 仿真研究

選取中國某樞紐機場的80個航班數(shù)據(jù)進行試驗，將時間劃分成若干時間段，每段為15 min。假設(shè)上午9：00開始出現(xiàn)了不利于飛行的大霧天氣，造成了機場旅客滯留、大面積航班延誤。直到11：00天氣條件轉(zhuǎn)好，才可以進行正常飛行。延誤航班數(shù)據(jù)如表3所示[5]。

表3 航班數(shù)據(jù)Tab.3 Scheduled flight data

為了驗證算法，本文采用標(biāo)準(zhǔn)遺傳算法和免疫遺傳算法來求解航班恢復(fù)模型，進行了比較研究。在算法求解中，本文算法選取參數(shù)如下：抗體規(guī)模N=20，隨機產(chǎn)生的新抗體個數(shù)一般為群體規(guī)模的40%[6]，即P=8，相似度常數(shù)λ=0.9，閥值A(chǔ)0=0.25，交叉和變異的概率分別為0.15和0.1，算法結(jié)束準(zhǔn)則為連續(xù)迭代100代。標(biāo)準(zhǔn)遺傳算法的參數(shù)選取如下：抗體規(guī)模N=20，交叉概率為0.15，變異概率為0.1，算法結(jié)束準(zhǔn)則為連續(xù)迭代100代。根據(jù)表3的數(shù)據(jù)，結(jié)果收斂圖如圖2所示，兩種算法最優(yōu)目標(biāo)函數(shù)值分別為1 512 606和1 541 079，標(biāo)準(zhǔn)遺傳算法也可以求得可行解，但比免疫遺傳算法結(jié)果較差，從圖2中還可以看出，免疫遺傳算法使結(jié)果快速地向最優(yōu)結(jié)果靠近，在種群上整體尋優(yōu)性能優(yōu)于標(biāo)準(zhǔn)遺傳算法，收斂速度更快（圖中曲線1表示免疫遺傳算法的求解適應(yīng)值曲線，曲線2表示標(biāo)準(zhǔn)遺傳算法的求解適應(yīng)值曲線）。

為了驗證本文模型和算法的實用性，利用傳統(tǒng)的FCFS策略和本文的免疫遺傳算法分別得到的航班排序和總延誤經(jīng)濟損失對比如表4所示。免疫遺傳算法的結(jié)果比FCFS策略節(jié)約了207 224元，因此按照免疫遺傳算法的排序結(jié)果調(diào)度航班，可以更為有效地減少經(jīng)濟損失。

表4 FCFS和免疫遺傳算法的恢復(fù)結(jié)果Tab.4 Recovery results of FCFS and immune genetic algorithm

4 結(jié)語

本文對航班延誤恢復(fù)調(diào)度進行了研究。為使航班延誤恢復(fù)調(diào)度更加合理，目標(biāo)函數(shù)設(shè)計綜合考慮了航班延誤的多項經(jīng)濟損失，較詳細地分析了各項經(jīng)濟損失的計算過程，并結(jié)合實際的約束條件構(gòu)建了一種新的航班延誤恢復(fù)模型。同時，構(gòu)造了免疫遺傳算法對模型進行求解。通過實際數(shù)據(jù)進行應(yīng)用研究，結(jié)果表明本文建立的模型和算法切實可行，產(chǎn)出的恢復(fù)調(diào)度序列效果良好，可降低航空公司的運營成本和提高運作效率。

[1] 彭莉娟，吳 鹍.基于累積延誤損失算法的GHP模型[J].系統(tǒng)仿真學(xué)報，2008，20（17）：44-46.

[2]張 靜.2004年世界前100家航空公司經(jīng)營狀況[J].中國民用航空，2005，6（11）：27-31.

[3]徐肖豪，李 雄.航班地面等待模型中的延誤成本分析與仿真[J].南京航空航天大學(xué)學(xué)報，2006，38（1）：115-120.

[4] 丁建立，王新茹.航班延誤恢復(fù)調(diào)度的混合粒子群算法[J].交通運輸工程學(xué)報，2008，8（2）：19-22.

[5] 丁建立，計金玲.基于免疫機制的航班延誤快速恢復(fù)模型及實現(xiàn)[J].計算機工程與設(shè)計，2008，29（19）：29-32.

[6] 陳麗安，張培銘.免疫遺傳算法在MATLAB環(huán)境中的實現(xiàn)[J].福州大學(xué)學(xué)報，2004，32（5）：55-59.

Study on Recovery Model of Flight Delays Based on Economic Loss

LIU Yan-hong，GAO Lin，LI Yao-hua
（Aeronautic Engineering College， CAUC， Tianjin 300300，China）

The recovery scheduling of flight delays is analyzed， a rapid recovery model of large-scale airport flight delays is presented， the model considers not only time of flight delays， but also economic loss of flight delays of different aircraft types.And an immune genetic algorithm is suggested to solve the model，which is improved immune system based on immune system，reserves the feature of stochastic global parallel search of genetic algorithm，and avoids immature convergence considerably.The simulation result with flight data shows that the model and algorithm suggested are feasible and effective.

economic loss of flight delays；immune system；immune genetic algorithm

TP29

A

1674－5590（2010）02－0046－05

2010-06-10；

2010-07-16 基金項目：中國民航大學(xué)青年骨干教師基金項目（062084）

劉艷紅（1970—），女，河南確山人，副教授，碩士，研究方向為飛機結(jié)構(gòu)設(shè)計與修理技術(shù)，智能結(jié)構(gòu)設(shè)計與控制技術(shù).

（責(zé)任編輯：楊媛媛）