基于航空公司成本最小化的飛機(jī)排班問(wèn)題模型與算法

吳東華, 夏洪山

(南京航空航天大學(xué) a.繼續(xù)教育學(xué)院;b.民航學(xué)院,南京 210016)

定義2對(duì)每個(gè)最優(yōu)值Z*l,(l=1,2,…,6),

基于航空公司成本最小化的飛機(jī)排班問(wèn)題模型與算法

吳東華a,b, 夏洪山*b

(南京航空航天大學(xué) a.繼續(xù)教育學(xué)院;b.民航學(xué)院,南京 210016)

針對(duì)影響航空公司運(yùn)營(yíng)成本的四個(gè)關(guān)鍵因素,在滿足航班銜接、航班覆蓋和機(jī)隊(duì)規(guī)模約束條件下,以最小化運(yùn)營(yíng)成本、最小地面等待時(shí)間、最小總飛行時(shí)間絕對(duì)偏差和最少起降次數(shù)為目標(biāo)函數(shù),建立了飛機(jī)排班問(wèn)題的 0-1 整數(shù)模糊線性規(guī)劃數(shù)學(xué)模型.基于東方航空公司實(shí)際數(shù)據(jù),應(yīng)用模糊線性規(guī)劃理論對(duì)模型進(jìn)行驗(yàn)證,表明該模型可行,算法有效.

航空運(yùn)輸;飛機(jī)排班;多目標(biāo)優(yōu)化;計(jì)算機(jī)仿真;東方航空公司

1 引 言

飛機(jī)排班問(wèn)題是多目標(biāo)多約束條件的組合優(yōu)化問(wèn)題,是民航界著名的 NP 難題.合理的飛機(jī)排班不僅有助于航班的安全、正點(diǎn)運(yùn)行,而且還能夠提高機(jī)隊(duì)的利用率,有效地降低運(yùn)營(yíng)和維護(hù)成本.航空公司優(yōu)化飛機(jī)排班問(wèn)題的目的是增加旅客運(yùn)輸、貨運(yùn)運(yùn)輸?shù)确矫娴氖杖?降低航空公司的運(yùn)營(yíng)成本,綜合考慮機(jī)隊(duì)飛行的經(jīng)濟(jì)效益和社會(huì)影響.

國(guó)外大多數(shù)航空公司的航線網(wǎng)絡(luò)都是各種形態(tài)的樞紐輪輻式(hub-and-spoke) 結(jié)構(gòu),在各樞紐之間及輪輻城市之間有很高的航班頻次,每天的航班計(jì)劃基本相同,而且其限制飛機(jī)排班的一個(gè)最重要約束是“4 天維護(hù)規(guī)則”.而在我國(guó),航空公司的運(yùn)營(yíng)主要是基于點(diǎn)到點(diǎn)的單樞紐模式,一周內(nèi)各天的航班計(jì)劃有較大的差異,飛機(jī)排班時(shí)需考慮的約束較多,因此國(guó)外現(xiàn)有的研究結(jié)果并不適用于我國(guó),必須找到一種切實(shí)可行、適應(yīng)我國(guó)航空公司運(yùn)營(yíng)的方式.國(guó)內(nèi)研究飛機(jī)排班問(wèn)題有:孫宏等人應(yīng)用模擬退火算法、二部圖最大匹配方法和固定工件排序模型及 Hungarian 算法研究了基于最少飛機(jī)數(shù)、飛機(jī)使用均衡和滿足飛機(jī)調(diào)度指令的飛機(jī)排班問(wèn)題,并在其《飛機(jī)排班數(shù)學(xué)規(guī)劃模型》中,對(duì) 20架飛機(jī),35 個(gè)航班應(yīng)用上述算法得到一個(gè)滿意的排班方案時(shí)間接近 23 秒[1].王偉、王錦彪從劃分與劃分加細(xì)的角度討論了航班組合等問(wèn)題[2].近年來(lái),高強(qiáng)[3]等設(shè)計(jì)了一種基于約束編程思想的列生成算法,將機(jī)型指派、路線選擇與機(jī)尾號(hào)指派綜合考慮,構(gòu)建了飛機(jī)排班的整數(shù)規(guī)劃與約束規(guī)劃雜交一體化模型.魏星等人[4]在其基礎(chǔ)上提出了一種加入航班經(jīng)停并以星期為排班周期的綜合排班新方法.廖峰等[5]應(yīng)用圖著色理論,根據(jù)" 先到先服務(wù)"的原則給出了飛機(jī)分配的頂點(diǎn)序列著色算法.朱星輝等人[6]把飛機(jī)排班問(wèn)題構(gòu)建為多商品網(wǎng)絡(luò)流模型,并應(yīng)用列生成算法求解.國(guó)外相關(guān)研究有:Clarke 等人[7]將飛機(jī)路線問(wèn)題轉(zhuǎn)換為帶有邊約束的旅行商問(wèn)題(TSP),并利用 Lagrangian 松弛算法求解;Papadakos[8]建立了航班計(jì)劃的多個(gè)綜合優(yōu)化模型,并在 Bender's 分解及列生成法的子問(wèn)題中應(yīng)用啟發(fā)式方法加速求解過(guò)程. Mattias[9,10]建立了基于列生成法的飛機(jī)排班的約束編程模型,并用約束傳播加速列的生成.

上述算法均為民航飛機(jī)排班問(wèn)題的解決提供了思路,然而,已有算法均不能有效解決飛機(jī)排班過(guò)程中的多目標(biāo)優(yōu)化問(wèn)題,沒(méi)有從根本上提高航空公司的經(jīng)濟(jì)效益.本文結(jié)合航空公司實(shí)際運(yùn)營(yíng)管理情況,通過(guò)分析國(guó)內(nèi)航空公司運(yùn)營(yíng)成本的構(gòu)成,針對(duì)影響其收益的四個(gè)關(guān)鍵要素,借鑒已有模型的合理性,建立了飛機(jī)排班問(wèn)題的 0-1 整數(shù)線性規(guī)劃模型,并應(yīng)用模糊數(shù)學(xué)理論對(duì)該模型進(jìn)行了求解.

2 飛機(jī)排班問(wèn)題的數(shù)學(xué)建模

為了從根本上提高航空公司效益,需要在影響航空公司收益的諸多要素中找到關(guān)鍵要素.飛機(jī)排班問(wèn)題的數(shù)學(xué)模型將在滿足航班銜接、航班覆蓋與機(jī)隊(duì)規(guī)模的基本運(yùn)行約束條件下,以這些關(guān)鍵要素為優(yōu)化目標(biāo).

2.1 航空公司收益與運(yùn)營(yíng)成本分析

《從統(tǒng)計(jì)看民航》[11]中的數(shù)據(jù)顯示了近年來(lái)我國(guó)民航企業(yè)業(yè)務(wù)收入的狀況(見(jiàn)表1).從表中我們發(fā)現(xiàn),我國(guó)民航企業(yè)業(yè)務(wù)收入在逐年增加,其中國(guó)內(nèi)航線收入一直高于國(guó)際及地區(qū)航線運(yùn)輸收入,幾乎是其兩倍.而航空公司的客運(yùn)和貨運(yùn)運(yùn)輸收益卻高于通用航空收入、機(jī)場(chǎng)服務(wù)收入與其他收入總和,大約占總收入的 60%.因此,既然飛機(jī)是一種昂貴的設(shè)備,那只有保證每天一定數(shù)量的飛行時(shí)間,盡量提高飛機(jī)的日利用率,才能最大限度地保證航空運(yùn)輸收入的增加,從而提高經(jīng)濟(jì)效益.

表1 2005-2008 年民航企業(yè)業(yè)務(wù)收入 (單位:萬(wàn)元) ________Table1 Operation revenue of civil aviation enterprises from 2005 to 2008(unit:ten thousand yuan)

從成本上來(lái)說(shuō),國(guó)內(nèi)航空公司的運(yùn)營(yíng)成本通常包括飛行運(yùn)營(yíng)成本(也稱直接運(yùn)營(yíng)成本 DOC)和非直接運(yùn)營(yíng)成本( 也稱間接運(yùn)營(yíng)成本) 兩部分[12],其具體內(nèi)容及相應(yīng)影響因素、所占比例如表2所示.

表2 航空公司運(yùn)營(yíng)成本構(gòu)成Table2 The construction of the airline operation cost

從表2可以看出,雖然飛行運(yùn)營(yíng)成本和非直接運(yùn)營(yíng)成本占總運(yùn)營(yíng)成本的比例相當(dāng),但在飛行運(yùn)營(yíng)成本中有更多可以進(jìn)一步優(yōu)化的部分,比如:直接飛行成本和飛機(jī)維修成本兩項(xiàng)就占飛行運(yùn)營(yíng)成本的 3/4 之多,占總運(yùn)營(yíng)成本的 40%.通過(guò)表2 還可以看出,影響直接飛行成本的因素主要有飛機(jī)日利用率、航段耗油量及國(guó)際油料價(jià)格.其中的國(guó)際油料價(jià)格在一定時(shí)間內(nèi)是相對(duì)穩(wěn)定的,模型中可以使用一個(gè)常量替代之.航段耗油量與飛機(jī)任務(wù)航段里程是成正比關(guān)系的,飛行里程長(zhǎng),航段耗油量自然就大些.另外,由于只有盡量提高飛機(jī)的運(yùn)輸能力,才能最大限度地保證航空客貨運(yùn)輸收入的增加,所以,提高飛機(jī)日利用率顯然是關(guān)鍵因素之一.而減少飛機(jī)的地面等待時(shí)間可以為飛機(jī)在空中飛行爭(zhēng)取更多的時(shí)間,為提高飛機(jī)日利用率提供保證.

影響飛機(jī)維修成本的因素主要是飛機(jī)的使用年限及民航總局規(guī)定的定期維護(hù).為了保證飛機(jī)有更長(zhǎng)的服務(wù)時(shí)間,避免飛機(jī)的忙閑不均帶來(lái)高的機(jī)隊(duì)維修成本,模型需要考慮飛機(jī)使用上的均衡,這包括每架飛機(jī)每日飛行時(shí)間上的均衡與航班起降班次的均衡.

占非直接運(yùn)營(yíng)成本中比例最多的是地面運(yùn)營(yíng)成本(59.6%),約占總運(yùn)營(yíng)成本的 28%.在影響地面運(yùn)營(yíng)成本的因素中,可以進(jìn)行優(yōu)化的是與起降相關(guān)的飛機(jī)地面成本.按照規(guī)定,不同最大業(yè)務(wù)載重量和不同座位數(shù)的飛機(jī)在各個(gè)類型的航站需要支付不同的起降費(fèi)和旅客服務(wù)費(fèi).

2.2 飛機(jī)排班問(wèn)題的數(shù)學(xué)模型

航空公司在進(jìn)行飛機(jī)排班時(shí)需要考慮如何合理調(diào)度機(jī)隊(duì)中的每架飛機(jī),完成所有給定航線的不同航班,在降低運(yùn)營(yíng)成本的同時(shí)實(shí)現(xiàn)經(jīng)濟(jì)和社會(huì)效益.模型的建立將以降低航段燃油量與起降費(fèi)、旅客服務(wù)費(fèi)等飛機(jī)運(yùn)營(yíng)成本,實(shí)現(xiàn)飛機(jī)飛行時(shí)間平衡、飛機(jī)起降次數(shù)均衡,以及降低飛機(jī)地面等待時(shí)間為優(yōu)化目標(biāo).

定義決策變量為

式中 可行航班環(huán) j∈ R(可行航班環(huán)集合).可行航班環(huán)集合是為了首先滿足航班銜接的要求,預(yù)先根據(jù)航班計(jì)劃,將當(dāng)天飛行任務(wù)中能滿足航班銜接要求的各航段串行連接起來(lái),組成了可行航班環(huán),多個(gè)可行航班環(huán)組成可行航班環(huán)集合 R.根據(jù)決策變量的定義可知,每一個(gè)可行航班環(huán)對(duì)應(yīng)一架飛機(jī)當(dāng)天的全部飛行任務(wù).

2.2.1 目標(biāo)函數(shù)

由于不同可行航班環(huán)的實(shí)際飛行時(shí)間不同,令航班環(huán) j的飛行時(shí)間為 Tj(小時(shí)),飛機(jī)的單位小時(shí)油耗為 c(噸), 設(shè):飛機(jī)的輪檔時(shí)間=1.2·飛行時(shí)間=1.2· Tj,每噸油料價(jià)格為 b(元),則航班環(huán) j的航油成本為 c·(1.2·Tj)·b.在 1 天中, 所有航班的航油成本 C1為

令:可行航班環(huán) j所停靠航站的使用費(fèi)(包括起降費(fèi)、安檢費(fèi)和旅客服務(wù)費(fèi))為 nj,則飛機(jī)在航班環(huán) j上所?？亢秸镜慕?jīng)停費(fèi) C2為

因此,飛機(jī)排班問(wèn)題的成本目標(biāo) Z1為

令:1 天內(nèi),每架飛機(jī)的平均飛行時(shí)間為 ～Q,其中 , ～Q 為 L-R 型 模糊 數(shù) ,記 為 : ～Q=(Q;).考慮飛機(jī)的飛行時(shí)間均衡,最小化所有飛機(jī)飛行時(shí)間與 ～Q 的總絕對(duì)偏差,目標(biāo) Z2為

令:可行航班環(huán) j上飛機(jī)起降次數(shù)為 Pj,設(shè)航班集合 F 的模為 M,機(jī)隊(duì)規(guī)模為 V,那么,1 天內(nèi),一架飛機(jī)平均起降次數(shù)最小化所有航班班次與平均起降次數(shù) N 的總絕對(duì)偏差,目標(biāo) Z5為

飛機(jī)過(guò)站時(shí)間是指從航空器滑至停機(jī)位開(kāi)啟機(jī)門(mén)至航空器準(zhǔn)備工作就緒關(guān)閉機(jī)門(mén)之間的時(shí)間.按照規(guī)定,飛機(jī)在地面進(jìn)行航班銜接的時(shí)間,不得少于最少過(guò)站時(shí)間.由于只有盡可能地縮短銜接航班間的地面等待時(shí)間,才能為提高飛機(jī)日利用率提供可能.因此,令:可行航班環(huán) j中銜接航班間的等待時(shí)間為 wj,最少過(guò)站時(shí)間為 tj,將最小化可行航班環(huán)中銜接航班間的等待時(shí)間總和作為目標(biāo)Z6

2.2.2 約束條件

令:航班號(hào) i,i∈ F(航班集合);定義參數(shù)ai,j為

飛機(jī)排班問(wèn)題的多目標(biāo) 0-1 整數(shù)規(guī)劃數(shù)學(xué)模型中的三個(gè)約束條件為

式(9)表示航班覆蓋的約束,即每個(gè)航班只能由一架飛機(jī)值飛[13],并且所有飛行任務(wù)只能覆蓋航班當(dāng)且僅當(dāng)一次;式(10)表示機(jī)隊(duì)規(guī)模要求,即所使用的飛機(jī)數(shù)量不能超出公司所擁有的機(jī)隊(duì)總量;式(11)是決策變量的 0-1 整數(shù)性要求.

3 模型求解算法研究

求解目標(biāo)函數(shù)系數(shù)帶有 L-R 型模糊數(shù)的多目 標(biāo) 模 糊 線 性 規(guī) 劃 問(wèn) 題 的 方 法 是: 先 根 據(jù) ～max的近似公式,將帶有 L-R 型模糊系數(shù)的目標(biāo)函數(shù)近似等價(jià)于一個(gè)具有三個(gè)目標(biāo)的線性規(guī)劃問(wèn)題,然后將線性規(guī)劃中的各個(gè)目標(biāo)函數(shù)模糊化,引入隸屬度函數(shù),從而導(dǎo)出一個(gè)新的線性規(guī)劃問(wèn)題,新問(wèn)題的最優(yōu)解成為原問(wèn)題的模糊最優(yōu)解[14].針對(duì)多目標(biāo)飛機(jī)排班問(wèn)題線性規(guī)劃模型,在求解時(shí)除了要考慮目標(biāo)函數(shù)中有帶 L-R 型模糊數(shù)系數(shù)的目標(biāo)如何轉(zhuǎn)化的問(wèn)題,同時(shí)還要采用折中的方法來(lái)處理多個(gè)目標(biāo)函數(shù),以使各目標(biāo)相對(duì)地“極大”,這主要是因?yàn)?要想使多個(gè)目標(biāo)函數(shù)均達(dá)到最優(yōu)解往往是困難的.

3.1 帶 L-R 型模糊系數(shù)的目標(biāo)函數(shù)的近似等價(jià)

首先解決目標(biāo)函數(shù)帶模糊數(shù)系數(shù)的問(wèn)題.在目標(biāo)函數(shù) Z2中包含 L-R 型模糊數(shù) ~Q,按照 L-R 型

至此,由于將帶 L-R 型模糊系數(shù)的目標(biāo)函數(shù)進(jìn)行了近似等價(jià),飛機(jī)排班問(wèn)題數(shù)學(xué)模型中的目標(biāo)函數(shù)由原來(lái)的 Z1,Z2,Z5與 Z6,變成了目前的 6 個(gè)目標(biāo)函數(shù),它們分別是 Z1,Z2,Z3,Z4,Z5,Z6,即式(4),式(12),式(13),式(14),式(6),式(7).

3.2 多目標(biāo)線性規(guī)劃問(wèn)題的模糊求解算法

令:在式(9)、式(10)、式(11)約束下求解各單目標(biāo)函數(shù) Zl(l=1,2,…,6) 的最優(yōu)值為 Z*l.定義 1定義 Zkl(k=1,2,…,6) 為:定義能反映各目標(biāo)重要性程度的伸縮性指標(biāo) dl(dl＞ 0)為其中 dl(l=1,2,…,6) 越小,表示目標(biāo)函數(shù) Zl越重要.

定義2對(duì)每個(gè)最優(yōu)值Z*l,(l=1,2,…,6),

定義 3設(shè):各目標(biāo)函數(shù)下的系數(shù)為 clj,定義多目標(biāo)隸屬度函數(shù) Fl(x),(l=1,2,…,6) 為

根據(jù)定義 3 可知,Fl(x) 越接近于 1,表示 x 屬于 Fl的程度越高;Fl(x) 越接近于 0,表示 x 屬于Fl的程度越低. 因此,隸屬度函數(shù) Fl(x) ∈ [0, 1](i=1,2,...,6) 可以表征 x 屬于 Fl的程度高低.通過(guò)引入隸屬函數(shù) Fl(x),可以將線性規(guī)劃中的多個(gè)目標(biāo)函數(shù)模糊化.

定義4令:則 F 是對(duì)應(yīng)于多目標(biāo)函數(shù) Z=Cx模糊化后的模糊目標(biāo)集,λ是x屬于F的隸屬度.

按照定義4中對(duì) F 和 λ 的定義,目標(biāo)函數(shù)帶L -R型模糊系數(shù)的飛機(jī)排班問(wèn)題的多目標(biāo)模糊線性規(guī)劃模型可以轉(zhuǎn)化成單目標(biāo) 0-1 整數(shù)線性規(guī)劃模型式(19).

綜上所述,求解飛機(jī)排班問(wèn)題的算法步驟如下:

Step1將式(4) 、式(5)、式(6)、式(7) 中求min 的目標(biāo)函數(shù)化成求 max 的目標(biāo).

Step2按照的近似公式,將目標(biāo)函數(shù) Z2近似等價(jià)地化為式(12)、式(13)、式(14)的目標(biāo)函數(shù).飛機(jī)排班問(wèn)題數(shù)學(xué)模型的6個(gè)目標(biāo)函數(shù)分別為式(4)、式(12)、式(13)、式(14)、式(6)、式(7).

Step3在式(9) 、式(10)、式(11) 約束下求解各單目標(biāo)函數(shù) Zl(l=1,2,…,6) ≥ 的最優(yōu)值為Z*.按照式(15) 計(jì)算 Z(k=1,2…,6).

Step4按照式(16) 計(jì)算伸縮性指標(biāo) dl.其中,l=1,2,…,6.

Step5對(duì)式(4) 、式(12) 、式(13) 、式(14)、式(6)、式(7)中每一個(gè)目標(biāo)函數(shù),按照式(17)選取隸屬度函數(shù) Fl(x).

Step6按照公式(18)中的定義,求解數(shù)學(xué)模型式(19),得到 λ 的最大值,記為 λ*.其中,0-1整數(shù)化最優(yōu)解,記為 x*.

Step7將 x*分別代入飛機(jī)排班問(wèn)題的各個(gè)目標(biāo)函數(shù)式(4)、式(5)、式(6)、式(7),即可獲得飛機(jī)排班問(wèn)題的最優(yōu)解.

4 仿真實(shí)驗(yàn)與分析

以中國(guó)東方航空公司飛機(jī)排班問(wèn)題為例,根據(jù)多目標(biāo)優(yōu)化模型及模糊線性規(guī)劃求解算法進(jìn)行優(yōu)化調(diào)度.該公司每日有從無(wú)錫、南京和浦東機(jī)場(chǎng)作為維修基地的 68 個(gè)國(guó)內(nèi)航班,需要由 12 架飛機(jī)進(jìn)行值飛.由于篇幅的關(guān)系,航班集合 F 的一部分在表3中顯示.

表3 部分航班時(shí)刻表Table3 Part of the flight schedule

根據(jù)航班計(jì)劃表,遵照民航總局相關(guān)規(guī)定,搜索到能從維修基地出發(fā),在完成當(dāng)天任務(wù)后返回到維修基地,滿足航班銜接條件的共 233 個(gè)可行航班環(huán),部分可行航班環(huán)見(jiàn)表4.其中,每個(gè)可行航班環(huán)是由航班計(jì)劃中的航班按序連接而成,并且滿足飛機(jī)當(dāng)天總飛行時(shí)間≤14 h;航班間最少過(guò)站時(shí)間≥45 min.

表4 部分航班環(huán)Table4 Part of flight-loop

部分可行航班環(huán)的航班間等待時(shí)間 wj、飛行時(shí)間 Tj、航班環(huán)包含的起降次數(shù) Pj顯示在表5中.

表5 部分航班環(huán)的 wj,Tj,pj值Table5 The values of wj,Tj,pjin the flight-loop

4.1 飛機(jī)排班結(jié)果對(duì)比

一直以來(lái),12架 A320飛機(jī)是按表6 所示的方案進(jìn)行排班的.從表6可以看出,第 5 架飛機(jī)是最繁忙的,因?yàn)樗枰碉w 8 個(gè)航班,根據(jù)航班序號(hào),我們發(fā)現(xiàn)它的飛行路線為:南京-南昌-貴陽(yáng)-南昌-南京-大連-哈爾濱-大連-南京.而第 1、2、3、4 與9、10、11、12 架飛機(jī)需要值飛 6 個(gè)航班,第 6、7、8架飛機(jī)需值飛4個(gè)航班.

按照算法重新優(yōu)化后的排班結(jié)果如表7顯示.對(duì)比表6與表7兩個(gè)方案,很容易發(fā)現(xiàn)第 1、2、3、4、5、8、9 架飛機(jī)的排班方案沒(méi)有發(fā)生變化,而第 6、7、10、11、12 共 5 架飛機(jī)的排班卻有很大的變化.例如:在表6 中,第 6 架飛機(jī)在完成6-19(南京-香港-南京)后銜接 32 號(hào)航班和 49 號(hào)航班(南京-香港-南京),當(dāng)天一共值飛 4 個(gè)航班,也就是說(shuō)該飛機(jī)當(dāng)天的飛行任務(wù)就是完成兩次的南京到香港往返飛行;而表7中新的方案卻要求該飛機(jī)在值飛完一次南京-香港往返之后銜接 31 和 45 號(hào)航班,并且飛行完 45 號(hào)航班后,還要繼續(xù)值飛 56 和 65 號(hào)航班,即接下來(lái)要飛往長(zhǎng)沙、昆明、武漢,最后降落在無(wú)錫機(jī)場(chǎng).這樣,這架飛機(jī)當(dāng)天要比原來(lái)多值飛兩個(gè)航班.同樣的狀況也發(fā)生在第 7 架飛機(jī)上,原來(lái)只需值飛 7-18-36-53(南京-西安-烏魯木齊-西安-南京)4 個(gè)航班,現(xiàn)在卻要增加飛行 63-68 (南京-張家界-南京)2 個(gè)航班.

表6 原有飛機(jī)排班方案Table6 Original fleet assignment scheme

表7 優(yōu)化后的飛機(jī)排班方案Table7 Optimized fleet assignment scheme

從各架飛機(jī)值飛的航班次數(shù)、飛行時(shí)間,以及地面等待時(shí)間方面對(duì)比優(yōu)化前后兩種方案,結(jié)果如表8所示.

表8 優(yōu)化前后飛機(jī)排班方案對(duì)比Table8 Comparison of fleet assignment schemes

4.2 性能對(duì)比

優(yōu)化前后的四個(gè)性能指標(biāo)值分別如表9所示.

表9 優(yōu)化前后性能指標(biāo)對(duì)比Table9 Comparison of performance index

和優(yōu)化前相比較,我們發(fā)現(xiàn)優(yōu)化后只有飛機(jī)飛行時(shí)間的總絕對(duì)偏差略高于原方案,其他指標(biāo)均有明顯改善,例如:飛行成本下降了 4.85%;飛機(jī)當(dāng)日平均飛行小時(shí)為 9.99 h,比統(tǒng)計(jì)數(shù)據(jù)平均日飛行小時(shí) 9.79[11]提高 2%;地面等待時(shí)間總和為 810 min,與原方案的 945 min 相比,下降了 14. 3%;起降次數(shù)的總絕對(duì)偏差仍舊為 10,與原方案一致,說(shuō)明新方法仍舊能保證飛機(jī)起降次數(shù)均衡.對(duì)比結(jié)果表明,該飛機(jī)排班數(shù)學(xué)模型可行,算法有效.

5 研究結(jié)論

本文通過(guò)分析航空公司運(yùn)營(yíng)規(guī)劃與管理中收入與成本構(gòu)成,提煉出影響航空公司收益的四大關(guān)鍵因素,將地面等待時(shí)間最少、飛機(jī)使用均衡和航班起降次數(shù)均衡因素納入調(diào)度問(wèn)題,以降低飛行成本、提高飛機(jī)日利用率為優(yōu)化目標(biāo),提出了飛機(jī)排班問(wèn)題的多目標(biāo)0-1 整數(shù)規(guī)劃數(shù)學(xué)模型.

在解決飛機(jī)排班問(wèn)題時(shí),為了同時(shí)滿足航班覆蓋與航班銜接兩個(gè)約束條件,本文采用的手段是:預(yù)先按照?qǐng)D的深度優(yōu)先搜索算法將那些能同時(shí)滿足最小過(guò)站時(shí)間和航班銜接要求的航班依次連接起來(lái),生成可行航班環(huán),組成可行航班環(huán)集合,并在可行航班環(huán)集合上定義決策變量.

本文將模糊數(shù)學(xué)與運(yùn)籌學(xué)理論應(yīng)用到求解該飛機(jī)排班問(wèn)題上,給出了目標(biāo)函數(shù)帶模糊系數(shù)的多目標(biāo)模糊線性規(guī)劃數(shù)學(xué)模型的求解算法.最后通過(guò)一個(gè)飛機(jī)排班問(wèn)題實(shí)例.優(yōu)化前后結(jié)果對(duì)比表明,該數(shù)學(xué)模型可行,算法有效.如何進(jìn)一步優(yōu)化飛機(jī)排班問(wèn)題,提高飛機(jī)的日利用率將是進(jìn)一步努力的方向.

[1] 孫宏.航空公司飛機(jī)排班問(wèn)題:模型及算法研究[D]. 西 南 交 通 大 學(xué),2003.[SUN H.Airline tail number assignment problem:model and algorithm [D].Southwest Jiaotong University,2003.]

[2] 王偉,王錦彪.中國(guó)民航飛機(jī)排班問(wèn)題的多部圖模型[J].交通與計(jì)算機(jī),2008(04):35-41.[WANG W,WANG J B.A multipartite graph model for aircraft arrangement of CAAC[J].Transport and Computer, 2008(04):35-41.]

[3] 高強(qiáng), 朱星輝,李云,等.飛機(jī)排班一體化模型與算法研究[J].武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版),2012(02):153-157.[GAO Q,ZHU X H,LI Y,et al.Research on integration model and algorithm of airline schedule[J].Journal of Wuhan University of Technology(Transportation Science&Engineering), 2012(02):153-157.]

[4] 魏星,朱金福.航空公司一體化飛機(jī)排班研究 [J].武漢理工大學(xué)學(xué)報(bào)(信息與管理工程版),2013 (02):86-90.[WEI X,ZHU J F.Integrated research of airlines aircraft scheduling[J].Journal of Wuhan University of Technology(Information&management Engineering),2013(02):86-90.]

[5] 朱星輝,朱金福,高強(qiáng).基于約束編程的飛機(jī)排班問(wèn)題研究[J].交通運(yùn)輸系統(tǒng)工程與信息,2011,(6): 151-156.[ZHU X H,ZHU J F,GAO Q.Aircraft scheduling based on constraint programming[J]. Journal of Transportation Systems Engineering and Information Technology,2011,11(6):151-156.][6] 廖峰,劉紅,文軍. 基于圖著色模型飛機(jī)智能化排班算法的研究[J].中國(guó)民航飛行學(xué)院學(xué)報(bào),2012(3): 20-23.[LIAO F,LIU H,WEN J.Study on aircraft intelligent assignmentofairlinersbased on graph coloring model[J].Journal of Civil Aviation Flight University of China,2012(3):20-23.]

[7] L W Clarke,E L Johnson,G L Nemhauser,et al.The aircraft rotation problem[J].Annals of Operations Research,1997,69(1):33-46.

[8] N Papadakos.Integrated airline scheduling[J].Computers &Operations Research.2009,36(1):176-195.

[9] G Mattias.The tail assignment problem[D].Goteborg: Department of Computer Science and Engineering, Chalmers University ofTechnology and Goteborg University,2005.

[10] G Mattias.Accelerating column generation for aircraft scheduling using constraint propagation[J].Computers

[8] 劉明俊,艾萬(wàn)政,程志友. 蘇通大橋橋區(qū)水域船舶通航能力研究[J]. 船海工程,2006(4):80-85.[LIU M J,AI W Z,CHENG Z Y.Research of navigating capacity in the area nearby Sutong bridge[J].Journal of Ship&Ocean Engineering,2006(4):80-85.]

[9] Olsen N R B,Melaaen M C.Three-dimensional calculation of scour around cylinders[J].Journal of Hydraulic Engineering,1993,119(9):1048-1054.

[10] Raudkivi A J.Functional trends of scour at bridge piers[J].Journal of Hydraulic Engineering,ASCE, 1986,112(1):l-12.

[11] YANG Yong-quan,ZHAO Hai-heng.Numerical simulation of turbulent flows passed through an orifice energy dissipator within a flood discharge tunnel[J].Journal of Hydrodynamics,Ser.B,1992,4(3):27-33.

[12] Liu Xiao-bing,Zeng Yong-zhong.Numerical prediction of vortex flow in hydraulic turbine draft tube for LES [J].Journal of Hydrodynamics,Ser.B,2005,17 (4):448-454. &Operations Research.2006,33(1):2918-2934.

[11] 中國(guó)民用航空總局規(guī)劃發(fā)展司.從統(tǒng)計(jì)看民航[M].北京:中國(guó) 民 航 出 版 社,2009:187.[Statistical Data on Civil Aviation of China[M].Beijing:China Civil aviation Press,2009:187.]

[12] 耿淑香.航空公司運(yùn)營(yíng)管理方略[M].北京:中國(guó)民航出 版 社,2000:34.[GENG S X.Airline operation strategy[M].Beijing:China Civil Aviation Press, 2000:34.]

[13] MASSOUDB.Airline operations and scheduling[M]. BurLin-gton: Ashgate Publishing Limited,2010: 71-122.]

[14] 張振良.模糊集理論與方法[M]. 武漢:武漢大學(xué)出版社,2010:227-235.[ZHANG Z L.Fuzzy set theory and its method[M].Wuhan:Wuhan University Press, 2010:227-235.]

Model and Algorithm for Fleet Assignment Problem Based on Airlines Cost Minimization

WU Dong-huaa,b,XIA Hong-shanb
(a.College of Continuing and Education;b.College of Civil Aviation, Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China)

Aiming at fleet assignment problem,on the basis of flight connecting,flight covering and fleet scale.The objective functions are taken with the minimum variable cost on fleet,the minimum time on ground-holding,the absolute minimum deviation of total flight time and the minimum frequency of taking off and landing.And a 0-1 integer programming mathematical model is established.The historical data of Chinese Orient Airlines Company are analyzed;fuzzy theory are used to demonstrate the model.The result shows that the proposed model is feasible and effective.

air transportation;fleet assignment problem;multi-objective optimization;computer simulation;China Eastern

1009-6744(2014)01-0109-08

TP391.41

A

2013-07-16

2013-10-08錄用日期:2013-10-28

國(guó)家自然科學(xué)基金項(xiàng)目(60672167);國(guó)家軟科學(xué)研究計(jì)劃項(xiàng)目(2008GXQ6B141).

吳東華(1973-),女,黑龍江佳木斯人, 講師, 工學(xué)博士生.*通訊作者:xhsca@nuaa.edu.cn