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

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

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

摘要：

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

關(guān)鍵詞：

航線網(wǎng)絡(luò)；中樞輻射；絕對魯棒優(yōu)化；區(qū)間數(shù)；人工智能算法

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

航線網(wǎng)絡(luò)布局對公司的長期運營成本及市場競爭力具有重要的戰(zhàn)略意義[1].航空公司航線網(wǎng)絡(luò)可按結(jié)構(gòu)分為城市對航線網(wǎng)絡(luò)和樞紐航線網(wǎng)絡(luò).城市對航線網(wǎng)絡(luò)的不足之處是沒有從網(wǎng)絡(luò)總體層次上對網(wǎng)絡(luò)內(nèi)航線資源進行系統(tǒng)的有機配置.

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

由于現(xiàn)實問題的復(fù)雜性，需要對航線網(wǎng)絡(luò)區(qū)間型魯棒優(yōu)化設(shè)計問題進行更加深入的研究.當(dāng)航線網(wǎng)絡(luò)設(shè)計參數(shù)（OD對的流量和成本）為區(qū)間型數(shù)值時，本文在連續(xù)型情景集的基礎(chǔ)上，建立了一個新的無容量限制的多分配中樞輻射航線網(wǎng)絡(luò)魯棒優(yōu)化模型，用修正的最短路算法和模擬退火算法相結(jié)合進行求解，對樞紐航線網(wǎng)絡(luò)優(yōu)化設(shè)計進行研究，并對模型進行實例分析.

1

問題描述

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

2

模型建立

2.1

模型變量

2.2

數(shù)學(xué)模型

3

算法設(shè)計

4

算例分析

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

和單位流成本

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

4.1

CAB標準數(shù)據(jù)分析

（1）

對最優(yōu)解及最優(yōu)網(wǎng)絡(luò)路徑的分析

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

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

（2） 最優(yōu)樞紐解的比較

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

4.2

國內(nèi)數(shù)據(jù)分析

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

5

結(jié)束語

本文建立了基于區(qū)間數(shù)的中樞輻射航線網(wǎng)絡(luò)優(yōu)化模型，利用修正最短路算法和模擬退火算法相結(jié)合進行求解，并基于美國和中國航空網(wǎng)絡(luò)數(shù)據(jù)對模型進行了應(yīng)用，得出如下結(jié)論：

（1） 在確定型及離散型情形下設(shè)計的網(wǎng)絡(luò)，在復(fù)雜的現(xiàn)實環(huán)境中具有一定的局限性，得出的解有可能會偏離實際情況的最優(yōu)解較遠，而本文的區(qū)間型網(wǎng)絡(luò)模型基于連續(xù)型的情景集，考慮了眾多復(fù)雜情況，得出的解具有較好的全局最優(yōu)性.

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

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

參考文獻：

[1]朱金福. 航空運輸規(guī)劃[M]. 西安：西北工業(yè)大學(xué)出版社，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]柏明國，朱金福，姚韻. 樞紐航線網(wǎng)絡(luò)的構(gòu)建方法及應(yīng)用[J]. 系統(tǒng)工程，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]姜濤，朱金福，覃義. 基于最短路的中樞輻射航線網(wǎng)絡(luò)魯棒優(yōu)化方法[J]. 系統(tǒng)工程，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]柏明國，姜濤，朱金福. 基于禁忌算法的中樞輻射航線網(wǎng)絡(luò)魯棒優(yōu)化方法[J]. 數(shù)學(xué)的實踐與認識，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]吳小歡，朱金福，吳薇薇. 航線網(wǎng)絡(luò)區(qū)間型相對魯棒優(yōu)化設(shè)計[J]. 系統(tǒng)工程學(xué)報，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.