王 謙 車 通 李博文

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

引言

圍繞樞紐航線網(wǎng)絡(luò)設(shè)計(jì)問題，國(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樞紐中位問題的基本內(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ì)這一問題，提出在四下標(biāo)模型中增加相應(yīng)約束條件，將無容量限制問題轉(zhuǎn)換為有容量限制下的樞紐航線網(wǎng)絡(luò)設(shè)計(jì)問題，但卻并沒有分析容量限制對(duì)于航線網(wǎng)絡(luò)方案的影響。事實(shí)上，無容量限制下的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ì)決策中的不足之處；然后，通過增加限制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)說明和問題描述

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

需要說明的是，任一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ǎng)絡(luò)模型，并試圖通過增加約束

(1)

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

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

(1)非樞紐節(jié)點(diǎn)不允許直達(dá)，只允許通過樞紐節(jié)點(diǎn)轉(zhuǎn)運(yùn)，且轉(zhuǎn)運(yùn)次數(shù)不超過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)只能通過樞紐進(jìn)行；式(6)為容量限制，要求流經(jīng)樞紐k的流量小于其最大容量限制；

Campbell四下標(biāo)模型在解決有容量限制問題時(shí)，會(huì)出現(xià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í)際情況不相符。從折扣因子的選擇來看，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)模型是一致且合理的。而且通過約束(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形式也解決了折扣因子的正確選擇問題。

三、算例分析

為了驗(yàn)證上述模型的正確性，選取北京、成都、廣州、杭州、昆明、上海、武漢和西安八個(gè)城市(按照1-8進(jìn)行編號(hào))，并基于MATLAB軟件在Acer，Inter(R)，Core(TM)i5，CPU2.4Hz，8G內(nèi)存平臺(tái)上，通過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流通過樞紐北京、成都、杭州和武漢中轉(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)輸路徑是由于在流量分配過程中，武漢容量已經(jīng)飽和，不能再接收新的流量，部分O&D流跳變到此路徑規(guī)避通過武漢流量的增加。顯然這導(dǎo)致計(jì)算通過樞紐武漢的流量部分缺失，與實(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)輸路徑也存在此類問題，O&D流選擇杭州-北京-北京-北京路徑運(yùn)輸，類似的，此路徑會(huì)造成經(jīng)過杭州樞紐流量的計(jì)算缺失，折扣因子的使用同樣也存在同樣問題。

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

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

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

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

(2)對(duì)于整個(gè)航線網(wǎng)絡(luò)來說廣州武漢同為樞紐，所以即使廣州處于起始位置，廣州武漢之間的折扣因子應(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ǔ)

本文通過增加限制條件約束航線網(wǎng)絡(luò)中樞紐節(jié)點(diǎn)所處位置，改進(jìn)了Campbell四下標(biāo)容量限制下的多分配樞紐選址問題優(yōu)化模型存在的局限性。通過算例分析發(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ì)問題，以期為國(guó)內(nèi)航空公司樞紐航線網(wǎng)絡(luò)設(shè)計(jì)提供科學(xué)決策依據(jù)。