航線網絡區間魯棒優化設計

基金項目： 國家自然科學基金資助項目（70771046，71171111，71201081）；江蘇省普通高校研究生科研創新計劃資助項目（CXZll_0220）

作者簡介： 吳小歡（1980-），男，博士研究生，研究方向為交通運輸規劃與管理，E-mail：wuxiaohuan2003@163.com

文章編號： 0258-2724（2013）03-0559-06DOI： 10.3969/j.issn.0258-2724.2013.03.026

摘要：

為解決航空公司航線網絡中樞紐機場具體位置及OD流路徑設計問題， 根據航線網絡設計參數OD 流量和單位流成本的不確定性， 定義了區間型情景集， 建立了區間型絕對魯棒優化模型， 設計了將修正最短路算法與人工智能算法相結合進行求解的有效算法，并利用航線網絡設計經典數據及中國航空網絡OD數據對模型進行了驗證. 研究結果表明：該模型的最優魯棒解具有全局最優性，確定型優化模型為本文模型在悲觀準則下，當OD 流量和單位流成本確定時的特例；在不同情景的悲觀準則和樂觀準則下的模型目標值之間的相關系數達到0.99以上；在悲觀準則下，用本文模型計算出標準算例的歸一化后的最優目標值為784.47，比確定型模型最優目標值減少了16.65%，比相對魯棒優化模型最優目標值減少了29.07%.

關鍵詞：

航線網絡；中樞輻射；絕對魯棒優化；區間數；人工智能算法

中圖分類號： V352文獻標志碼： A

航線網絡布局對公司的長期運營成本及市場競爭力具有重要的戰略意義[1].航空公司航線網絡可按結構分為城市對航線網絡和樞紐航線網絡.城市對航線網絡的不足之處是沒有從網絡總體層次上對網絡內航線資源進行系統的有機配置.

樞紐航線網絡優化設計理論主要是依據航空公司一些已知設計參數（OD對流量、單位流成本及邊或節點的容量），進行樞紐及OD對流量分配或路徑的一體化優化設計.網絡優化設計一般可分為確定型、隨機型和魯棒優化型.對于確定型網絡設計模型[2-10]和隨機型網絡設計模型[11-13]，都需要對網絡設計參數值或分布做出準確預測，才能使設計的網絡符合未來實際需要.實際中很難事先準確獲知這些參數值或概率分布，因此，航線網絡多采用魯棒優化理論進行設計[14-18].在魯棒優化設計理論中，稱網絡設計參數的組合為情景，所有可能參數組合的集合稱為情景集.若情景集中元素可數，稱該情景集為離散型情景集；若情景集中元素不可數，稱該情景集為連續型情景集.文獻[14-18]都是在離散的情景集范圍內進行討論.由于現實的復雜性及不確定性，不能確定實際發生的情景一定會在該有限情景集內，而依據這些情景所建立的魯棒優化模型并不能保證其魯棒解具有很好的魯棒性.為此有學者建立了區間型魯棒優化模型.文獻[19-22]對區間型魯棒優化問題進行了探討，文獻[19]對航線網絡區間型相對魯棒優化問題進行了研究，給出了相應的魯棒優化模型和求解策略，文獻[20-22]表明這些不確定性問題是NP難題，由于其目標函數分別為多個元素權重之和、最小生成樹和最短路邊的權重之和的形式，無法直接運用于航空公司網絡設計.

由于現實問題的復雜性，需要對航線網絡區間型魯棒優化設計問題進行更加深入的研究.當航線網絡設計參數（OD對的流量和成本）為區間型數值時，本文在連續型情景集的基礎上，建立了一個新的無容量限制的多分配中樞輻射航線網絡魯棒優化模型，用修正的最短路算法和模擬退火算法相結合進行求解，對樞紐航線網絡優化設計進行研究，并對模型進行實例分析.

1

問題描述

對于絕對魯棒優化設計準則，易知其優化設計實際上為保守（悲觀）性的優化設計，在實際應用中，也可將絕對魯棒優化擴展為樂觀性的優化設計.由于絕對魯棒優化設計方法簡單易行，本文將對所提出的網絡優化問題采用絕對魯棒優化設計方法.

2

模型建立

2.1

模型變量

2.2

數學模型

3

算法設計

4

算例分析

文獻[3]給出了美國25個機場流量

和單位流成本

的經典CAB（civil aeronautics board）數據.文獻[10]給出中國15個機場的流量和單位流成本數據，這些數據被廣泛應用于樞紐選址問題的研究，用于測試算法效率及有效性.將CAB數據（前15個機場的）和文獻[10]中數據視為初始數據，假定在未來一定時期內，客流量W及單位流成本C在區間[W（1-10%），W（1+60%）]和[C（1-10%）， C（1+5%）]范圍之內變動，從這15個機場中選若干個機場作為樞紐機場，利用Matlab軟件在DELL，Intel（R），Pentium（R）4，CPU2.66 GHz， 512 MB內存的平臺上求解.

4.1

CAB標準數據分析

（1）

對最優解及最優網絡路徑的分析

在兩種準則下求得所有可能樞紐組合（共455種）對應的模型目標值之間的相關系數為0.996 2，是高度線性相關的，表明樞紐選擇對最優成本有很大關系，如果樞紐選址準確，將使實際問題在悲觀和樂觀準則下總成本都較小.在悲觀準則下， 15個機場之間的連接示意圖如圖1所示.

在圖1中，機場4，7，12為樞紐機場， e（4，7）、e（4，12）和e（7，12）為樞紐邊.由圖1可以看出， 3個樞紐機場的位置分布比較合理，輻射面較大.與樞紐機場4連接的城市最多，樞紐機場7次之，樞紐機場12最少.由CAB數據中各機場的旅客轉運量來看，機場4的轉運量最多；機場12的旅客轉運量排第二，機場12位置雖然比較偏遠，但其轉運量很大，這是機場12選為樞紐機場的主要原因；機場7旅客轉運量排第六，但網絡運輸總成本最小.

（2） 最優樞紐解的比較

在確定型情形下，即將本文模型的成本及流量設為原來的值，對流量矩陣W進行歸一化處理，由本文的悲觀求解準則，選取總成本最小的樞紐組合，這里只對節點數n=15的結果進行分析，具體結果與文獻[19]中的表5相同.對比文獻[5，8]中的結果可知，求得的最優目標函數值和最優樞紐完全一致，這說明文獻[5，8]中的結論是本文在成本及流量取確定值時的一種特殊情形.

4.2

國內數據分析

由表1可見，當樞紐個數和折扣系數不同時，所有可能樞紐組合在兩種不同求解策略下對應的模型目標值之間均是高度線性相關的.由表1第5列可以看出，在兩種求解準則下，不同情形的魯棒解略有不同，結合實際情況綜合考慮，很容易從這兩個魯棒解中選取一個更符合實際的解.

5

結束語

本文建立了基于區間數的中樞輻射航線網絡優化模型，利用修正最短路算法和模擬退火算法相結合進行求解，并基于美國和中國航空網絡數據對模型進行了應用，得出如下結論：

（1） 在確定型及離散型情形下設計的網絡，在復雜的現實環境中具有一定的局限性，得出的解有可能會偏離實際情況的最優解較遠，而本文的區間型網絡模型基于連續型的情景集，考慮了眾多復雜情況，得出的解具有較好的全局最優性.

（2） 樞紐的選取對網絡設計成本具有重要影響，樞紐節點選取得合理，無論是在悲觀最優目標值還是樂觀最優目標值下，其魯棒解均可使總成本較低.下一步工作將深入研究不確定情形下有容量限制的中樞輻射航線網絡設計及網絡評價問題.

致謝：本文工作得到南京航空航天大學青年科技創新基金項目（56Y1082）的資助.

參考文獻：

[1]朱金福. 航空運輸規劃[M]. 西安：西北工業大學出版社，2009： 322-364.

[2]SIBEL A， BAHAR Y K. Network hub location problems： the state of the art[J]. European Journal of Operational Research， 2008， 190（1）： 1-21.

[3]OKELLY M E. A quadratic integer program for the location of interacting hub facilities[J]. European Journal of Operational Research， 1987， 32（3）： 393-404.

[4]SKORIN-KAPOV D， SKORIN-KAPOV J. On tabu search for the location of interacting hub facilities[J]. European Journal of Operational Research， 1994， 73（2）： 502-509.

[5]SKORIN-KAPOV D， SKORIN-KAPOV J， OKELLY M. Tight linear programming relaxations of uncapacitated p-hub median problems[J]. European Journal of Operational Research， 1996， 94（3）： 582-593.

[6]AYKIN T. The hub location and routing problem[J]. European Journal of Operational Research， 1995， 83（1）： 200-219.

[7]CHEN Jengfung. A hybrid heuristic for the uncapacitated single allocation hub location problem[J]. Omega， 2007， 35（2）： 211- 220.

[8]ERNST A T， KRISHNAMOORTHY M. Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem[J]. European Journal of Operational Research， 1998， 104（1）： 100-112.

[9]EBERY J， KRISHNAMOORTHY M， ERNST A， et al. The capacitated multiple allocation hub location problem： Formulations and algorithms[J]. European Journal of Operational Research， 2000， 120（3）： 614-631.

[10]柏明國，朱金福，姚韻. 樞紐航線網絡的構建方法及應用[J]. 系統工程，2006，24（5）： 29-34.

BAI Mingguo， ZHU Jinfu， YAO Yun. Design and application of hub and spoke network[J]. Systems Engineering， 2006， 24（5）： 29-34.

[11]SIM T L， TIMOTHY J T， BARRETT W. The stochastic-hub center problem with service-level constraints[J]. Computers and Operations Research， 2009， 36（12）： 3166-3177.

[12]CONTRERAS I， CORDEAU J F，LAPORTE G. Stochastic uncapacitated hub location[J]. European Journal of Operational Research， 2011， 212（3）： 518-528.

[13]YANG Tahui. Stochastic air freight hub location and flight routes planning[J]. Applied Mathematical Modelling， 2009， 33（12）： 4424-4430.

[14]KOUVELIS P， YU G. Robust discrete optimization and its applications[M]. Boston： Kluwer Academic Publishers， 1997： 26-73.

[15]GUTIERREZ G J， KOUVELIS P， KURAWARWALA A A. A robustness approach to uncapacitated network design problems[J]. European Journal of Operational Research， 1996， 94（2）： 362-376.

[16]姜濤，朱金福，覃義. 基于最短路的中樞輻射航線網絡魯棒優化方法[J]. 系統工程，2007，25（1）： 53-59.

JIANG Tao， ZHU Jinfu， QIN Yi. Robust optimization of hub-and-spoke airline network design based on shortest path algorithm[J]. Systems Engineering， 2007， 25（1）： 53-59.

[17]柏明國，姜濤，朱金福. 基于禁忌算法的中樞輻射航線網絡魯棒優化方法[J]. 數學的實踐與認識，2008，38（13）： 60-69.

BAI Mingguo， JIANG Tao， ZHU Jinfu. The robust optimization of the hub-and-spoke airline network design based on tabu search[J]. Mathematics in Practice and Theory， 2008， 38（13）： 60-69.

[18]ALUMUR S A， NICKEL S， SALDANHA-DA-GAMA F. Hub location under certainty[J]. Transportation Research Part B：Methodological， 2012， 46（4）： 529-543.

[19]吳小歡，朱金福，吳薇薇. 航線網絡區間型相對魯棒優化設計[J]. 系統工程學報，2012，27（1）： 69-78.

WU Xiaohuan， ZHU Jinfu， WU Weiwei. Relative interval robust optimization of airline network designing[J]. Journal of Systems Engineering， 2012， 27（1）： 69-78.

[20]AVERBAKH I. On the complexity of a class of combinatorial optimization problems with uncertainty[J]. Mathematical Programming， 2001， 90（2）： 263-272.

[21]AVERBAKH I， LEBEDEVB V. Interval data minmax regret network optimization problems[J]. Discrete Applied Mathematics， 2004， 138（3）： 289-301.

[22]PEREIRA J， AVERBAKH I. Exact and heuristic algorithms for the interval data robust assignment problem[J]. Computers Operations Research， 2011， 38（8）： 1153-1163.