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

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

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

　　1引言

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

　　航空論文范例：航空通信導航頻率干擾問題的探究

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

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

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

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

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

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

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

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

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

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

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

　　2求解算法

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

　　3算例分析

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

　　3.1敏感性分析

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

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

　　4結語

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

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

轉載請注明來自發(fā)表學術論文網(wǎng)：http://m.liangshanbai.cn/dzlw/27393.html