樊 瑋，寧俊文

（中國民航大學(xué)計算機科學(xué)與技術(shù)學(xué)院，天津 300300）

航線網(wǎng)絡(luò)規(guī)劃是航空公司運行控制的基礎(chǔ)，對航空公司運營效率提升至關(guān)重要。城市對航線網(wǎng)絡(luò)和樞紐航線網(wǎng)絡(luò)是最常見的網(wǎng)絡(luò)結(jié)構(gòu)。從通達(dá)性和經(jīng)濟性兩方面考慮，樞紐航線網(wǎng)絡(luò)較城市航線對網(wǎng)絡(luò)會增加飛行頻率、通達(dá)性較差[1]，但往往與經(jīng)濟、社會發(fā)展的規(guī)模強相關(guān)，可從整體上降低航空公司運營成本，因此，樞紐航線網(wǎng)絡(luò)依然是中等以上規(guī)模航空公司的首選[2-3]。

樞紐網(wǎng)絡(luò)結(jié)構(gòu)分為p樞紐中值、無容量樞紐定位、p樞紐中位和樞紐覆蓋4 種基本形式[4]，基本思路都是基于航線網(wǎng)絡(luò)可達(dá)城市集合，利用數(shù)學(xué)規(guī)劃法選擇有利于設(shè)定目標(biāo)的樞紐城市集合[5-6]。常見的樞紐航線網(wǎng)絡(luò)規(guī)劃大都直接選取樞紐城市，也有少數(shù)研究根據(jù)城市屬性（描述城市的性質(zhì)與關(guān)系）、影響航線網(wǎng)絡(luò)構(gòu)造的因素（如機場運營效率、地理位置、機場服務(wù)水平等[7-8]），采用多屬性決策方法選取候選樞紐城市集，但缺少對教育資源、城市生產(chǎn)總值、衛(wèi)生狀況等屬性的考慮，而這些屬性往往對航線旅客人數(shù)具有重要影響。另一方面，現(xiàn)有模型基本以總運輸成本最小[9-11]或匯運和分運成本最小[12-14]為優(yōu)化目標(biāo)，很少有將二者綜合考慮的模型。

在綜合考慮機場運營效率、地理位置、機場服務(wù)水平的基礎(chǔ)上，增加基于教育資源、城市生產(chǎn)總值、衛(wèi)生狀況得到的城市綜合分值屬性，在無容量限制的多分配p樞紐定位模型（Up）[13]基礎(chǔ)上，建立以總運輸成本、匯運和分運成本最小化為目標(biāo)的多目標(biāo)規(guī)劃模型（UMp）。為了降低航線網(wǎng)絡(luò)可達(dá)城市較多情況下模型求解的時間復(fù)雜度，實現(xiàn)航空運輸利益最大化，首先，采用一種改進的淘汰選擇算法[15]選取候選樞紐城市集，再用Cplex 軟件對多目標(biāo)優(yōu)化模型進行分步求解。

1 城市候選集選取算法

相對于可達(dá)城市全集，采用候選樞紐城市集能較大幅度降低算法的時間復(fù)雜度?；贓LECTRE 算法構(gòu)造一系列弱支配關(guān)系淘汰較劣方案，從而逐步縮小方案集直到選出滿意的方案。首先，基于ELECTRE 算法進行候選城市篩選，算法計算步驟如下。

1）計算加權(quán)正規(guī)化評估值

定義可達(dá)城市集合M= {1，2，…，p}，每個城市的屬性集合N={1，2，…，q}。在M和N上構(gòu)造原始評估矩陣A=（aij）p×q，元素aij為城市i的屬性j的原始評估值，然后對所有元素aij進行正規(guī)化處理，即

定義權(quán)重集合W={w1，w2，…，wq}，其中wj為屬性j的權(quán)重，再進行加權(quán)正規(guī)化處理，即

2）計算和諧集與非和諧集

根據(jù)可達(dá)城市集合中的每個城市對（k，l），將其屬性集N劃分為兩個不相交的子集Okl和Ukl，其中：Okl為和諧集，由城市k不劣于城市l(wèi)的屬性組成；Ukl為非和諧集，由城市k劣于城市l(wèi)的屬性組成。兩個不相交子集表示如下

3）計算和諧矩陣與非和諧矩陣

和諧矩陣C=（ckl）p×p體現(xiàn)了兩城市間的相對重要性，ckl值越高，表明城市k優(yōu)于城市l(wèi)的程度越大。非和諧矩陣D=（dkl）p×p反映了城市k劣于城市l(wèi)的程度，dkl值越高，表明城市k劣于城市l(wèi)的程度越大。C 和D的元素表示如下

4）計算和諧超越矩陣與非和諧超越矩陣

式中

式中

5）計算合計超越矩陣

合計超越矩陣E=（ekl）p×p是和諧與非和諧超越矩陣的交集，即ekl=fkl gkl，表示了城市選擇的優(yōu)先順序，若ekl=1，則表示城市k在一致與非一致準(zhǔn)則上均優(yōu)于城市l(wèi)。

最后，根據(jù)合計超越矩陣選擇候選樞紐城市集L。

2 航線網(wǎng)絡(luò)模型

從候選樞紐城市集中選出p個作為樞紐城市，模型中變量定義如下：

1）i，j代表城市節(jié)點；k，m代表候選城市節(jié)點；

2）vij為城市i到城市j的運輸成本；qij為城市i到城市j的旅客需求量；dij為城市i到城市j的距離；

3）變量Xijkm為0-1 決策變量，當(dāng)OD 流（i，j）經(jīng)過樞紐城市k，m中轉(zhuǎn)時為1，否則為0，其中，k和m可以相同；Hk是0-1 決策變量，當(dāng)城市k是樞紐城市時為1，否則為0。

2.1 運輸成本

樞紐航線網(wǎng)絡(luò)的運輸成本由匯運、轉(zhuǎn)運、分運3 種成本組成，如圖1所示。

圖1 3 種運輸操作Fig.1 Three kinds of transportation operations

總運輸成本定義為

式中x、a、b分別為匯運、轉(zhuǎn)運、分運的折扣因子。一般情況下a ＜x，且x、a、b都小于1，a≠0，取x= 0.6，a=0.5，b=0.5。

匯運和分運成本之和定義為

2.2 樞紐城市選擇模型

航線網(wǎng)絡(luò)設(shè)計的首要目標(biāo)是使航線成本最小化，但總運輸成本與匯運和分運成本之間并非呈線性關(guān)系，因此，建立的UMp 模型采用多目標(biāo)分層求解方式。

根據(jù)航空運輸成本優(yōu)先級關(guān)系，首先對總運輸成本最小進行求解（式（13）），然后在此基礎(chǔ)上求得匯運和分運成本最小的二次解（式（14）），最后綜合總成本及匯運和分運成本再次求得最優(yōu)解（式（15））。模型表示如下

約束條件如下

約束條件中：式（16）確保樞紐城市的個數(shù)為p；式（17）確保所有OD（origin destination）流的運量必須由起始城市運到目的城市；式（18）和式（19）保證了所有的OD 流只能通過樞紐城市進行中轉(zhuǎn)運輸。

3 實例分析

依據(jù)中國城市排行榜[16]獲得國內(nèi)20 個重要城市的地理位置和綜合分值，依據(jù)中國民航資源網(wǎng)[17]獲得對應(yīng)機場的運營效率和服務(wù)水平，得到各屬性的原始評估值；給定地理位置、綜合分值、機場運營效率、機場服務(wù)水平構(gòu)成的屬性集N={1，2，3，4}所對應(yīng)的權(quán)重集W={0.20，0.30，0.35，0.15}，計算得到各城市的加權(quán)正則化屬性值。如表1所示。

表1 城市各屬性的原始評估值及加權(quán)正則化屬性值Tab.1 Original value and weighted value of each attribute of city

根據(jù)加權(quán)正則化屬性集構(gòu)建和諧集與非和諧集，如表2 和表3所示（限于篇幅，僅列出部分城市）。從表2 和表3 中可得到O13={2}，U13={1，3，4}，表示北京的綜合分值優(yōu)于成都，但地理位置、機場運營效率、機場服務(wù)水平劣于成都。

表2 城市和諧集Tab.2 Harmony set of city

表3 城市非和諧集Tab.3 Inharmony set of city

據(jù)以上計算結(jié)果建立和諧矩陣與非和諧矩陣如下

如c13=0.30，d13=0.36，表示北京優(yōu)于成都的程度較小，劣于成都的程度較大。

根據(jù)式（8）和式（10）求得門檻值和之后，求解和諧超越矩陣與非和諧超越矩陣，即

根據(jù)F 和G 構(gòu)造城市合計超越矩陣E，如表4所示。

表4 城市合計超越矩陣Tab.4 Total exceeding matrix of city

為了更加直觀表示城市的優(yōu)劣，將表4 用偏序圖（從左到右）表示，如圖2所示?？蛇x重慶、成都、北京、上海、廣州、杭州、西安、深圳、沈陽、廈門等城市作為候選樞紐城市集L。

圖2 城市優(yōu)劣偏序圖Fig.2 Pros and cons partial order map of city

采用15 個城市和20 個城市的場景進行模型驗證，場景1 含有15 個城市（序號1、2、3、6、7、8、9、10、12、14、16、17、18、19、20），場景2 包含所有20 個城市，對場景1 經(jīng)由表4 篩選排名前7 的候選樞紐城市，對場景2 經(jīng)由表4 篩選排名前10 的候選樞紐城市。

依據(jù)varflight[18]網(wǎng)站提供的2019年1月—10月的航線網(wǎng)絡(luò)數(shù)據(jù)，取α=1/4，β=3/4 來計算UMp 模型的總成本。指定樞紐城市數(shù)p=2～5，進行UMp 模型求解并與Up 模型進行對比。表5 為根據(jù)場景1 計算得到的結(jié)果，表6 為根據(jù)場景2 計算得到的結(jié)果。

表5 場景1 中的計算結(jié)果Tab.5 Calculation results under scenario 1

表6 場景2 中的計算結(jié)果Tab.6 Calculation results under scenario 2

圖3 和圖4 分別為p=5 時場景1 和場景2 下UMp模型和Up 模型的航線網(wǎng)絡(luò)圖（紅色點為樞紐點），表7為UMp 優(yōu)先級穩(wěn)定性的測試結(jié)果（優(yōu)先級Z1＞Z2＞Z3）。

圖4 場景2 下的航線網(wǎng)絡(luò)圖Fig.4 Route network connection diagram under scenario 2

圖3 場景1 下的航線網(wǎng)絡(luò)圖Fig.3 Route network connection diagram under scenario 1

表7 UMp 優(yōu)先級穩(wěn)定性的測試結(jié)果Tab.7 Test results of UMp priority level stability 次

綜上，對結(jié)果進行分析如下。

1）以二次優(yōu)化后的最終總運輸成本Z3進行比較：在場景1 下，p=2 時，UMp 劣于Up；p＞2 時，UMp 明顯優(yōu)于Up；在場景2 下，p=2，3 時，UMp 劣于Up，p＞3 時，UMp 明顯優(yōu)于Up。由此可見，UMp 模型適合用于城市規(guī)模較大、樞紐城市相對較多的情況，這也符合航空公司實際航線網(wǎng)絡(luò)規(guī)劃的情況。

2）在場景1 中，當(dāng)p=4，5 時，UMp 和Up 所選樞紐城市一致，但UMp 的成本遠(yuǎn)低于Up。原因在于UMp 和Up 會給出不同的航線網(wǎng)絡(luò)設(shè)計，圖3 給出了p=5 時UMp 和Up 兩種算法所得到的航線網(wǎng)絡(luò)圖?？梢?，在相同計算條件下，即使樞紐城市選擇相同，UMp能給出更優(yōu)的航線網(wǎng)絡(luò)設(shè)計。

3）在場景2 中，UMp 和Up 所選的樞紐城市不一致，圖4 給出了p=5 時的航線網(wǎng)絡(luò)圖，可看出樞紐城市的選取影響航線網(wǎng)絡(luò)成本，UMp 模型能在相同規(guī)模下選取較優(yōu)的樞紐城市，從而得到較優(yōu)的結(jié)果。

4）為了檢驗UMp 結(jié)果的穩(wěn)定性，進行了迭代次數(shù)檢測。最多迭代次數(shù)為12 次，最少迭代次數(shù)為6 次，最終結(jié)果達(dá)到穩(wěn)定，說明UMp 是穩(wěn)定且可行的。

4 結(jié)語

針對航線網(wǎng)絡(luò)樞紐城市選擇的問題，提出了無容量限制的多分配p樞紐定位的多目標(biāo)優(yōu)化模型。該模型在綜合考量可達(dá)城市的地理位置、綜合分值、機場運營效率、機場服務(wù)水平4 個屬性的基礎(chǔ)上，采用ELECTRE算法選擇了候選樞紐城市集，然后以總運輸成本、匯運和分運成本、二次優(yōu)化總運輸成本最小為目標(biāo)建立了樞紐城市選擇多目標(biāo)優(yōu)化模型，最后，基于目標(biāo)優(yōu)先級迭代對模型求解，得到穩(wěn)定的優(yōu)化結(jié)果。

UMp 模型與傳統(tǒng)Up 模型相比，適用于候選城市多且擬選擇樞紐較多的情況，能在合理選擇樞紐城市的基礎(chǔ)上，設(shè)計優(yōu)化的航線網(wǎng)絡(luò)結(jié)構(gòu)，有效降低航線網(wǎng)絡(luò)的總運輸成本，但未考慮樞紐城市的構(gòu)建成本及航線的延誤成本等因素，這可作為進一步的研究方向。