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

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

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

　　1引言

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

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

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

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

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

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

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

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

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

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

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

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

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

　　2求解算法

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

　　3算例分析

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

　　3.1敏感性分析

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

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

　　4結(jié)語(yǔ)

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

　　算例結(jié)果表明該模型較好地彌補(bǔ)了傳統(tǒng)方法的不足，規(guī)劃結(jié)果更加切合航空公司運(yùn)營(yíng)實(shí)際。在模型的構(gòu)建過(guò)程中，本文假定OD客流需求、機(jī)型航線運(yùn)營(yíng)成本、航線最大航班容量等因素是確定的，網(wǎng)絡(luò)設(shè)計(jì)和機(jī)隊(duì)匹配方案因各種制約因素的變化而變化，因此在今后的研究中需要進(jìn)一步設(shè)計(jì)樞紐網(wǎng)絡(luò)設(shè)計(jì)與機(jī)隊(duì)匹配聯(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)載請(qǐng)注明來(lái)自發(fā)表學(xué)術(shù)論文網(wǎng)：http:///dzlw/27393.html