有容量限制下的樞紐航線網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)模型

王 謙 車 通 李博文

(中國(guó)民用航空飛行學(xué)院機(jī)場(chǎng)工程與運(yùn)輸管理學(xué)院 四川 廣漢 618307)

引言

圍繞樞紐航線網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題，國(guó)內(nèi)外已經(jīng)進(jìn)行了深入的研究。Campbell，Skorin-Kapov，O'klly，Ernst等人分別構(gòu)建了四下標(biāo)[1,2,3]和三下標(biāo)樞紐樞紐航線網(wǎng)絡(luò)模型[4]，并總結(jié)了P樞紐中位問(wèn)題的基本內(nèi)涵[5]。后面學(xué)者們又針對(duì)機(jī)場(chǎng)建設(shè)成本和運(yùn)輸折扣因子[6,7]、O&D流及單位流成本不確定性等方面，探討了影響樞紐航線網(wǎng)絡(luò)方案的因素，并設(shè)計(jì)了相應(yīng)的求解算法加快計(jì)算速度[8]。但是，上述研究成果并沒有考慮到樞紐機(jī)場(chǎng)容量限制對(duì)于樞紐航線網(wǎng)絡(luò)設(shè)計(jì)的影響。Campbell針對(duì)這一問(wèn)題，提出在四下標(biāo)模型中增加相應(yīng)約束條件，將無(wú)容量限制問(wèn)題轉(zhuǎn)換為有容量限制下的樞紐航線網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題，但卻并沒有分析容量限制對(duì)于航線網(wǎng)絡(luò)方案的影響。事實(shí)上，無(wú)容量限制下的Campbell四下標(biāo)模型，由于在樞紐之間施加的折扣因子，導(dǎo)致特定O&D客流在選擇不同運(yùn)輸路線形式時(shí)是被確定的(如O&D客流的四下標(biāo)路線形式為i-i-j-j)，但在樞紐機(jī)場(chǎng)有容量限制下，這種確定的形式將被打破(如O&D客流的四下標(biāo)路線形式可能變?yōu)閕-j-j-j，由此造成樞紐機(jī)場(chǎng)i的本地流出客流量并未統(tǒng)計(jì))，因此導(dǎo)致和實(shí)際情況不再相符[9]。

鑒于此，本文為了構(gòu)建更為符合實(shí)際情況的樞紐網(wǎng)絡(luò)模型，首先，指出Campbell四下標(biāo)模型在解決有容量限制樞紐網(wǎng)絡(luò)設(shè)計(jì)決策中的不足之處；然后，通過(guò)增加限制O&D流運(yùn)輸路徑的約束條件，提出改進(jìn)的Campbell四下標(biāo)樞紐航線網(wǎng)絡(luò)模型；最后，選取國(guó)內(nèi)8個(gè)中心城市相關(guān)數(shù)據(jù)驗(yàn)證改進(jìn)模型的可行性，以此為構(gòu)建更為符合實(shí)際的樞紐航線網(wǎng)絡(luò)提供理論指導(dǎo)。

一、符號(hào)說(shuō)明和問(wèn)題描述

在模型中，已知任一O&D市場(chǎng)i-j(?i,j∈N.)的旅客需求量為wij(單位：人次)，依次流經(jīng)樞紐節(jié)點(diǎn)k,m的單位流成本cikmj(單位：元/人次)，結(jié)合樞紐數(shù)量限制來(lái)確定每對(duì)O&D流i-j依次流經(jīng)樞紐節(jié)點(diǎn)k,m的旅客需求分配比例xikmj和樞紐位址yk，以實(shí)現(xiàn)航線網(wǎng)絡(luò)運(yùn)輸總成本最小。

需要說(shuō)明的是，任一O&D市場(chǎng)i-j的單位流成本cikmj，有cikmj=αcik+βckm+γckj成立，其中：cij為節(jié)點(diǎn)i到節(jié)點(diǎn)j單位流成本(單位：元/人次)；α,β,γ分別為非樞紐與樞紐之間、樞紐與樞紐之間、樞紐與非樞紐之間的折扣因子，又稱匯運(yùn)折扣因子、轉(zhuǎn)運(yùn)折扣因子、分運(yùn)折扣因子。且一般有0≤β<α,γ≤1成立。

二、基本假設(shè)與模型結(jié)構(gòu)

(一)Campbell四下標(biāo)模型

Campbell四下標(biāo)模型以航線網(wǎng)絡(luò)運(yùn)輸總成本最低為目標(biāo)函數(shù)，以O(shè)&D運(yùn)輸路徑為決策變量，建立的是無(wú)容量限制多分配的樞紐航線網(wǎng)絡(luò)模型，并試圖通過(guò)增加約束

(1)

從而使原問(wèn)題轉(zhuǎn)換為容量限制下的多分配樞紐選址問(wèn)題(CMAHLP)[9][10]。

模型主要有如下假設(shè)：

(1)非樞紐節(jié)點(diǎn)不允許直達(dá)，只允許通過(guò)樞紐節(jié)點(diǎn)轉(zhuǎn)運(yùn)，且轉(zhuǎn)運(yùn)次數(shù)不超過(guò)2次；

(2)轉(zhuǎn)運(yùn)只允許發(fā)生在樞紐節(jié)點(diǎn)；

(3)由于運(yùn)輸存在規(guī)模經(jīng)濟(jì)性，各節(jié)點(diǎn)之間的運(yùn)輸成本要乘以相應(yīng)的折扣因子；

(4)各節(jié)點(diǎn)之間的O&D流需求是固定的。

(2)

(3)

(4)

(5)

(6)

xikmj≥0,?i,k,m,j∈N.

(7)

yk∈{0,1},?k∈N.

(8)

其中式(2)為目標(biāo)函數(shù)，要求航空客流運(yùn)輸成本以及樞紐建設(shè)總成本最小；式(3)保證所有的O&D流必須從起始城市運(yùn)往目的城市；式(4)及式(5)限制了中轉(zhuǎn)只能通過(guò)樞紐進(jìn)行；式(6)為容量限制，要求流經(jīng)樞紐k的流量小于其最大容量限制；

Campbell四下標(biāo)模型在解決有容量限制問(wèn)題時(shí)，會(huì)出現(xiàn)樞紐容量限制跳變問(wèn)題。比如機(jī)場(chǎng)i、j均為樞紐機(jī)場(chǎng)，且兩者之間的O&D流i-j選擇直達(dá)運(yùn)輸方式進(jìn)行運(yùn)輸，此時(shí)相應(yīng)客流路徑的表達(dá)方式則有i-i-j-j、i-j-j-j和i-i-i-j三種形式。按照約束(1)計(jì)算樞紐機(jī)場(chǎng)容量方式，顯然只有客流路徑i-i-j-j把從i流出的客流量，以及流入j的客流量統(tǒng)計(jì)進(jìn)相應(yīng)機(jī)場(chǎng)實(shí)際發(fā)生流量之中。但是，當(dāng)該樞紐機(jī)場(chǎng)實(shí)際流量達(dá)到容量上限時(shí)，就會(huì)出現(xiàn)客流路徑表達(dá)方式從i-i-j-j跳變?yōu)閕-j-j-j現(xiàn)象(因?yàn)閕-j-j-j形式并沒有將從樞紐i流出的客流量統(tǒng)計(jì)到)，并由此強(qiáng)制滿足約束條件(1)，但這卻顯然和實(shí)際情況不相符。從折扣因子的選擇來(lái)看，i-j-j-j形式中的折扣因子為匯運(yùn)折扣因子α，但對(duì)于樞紐i,j節(jié)點(diǎn)而言，施加轉(zhuǎn)運(yùn)折扣因子β才符合實(shí)際情況。

(二)改進(jìn)的Campbell四下標(biāo)模型

基于此，本文在Campbell四下標(biāo)模型基礎(chǔ)上，增加式(9)-(10)約束條件，即在任一客流路徑中，當(dāng)樞紐機(jī)場(chǎng)作為終點(diǎn)或起點(diǎn)時(shí)，必須強(qiáng)制選擇指定路徑以確保統(tǒng)計(jì)到流入、流出和轉(zhuǎn)運(yùn)的客流量。

(9)

(10)

式(9)和式(10)限制了部分客流的運(yùn)輸方式，當(dāng)樞紐作為起點(diǎn)或終點(diǎn)城市時(shí)，O&D流運(yùn)輸路徑必須包含其自身到自身的部分，確保樞紐在任何情況下都會(huì)存在于路徑i-k-m-j中的k或m位置。由前人研究可知，任一兩地之間的航空運(yùn)輸成本通常與距離成正比，且滿足三角形邊長(zhǎng)不等式關(guān)系，在樞紐之間規(guī)模經(jīng)濟(jì)性最強(qiáng)，即轉(zhuǎn)運(yùn)折扣因子相對(duì)最小的情況下，樞紐之間必然是直達(dá)形式，這與Campbell四下標(biāo)模型是一致且合理的。而且通過(guò)約束(9)-(10)，使得對(duì)于樞紐容量限制不再出現(xiàn)跳變現(xiàn)象，即嚴(yán)格統(tǒng)計(jì)到進(jìn)入、流出樞紐機(jī)場(chǎng)，以及從樞紐機(jī)場(chǎng)中轉(zhuǎn)這三部分客流量。同時(shí)，i-i-m-j和i-m-j-j形式也解決了折扣因子的正確選擇問(wèn)題。

三、算例分析

為了驗(yàn)證上述模型的正確性，選取北京、成都、廣州、杭州、昆明、上海、武漢和西安八個(gè)城市(按照1-8進(jìn)行編號(hào))，并基于MATLAB軟件在Acer，Inter(R)，Core(TM)i5，CPU2.4Hz，8G內(nèi)存平臺(tái)上，通過(guò)yalmip+Gurobi求解器進(jìn)行驗(yàn)證計(jì)算。選取α=γ=1。表1至表3分別給出了兩個(gè)模型部分客流路徑和不同轉(zhuǎn)運(yùn)折扣因子下的樞紐位址，其中：hub表示樞紐。

表1 Campbell模型客流路徑(β=0.8)

Campbell四下標(biāo)模型計(jì)算結(jié)果為y1=y2=y4=y7，即OD流通過(guò)樞紐北京、成都、杭州和武漢中轉(zhuǎn)運(yùn)輸。對(duì)應(yīng)的另一列則為O&D流i-j經(jīng)樞紐k,m中轉(zhuǎn)的流量占i-j總流量的比例值xikmj。分析表1得出：

(1)武漢-北京O&D流同時(shí)出現(xiàn)兩種不同流經(jīng)“路徑”?？梢钥闯?，這種情況即是上文敘述的三種不同直達(dá)形式的兩種。實(shí)際上武漢和北京同為樞紐，應(yīng)只能選擇武漢-武漢-北京-北京路徑運(yùn)輸。出現(xiàn)武漢-北京-北京-北京運(yùn)輸路徑是由于在流量分配過(guò)程中，武漢容量已經(jīng)飽和，不能再接收新的流量，部分O&D流跳變到此路徑規(guī)避通過(guò)武漢流量的增加。顯然這導(dǎo)致計(jì)算通過(guò)樞紐武漢的流量部分缺失，與實(shí)際不符。

(2)武漢-北京部分O&D流的跳變也導(dǎo)致成本折扣因子從轉(zhuǎn)運(yùn)因子β=0.8變換到匯運(yùn)因子α=1。會(huì)導(dǎo)致這部分O&D流的運(yùn)輸成本增加，但是因武漢容量超出導(dǎo)致選擇新樞紐或調(diào)增其他路徑造成的成本大于調(diào)整武漢-北京O&D流運(yùn)輸路徑造成的成本增加，所以最終部分O&D流選擇跳變到武漢-北京-北京-北京路徑進(jìn)行運(yùn)輸，同時(shí)樞紐武漢的容量約束限制也得以滿足；杭州-北京O&D流的運(yùn)輸路徑也存在此類問(wèn)題，O&D流選擇杭州-北京-北京-北京路徑運(yùn)輸，類似的，此路徑會(huì)造成經(jīng)過(guò)杭州樞紐流量的計(jì)算缺失，折扣因子的使用同樣也存在同樣問(wèn)題。

綜上所述可以發(fā)現(xiàn)，Campbell四下標(biāo)模型在處理容量限制下的多分配樞紐選址問(wèn)題上并不能真正約束到通過(guò)一個(gè)樞紐城市的流量，存在容量限制跳變且成本折扣因子不對(duì)應(yīng)的局限性。

表2 改進(jìn)模型路徑(β=0.8)

改進(jìn)的Campbell四下標(biāo)模型計(jì)算結(jié)果為y1=y3=y4=y5=y7，即O&D流通過(guò)樞紐北京、廣州、杭州、昆明和武漢中轉(zhuǎn)運(yùn)輸，分析表2可以得出：

(1)客流流經(jīng)路徑中樞紐都處于合適位置，如客流路徑廣州-廣州-武漢-西安，樞紐廣州不僅處于起點(diǎn)位置，也會(huì)存在于中i-k-m-j的為k位置，對(duì)于通過(guò)樞紐廣州和武漢的流量計(jì)算是合理且全面的。

(2)對(duì)于整個(gè)航線網(wǎng)絡(luò)來(lái)說(shuō)廣州武漢同為樞紐，所以即使廣州處于起始位置，廣州武漢之間的折扣因子應(yīng)選擇β=0.8，體現(xiàn)樞紐之間的規(guī)模經(jīng)濟(jì)性。因此改進(jìn)模型的折扣因子選擇也是合理的。

表3 樞紐位置

由表3可以看出在β=0.2及β=0.4時(shí)，Campbell四下標(biāo)模型和改進(jìn)模型的結(jié)果是一致的，也反映了改進(jìn)模型的合理性。在β=0.8和β=0.6時(shí)改進(jìn)模型的樞紐位置和Campbell四下標(biāo)模型有了一定的變化，這是由于在算例中，隨著樞紐個(gè)數(shù)的減少，樞紐容量逐漸飽和，而改進(jìn)模型中對(duì)于樞紐容量的限制更為準(zhǔn)確，樞紐位置及航線連接方式改變，樞紐選擇自然會(huì)有所不同。

綜上所述，改進(jìn)的Campbell四下標(biāo)模型構(gòu)造下的樞紐航線網(wǎng)絡(luò)更為符合現(xiàn)實(shí)情況，契合樞紐建設(shè)的容量標(biāo)準(zhǔn)，因此改進(jìn)模型可行。

四、結(jié)語(yǔ)

本文通過(guò)增加限制條件約束航線網(wǎng)絡(luò)中樞紐節(jié)點(diǎn)所處位置，改進(jìn)了Campbell四下標(biāo)容量限制下的多分配樞紐選址問(wèn)題優(yōu)化模型存在的局限性。通過(guò)算例分析發(fā)現(xiàn)：改進(jìn)模型能夠解決有容量限制下Campbell四下標(biāo)模型在容量限制以及成本折扣因子使用方面出現(xiàn)的不足，且改進(jìn)模型構(gòu)建的網(wǎng)絡(luò)方案更加符合樞紐建設(shè)的實(shí)際要求。在下一步研究中將以此模型為基礎(chǔ)，進(jìn)一步結(jié)合國(guó)內(nèi)補(bǔ)貼提供者參與的影響，研究樞紐航線網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)問(wèn)題，以期為國(guó)內(nèi)航空公司樞紐航線網(wǎng)絡(luò)設(shè)計(jì)提供科學(xué)決策依據(jù)。