周 敬

(同濟(jì)大學(xué)經(jīng)濟(jì)與管理學(xué)院,上海 200092)

商業(yè)航空公司的服務(wù)運(yùn)營(yíng)成本高昂,其中航班的日常運(yùn)行成本占比較大。以中國(guó)東方航空公司為例,2021 年財(cái)務(wù)報(bào)告顯示,全年運(yùn)營(yíng)成本達(dá)到800.41億元,其中直接與航班運(yùn)行綁定的成本占到50%,包括航空油料消耗、機(jī)場(chǎng)起降費(fèi)、餐食費(fèi)等[1]。但航空公司的利潤(rùn)率較低,CSI Market的數(shù)據(jù)顯示,2022年第二季度全球航空公司的總利潤(rùn)率只有1.07%[2]。因此,航空公司在航班運(yùn)行的日常規(guī)劃過(guò)程(航班時(shí)刻表安排、機(jī)型分配)需要作出最佳決策,適應(yīng)快速變化的市場(chǎng),才能有效降低成本,提高盈利水平。Sabre[3]的數(shù)據(jù)顯示,越南航空公司通過(guò)與該司合作,協(xié)調(diào)日常規(guī)劃,將節(jié)省高達(dá)10%的運(yùn)營(yíng)預(yù)算成本,并帶來(lái)可觀的盈利。

航空公司的運(yùn)營(yíng)規(guī)劃過(guò)程中有兩個(gè)重要決策:航班時(shí)刻表安排和機(jī)型分配。兩者對(duì)航空公司盈利能力影響重大,決策順序是航班時(shí)刻表安排在前,機(jī)型分配在后[4]。第一步時(shí)刻表安排細(xì)分為兩個(gè)步驟,包括頻率規(guī)劃和時(shí)間表制定。該過(guò)程為航班的起飛和抵達(dá)提供了明確的預(yù)計(jì)時(shí)間表。機(jī)型分配是為每個(gè)航班分配適當(dāng)?shù)娘w機(jī)類(lèi)型,使得每個(gè)航班的座位容量與預(yù)期需求緊密匹配。兩項(xiàng)決策與市場(chǎng)需求波動(dòng)相關(guān)。旅客對(duì)于不同的航空時(shí)刻有不同的偏好,同樣的航班在不同時(shí)間起飛所吸引到的旅客數(shù)量不同,之后的機(jī)型分配也應(yīng)該按照旅客數(shù)量匹配相應(yīng)容量的機(jī)型。因此,研究如何在需求波動(dòng)的情況下優(yōu)化航班時(shí)刻表和機(jī)隊(duì)分配計(jì)劃對(duì)提高航空公司盈利能力具有重要的價(jià)值。

機(jī)型分配問(wèn)題首先由Abara[5]提出,通過(guò)連接網(wǎng)絡(luò)進(jìn)行數(shù)學(xué)建模,該網(wǎng)絡(luò)將所有可能相鄰航段之間的連接設(shè)置為決策變量。Hane等[6]引入了時(shí)空網(wǎng)絡(luò)建模這個(gè)問(wèn)題,該網(wǎng)絡(luò)直接將航段作為決策變量進(jìn)行建模。對(duì)比這兩種網(wǎng)絡(luò),前者在求解模型后可以清楚地描述飛機(jī)的航線,而后者則不能,但后者的計(jì)算復(fù)雜度較低。因此,后者即時(shí)空網(wǎng)絡(luò)將被應(yīng)用于后續(xù)的數(shù)學(xué)建模中。汪瑜等[7]也將航班機(jī)型分配描述為時(shí)序網(wǎng)絡(luò)圖中的網(wǎng)絡(luò)流問(wèn)題,設(shè)計(jì)模擬退火算法。類(lèi)似地,張恩翼[8]基于遺傳算法對(duì)飛機(jī)機(jī)型指派優(yōu)化模型進(jìn)行了求解。張開(kāi)華[9]根據(jù)開(kāi)始訂座至離港前3天同一時(shí)間節(jié)點(diǎn)已銷(xiāo)售的座位數(shù),建立基于BP 神經(jīng)網(wǎng)絡(luò)的離港人數(shù)預(yù)測(cè)模型,然后由需求預(yù)測(cè)和機(jī)型預(yù)分配結(jié)果為航班重新分配機(jī)型。

在機(jī)型分配的基礎(chǔ)上允許航班時(shí)間表的變化更加符合實(shí)際情況。Levin[10]使用無(wú)環(huán)有向圖來(lái)描述空中交通流,根據(jù)固定時(shí)刻表和可變時(shí)刻表構(gòu)建了兩個(gè)機(jī)型分配模型。Rexing等[11]全面地建立了航班時(shí)刻表和機(jī)型分配的集成模型,通過(guò)在基本機(jī)型分配模型中復(fù)制不同起飛時(shí)間的航班來(lái)創(chuàng)建時(shí)間窗口,并使用刪除冗余弧和節(jié)點(diǎn)合并的方式來(lái)加快求解速度。Sherali 等[12]使用了有效的不等式和Benders分解,從而加速解決混合整數(shù)規(guī)劃問(wèn)題。Sherali等[13]擴(kuò)展了他們之前的研究,考慮了靈活的出發(fā)時(shí)間和乘客溢出后的重新捕獲。Pita等[14]在模型中考慮了機(jī)場(chǎng)擁堵和乘客延誤成本。Pita等[15]將決策者從航空公司擴(kuò)展到航空運(yùn)輸系統(tǒng)。上述研究在航班時(shí)刻表和機(jī)型分配的集成建模上有一定的突破,但求解時(shí)嚴(yán)格限制了航司可選的出發(fā)時(shí)間和航線,并且沒(méi)有考慮到旅客市場(chǎng)的因素。

針對(duì)航空旅客市場(chǎng)情況,熊紅林等[16]運(yùn)用機(jī)器學(xué)習(xí)方法進(jìn)行了預(yù)測(cè),將長(zhǎng)短期記憶網(wǎng)絡(luò)(LSTM)與支持向量回歸(SVR)相結(jié)合,相比于單一模型預(yù)測(cè),提高了預(yù)測(cè)的準(zhǔn)確度,為航空運(yùn)營(yíng)管理提供一定的決策支持。為了將市場(chǎng)因素融入優(yōu)化模型,Kniker[17]提出了溢出和再捕獲過(guò)程模型,即乘客混合模型(PMM),它以一個(gè)確定的時(shí)刻表、機(jī)型分配結(jié)果和無(wú)限制的行程需求作為輸入,然后將這種情況下溢出客流重新安排,從而最大化利潤(rùn)或最小化成本。隨后,Barnhart等[18]利用PMM,通過(guò)考慮基于行程的利潤(rùn),在機(jī)型分配方面取得進(jìn)展。Lohatepannt等[19]將時(shí)刻表安排和機(jī)型分配的綜合問(wèn)題與PMM 相結(jié)合。Sherali等[20]針對(duì)特定機(jī)型設(shè)計(jì)了一個(gè)類(lèi)似的乘客需求驅(qū)動(dòng)的調(diào)度模型。Barnhart等[21]收集了更多實(shí)際數(shù)據(jù),更加合理地估測(cè)了目標(biāo)函數(shù)中的各項(xiàng)參數(shù)。上述研究面臨的問(wèn)題規(guī)模大,實(shí)際求解時(shí)都進(jìn)行了簡(jiǎn)化,往往與實(shí)際的時(shí)刻和機(jī)型安排有所偏離,并且只是假設(shè)所有座位都要盡量坐滿,沒(méi)有考慮影響乘客做選擇的因素。

將離散選擇模型融入優(yōu)化建模,提高模型對(duì)乘客選擇行為的適應(yīng)性,能夠模擬真實(shí)的市場(chǎng)情況。離散選擇模型假設(shè)乘客根據(jù)特定產(chǎn)品的效用進(jìn)行選擇[22]。在航空運(yùn)輸研究中,產(chǎn)品指的是一個(gè)旅客的行程。行程的效用受到各種因素的影響,通過(guò)離散選擇模型中的多項(xiàng)式logit(MNL)方法,可以發(fā)現(xiàn),這些因素主要包括中間停靠次數(shù)、出發(fā)時(shí)間、航程時(shí)間和票價(jià)[23-25]。例如,由于轉(zhuǎn)機(jī)服務(wù)耗時(shí)耗力,乘客傾向于選擇直飛航班,而非中間?？看螖?shù)多的航班。Atasoy等[26]首次將離散選擇模型應(yīng)用于航班時(shí)刻表安排與機(jī)型分配的整合,并集成了機(jī)票定價(jià)。該研究的不足在于設(shè)計(jì)的啟發(fā)式算法不能很好地處理大規(guī)模的混合整數(shù)非線性模型,結(jié)果僅能分析兩對(duì)航班的情況,也沒(méi)有考慮市場(chǎng)波動(dòng)的因素,很難應(yīng)用于實(shí)際。Dong等[27]為每個(gè)行程設(shè)定了有限的出發(fā)時(shí)間選項(xiàng),并幫助航空公司根據(jù)乘客需求變化在這些選項(xiàng)中決定價(jià)格。Wei等[28]也應(yīng)用了乘客選擇函數(shù)來(lái)評(píng)估基于行程的利潤(rùn)。Birolini等[29]通過(guò)嵌套Logit公式在改善供需互動(dòng)方面取得了進(jìn)展。上述研究應(yīng)用啟發(fā)式算法處理了較大規(guī)模的混合整數(shù)模型,但都對(duì)出發(fā)時(shí)間和航線做了簡(jiǎn)化,也沒(méi)有考慮市場(chǎng)波動(dòng)的因素。

以往研究為航班時(shí)刻表安排和機(jī)型分配這兩個(gè)決策的集成提供了數(shù)學(xué)模型,并將消費(fèi)者選擇模型融入航空運(yùn)營(yíng)規(guī)劃中。但這些研究設(shè)計(jì)的算法難以有效解決大規(guī)?；旌险麛?shù)規(guī)劃問(wèn)題,且鮮有研究致力于應(yīng)對(duì)波動(dòng)的需求。因此,本文研究的問(wèn)題是航空公司如何在考慮多航段服務(wù)市場(chǎng)需求存在波動(dòng)的情況下,及時(shí)有效地進(jìn)行航空運(yùn)營(yíng)規(guī)劃的兩個(gè)步驟,即航班時(shí)刻表安排和機(jī)型分配。采用時(shí)空網(wǎng)絡(luò)建模,結(jié)合消費(fèi)者離散選擇模型,研究波動(dòng)服務(wù)需求下時(shí)間表與機(jī)型分配的集成模型,并設(shè)計(jì)相應(yīng)算法解決大規(guī)?；旌险麛?shù)規(guī)劃問(wèn)題。

1 問(wèn)題描述與模型建立

1.1 問(wèn)題描述

建模過(guò)程中出現(xiàn)的術(shù)語(yǔ)進(jìn)行如下定義:飛行航班/航段為飛機(jī)從出發(fā)機(jī)場(chǎng)到目的機(jī)場(chǎng)的不間斷旅行,即一次起飛和一次著陸;市場(chǎng)為一個(gè)有序的出發(fā)地-目的地的機(jī)場(chǎng)對(duì)。特定市場(chǎng)中的行程由特定的預(yù)定航班段序列組成,其中第一段在特定時(shí)間從始發(fā)機(jī)場(chǎng)出發(fā),最后一段在稍后時(shí)間終止于最終目的地機(jī)場(chǎng)。航班、市場(chǎng)和行程之間的關(guān)系為:一個(gè)市場(chǎng)包含多個(gè)可選擇的行程,一個(gè)行程包含一個(gè)或多個(gè)航班。

本文需要建模解決的問(wèn)題是,考慮多航段服務(wù)市場(chǎng)需求存在波動(dòng)的情況下,航空公司如何完成運(yùn)營(yíng)規(guī)劃中具體航班的時(shí)刻表安排和機(jī)型分配,吸引旅客體驗(yàn)相關(guān)行程的服務(wù),從而獲得最大的收益?？傮w建模架構(gòu)如圖1所示。建模求解可得到航空公司在波動(dòng)的服務(wù)市場(chǎng)需求情形下,每個(gè)行程所占的市場(chǎng)份額,每個(gè)航班的計(jì)劃起降時(shí)間以及執(zhí)行該航班的具體機(jī)型。

圖1 考慮多航段服務(wù)需求響應(yīng)的航班時(shí)刻表安排與機(jī)型分配集成問(wèn)題Fig.1 Framework of integrated flight timetabling and fleet assignment problem

航空公司通過(guò)售賣(mài)以行程為單位的機(jī)票,為旅客提供旅行服務(wù)并獲得收益。服務(wù)市場(chǎng)行情發(fā)生波動(dòng)時(shí),該市場(chǎng)的總需求也會(huì)發(fā)生波動(dòng),當(dāng)市場(chǎng)行情變好時(shí),總需求上升;當(dāng)市場(chǎng)行情變差時(shí),總需求下降。

市場(chǎng)上的所有旅客根據(jù)吸引力大小選擇相應(yīng)市場(chǎng)中的行程,不同的行程對(duì)于旅客有不同的吸引力,吸引力更高的行程獲得更多的市場(chǎng)份額;相反,吸引力更低的行程獲得較少的市場(chǎng)份額,相應(yīng)行程的市場(chǎng)份額需要在建模中確定。行程的吸引力與運(yùn)營(yíng)規(guī)劃中的航班時(shí)刻表有關(guān),即不同的起降時(shí)間會(huì)影響飛行服務(wù)的吸引力,進(jìn)而影響旅客需求。例如,旅客通常不會(huì)選擇凌晨和午夜的航班,在航班頻次有限的情況下,這些時(shí)刻出發(fā)的旅客需求較低,可售出的機(jī)票較少,航空公司獲得的收益較少,一般不會(huì)被選擇。

確定航班時(shí)刻表后進(jìn)行機(jī)型分配,即確定某一時(shí)刻起飛的某一航班需要由哪一種機(jī)型來(lái)執(zhí)行飛行任務(wù)。該步驟也與旅客需求相關(guān),當(dāng)旅客對(duì)某一個(gè)航班的需求較大時(shí),航空公司應(yīng)當(dāng)分配較大容量的機(jī)型,盡可能滿足旅客需求,雖然大機(jī)型成本高于小機(jī)型,但多售賣(mài)出的機(jī)票收益可以覆蓋這部分成本,保證航班獲得盡可能多的收益;相反,需求較小時(shí)應(yīng)當(dāng)分配容量較小的機(jī)型,因?yàn)榇髾C(jī)型的運(yùn)營(yíng)成本高于小機(jī)型,分配小機(jī)型可以節(jié)省成本。

1.2 模型構(gòu)建

模型在考慮了多航段服務(wù)需求波動(dòng)的情況下整合了時(shí)刻表安排和機(jī)型分配。機(jī)型分配建模使用時(shí)空網(wǎng)絡(luò)模型,為每一個(gè)機(jī)場(chǎng)創(chuàng)建一天的時(shí)間線,在時(shí)間線上創(chuàng)立事件發(fā)生的節(jié)點(diǎn)。其中,事件是指航班的起飛和降落。不同機(jī)場(chǎng)的時(shí)間線通過(guò)添加對(duì)應(yīng)的航班弧連接,這條弧是該航班的起降機(jī)場(chǎng)在各自時(shí)間線上按照對(duì)應(yīng)的起飛和降落時(shí)間連接線。然后通過(guò)復(fù)制不同出發(fā)時(shí)間的航班弧,把時(shí)刻表安排考慮進(jìn)機(jī)型分配模型,做到時(shí)刻表安排和機(jī)型分配集成考慮。為簡(jiǎn)化模型,假設(shè)時(shí)間表每天都重復(fù)安排。

由圖2可見(jiàn),例子中共有3個(gè)機(jī)場(chǎng)A、B 和C,創(chuàng)建3 條對(duì)應(yīng)的時(shí)間線,時(shí)間線上從左至右為0:00 a.m.～12:00 p.m.,按照時(shí)間先后順序創(chuàng)建航班的起點(diǎn)和終點(diǎn)(1～12),并將這些點(diǎn)連接形成航班弧。航班A～B有3個(gè)可選的出發(fā)時(shí)間1、2和3,航班B～C有3個(gè)可選的出發(fā)時(shí)間7、8和9。

圖2 時(shí)空網(wǎng)絡(luò)模型構(gòu)建示意圖Fig.2 Time-space network

在此基礎(chǔ)上,考慮多航段服務(wù)需求響應(yīng)的航班時(shí)刻表安排和機(jī)型分配的集成模型,可表述如下:

集合

AP——航空公司提供服務(wù)涉及的機(jī)場(chǎng)集合,索引為ap

M——航空公司提供服務(wù)的市場(chǎng)集合,索引為m

S——航空公司提供服務(wù)的航段集合,索引為s

So(ap)?S——以機(jī)場(chǎng)ap為起點(diǎn)的一組航段,索引為s

Sd(ap)?S——以機(jī)場(chǎng)ap為終點(diǎn)的一組航段,索引為s

T——時(shí)間段的集合,每段為60 min,索引為t

F——航空公司所有可用機(jī)型的集合,索引為f

FL——紅眼航段,即相應(yīng)的航段在一天開(kāi)始時(shí)(如0:00～4:00 a.m.)起飛

Im——市場(chǎng)m上所有行程的集合,索引為i

N——時(shí)空網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合,索引為(f,ap,t),用于機(jī)型f、機(jī)場(chǎng)ap和時(shí)間段t

K——具有不同市場(chǎng)需求的場(chǎng)景集,索引為k

參數(shù)

Demm,k——情景k下的市場(chǎng)m總需求

Ai——行程i的吸引力

Ticketi——行程i的票價(jià)

Opes,f——使用機(jī)型f運(yùn)營(yíng)航班s的運(yùn)營(yíng)成本

Capf——機(jī)型f的座位容量

Freqs——每天飛航段s的頻數(shù)

Availf——機(jī)型f的可用飛機(jī)數(shù)量

CountT——飛機(jī)計(jì)數(shù)時(shí)間

D(s,t)——航班s的計(jì)劃起飛時(shí)間(該航班經(jīng)過(guò)的時(shí)間加上最小飛機(jī)周轉(zhuǎn)時(shí)間后落在時(shí)間段t之內(nèi))

Pk——場(chǎng)景k發(fā)生的概率k

其中,有兩個(gè)參數(shù)需要更詳細(xì)地估計(jì),分別為目標(biāo)函數(shù)中的航段運(yùn)營(yíng)成本(Opes,f)和行程的吸引力。

首先,在計(jì)算航段營(yíng)運(yùn)成本(Opes,f)時(shí),使用Swan等[24]的模型。有兩種公式分別用于計(jì)算短途和長(zhǎng)途航段的飛機(jī)運(yùn)營(yíng)成本。短途航段為1 000～5 000 km 之間的國(guó)內(nèi)行程,長(zhǎng)途航段為5 000 km以上的國(guó)際行程。本文模型只考慮短途,不涉及復(fù)雜的國(guó)際行程,因此應(yīng)用短途公式。短途飛機(jī)出行成本可根據(jù)設(shè)計(jì)座位數(shù)S和出行距離D計(jì)算,如下式所示:

其次,Lurkin等[19]提供了估算行程吸引力的方法。他們構(gòu)建了一個(gè)回歸模型,以行程的吸引力Ai作為因變量,以行程的屬性(出發(fā)時(shí)間x1、票價(jià)x2和旅程時(shí)間x3)作為自變量。該研究的系數(shù)估計(jì)結(jié)果可用于計(jì)算中,得到吸引力的數(shù)值直接代入模型作為已知參數(shù)。其他航空公司的總吸引力使用相關(guān)航線的平均吸引力來(lái)估計(jì),即

決策變量

xs,f,t,k——二進(jìn)制變量,在情景k下,如果機(jī)型f分配給起飛時(shí)間段為t的航班s,則該變量等于1,否則等于0

σi,k——場(chǎng)景k下航空公司(決策主體)提供的可選行程i對(duì)應(yīng)的市場(chǎng)份額

數(shù)學(xué)模型

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

機(jī)型分配約束(與航班時(shí)刻表安排集成)

消費(fèi)者選擇模型約束

該模型的目標(biāo)是最大化航空公司的運(yùn)營(yíng)總利潤(rùn),如式(3)所示,在不同市場(chǎng)需求場(chǎng)景下,運(yùn)營(yíng)總利潤(rùn)由總票價(jià)收入(包含航空公司提供的所有市場(chǎng)的所有航線)減去所有運(yùn)營(yíng)航班(包含所有飛機(jī)類(lèi)型和所有起飛時(shí)間段)的總成本得出。

約束條件共有兩個(gè)大類(lèi)。約束條件式(4)～(7)是機(jī)型分配約束,將決策變量按照可行的起飛時(shí)間進(jìn)行了復(fù)制,與航班時(shí)刻表集成,保持滿足機(jī)型覆蓋相應(yīng)的航段、飛機(jī)流量平衡、飛行頻率和飛機(jī)數(shù)量上限。式(4)限制在每種市場(chǎng)情況下,一個(gè)航班的一個(gè)起飛時(shí)段最多可以選擇一個(gè)機(jī)型執(zhí)行一次飛行任務(wù)。式(5)確保每個(gè)機(jī)場(chǎng)的時(shí)間線上,每個(gè)節(jié)點(diǎn)都能保證飛機(jī)數(shù)量的進(jìn)出平衡,即時(shí)間節(jié)點(diǎn)t之前停在地面上的飛機(jī)加上到達(dá)的飛機(jī),等于時(shí)間節(jié)點(diǎn)t之后仍然停在地面上的飛機(jī)加上起飛的飛機(jī)。式(6)確保決策主體航空公司之前計(jì)劃好的航班頻次可以被滿足。式(7)保證了每種機(jī)型在同一時(shí)間使用時(shí)不會(huì)超過(guò)該機(jī)型數(shù)量的上限。

約束條件式(8)～(11)是基于消費(fèi)者選擇模型約束。式(8)限制乘客需求小于等于飛機(jī)容量。式(9)確保乘客只能選擇分配了機(jī)型進(jìn)行運(yùn)營(yíng)的航班。左側(cè)xs,f,t,k為0-1變量,將該變量在集合F中相加的取值仍為0或1(F中最多只有一個(gè)f被分配),右側(cè)取值為0≤σi,k≤1。如果左側(cè)取值為0,說(shuō)明該任務(wù)不執(zhí)行。右側(cè)取值也必須為0,因?yàn)橄M(fèi)者不會(huì)選擇對(duì)應(yīng)的行程。式(10)確保決策主體航空公司和所有其他航空公司的市場(chǎng)份額之和等于1。式(11)保證了每個(gè)行程的市場(chǎng)份額與其吸引力成比例。使用“≤”而不是“=”的原因是:如果強(qiáng)制要求“=”,偶爾會(huì)出現(xiàn)左側(cè)σi,k取值過(guò)大導(dǎo)致式(8)不滿足?，F(xiàn)實(shí)意義是,即使一個(gè)行程吸引力大,但飛機(jī)的容量是有限的,不能保證所有旅客的訂單都得到滿足。

2 算法設(shè)計(jì)

該研究是一個(gè)大規(guī)?；旌险麛?shù)線性規(guī)劃問(wèn)題,可以通過(guò)編寫(xiě)程序,代入優(yōu)化求解器進(jìn)行求解,但由于規(guī)模較大,直接使用求解器難以找到滿意結(jié)果。在航空業(yè)的實(shí)踐中,市場(chǎng)情況瞬息萬(wàn)變,如果航空公司決策滯后會(huì)錯(cuò)失市場(chǎng)先機(jī),造成利潤(rùn)損失。因此,該問(wèn)題還需要設(shè)計(jì)相應(yīng)的算法,從而在更快時(shí)間內(nèi)獲得更高質(zhì)量的結(jié)果。

2.1 基于模型的算法設(shè)計(jì)分析

算法設(shè)計(jì)分析基于1.2節(jié)數(shù)學(xué)模型中的變量和約束,從變量的松弛和約束的分解兩個(gè)方面尋找突破口。

(1)變量的松弛。模型中共有3個(gè)變量,包括0-1變量(xs,f,t,k)、整數(shù)變量和連續(xù)變量。通過(guò)觀察約束式(5)發(fā)現(xiàn),該約束含有0-1變量和整數(shù)變量,其中整數(shù)變量?jī)H在該約束中用到,對(duì)整數(shù)變量進(jìn)行轉(zhuǎn)化會(huì)使模型難度大幅降低。

(2)約束的分解。模型兩個(gè)部分通過(guò)約束式(8)和(9)進(jìn)行銜接,式(8)是指航班實(shí)際乘坐人數(shù)不能超過(guò)該機(jī)型的上限,式(9)是指只有旅程中的所有航班被分配了機(jī)型,乘客才能選擇對(duì)應(yīng)的每個(gè)旅程。由于式(8)和式(9)分別按照航班和旅程分類(lèi),兩者不是一一對(duì)應(yīng)的關(guān)系,無(wú)法高效地使用分解的方式進(jìn)行精確求解。

經(jīng)過(guò)上述分析將問(wèn)題中的整數(shù)變量線性化,現(xiàn)在問(wèn)題中較難處理的只有0-1變量,由于模型結(jié)構(gòu)難以分解,故采用啟發(fā)式算法求解。通過(guò)對(duì)小規(guī)模算例進(jìn)行線性松弛,用CPLEX 求解結(jié)果,發(fā)現(xiàn)原本為0-1變量的結(jié)果中,取值在0-1之間,較為接近1的變量往往就是未進(jìn)行線性松弛的最優(yōu)解中取1的變量。因此,采用先線性松弛,再將接近1的值直接固定為1,循環(huán)往復(fù)的算法(又稱(chēng)潛水啟發(fā)式算法)。Sadykov等[31]使用了該算法思想,與其他啟發(fā)式方法相比,該算法處理含0-1變量相對(duì)高效。

2.2 潛水啟發(fā)式算法

潛水啟發(fā)式算法應(yīng)用深度優(yōu)先搜索,無(wú)須回溯,將混合整數(shù)問(wèn)題簡(jiǎn)化為線性松弛(LP)問(wèn)題,將得到的一個(gè)或多個(gè)分?jǐn)?shù)值固定為正整數(shù)值,循環(huán)往復(fù)直到不存在分?jǐn)?shù)解。這種思想對(duì)求解混合整數(shù)規(guī)劃問(wèn)題的速度和效果進(jìn)行了重新優(yōu)化。根據(jù)當(dāng)前問(wèn)題,制定了潛水啟發(fā)式算法的幾個(gè)關(guān)鍵策略:

(1)高分?jǐn)?shù)固定。此策略?xún)H固定數(shù)值接近1的機(jī)型分配0-1變量x。針對(duì)本文的模型,將分?jǐn)?shù)值和目標(biāo)值1之間的差距設(shè)置為0.01,在求解LP 解的下一次迭代中將等于或大于0.99的變量固定為1。如果沒(méi)有這種變量,則選擇剩下未固定的x中數(shù)值最大的固定為1。

(2)低分?jǐn)?shù)固定。在(1)的基礎(chǔ)上,一旦部分變量x固定為1,根據(jù)約束條件式(4),具有相同航段和出發(fā)時(shí)間但不同機(jī)型的其余變量x應(yīng)固定為0。該策略有助于根據(jù)數(shù)學(xué)模型加速尋找結(jié)果的過(guò)程,并且不會(huì)對(duì)最終解決方案的質(zhì)量產(chǎn)生負(fù)面影響。

(3)迭代輪次。對(duì)于LP問(wèn)題,一旦得到LP的解,就使用上述兩種策略來(lái)固定幾個(gè)變量,然后將這些固定的數(shù)字代回模型中,并更新LP問(wèn)題,進(jìn)行新一輪的求解。最后,當(dāng)沒(méi)有要固定的變量時(shí),可以停止?jié)撍^(guò)程。

2.3 算法步驟

上述關(guān)鍵策略被整合到模型求解過(guò)程可以分為如下步驟:

(1)生成初始解。

步驟1輸入機(jī)場(chǎng)信息,包含機(jī)場(chǎng)的名稱(chēng);

步驟2根據(jù)機(jī)場(chǎng)個(gè)數(shù)預(yù)估需要使用飛機(jī)的種類(lèi)和數(shù)目,輸入相應(yīng)規(guī)模的機(jī)型信息,包含機(jī)型名稱(chēng)、座位數(shù)和每種機(jī)型的數(shù)量上限;

步驟3輸入對(duì)應(yīng)機(jī)場(chǎng)的航班信息,包含航班的起點(diǎn)、終點(diǎn)、頻次、飛行距離和飛行時(shí)間,并將這些基礎(chǔ)信息按照可選的多個(gè)起飛時(shí)間進(jìn)行復(fù)制;

步驟4根據(jù)航班信息,創(chuàng)建相應(yīng)的市場(chǎng)和可選的行程池,每個(gè)行程包含相應(yīng)的航班序列;

步驟5如果行程的起點(diǎn)和終點(diǎn)分別與市場(chǎng)的起點(diǎn)和終點(diǎn)相同,則將該行程加入相應(yīng)的市場(chǎng)中,每個(gè)市場(chǎng)含有相應(yīng)的可選行程;

步驟6根據(jù)模型設(shè)置主體航司提供的各個(gè)行程所占市場(chǎng)份額以及其他航司相關(guān)市場(chǎng)份額為0～1的線性決策變量,將機(jī)型分配階段的決策變量x從原來(lái)的0-1決策變量改為0～1的線性決策變量;

步驟7將航班時(shí)刻表、機(jī)型分配和消費(fèi)者選擇模型的約束加入模型;

步驟8根據(jù)航班飛行距離和飛行時(shí)間計(jì)算航班的單位運(yùn)營(yíng)成本,將目標(biāo)函數(shù)加入模型;

步驟9通過(guò)CPLEX 獲得初始解。

(2)迭代求解。

步驟10創(chuàng)建專(zhuān)門(mén)的類(lèi)儲(chǔ)存初始解中機(jī)型分配階段的所有決策變量x的值,將所有x的屬性標(biāo)記為“未固定”;

步驟11在0～1的范圍內(nèi)規(guī)定一個(gè)接近1的數(shù)值作為“上界”的判斷標(biāo)準(zhǔn)(例如上界=0.99);

步驟12當(dāng)x大于上界,令x=1;

步驟13在步驟12基礎(chǔ)上,根據(jù)機(jī)型分配的覆蓋約束,將與被固定的變量對(duì)應(yīng)的航班(同樣的市場(chǎng)情形、起點(diǎn)、終點(diǎn)和出發(fā)時(shí)間,不同的機(jī)型)找出來(lái),令x=0;

步驟14將步驟12和13固定的變量的屬性改為“已固定”;

步驟15如果沒(méi)有x大于上界,在所有屬性標(biāo)記為“未固定”的x值中搜索最大值,找到后令x=1;

步驟16在步驟15基礎(chǔ)上,根據(jù)機(jī)型分配的覆蓋約束,將與被固定的變量對(duì)應(yīng)的航班(同樣的市場(chǎng)情形、起點(diǎn)、終點(diǎn)和出發(fā)時(shí)間,不同的機(jī)型)找出來(lái),令x=0;

步驟17將步驟15和16固定的變量的屬性改為“已固定”;

步驟18在所有x中搜索是否還有x的屬性為“未固定”,如果存在“未固定”的x,則通過(guò)CPLEX 獲得固定部分x后的初始解,返回步驟12;如果不存在“未固定”的x,則輸出最后一次獲得的求解結(jié)果,得到最終值。

上述步驟可以被整理成相應(yīng)的流程,如圖3所示。

圖3 潛水啟發(fā)式算法步驟流程Fig.3 Steps of diving heuristic algorithm

圖3中,右側(cè)兩個(gè)關(guān)鍵的判斷步驟可以用實(shí)例表示(見(jiàn)圖4),當(dāng)CPLEX 解完模型的線性松弛獲得初始解時(shí),程序?qū)⑺衳的初始解存儲(chǔ)在一個(gè)集合(未固定集)中,此時(shí)x是線性變量。規(guī)定上界為0.99,當(dāng)x大于上界時(shí),如情形1 中x=0.999 ≥0.99,將x固定為1;若集合中不存在x大于上界,如情形2中max{x1,x2,…}=0.80,則將最大值固定為1。之后將已固定的變量從未固定集中刪除,更新未固定集,繼續(xù)使用CPLEX 求解模型,進(jìn)行迭代,直至所有x都被固定,滿足0-1變量的條件,得到最終的結(jié)果。

圖4 潛水啟發(fā)式算法關(guān)鍵固定策略示意圖Fig.4 Key fixing strategies in diving heuristic algorithm

3 仿真測(cè)試及結(jié)果分析

3.1 參數(shù)設(shè)置

為了檢驗(yàn)所提出啟發(fā)式算法的效果,使用不同規(guī)模的算例進(jìn)行實(shí)驗(yàn),共6個(gè)算例,算例從小到大包含機(jī)場(chǎng)的個(gè)數(shù)分別為10、12、14、16、18和20個(gè)。除了機(jī)場(chǎng)信息,每個(gè)算例包含了機(jī)型、市場(chǎng)、行程和航班信息[32]。為了簡(jiǎn)化模型,只考慮直達(dá)航班,因此,行程信息可以和航班信息合并。下面以最小規(guī)模的例子進(jìn)行說(shuō)明。

機(jī)場(chǎng)信息包含機(jī)場(chǎng)的名稱(chēng),用于索引,這里用A、B、C等字母代替。機(jī)型信息如表1所示,包括機(jī)型名稱(chēng)、座位數(shù)和可用飛機(jī)數(shù)量,其中可用飛機(jī)數(shù)量是可以變化的輸入量,在3.2.2節(jié)的靈敏度分析中作為改變的參數(shù)測(cè)試算法的魯棒性。

表1 機(jī)型信息Tab.1 Fleet type information

在市場(chǎng)信息方面,為了模擬需求波動(dòng)的服務(wù)市場(chǎng),假設(shè)乘客需求遵循特定的分布,并將規(guī)劃過(guò)程分為幾個(gè)場(chǎng)景。對(duì)于模擬市場(chǎng)的情況,假設(shè)只有市場(chǎng)需求在變化,有好、一般和壞3種情況(見(jiàn)圖5),3種情況發(fā)生的概率分別為20%、50%和30%。假設(shè)每個(gè)市場(chǎng)都有一個(gè)基本的需求水平,當(dāng)市場(chǎng)好時(shí),需求在基本水平之上增長(zhǎng)10%;當(dāng)市場(chǎng)壞時(shí),需求下降20%。市場(chǎng)需求變化參數(shù)也是可以變化的輸入量,在3.2.2節(jié)的靈敏度分析中作為改變的參數(shù)測(cè)試算法的魯棒性。

圖5 市場(chǎng)需求變化參數(shù)設(shè)置Fig.5 Parameter settings for market demand changes

市場(chǎng)信息還包括起點(diǎn)、終點(diǎn)、市場(chǎng)總需求量、決策主體的票價(jià)、決策主體的吸引力和其他航司的總吸引力。表2以最小算例(包含10個(gè)機(jī)場(chǎng))舉例說(shuō)明了這些信息,其中起點(diǎn)和終點(diǎn)機(jī)場(chǎng)用A、B、C等標(biāo)號(hào),市場(chǎng)總需求量、決策主體的票價(jià)、決策主體的吸引力和其他航司的總吸引力等信息在實(shí)驗(yàn)中都是保持不變的已知數(shù)值。

表2 市場(chǎng)信息以及對(duì)應(yīng)行程的吸引力參數(shù)Tab.2 Market and itinerary information

航班信息包括出發(fā)機(jī)場(chǎng)、到達(dá)機(jī)場(chǎng)、頻率、距離和旅程時(shí)間。表3也以最小算例(包含10個(gè)機(jī)場(chǎng))舉例說(shuō)明了上述信息,相同地,出發(fā)和到達(dá)機(jī)場(chǎng)用A、B、C 等標(biāo)號(hào),頻率、距離和旅程時(shí)間等信息在實(shí)驗(yàn)中都是保持不變的已知數(shù)值。其中,距離和旅程時(shí)間不是直接代入模型的參數(shù),而是用于計(jì)算目標(biāo)函數(shù)中單個(gè)航班的運(yùn)營(yíng)成本。

表3 航班信息以及用于計(jì)算目標(biāo)函數(shù)中相關(guān)參數(shù)的數(shù)據(jù)Tab.3 Flight information

模型中還有一些參數(shù)需要提前設(shè)置。在機(jī)型分配部分,將最早起飛時(shí)間minT設(shè)置為4:00,最晚起飛時(shí)間maxT設(shè)置為24:00,因?yàn)榇蠖鄶?shù)航班計(jì)劃在4:00～24:00之間起飛。紅眼航班的設(shè)置被忽略,因此,在約束式(7)中只考慮地弧。

為簡(jiǎn)化模型,實(shí)驗(yàn)假設(shè)航班時(shí)刻表是每天重復(fù)的,航班僅在每個(gè)整點(diǎn)出發(fā)。為了保持每天出發(fā)的飛機(jī)能按時(shí)返回執(zhí)行第二天的任務(wù),即飛機(jī)的平衡,通過(guò)在預(yù)先指定的時(shí)間點(diǎn)CountT計(jì)數(shù)網(wǎng)絡(luò)中空中和地面的飛機(jī)數(shù)量(例如,該測(cè)試中選擇的時(shí)間點(diǎn)是11:30 p.m.)。

3.2 仿真測(cè)試

3.2.1結(jié)果分析 本文程序在C++編譯器VisualStudio中設(shè)計(jì)了5個(gè)類(lèi)別,包括機(jī)場(chǎng)、機(jī)型、航段、市場(chǎng)和行程,以構(gòu)建集成模型。其中,一個(gè)市場(chǎng)包含多個(gè)行程,一個(gè)行程包含多個(gè)航段。一個(gè)市場(chǎng)的出發(fā)地和目的地與該市場(chǎng)中包含的行程一致。仿真測(cè)試在帶有16 GB內(nèi)存的Intel(R)Core(TM)i7-10710U CPU 的windows系統(tǒng)上進(jìn)行。

該部分把3.1節(jié)中的參數(shù)代入模型并進(jìn)行了兩種測(cè)試。首先使用CPLEX 求解模型結(jié)果。由于最后收斂速度較慢,測(cè)試按照算例規(guī)模從小到大設(shè)置了最大運(yùn)行時(shí)間,分別為1 200 s、1 440 s、1 680 s、1 920 s、2 160 s和2 400 s,問(wèn)題規(guī)模如表4所示。然后使用設(shè)計(jì)的潛水啟發(fā)式算法進(jìn)行測(cè)試。由于該算法每次會(huì)固定一定數(shù)量的0-1 決策變量,而0-1決策變量的數(shù)量是有限的,故在迭代有限次后會(huì)終止(其他線性變量收斂速度很快),因此不需要設(shè)置最大運(yùn)行時(shí)間。CPLEX 和潛水啟發(fā)式算法測(cè)試結(jié)果對(duì)比如表5所示。

表4 測(cè)試算例變量和約束規(guī)模Tab.4 Scales of variables and constraints in test cases

表5 CPLEX和潛水啟發(fā)式算法的結(jié)果比較Tab.5 Comparisons between CPLEX and diving heuristic algorithm

由表4可以看出,在算例規(guī)模較小,即算例1時(shí),雖然CPLEX 的運(yùn)行時(shí)間1 200.00 s大于潛水啟發(fā)式算法的74.36 s,但CPLEX 能夠獲得比潛水啟發(fā)式算法明顯更優(yōu)的結(jié)果,即CPLEX 的目標(biāo)值(利潤(rùn))306 570.05 大于潛水啟發(fā)式算法的目標(biāo)值(利潤(rùn))284 519.92。

當(dāng)算例規(guī)模較大時(shí),即算例2～算例6,潛水啟發(fā)式算法不僅運(yùn)行時(shí)間明顯快于CPLEX,得到的結(jié)果也明顯優(yōu)于CPLEX。具體而言,算例2中潛水啟發(fā)式算法的運(yùn)行時(shí)間112.55 s不到CPLEX 運(yùn)行時(shí)間1 440.00 s的1/10,潛水啟發(fā)式算法的目標(biāo)值345 222.46大于CPLEX 的目標(biāo)值308 512.20。

從算例3 開(kāi)始,CPLEX 得到的目標(biāo)值249 085.83小于算例1的目標(biāo)值306 570.05。而在實(shí)際中,算例的規(guī)模越大,獲得的目標(biāo)值應(yīng)該大于或等于較小算例的目標(biāo)值(如果擴(kuò)大規(guī)模面臨虧損,則航空公司不運(yùn)營(yíng)這些航班,獲得0收益更佳)。這說(shuō)明,CPLEX 在規(guī)定時(shí)間內(nèi)沒(méi)有找到滿意的結(jié)果。潛水啟發(fā)式算法得到的結(jié)果顯示,隨著算例規(guī)模的擴(kuò)大,航空公司的利潤(rùn)提升,這符合常理,且明顯優(yōu)于CPLEX 的結(jié)果。

隨著算例的擴(kuò)大,潛水啟發(fā)式算法的目標(biāo)值優(yōu)勢(shì)越來(lái)越大,算例2時(shí)剛剛超過(guò)CPLEX 的目標(biāo)值,兩者基本持平,到算例6時(shí)與CPLEX 相比,目標(biāo)值擴(kuò)大了2.5倍。雖然時(shí)間優(yōu)勢(shì)有一定程度的縮小,算例2中潛水啟發(fā)式算法的運(yùn)行時(shí)間112.55 s不到CPLEX 運(yùn)行時(shí)間1 440.00 s的1/10,算例6中潛水啟發(fā)式算法的運(yùn)行時(shí)間729.93 s不到CPLEX運(yùn)行時(shí)間2 400.00 s的1/3,但仍然是潛水啟發(fā)式算法一個(gè)巨大的速度優(yōu)勢(shì)。

具體探究得到的決策變量值發(fā)現(xiàn),以最小算例的結(jié)果為例,如圖6所示。當(dāng)市場(chǎng)需求發(fā)生波動(dòng)時(shí),由于該航班的頻次較小且只有兩次,熱門(mén)時(shí)段備選充足,起飛時(shí)刻受到的影響微小,10:00和11:00都是相對(duì)熱門(mén)的起飛時(shí)間。

圖6 最小算例機(jī)型變化結(jié)果示意圖Fig.6 Fleet type changes in the smallest case

但由于市場(chǎng)需求總量變小,同樣的熱門(mén)時(shí)段所吸引到的旅客數(shù)量會(huì)發(fā)生變化。當(dāng)市場(chǎng)不景氣時(shí),吸引到的旅客數(shù)變小,航空公司應(yīng)分配容量較小的機(jī)型F1,避免因使用過(guò)大機(jī)型而空座位數(shù)較多,造成成本的浪費(fèi);當(dāng)市場(chǎng)狀況良好時(shí),航空公司將分配容量較大的機(jī)型F2,容納更多的旅客,獲得更多的收益。即使使用大機(jī)型的成本升高,但由于旅客數(shù)增加,新增的收益超過(guò)了成本。這種結(jié)果符合實(shí)際情況,表明數(shù)學(xué)建模是有意義的,并且設(shè)計(jì)的算法在提升計(jì)算速度和大算例的求解上比CPLEX 更有優(yōu)勢(shì),對(duì)于航空公司運(yùn)營(yíng)規(guī)劃有著重要意義。

3.2.2靈敏度分析 為了驗(yàn)證潛水啟發(fā)式算法的有效性,設(shè)計(jì)了靈敏度分析的實(shí)驗(yàn),將輸入數(shù)據(jù)中每種機(jī)型的數(shù)量進(jìn)行微調(diào),檢驗(yàn)在輸入數(shù)據(jù)變化的情況下,該算法是否仍然能夠快速解決問(wèn)題并得到滿意的結(jié)果,即檢驗(yàn)算法的魯棒性。首先選擇機(jī)型數(shù)量作為可變的參數(shù),任意選中3個(gè)機(jī)型的其中幾種,將機(jī)型數(shù)量增加2。由于每個(gè)算例有3種機(jī)型,每種機(jī)型的數(shù)量是否增加2是兩種情況,共有2×2×2=8種情況。最終進(jìn)行了6個(gè)算例×8 種情況共48組實(shí)驗(yàn),結(jié)果如表6所示。

表6 潛水啟發(fā)式算法靈敏度分析結(jié)果-機(jī)型數(shù)量變動(dòng)Tab.6 Sensitivity analysis under fleet number changes

在計(jì)算速度上,潛水啟發(fā)式算法運(yùn)行時(shí)間穩(wěn)定,與3.2.1節(jié)測(cè)試算例的運(yùn)行時(shí)間相似,沒(méi)有因?yàn)檩斎霐?shù)據(jù)的改變而發(fā)生較大的波動(dòng)。雖然在F1+2和F1+2、F3+2兩種情況下,與機(jī)型數(shù)量不變時(shí)相比,運(yùn)行時(shí)間有約20%的增長(zhǎng)(如算例2中F1+2和F1+2、F3+2兩種情況下的運(yùn)行時(shí)間135.36 s和144.82 s比與機(jī)型數(shù)量不變的運(yùn)行時(shí)間112.55 s長(zhǎng)約20%),但總體運(yùn)行時(shí)間較為穩(wěn)定,遠(yuǎn)快于CPLEX。

在目標(biāo)值上,求解較大規(guī)模算例時(shí),潛水啟發(fā)式算法也有明顯優(yōu)勢(shì),與3.2.1節(jié)測(cè)試算例相比,總體上因?yàn)闄C(jī)型數(shù)量的增加,所以得到更優(yōu)的目標(biāo)值。例如,對(duì)于算例1,除了F3+2之外,當(dāng)機(jī)型數(shù)量增加時(shí),可以為航班時(shí)刻表和機(jī)型分配提供更多可行方案,容納更多的乘客,獲得更高的收益。對(duì)于算例1中的F3+2,出現(xiàn)了當(dāng)大機(jī)型數(shù)量增加時(shí)所獲收益更小的情況。這是由于算例中有部分更適合使用小機(jī)型的情況,即需求量不大,只需要小機(jī)型就可以容納,并且小機(jī)型更加節(jié)省成本。而該啟發(fā)式算法在求解線性松弛問(wèn)題時(shí),根據(jù)x的數(shù)值大小,提前選定了大機(jī)型,這并非最優(yōu)的結(jié)果。實(shí)際上,使用小機(jī)型更加節(jié)省成本,但提前選定的結(jié)果后續(xù)無(wú)法調(diào)整,造成了較小程度的利潤(rùn)損失。

和算例1中的F3+2類(lèi)似,算例2中的F1+2存在利潤(rùn)損失情況,不同的是,算例2 中的F1+2出現(xiàn)了當(dāng)小機(jī)型數(shù)量增加時(shí)所獲收益更小的情況。這是由于算例中有部分更適合使用大機(jī)型的情況,即需求量大,大機(jī)型可以容納更多乘客,獲得更多利潤(rùn),能夠覆蓋使用大機(jī)型的高額成本。而該啟發(fā)式算法在求解線性松弛問(wèn)題時(shí),根據(jù)x的數(shù)值大小,提前選定了小機(jī)型,這并非最優(yōu)的結(jié)果。實(shí)際上,使用大機(jī)型能獲得更多的收益,但提前選定的結(jié)果后續(xù)無(wú)法調(diào)整,造成了較小程度的利潤(rùn)損失。

根據(jù)靈敏度分析結(jié)果,將CPLEX 與潛水啟發(fā)式算法的目標(biāo)值差距比例用散點(diǎn)圖表示,如圖7所示。其中,橫坐標(biāo)為測(cè)試的48個(gè)算例的序號(hào)。把不同規(guī)模的算例按照從大到小排列,同一算例的不同參數(shù)按照表6 的順序排列?？v坐標(biāo)的值是由CPLEX 的目標(biāo)值減去該算法的目標(biāo)值,所得差值除以CPLEX 的目標(biāo)值后得到的比例。在極少數(shù)情況下,如果CPLEX 的目標(biāo)值為負(fù)數(shù),則在得到差值后,除以CPLEX 的目標(biāo)值的相反數(shù)。該比例為正說(shuō)明CPLEX 目標(biāo)值更優(yōu),比例為0說(shuō)明CPLEX 與該算法目標(biāo)值持平,比例為負(fù)則說(shuō)明該算法目標(biāo)值更優(yōu)。

圖7 潛水啟發(fā)式算法與CPLEX 的目標(biāo)值差距比例-機(jī)型數(shù)量變動(dòng)Fig.7 Objective value gap ratios between CPLEX and diving heuristics under fleet number changes

通過(guò)觀察圖7 可以看出:當(dāng)算例規(guī)模較小時(shí),CPLEX 結(jié)果略好于潛水啟發(fā)式算法,兩者基本持平,目標(biāo)值差距比例約為5%～10%;當(dāng)算例規(guī)模擴(kuò)大時(shí),該比例不斷縮小,降至負(fù)值,尤其是從算例3開(kāi)始,該比例變成了較大的負(fù)值,最大的負(fù)值為-2.2,說(shuō)明潛水啟發(fā)式算法的目標(biāo)值明顯優(yōu)于CPLEX。

類(lèi)似地,對(duì)輸入數(shù)據(jù)中的市場(chǎng)概率進(jìn)行調(diào)換,檢驗(yàn)算法的魯棒性。將市場(chǎng)需求的好/一般/壞概率作為可變的參數(shù),任意調(diào)換位置,共有3×2×1=6種情況。最終進(jìn)行了6個(gè)算例×6種情況共36組實(shí)驗(yàn),結(jié)果如表7所示。

表7 潛水啟發(fā)式算法靈敏度分析結(jié)果-市場(chǎng)概率變動(dòng)Tab.7 Sensitivity analysis under market changes

在計(jì)算速度上,潛水啟發(fā)式算法運(yùn)行時(shí)間穩(wěn)定,與3.2.1節(jié)測(cè)試算例運(yùn)行時(shí)間相似,沒(méi)有因?yàn)檩斎霐?shù)據(jù)的改變而發(fā)生較大的波動(dòng)。雖然運(yùn)行時(shí)間有20%的增長(zhǎng)(如算例6中30%～50%～20%和50%～30%～20%兩種情況下的運(yùn)行時(shí)間858.65 s和915.23 s比與機(jī)型數(shù)量不變的運(yùn)行時(shí)間729.93 s長(zhǎng)約20%),但總體運(yùn)行時(shí)間較為穩(wěn)定,遠(yuǎn)快于CPLEX。

在目標(biāo)值上,求解小規(guī)模算例(算例1～3)時(shí),潛水啟發(fā)式算法在多數(shù)情況下占優(yōu),如算例2中,除了30%～20%～50%的情況,其他情況下得到的目標(biāo)值均優(yōu)于CPLEX。求解大規(guī)模算例(算例4～6)時(shí),潛水啟發(fā)式算法比CPLEX 具有明顯優(yōu)勢(shì)。潛水啟發(fā)式算法的目標(biāo)值符合市場(chǎng)需求的增減情況,如算例6中50%～30%～20%的情況是所有情形中需求量最大的,計(jì)算出的目標(biāo)值也是最大的。而CPLEX 得到的目標(biāo)值合理性不足,在算例6中同樣情形的目標(biāo)值是負(fù)值,不符合實(shí)際。

將CPLEX 與潛水啟發(fā)式算法的目標(biāo)值差距比例用散點(diǎn)圖表示,如圖8所示。其中,橫坐標(biāo)為測(cè)試的36個(gè)算例的序號(hào)。把不同規(guī)模的算例按照從大到小排列,同一算例的不同參數(shù)按照表7的順序排列。通過(guò)觀察圖8可以看出:當(dāng)算例較小時(shí),潛水啟發(fā)式算法結(jié)果略好于CPLEX,兩者基本持平,目標(biāo)值差距比例在20%內(nèi);當(dāng)算例規(guī)模擴(kuò)大時(shí),該差距不斷擴(kuò)大,尤其是從算例4開(kāi)始,該比例變成了較大的負(fù)值,最大的負(fù)值約為-6.2,說(shuō)明潛水啟發(fā)式算法的目標(biāo)值明顯優(yōu)于CPLEX。

圖8 潛水啟發(fā)式算法與CPLEX 的目標(biāo)值差距比例-市場(chǎng)概率變動(dòng)Fig.8 Objective value gap ratios between CPLEX and diving heuristics under market changes

根據(jù)上述分析,在機(jī)型數(shù)量變動(dòng)時(shí),潛水啟發(fā)式算法雖然出現(xiàn)了較小程度的利潤(rùn)損失,但該算法相對(duì)于CPLEX 在求解速度和目標(biāo)值上都有明顯的優(yōu)勢(shì),并且擁有非常好的魯棒性;在市場(chǎng)概率變動(dòng)時(shí),潛水啟發(fā)式算法在求解速度和目標(biāo)值上都占優(yōu),并且目標(biāo)值的優(yōu)勢(shì)會(huì)隨著算例規(guī)模的擴(kuò)大而增加。因此,相比于CPLEX,潛水啟發(fā)式算法可以更加有效地幫助航空公司在需求變動(dòng)情形下進(jìn)行航班時(shí)刻表和機(jī)型分配的運(yùn)營(yíng)規(guī)劃決策。

4 結(jié)論

本文針對(duì)多航段航空服務(wù)市場(chǎng)需求波動(dòng)情形,將航班時(shí)刻表安排和機(jī)型分配作為一個(gè)整體,研究了兩個(gè)服務(wù)運(yùn)營(yíng)決策的集成問(wèn)題。該問(wèn)題以航空公司運(yùn)營(yíng)總利潤(rùn)最大化為目標(biāo),考慮航空服務(wù)對(duì)消費(fèi)者的吸引力,復(fù)制多個(gè)可選起飛時(shí)段的航班,將航空服務(wù)市場(chǎng)需求波動(dòng)的多種情形按照離散分布作為輸入數(shù)據(jù),借助時(shí)空網(wǎng)絡(luò)理論,構(gòu)建了一個(gè)混合整數(shù)線性規(guī)劃模型。然后生成包含10～20個(gè)機(jī)場(chǎng)的6個(gè)算例,使用優(yōu)化求解器CPLEX 進(jìn)行求解,并設(shè)計(jì)了一種潛水啟發(fā)式算法進(jìn)行仿真測(cè)試。結(jié)果表明,當(dāng)算例的規(guī)模超過(guò)12 個(gè)機(jī)場(chǎng)時(shí),該算法在速度和目標(biāo)值上都優(yōu)于CPLEX。最后,靈敏度分析驗(yàn)證了該算法的魯棒性,說(shuō)明該算法可以幫助航空公司找到比CPLEX 更快更優(yōu)的即時(shí)決策解決方案。

本文在兩個(gè)方面取得了突破。首先將時(shí)刻表和機(jī)型分配與不斷變化的需求相結(jié)合進(jìn)行數(shù)學(xué)建模,然后提供了一種潛水啟發(fā)式算法處理市場(chǎng)上的各種場(chǎng)景,計(jì)算速度明顯優(yōu)于CPLEX,在求解大算例時(shí),計(jì)算結(jié)果也明顯優(yōu)于CPLEX。未來(lái)研究可以通過(guò)擴(kuò)展大規(guī)模案例和設(shè)計(jì)更好的算法來(lái)改進(jìn),也可以與更多的航空公司調(diào)度問(wèn)題相結(jié)合,考慮市場(chǎng)波動(dòng)對(duì)航空公司決策過(guò)程中更多因素的影響,從而進(jìn)一步優(yōu)化航空公司的決策過(guò)程。