樞紐航空公司機(jī)隊與航線網(wǎng)絡(luò)的聯(lián)合規(guī)劃方法

　　摘要：針對傳統(tǒng)方法在解決航線網(wǎng)絡(luò)設(shè)計及其所需匹配運力兩類決策相互脫節(jié)的缺陷，提出一種機(jī)隊規(guī)劃和航線網(wǎng)絡(luò)設(shè)計的聯(lián)合優(yōu)化方法。該方法首先基于單分配樞紐網(wǎng)絡(luò)結(jié)構(gòu)，以各城市對市場需求量、航線最大航班容量和機(jī)隊可用飛行實力等為約束條件，以實現(xiàn)樞紐航線網(wǎng)絡(luò)運營成本最小化為目標(biāo)函數(shù)，構(gòu)建聯(lián)合規(guī)劃數(shù)學(xué)模型，然后設(shè)計改進(jìn)的遺傳算法求解該模型，最后根據(jù)各類機(jī)型機(jī)隊的利用率獲取機(jī)隊規(guī)劃方案。算例分析表明：與傳統(tǒng)方法相比，聯(lián)合優(yōu)化模型的網(wǎng)絡(luò)運營總成本降低了11.25%;與傳統(tǒng)遺傳算法和分枝定界法相比，改進(jìn)的遺傳算法的求解時間平均降低了80%。

　　關(guān)鍵詞：航空運輸;樞紐網(wǎng)絡(luò)設(shè)計;機(jī)隊規(guī)劃;運力優(yōu)化匹配;遺傳算法

　　1引言

　　樞紐航線網(wǎng)絡(luò)設(shè)計是指在未來規(guī)劃區(qū)域給定若干個離散城市的基礎(chǔ)上，就城市之間的連接關(guān)系、客貨流的運輸路徑和樞紐位址及其個數(shù)進(jìn)行系統(tǒng)安排，以實現(xiàn)樞紐網(wǎng)絡(luò)設(shè)計的系統(tǒng)總成本最小化。機(jī)隊規(guī)劃是指在模擬航空公司運營環(huán)境如航線網(wǎng)絡(luò)結(jié)構(gòu)、客貨流量等基礎(chǔ)上，就所需的機(jī)隊規(guī)模及結(jié)構(gòu)進(jìn)行系統(tǒng)安排，以實現(xiàn)機(jī)隊運營效益(如成本、利潤等)的最大化。機(jī)隊和航線網(wǎng)絡(luò)規(guī)劃是航空公司未來數(shù)十年內(nèi)的重大戰(zhàn)略決策問題，其結(jié)果好壞從根本上決定了航空公司的運營效益和市場競爭力。

　　航空論文范例：航空通信導(dǎo)航頻率干擾問題的探究

　　目前，航空公司開展機(jī)隊與樞紐網(wǎng)絡(luò)規(guī)劃普遍采用“先網(wǎng)絡(luò)設(shè)計，后機(jī)隊規(guī)劃”的分散決策模式。相關(guān)研究主要集中于樞紐網(wǎng)絡(luò)設(shè)計和機(jī)隊規(guī)劃兩方面。樞紐網(wǎng)絡(luò)設(shè)計方面，樞紐網(wǎng)絡(luò)通過匯運、轉(zhuǎn)運和分運使運輸具有規(guī)模經(jīng)濟(jì)性，O’Kelly、SkorinKapov、Ernst、Ebery、柏明國等以折扣系數(shù)表示樞紐之間運輸?shù)囊?guī)模經(jīng)濟(jì)性，構(gòu)建了以總成本最小化的樞紐網(wǎng)絡(luò)設(shè)計模型[15]。

　　上述研究的建模思路假設(shè)邊上的單位流成本為獨立參數(shù)，并未考慮到網(wǎng)絡(luò)各邊上的實際運營所需匹配的各類運輸工具的固定成本對樞紐網(wǎng)絡(luò)設(shè)計方案的影響。因此Qin、Campbell、O’Kelly、Ghodratnama進(jìn)一步考慮了樞紐網(wǎng)絡(luò)設(shè)計中的固定成本，并將其按照運輸時間(或距離)分?jǐn)偟綐屑~網(wǎng)絡(luò)中，再結(jié)合樞紐網(wǎng)絡(luò)規(guī)模經(jīng)濟(jì)性開展了樞紐網(wǎng)絡(luò)設(shè)計問題建模研究[69]。然而，網(wǎng)絡(luò)中各邊上的運輸工具的固定成本和變動成本取決于該邊上匹配的運輸工具類型，而不同類型運輸工具的固定成本以及在不同邊上的變動成本存在顯著性差異，因此，O’Kelly和Camargo以分段函數(shù)形式表示樞紐之間客貨流量與固定成本和折扣系數(shù)的關(guān)系，構(gòu)建樞紐網(wǎng)絡(luò)設(shè)計模型[10,11]。

　　以上研究僅考慮了樞紐之間轉(zhuǎn)運的客流量，而樞紐和輪輻之間合并和分發(fā)客貨流，也會產(chǎn)生大量的客流形成規(guī)模經(jīng)濟(jì)，因此，Kimmis、SerperandAlumur、Zhang等構(gòu)建了考慮不同類型運輸工具的運營成本差異為每條邊指定單位成本最低的運輸工具，構(gòu)建樞紐網(wǎng)絡(luò)設(shè)計模型[1113]，但并未考慮樞紐網(wǎng)絡(luò)中關(guān)鍵資源約束;張培文等構(gòu)建了在機(jī)隊配置已定的條件下考慮不同機(jī)型的運營成本差異的樞紐航線網(wǎng)絡(luò)設(shè)計模型[15]，但本質(zhì)上仍然不是樞紐網(wǎng)絡(luò)與機(jī)隊聯(lián)合規(guī)劃問題的探討。

　　另外，樞紐網(wǎng)絡(luò)固有的容量限制使得運營過程中可能出現(xiàn)擁堵，Ghodratnama、徐濤、吳艷芳等構(gòu)建了考慮擁堵成本的樞紐網(wǎng)絡(luò)設(shè)計模型[9,16,17];Kaveh、Costa、樂美龍、馮乾等構(gòu)建了考慮節(jié)點流容量限制的樞紐網(wǎng)絡(luò)設(shè)計模型[1821]。而航空公司構(gòu)建樞紐網(wǎng)絡(luò)時不僅需要考慮樞紐節(jié)點容量限制，還需考慮受空域容量限制下的航班流量，因此，可以在構(gòu)建數(shù)學(xué)模型時以每條航線上預(yù)期可獲取的航班時刻資源表示機(jī)場容量和空域容量約束[27]。機(jī)隊規(guī)劃方面，已有研究普遍基于給定的航線網(wǎng)絡(luò)方案，開展機(jī)隊中各類機(jī)型飛機(jī)數(shù)量的決策。宏觀機(jī)隊規(guī)劃從整個航線網(wǎng)絡(luò)層面對客貨流需求和機(jī)隊運力進(jìn)行匹配以獲取各類機(jī)型飛機(jī)的數(shù)量，但該方法無法準(zhǔn)確反映各類機(jī)型在航線上的技術(shù)經(jīng)濟(jì)適應(yīng)性。

　　因此，目前研究主要集中在基于航班機(jī)型分配和基于航線運力分配的微觀機(jī)隊規(guī)劃方法，其中考慮的因素主要包括了各航線上的最大航班容量、最小航班頻次及交通容量限制，以及航線航班上客貨流量與運力的供需匹配關(guān)系2231]，但卻很少考慮到樞紐網(wǎng)絡(luò)中的客貨流中轉(zhuǎn)銜接溢出效應(yīng)導(dǎo)致的航線之間客貨流溢出的相互關(guān)系，導(dǎo)致了機(jī)隊規(guī)劃供需計算不準(zhǔn)確問題，如文獻(xiàn)[32]基于樞紐網(wǎng)絡(luò)客貨流中轉(zhuǎn)銜接效益，研究了相應(yīng)的機(jī)隊規(guī)劃模型及其求解算法。

　　然而，這種在既定樞紐網(wǎng)絡(luò)方案下的機(jī)隊規(guī)劃問題探討，并沒有考慮到客貨流分配方案和航線運力匹配決策之間的相互關(guān)系，因此本質(zhì)上仍然不是樞紐網(wǎng)絡(luò)與機(jī)隊聯(lián)合規(guī)劃問題的探討。綜合來看，國內(nèi)外在該領(lǐng)域的研究主要局限于單一的樞紐網(wǎng)絡(luò)設(shè)計或機(jī)隊規(guī)劃問題，即基于分散的戰(zhàn)略決策模式展開研究。因此，本文嘗試將樞紐網(wǎng)絡(luò)設(shè)計和機(jī)隊規(guī)劃決策融合在一起，提出樞紐網(wǎng)絡(luò)和機(jī)隊規(guī)劃的聯(lián)合優(yōu)化方法。

　　本文的主要貢獻(xiàn)在于：①以單分配樞紐網(wǎng)絡(luò)設(shè)計的三下標(biāo)數(shù)學(xué)規(guī)劃模型為基礎(chǔ)，將任意城市之間的運力匹配各類機(jī)型在航線上的飛行頻次決策問題融入到樞紐網(wǎng)絡(luò)設(shè)計決策之中;②在構(gòu)造目標(biāo)函數(shù)時，使用與實際情況更加接近的機(jī)型航線運營成本取代單位成本和折扣因子;③使用更接近于實際的航線最大航班頻次約束替代機(jī)場或航線的客流容量約束;④考慮問題的NPHard屬性，先利用選取樞紐城市的多屬性評價法確定候選樞紐集，再根據(jù)問題特性設(shè)計改進(jìn)的遺傳算法。

　　模型構(gòu)建1問題描述與假設(shè)在未來規(guī)劃區(qū)域內(nèi)，已知個城市、1)個OD客流、任意城市間的航線最大航班容量ij、機(jī)型(∈)機(jī)隊的可用飛行實力(表示為輪檔飛行時間)及其平均月利用率、各機(jī)型飛機(jī)在航線上的運營成本ij和客座率ij，考慮從擬運營的城市集中選取個城市作為樞紐，并確定樞紐城市的位址、輪輻城市與樞紐城市的連接方式ik，機(jī)隊運力匹配方案ij及相應(yīng)的各機(jī)型的飛機(jī)數(shù)量，以使得整個網(wǎng)絡(luò)系統(tǒng)運營成本最小。

　　本文采用單分配樞紐航線網(wǎng)絡(luò)設(shè)計中的經(jīng)典假設(shè)6,8,12，再結(jié)合機(jī)隊規(guī)劃問題的特性278]，給出如下假設(shè)條件。(1)樞紐城市之間形成全連通網(wǎng)絡(luò)，且輪輻城市之間不允許直接連接;(2)任一輪輻城市有且僅能和一個樞紐城市相連接;(3)任意OD客流僅在樞紐城市進(jìn)行中轉(zhuǎn)，且中轉(zhuǎn)次數(shù)不超過次;(4)任意OD客流必須全部由起始城市運送到目的城市;(5)航線→,∈N上允許的最大航班容量總是有限的;(6)機(jī)型∈的平均月利用率是固定的，可以根據(jù)航空公司歷史運營數(shù)據(jù)估計;(7)機(jī)型∈機(jī)隊的可用飛行實力受到機(jī)型的飛行機(jī)組實際能夠完成的最大航班任務(wù)時間的制約。

　　1.1樞紐網(wǎng)絡(luò)設(shè)計與航線運力匹配的聯(lián)合優(yōu)化模型

　　三下標(biāo)樞紐網(wǎng)絡(luò)建模方法是解決樞紐網(wǎng)絡(luò)設(shè)計的經(jīng)典方法，該方法基于起止點，通過定義各OD流匯運、轉(zhuǎn)運和分運流變量，結(jié)合樞紐設(shè)置數(shù)量限制、流平衡限制、流完整性限制等約束，實現(xiàn)樞紐網(wǎng)絡(luò)系統(tǒng)總成本最小化3,12]。航線運力匹配是一類運營計劃層面的決策，該方法通過定義各航線上匹配的機(jī)型及其飛行頻次決策變量，結(jié)合客流最大需求限制、航線最大航班容量限制及各類機(jī)型機(jī)隊的可用飛行實力限制等因素，以獲取航線運力匹配經(jīng)濟(jì)性最佳方案27,28]。

　　2求解算法

　　單分配樞紐網(wǎng)絡(luò)設(shè)計是一個NPhard問題，加入航線運力匹配決策后求解難度更大，因此，為降低模型的求解難度，利用傳統(tǒng)的樞紐城市的多標(biāo)準(zhǔn)評價方法構(gòu)建具有樞紐建設(shè)條件的候選樞紐集;然后根據(jù)問題的特點設(shè)計了遺傳算法求解模型。

　　3算例分析

　　選取中國某航空公司的運營數(shù)據(jù)模擬設(shè)計樞紐網(wǎng)絡(luò)，該公司機(jī)隊數(shù)據(jù)如表所示，擬開航的城市12個。樞紐設(shè)置成本：根據(jù)《中國民用航空第十三個五年規(guī)劃》和2018年民航業(yè)發(fā)展統(tǒng)計公報匯總修正獲取;各機(jī)型飛機(jī)利用率、機(jī)隊的可用飛行實力、機(jī)型航線運營成本、機(jī)型航線客座率、OD客流需求：根據(jù)該公司的2018年實際平均數(shù)據(jù);航班最大航班容量：結(jié)合擬運營機(jī)場的時刻資源使用情況、《民航航班時刻管理辦法》、公司的航線航班分布，與航班計劃人員共同確定。因篇幅限制，本文略去具體數(shù)據(jù)。

　　3.1敏感性分析

　　上述算例通過某航空公司生產(chǎn)數(shù)據(jù)模擬了樞紐網(wǎng)絡(luò)設(shè)計和機(jī)隊規(guī)劃聯(lián)合決策工作，不能說明部分參數(shù)的變動對優(yōu)化決策結(jié)果的影響，因此本節(jié)將分析各機(jī)型機(jī)隊的可用飛行實力、航線最大航班容量、樞紐數(shù)量對航空公司樞紐網(wǎng)絡(luò)設(shè)計和機(jī)隊規(guī)劃方案的影響。 為驗證說明機(jī)隊的可用飛行實力對航空公司樞紐航線網(wǎng)絡(luò)設(shè)計和機(jī)隊規(guī)劃方案的影響，假定各機(jī)型的可用飛行實力相同，設(shè)定種情景：機(jī)隊可用飛行實力資源數(shù)量為6000、7000、8000、9000、10000、12000和20000，利用本文的聯(lián)合優(yōu)化模型與算法求解。

　　可以發(fā)現(xiàn)，①當(dāng)各機(jī)型機(jī)隊的可用飛行實力為6000時，無可行的網(wǎng)絡(luò)設(shè)計和機(jī)隊規(guī)劃方案，說明受航空公司機(jī)隊可用飛行實力資源總量的限制，無法滿足既定的所有OD客流需求;②當(dāng)各機(jī)型機(jī)隊的可用飛行實力大于等于7000時，所獲得的網(wǎng)絡(luò)設(shè)計方案相同，機(jī)隊規(guī)劃方案不完全一致，總體來說，隨著可用飛行實力的增加，大座級飛機(jī)的數(shù)量呈增長趨勢，小座級飛機(jī)呈減少趨勢;③當(dāng)機(jī)隊的可用飛行實力達(dá)到一定數(shù)量時，機(jī)隊規(guī)劃方案不再改變(例如機(jī)隊的可用飛行實力為12000和20000時，機(jī)隊規(guī)劃方案和總成本均相同)。因此，航空公司在機(jī)隊規(guī)劃工作過程中必須考慮機(jī)隊的可用飛行實力限制，才能使規(guī)劃所得的機(jī)隊規(guī)劃方案更利于未來實際的運營。

　　4結(jié)語

　　針對航空公司所采用的“先網(wǎng)絡(luò)設(shè)計，后機(jī)隊規(guī)劃”分散決策模式的缺陷，本文在現(xiàn)有的樞紐網(wǎng)絡(luò)設(shè)計和機(jī)隊規(guī)劃問題的研究基礎(chǔ)上，提出了一種樞紐網(wǎng)絡(luò)設(shè)計和機(jī)隊規(guī)劃的聯(lián)合優(yōu)化方法，其實質(zhì)在于將第二階段的航線運力優(yōu)化匹配融入到樞紐網(wǎng)絡(luò)設(shè)計階段，以滿足所有OD客流運輸需求的總成本最低為優(yōu)化目標(biāo)，綜合考慮了樞紐網(wǎng)絡(luò)設(shè)計和機(jī)隊規(guī)劃的制約因素，以及二者之間的平衡，實現(xiàn)樞紐航線網(wǎng)絡(luò)設(shè)計與運力優(yōu)化匹配的聯(lián)合決策。

　　算例結(jié)果表明該模型較好地彌補了傳統(tǒng)方法的不足，規(guī)劃結(jié)果更加切合航空公司運營實際。在模型的構(gòu)建過程中，本文假定OD客流需求、機(jī)型航線運營成本、航線最大航班容量等因素是確定的，網(wǎng)絡(luò)設(shè)計和機(jī)隊匹配方案因各種制約因素的變化而變化，因此在今后的研究中需要進(jìn)一步設(shè)計樞紐網(wǎng)絡(luò)設(shè)計與機(jī)隊匹配聯(lián)合決策的魯棒性模型與算法。

　　參考文獻(xiàn)

　　[1]O’Kelly.Aquadraticintegerprogramforthelocationofinteractinghubfacilities[J].EuropeanJournalofOperationalResearch,1987,32:393404.

　　[2]SkorinKapovD,SkorinKapovJ,O’Kelly.Tightlinearprogrammingrelaxationsofuncapacitatedhubmedianproblems[J].EuropeanJournalofOperationalResearch,1996,94:582593.

　　[3]ErnstA,KrishnamoorthyM.Anexactsolutionapproachbasedonshortestpathsforphubmedianproblems[J].INPORMSJournalonComputing,1998,10(2):149161.

　　作者：張培文1,2，汪瑜2,*，王旻軻2

轉(zhuǎn)載請注明來自發(fā)表學(xué)術(shù)論文網(wǎng)：http:///dzlw/27393.html