航線網(wǎng)絡(luò)中樞紐城市選擇的多目標(biāo)優(yōu)化模型

樊 瑋，寧俊文

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

航線網(wǎng)絡(luò)規(guī)劃是航空公司運(yùn)行控制的基礎(chǔ)，對(duì)航空公司運(yùn)營(yíng)效率提升至關(guān)重要。城市對(duì)航線網(wǎng)絡(luò)和樞紐航線網(wǎng)絡(luò)是最常見的網(wǎng)絡(luò)結(jié)構(gòu)。從通達(dá)性和經(jīng)濟(jì)性兩方面考慮，樞紐航線網(wǎng)絡(luò)較城市航線對(duì)網(wǎng)絡(luò)會(huì)增加飛行頻率、通達(dá)性較差[1]，但往往與經(jīng)濟(jì)、社會(huì)發(fā)展的規(guī)模強(qiáng)相關(guān)，可從整體上降低航空公司運(yùn)營(yíng)成本，因此，樞紐航線網(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)造的因素（如機(jī)場(chǎng)運(yùn)營(yíng)效率、地理位置、機(jī)場(chǎng)服務(wù)水平等[7-8]），采用多屬性決策方法選取候選樞紐城市集，但缺少對(duì)教育資源、城市生產(chǎn)總值、衛(wèi)生狀況等屬性的考慮，而這些屬性往往對(duì)航線旅客人數(shù)具有重要影響。另一方面，現(xiàn)有模型基本以總運(yùn)輸成本最小[9-11]或匯運(yùn)和分運(yùn)成本最小[12-14]為優(yōu)化目標(biāo)，很少有將二者綜合考慮的模型。

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

1 城市候選集選取算法

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

1）計(jì)算加權(quán)正規(guī)化評(píng)估值

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

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

2）計(jì)算和諧集與非和諧集

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

3）計(jì)算和諧矩陣與非和諧矩陣

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

4）計(jì)算和諧超越矩陣與非和諧超越矩陣

式中

式中

5）計(jì)算合計(jì)超越矩陣

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

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

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

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

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

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

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

2.1 運(yùn)輸成本

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

圖1 3 種運(yùn)輸操作Fig.1 Three kinds of transportation operations

總運(yùn)輸成本定義為

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

匯運(yùn)和分運(yùn)成本之和定義為

2.2 樞紐城市選擇模型

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

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

約束條件如下

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

3 實(shí)例分析

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

表1 城市各屬性的原始評(píng)估值及加權(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)于成都，但地理位置、機(jī)場(chǎng)運(yùn)營(yíng)效率、機(jī)場(chǎng)服務(wù)水平劣于成都。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

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