中樞輻射式航線網絡分階段航線決策研究

牟德一，王攀宇

(中國民航大學理學院，天津 300300)

航線網絡的發展經歷了線性航線(liner)，城市對航線網絡(city to city)和中樞輻射式航線網絡(hub to spoke).其中，中樞輻射式航線網絡是隨著航空運輸業不斷發展，競爭程度不斷加劇的情形下產生的.較大的航空公司為了在競爭中獲得有利的地位開始追求機隊和航線的規模經濟.這樣的發展逐步形成了樞紐機場.他們將周邊機場的旅客和貨物利用中小型飛機匯集到樞紐機場，再將這些旅客和貨物利用大型飛機運送至其他樞紐機場.這樣輻射機場與樞紐機場形成了供給與被供給的關系.為了更好的發揮這種關系，減少銜接和等待時間航空公司多采用“到離航班群”設置模式，從而形成了航班波.這樣就增加了高峰期樞紐機場的壓力，延誤的幾率大大增加.張軍、都業富［1］應用規模經濟性理論，分析航空公司在不同需求特征條件下中樞輻射式航線網絡的實用性，并說明了當航空運輸需求大于MES時，中樞輻射式航線網絡會出現報酬遞減的現象.姜濤、朱金福［2］通過對混合航線網絡的研究發現，適當的在非樞紐城市之間開辟直達航線能夠使是航空公司的利潤進一步增加.文獻［3］通過建立多目標的航線網絡優化模型來使總利潤最大化.

航線網絡設計是航空公司優化的核心問題.其優化的好壞關系到后續的諸多優化.趙桂紅［4］分析了不同的航線網絡對成本、服務要求和市場份額帶來的影響，從而得出中國民航的航線網絡應當將輪輻式航線模式和減輕樞紐城市壓力航線模式結合起來的結論.

對中樞輻射航線網絡優化設計的研究大體可分以下三步:

第1步，確定樞紐機場的位置與數量.

第2步，確定樞紐機場與非樞紐機場以何種方式連接.

第3步，對連接好的各條航線進行運力分配，以使整個航線網絡成本最低或收益最大.

針對第一步的研究已經很多［5－7］.鑒于我國已經基本形成了以北京、上海和廣州為樞紐機場的格局.因此本文針對第二步的內容進行研究.在選取了樞紐機場后，根據具體的需求和成本的相關數據把確定性的中樞輻射航線網絡設計問題轉化為最短路徑進行解決［8－9］.姜濤［10］等人針對需求和成本具有不確定性的航線網絡優化設計問題進行了研究，將開辟航線的費用考慮在內，建立了嚴格的無容量限制的多分配中樞輻射航線網絡魯棒優化模型.由于上述模型的求解都采用最短路徑算法.而該算法的時間復雜性并不好.我們要設計的非嚴格的中樞輻射式航線網絡通常涉及很多城市，再加上對于解的整數要求更加大了計算的時間.因此，本文在想構造一個嚴格的中樞輻射航線網絡的基礎上，針對影響航線選擇的諸多因素，采用多屬性決策法得出最適合開通的航線的排序.由決策者根據排序進行航線選擇.這樣既減輕了算法在時間復雜性的負擔又有設計出了能減輕樞紐機場壓力的非嚴格中樞輻射式航線網絡.

1 航線選擇的方法

1.1 構造嚴格的中樞輻射航線網絡

1)相關符號說明

N:某航空公司運營 n個城市的全體，其中︱N︱=n.

H:樞紐機場的全體，其中H?N，︱H︱=p.

Cij:經過航線(i，j)運送一個單位客流的成本，可以有 Cij≠Cji.

Wij:從城市i到城市j的客流量.

A:航線的集合，(i，j)∈A .

航線決策模型:

目標函數(1)是使總的運輸成本最小.約束條件(2)是流量守恒方程.約束條件(3)保證了只有航線(i，j)開通時才有流量通過.約束條件(4)保證了非樞紐機場之間不能連通.約束條件(5)保證樞紐機場完全連通.

2)算法設計

由于在求解優化問題上禁忌搜索算法得到了廣泛的認可，我們提出了一個關于航線選擇的禁忌搜索算法的設計思路.上述模型考慮是嚴格的中樞輻射航線網絡的設計問題，因此每一個非樞紐節點只能連接到一個樞紐節點上.對于旅客流量較大的節點更適合直接連接距離它較近的樞紐節點，這樣從該節點出發的運輸距離很可能會縮短;而對于旅客流量相對較小的節點，旅客目的地分布的隨機性較大，連接到最近的樞紐并不一定使總運輸距離最短.因此實際的具體思路如下:

第1步:確定初始狀態.把非樞紐節點先連接到最近的樞紐節點上，構成初始的航線網絡，并計算出此時總成本F0.

第2步:從具有最小旅客流量的非樞紐節點n1開始，每一個非樞紐節點有兩次在分配的機會.第1次是把該非樞紐節點非配給離它第二近距離的樞紐節點P'.第2次是分配給倒離客流量最大的節點較近的節點n'.如果n'就是離他第二近距離的樞紐，則不用進行第2次嘗試，如果n'是非樞紐節點并且與n1連接到不同的樞紐節點上，則連接到與n'相連接的樞紐節點.如果最后計算值比原方案要低，則保留新的分配方案，否則維持原方案.如果所有的非樞紐節點都已經遍歷，則計入第3步.

第3步:如果與某樞紐連接的非樞紐節點集合的最佳方案比原方案要好，則返回到第2步.否則停止搜索.

本文選取國內15個大中型城市作為某航空公司運營城市的全體.分別是北京，上海、廣州、沈陽、烏魯木齊、西安、長沙、成都、海口、杭州、昆明、南京、武漢、廈門、鄭州.根據我國實際情況，以北京、上海、廣州為樞紐機場，其他12個城市為非樞紐機場.根據文獻［11］中的相關數據.得出以嚴格的中樞輻射航線為框架的航線網絡.我們開通了北京－上海、北京－廣州、廣州－上海、北京－沈陽、北京－烏魯木齊、北京－西安、北京－鄭州、上海－南京、上海－武漢、上海－杭州、廣州－成都、廣州－廈門，廣州－長沙、廣州－海口、廣州－昆明.這樣我們用15條航線把15個城市連接起來.但這樣的航線網絡會產生很大的旅客延誤成本，同時，航班波的出現會給樞紐機場造成很大壓力.為了解決上述問題，綜合考慮了影響航線選擇的因素，采用多屬性決策法選擇出需要進一步開通的航線.

1.2 加性加權法構造航線

影響航空公司航線決策的因素有很多，秦漢軒，程希駿［12］根據航空公司長期經營的經驗，對影響航線決策的各種因素進行了分析.并確定了以下5個因素進行航線決策.分別是中長期市場需求量(yi1)、短期平均客座率(yi2)、競爭力(yi3)、成本票價比(yi4)、對航線網絡的影響(yi5).

根據文獻［13］所提供的方法確定各因素的權重.通過成對比較各因素的權重的重要性.用本征向量法，把各因素兩兩比較的結果聚合起來以確定各因素的權重.對上述5個因素進行專家評分，兩兩比較后得到矩陣A.

再由本證向量法我們可求得權向量wT=［0.22 0.39 0.25 0.09 0.05］.

把各條待決策航線按照上述的5個因素和收集的相關數據［11］構造一個n行5列 的決策矩陣Yn5.再與權向量wT相乘后得到相應各種航線的加權和的值，按所得值的大小進行排序，排序在前的優先開通.針對上述15個城市應用該方法進行了航線決策.對于已確定的開通的15條航線以“1”來表示.因此可得到各條航線上的加權和，見表1.

表1 15個城市間的航線權重數值

由表1可知，分值最高的航線為廣州－杭州，則該航線為最適宜開通的航線.相反，烏市(烏魯木齊)－廈門航線得分最低，為最不適宜開通的航線.決策者可以根據航空公司剩余的運力情況選擇所要開通的航線.如果運力充足可以先找到盈虧平衡的航線則分值排在該航線以前的航線以前的航線都可以開通.本文選取了前25條航線，構造成了可以有效減輕樞紐機場壓力的非樞紐航線網絡，顯然成都－昆明、海口－鄭州航線的開通可以有效減輕廣州機場的壓力.而西安－杭州的航線的開通則可減輕上海機場的壓力.與此同時，該方法可操作性強，便于航空公司運用.

2 結語

中樞輻射式航線網絡的航線決策一直是航空公司關注的熱點問題.對于我國而言，設計出既符合我國實際國情、布局合理、可操作的航線決策方法尤為重要.本文把傳統的運籌學模型決策方法與多屬性決策方法相結合.根據我國實際情況及數據，以北京，上海，廣州為樞紐，設計出了實用有效的、可操作性強的航線網絡構造方法，可為我國快速發展的航空公司航線網絡規劃提供參考.

［1］張 軍，都富業.發展中樞輻射航線網絡戰略思考［J］.中國民航學院學報，2004(6):183－186.

［2］姜 濤，朱金福.航空公司航線網絡的效益分析研究［J］.工業技術經濟，2006，11(25):105－107.

［3］WEN Y H，HSU C I.Interactive multiobjective programming in airline network design for international airline code－share alliance［J］.European Journal of Operational，2006(174):404－426.

［4］李桂進.我國民航的航線網絡規劃［J］.中國民用航空，2001(4):47－49.

［5］ALFERDO M，LAZARO C，MERCEDES L.New formulations for the uncapacitated multiple allodation hub location problem［J］.European Journal of Operational Research，2006(7):274－292.

［6］EISELT H A，VLADIMIR M.A conditional p－hub location problem with attraction functions［J］.computers ＆ Operations Research，2009，(36):3128－3135.

［7］SIBEL A，BAHAR Y K.Network hub location problems:the state of the art［J］.European Journal of Operational Research，2008(190):1－21.

［8］ERNST A T，AN K M.An exact solution approach based on shortest－paths for p－hub median problem［J］.Informs Journal on Computing，1998，10(2):149－161.

［9］SPHN J，PARK S.Efficient solution procedure and reduced size formulations for p－hub location problems［J］.European Journal of Operational Research，1998，108:118－126.

［10］姜 濤，朱金福，覃 義.中樞輻射航線網絡的魯棒優化方法研究［J］.小型微型計算機系統，2008，29(7):1366－1371.

［11］中國民用航空總局規劃科技司.從統計看民航［M］.北京:中國民航出版社，2008.

［12］秦漢軒，程希駿.航空公司航線決策的一種系統方法［J］.運籌與管理，2000，9(3):56－63.

［13］DUCKSTEIN L，GERSHON M.Multicriterion analysis of avegetation management problem using ELECTER－Ⅱ［J］.Applied Mathematical Modelling，1983(7):254.