考慮延遲懲罰的軸輻式樞紐網(wǎng)絡(luò)中斷問(wèn)題研究

楊 珺，邵路路，劉舒佶

（1.華中科技大學(xué) 管理學(xué)院，武漢430074；2.威斯康星麥迪遜分校 工業(yè)與系統(tǒng)工程系，威斯康星，麥迪遜53706）

考慮延遲懲罰的軸輻式樞紐網(wǎng)絡(luò)中斷問(wèn)題研究

楊 珺＊1，邵路路1，劉舒佶2

（1.華中科技大學(xué) 管理學(xué)院，武漢430074；2.威斯康星麥迪遜分校 工業(yè)與系統(tǒng)工程系，威斯康星，麥迪遜53706）

隨著越來(lái)越多的航空公司采用軸輻式網(wǎng)絡(luò)系統(tǒng)模式開(kāi)展全球航空運(yùn)輸服務(wù)，軸輻式網(wǎng)絡(luò)研究逐漸引起大家的重視.本文針對(duì)樞紐中位選址問(wèn)題，首先提出了考慮延遲懲罰并面向整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)完全性中斷問(wèn)題，建立節(jié)點(diǎn)中斷的上、下界模型，對(duì)禁忌搜索算法進(jìn)行改進(jìn)，并對(duì)三種改進(jìn)算法展開(kāi)比較；然后將兩種中斷模型和禁忌搜索算法應(yīng)用于中國(guó)航空網(wǎng)絡(luò)實(shí)例中，通過(guò)計(jì)算結(jié)果分析中國(guó)航空網(wǎng)絡(luò)中的關(guān)鍵城市，在資源有限的情況下，提出城市分級(jí)防御的規(guī)劃和航空網(wǎng)絡(luò)考慮中斷情況下的資金準(zhǔn)備的建議.為軸輻式樞紐網(wǎng)絡(luò)決策者在網(wǎng)絡(luò)規(guī)劃和防御問(wèn)題上提供了理論參考和實(shí)踐證明.

系統(tǒng)工程；航空運(yùn)輸；中斷模型；啟發(fā)式算法；樞紐；網(wǎng)絡(luò)

1 引言

軸輻式網(wǎng)絡(luò)系統(tǒng)起源于航空運(yùn)輸領(lǐng)域，后憑借其規(guī)模經(jīng)濟(jì)的優(yōu)勢(shì)，被廣泛應(yīng)用于軍事[1]、航空[2]及旅游等領(lǐng)域.這種結(jié)構(gòu)不僅減少了網(wǎng)絡(luò)的構(gòu)建成本[3]，更能通過(guò)物流、信息流的集中進(jìn)一步降低運(yùn)輸成本.然而，在恐怖策劃和襲擊等人為的攻擊和自然災(zāi)害等因素影響下，軸輻式網(wǎng)絡(luò)系統(tǒng)往往顯得十分脆弱，網(wǎng)絡(luò)的中斷會(huì)給企業(yè)帶來(lái)巨大的經(jīng)濟(jì)損失.紐約著名的911恐怖襲擊事件摧毀了大片通話線路、商務(wù)線路、數(shù)據(jù)電路[4]，給許多企業(yè)帶來(lái)無(wú)法彌補(bǔ)的損失.

由于戰(zhàn)爭(zhēng)中供應(yīng)線的中斷會(huì)造成嚴(yán)重?fù)p失，中斷問(wèn)題開(kāi)始受到了廣泛關(guān)注（McMasters and Mustin1970）[5].Smith和Lim主要研究了關(guān)于不同中斷情形發(fā)生后如何進(jìn)行網(wǎng)絡(luò)防御與設(shè)計(jì)問(wèn)題[6].以往的研究主要集中在網(wǎng)絡(luò)弧的中斷而非節(jié)點(diǎn)的中斷，然而關(guān)鍵節(jié)點(diǎn)的服務(wù)設(shè)施的中斷會(huì)帶來(lái)嚴(yán)重后果，因此必須找到并保護(hù)容易發(fā)生中斷并且可能帶來(lái)重大損失的設(shè)施.Church和Scaparra提出了關(guān)鍵基礎(chǔ)設(shè)施防護(hù)的雙層模型[7].楊珺等研究了基于P-中位模型的網(wǎng)絡(luò)關(guān)鍵設(shè)施識(shí)別問(wèn)題的算法設(shè)計(jì)與實(shí)現(xiàn)[8]；還研究了最壞中斷損失下的網(wǎng)絡(luò)設(shè)施選址問(wèn)題[9].翁克瑞研究了軸輻式物流網(wǎng)絡(luò)設(shè)計(jì)的選址與路線優(yōu)化問(wèn)題[10]，分析了成本—路線優(yōu)化的軸輻式物流網(wǎng)絡(luò)設(shè)計(jì)等問(wèn)題[11].Murray和Matisziw建立了流量中斷模型（FIM）[12]，研究在網(wǎng)絡(luò)設(shè)施中斷情況下的整數(shù)規(guī)劃模型.Snyder和Daskin提出了加入設(shè)施停止運(yùn)行后的可靠性設(shè)施選址模型[13].以上文獻(xiàn)都沒(méi)有分析輻射式網(wǎng)絡(luò)的設(shè)施中斷給網(wǎng)絡(luò)帶來(lái)的影響.本文從HUB的網(wǎng)絡(luò)結(jié)構(gòu)出發(fā)，研究考慮延遲懲罰因素的節(jié)點(diǎn)完全中斷問(wèn)題.

2 問(wèn)題描述與建模

由于節(jié)點(diǎn)徹底性中斷具有一定的隨機(jī)性，故應(yīng)分析中斷后的損失區(qū)間，以此來(lái)預(yù)計(jì)至少需要多少儲(chǔ)備資金應(yīng)對(duì)中斷導(dǎo)致的成本增長(zhǎng).

2.1 r中斷節(jié)點(diǎn)的成本上界問(wèn)題

我們首先研究r個(gè)節(jié)點(diǎn)中斷導(dǎo)致運(yùn)營(yíng)成本最大的情況，對(duì)最壞情況下的RIN上界問(wèn)題（r-interdiction node upper bound problem，RIN-UB）進(jìn)行建模.集合與參數(shù)如下：

N——n個(gè)節(jié)點(diǎn)集合；

F——現(xiàn)有p個(gè)樞紐集合；

r——中斷樞紐數(shù)；

wij——起點(diǎn)i與終點(diǎn) j間的需求量或流量；

χ、α和δ——分別是匯集、轉(zhuǎn)移和分散過(guò)程的成本；

mij——中斷節(jié)點(diǎn)恢復(fù)后由于中斷導(dǎo)致延遲的懲罰單位運(yùn)輸成本，mij=；

β——懲罰系數(shù)，β=2；

r個(gè)中斷節(jié)點(diǎn)的成本上界問(wèn)題（RIN-UB）表示如下：

Subject to:

目標(biāo)函數(shù)（1）最大化中斷了r個(gè)節(jié)點(diǎn)后的剩余節(jié)點(diǎn)重新分配與中斷節(jié)點(diǎn)恢復(fù)后重新流通的總運(yùn)輸成本.約束條件（2）規(guī)定在現(xiàn)有節(jié)點(diǎn)中選擇r個(gè)進(jìn)行中斷.約束條件（3）規(guī)定每個(gè)OD對(duì)(i,j)中只要有一個(gè)節(jié)點(diǎn)被中斷，該OD對(duì)流量就無(wú)法流通.約束條件（4）規(guī)定每個(gè)OD對(duì)(i,j)中兩個(gè)節(jié)點(diǎn)均未被中斷，則必須在剩余樞紐節(jié)點(diǎn)中進(jìn)行分配運(yùn)輸.約束條件（5）規(guī)定每個(gè)OD對(duì)(i,j)在為其服務(wù)的樞紐中斷后將分配到最近的可用樞紐對(duì)，也就是說(shuō)，約束條件（5）防止每個(gè)OD對(duì)(i,j)分配到比樞紐對(duì)(k,m)與OD對(duì)(i,j)距離更遠(yuǎn)的樞紐對(duì)，除非樞紐對(duì)(k ,m)中的樞紐被中斷，因此，OD對(duì)(i,j)將在中斷后分配到最近的可用樞紐對(duì).最后，約束條件（6）、（7）和（8）分別是0-1整數(shù)限制和非負(fù)限制.

2.2 r個(gè)中斷節(jié)點(diǎn)的成本下界問(wèn)題

結(jié)合上述RIN-UB問(wèn)題模型，我們建立最好情況下的RIN下界問(wèn)題（r-interdiction node upper bound problem，RIN-LB）模型，表示如下：

以及式（2）、式（5）、式（6）、式（7）、式（8）.

RIN-LB模型的符號(hào)表示與RIN-UB模型一致，各約束條件表示也類似.RIN-LB模型與RINUB模型不同點(diǎn)在于，RIN-UB研究的是最壞中斷情況下的解，而RIN-LB研究的是最好中斷情況下的解，即RIN問(wèn)題的下界.

3 RIN問(wèn)題的啟發(fā)式算法

對(duì)RIN問(wèn)題將采用禁忌搜索（TS）算法進(jìn)行計(jì)算，并進(jìn)行一定改進(jìn)，通過(guò)幾種改進(jìn)形式的比較確定較快的TS算法.

3.1 禁忌搜索算法的初始化階段

本文將分別通過(guò)三種方式取得RIN-UB問(wèn)題和RIN-LB問(wèn)題TS算法的初始解.

近幾年，國(guó)際標(biāo)準(zhǔn)化組織不斷加快對(duì)D2D通信技術(shù)的標(biāo)準(zhǔn)化研究工作。3GPP(第三代合作計(jì)劃)于2011年9月提出了近鄰服務(wù)研究項(xiàng)目(ProSe SI)，該項(xiàng)目關(guān)注D2D通信的具體實(shí)現(xiàn)、技術(shù)細(xì)節(jié)和適用場(chǎng)景。Release 12標(biāo)準(zhǔn)針對(duì)基于LTE-A核心網(wǎng)平臺(tái)的D2D通信技術(shù)進(jìn)行探討，同時(shí)也展示了不同的D2D通信場(chǎng)景和需求，如本地?cái)?shù)據(jù)交換、公共安全服務(wù)等[3]。Release 14標(biāo)準(zhǔn)圍繞D2D通信進(jìn)行系統(tǒng)架構(gòu)和通信協(xié)議的詳細(xì)設(shè)計(jì)和規(guī)范[4]。

（1）隨機(jī)初始解.

在無(wú)容量限制的多分配p－樞紐中位問(wèn)題(UMApHMP)最優(yōu)解的基礎(chǔ)上，于整個(gè)網(wǎng)絡(luò)所有節(jié)點(diǎn)中隨機(jī)選取r個(gè)節(jié)點(diǎn)作為中斷節(jié)點(diǎn)，RIN-UB問(wèn)題和RIN-LB問(wèn)題的初始解，，并作為

（2）基于流量的初始解.

定義wi,i=1,2,…,n為UMApHMP問(wèn)題最優(yōu)解分配前提下節(jié)點(diǎn)i輸出與輸入的流量總和，根據(jù)wi降序排列所有節(jié)點(diǎn).選擇前 r個(gè)節(jié)點(diǎn)作為RIN-UB問(wèn)題初始中斷節(jié)點(diǎn)，，選擇后r個(gè)節(jié)點(diǎn)為RIN-LB問(wèn)題初始中斷節(jié)點(diǎn)，

（3）基于流量與距離的初始解.

定義ci為樞紐節(jié)點(diǎn)或非樞紐節(jié)點(diǎn)與所有節(jié)點(diǎn)距離和，相同ci的節(jié)點(diǎn)，wi較大者優(yōu)先選為中斷節(jié)點(diǎn)，相同wi的節(jié)點(diǎn)，ci較小者優(yōu)先選為中斷節(jié)點(diǎn).因此根據(jù)降序排列所有節(jié)點(diǎn)，選擇前r個(gè)節(jié)點(diǎn)作為RIN-UB問(wèn)題初始中斷節(jié)點(diǎn)，，選擇后 r個(gè)節(jié)點(diǎn)作為RIN-LB問(wèn)題初始中斷節(jié)點(diǎn)，

3.2 禁忌搜索算法的改進(jìn)化階段

TS算法的改進(jìn)化階段在鄰域搜索的基礎(chǔ)上再進(jìn)行禁忌搜索，以確定RIN-UB問(wèn)題和RIN-LB問(wèn)題的最優(yōu)解.RIN-UB問(wèn)題TS改進(jìn)化階段如下.

Step1已知節(jié)點(diǎn)集合 N和樞紐點(diǎn)集合F={h1,h2,…,hp}，設(shè)置最優(yōu)值=0，初始解根據(jù)上述三種方法獲得并賦值給最優(yōu)解=， 計(jì) 算 中 斷 后 的 目 標(biāo) 值

Step3禁忌搜索.

（3）在禁忌表中除了新加入的節(jié)點(diǎn)對(duì)外，對(duì) 其 余 節(jié) 點(diǎn) 對(duì) (a ,b) 進(jìn) 行 操 作len(a ,b)=len(a ,b)-1，如果 len(a ,b)=0，節(jié)點(diǎn)對(duì)(a,b)離開(kāi)禁忌表.

（4）當(dāng)t=10時(shí)，禁忌搜索停止，否則重復(fù)步驟（2）.

Step4報(bào)告最優(yōu)值和最優(yōu)解.

除了目標(biāo)函數(shù)是求設(shè)施中斷后運(yùn)營(yíng)成本的最小化以外,RIN-LB問(wèn)題TS的算法步驟與RIN-UB基本相同,在此不再累述.

4 算法測(cè)試

4.1 算法說(shuō)明

AP數(shù)據(jù)是澳大利亞郵政數(shù)據(jù)，來(lái)自澳大利亞的郵件流量,數(shù)據(jù)包括代表郵政區(qū)域的200個(gè)節(jié)點(diǎn)，可從OR-Library[14]中直接獲得該數(shù)據(jù).

4.2 結(jié)果與分析

表1和表2為基于AP數(shù)據(jù)n=100的禁忌搜索算法在RIN-UB問(wèn)題和RIN-LB問(wèn)題中的計(jì)算結(jié)果.節(jié)點(diǎn)數(shù)n、樞紐數(shù) p、折扣系數(shù)α、中斷前最優(yōu)值和最優(yōu)樞紐選址結(jié)果OHL均為已知，成本折扣系數(shù) χ=3，α=0.75，δ=2，懲罰系數(shù) β=2.中斷前的樞紐是通過(guò)對(duì)選址問(wèn)題的計(jì)算所獲得的最優(yōu)解，一些ORLIB未提供的而規(guī)模較大的數(shù)據(jù)則通過(guò)Ernst和Krishnamoorthy的算法實(shí)現(xiàn)后獲得.表中的r列代表中斷樞紐數(shù)，和表示由CPLEX獲得的RIN問(wèn)題上下界最優(yōu)值，ONI、OHI和OSI分別表示中斷問(wèn)題的最優(yōu)解、中斷問(wèn)題最優(yōu)解的樞紐部分和中斷問(wèn)題最優(yōu)解的非樞紐部分.基于三種初始解的禁忌搜索算法的每種情況都重復(fù)運(yùn)行100次,θR、θW和θWC為隨機(jī)初始解、基于流量初始解，以及基于流量和距離初始解的三種TS算法獲得最優(yōu)解的概率, R.time、W.time和WC.time為基于隨機(jī)初始解、基于流量初始解和基于流量與距離初始解三種TS算法的運(yùn)行時(shí)間.

表1 AP數(shù)據(jù)測(cè)試結(jié)果（上界，n=100，β=2）Table1 The result of testing AP data(up bound,n=100，β=2)

表2 AP數(shù)據(jù)測(cè)試結(jié)果（下界，n=100，β=2）Table2 The result of testing AP data(down bound,n=100，β=2)

通過(guò)表1和表2不難發(fā)現(xiàn)，三種初始解獲得最優(yōu)解的概率都為100%.而在運(yùn)算時(shí)間方面，基于流量與距離的初始解能在最短時(shí)間內(nèi)達(dá)到最優(yōu)，基于流量的初始解位居第二，而隨機(jī)初始解較差.三者的差距在規(guī)模較小的問(wèn)題中并不明顯，而隨著n和r的值逐步擴(kuò)大，運(yùn)算時(shí)間的差別也越來(lái)越大，甚至出現(xiàn)隨機(jī)初始解達(dá)到最優(yōu)解的時(shí)間比后兩種TS算法多50%左右.

圖1與圖2中顯示的分別是基于隨機(jī)初始解、基于流量初始解和基于流量與距離初始解三種 TS算法在處理 AP數(shù)據(jù)（n=100，p=80，r={5,10,20} ，β=2）時(shí)，不同 r所要的運(yùn)算時(shí)間.

圖1 AP數(shù)據(jù)RIN-UB問(wèn)題運(yùn)算時(shí)間對(duì)比（n=100，p=80，r={5 ,10,20}，β=2）Fig.1 Comparison of operation time of RIN-UB problem processing AP data（n=100，p=80，r={5 ,10,20}，β=2）

圖2 AP數(shù)據(jù)RIN-LB問(wèn)題運(yùn)算時(shí)間對(duì)比（n=100，p=80，r={5 ,10,20}，β=2）Fig.2 Comparison of operation time of RIN-LB problem processing AP data（n=100，p=80，r={5 ,10,20}，β=2）

不論是RIN-UB問(wèn)題還是RIN-LB問(wèn)題，由于已有樞紐節(jié)點(diǎn)的數(shù)量 p不再影響中斷節(jié)點(diǎn)選擇的范圍，因而相同的n和r，即使 p變化，運(yùn)算時(shí)間也相差不大.流量和距離的初始解由于其設(shè)計(jì)的合理性和全面性，能夠在最短時(shí)間內(nèi)達(dá)到最優(yōu)解，因而優(yōu)于其它兩種TS算法.

5 RIN問(wèn)題實(shí)例結(jié)果與分析

為了測(cè)試 r中斷節(jié)點(diǎn)問(wèn)題的上下界模型和禁忌搜索算法的實(shí)用性，本節(jié)將其應(yīng)用于實(shí)際問(wèn)題中進(jìn)行求解分析.

針對(duì)中國(guó)航空實(shí)際網(wǎng)絡(luò)現(xiàn)狀，即北京、上海和廣州為國(guó)際樞紐機(jī)場(chǎng)，沈陽(yáng)、武漢、成都、西安、烏魯木齊和昆明為地方樞紐機(jī)場(chǎng),下面采用基于流量和距離初始解的TS算法對(duì)RINUB問(wèn)題和RIN-LB問(wèn)題進(jìn)行求解.表3為城市與其對(duì)應(yīng)代碼.

表3 城市與對(duì)應(yīng)代碼Table3 The corresponding code of the city

表4 中國(guó)航空實(shí)際客運(yùn)RIN-UB問(wèn)題計(jì)算結(jié)果Table4 The results of RIN-UB problem of Air China’s actual carrier of passengers

表5 中國(guó)航空實(shí)際客運(yùn)RIN-LB問(wèn)題計(jì)算結(jié)果Table5 The results of RIN-LB problem of Air China’s actual carrier of passengers

表6 中國(guó)航空實(shí)際貨運(yùn)RIN-UB問(wèn)題計(jì)算結(jié)果Table6 The results of RIN-UB problem of Air China’s actual carrier of passengers

表7 中國(guó)航空實(shí)際貨運(yùn)RIN-LB問(wèn)題計(jì)算結(jié)果Table7 The results of RIN-LB problem of Air China’s actual carrier of passengers

從表4與表6中可以發(fā)現(xiàn)，北京、上海、廣州和武漢成為影響最大的四座城市，廣州在客運(yùn)方面影響比上海大，而后者在貨運(yùn)方面較前者更有影響力.作為非樞紐節(jié)點(diǎn)的深圳和作為樞紐節(jié)點(diǎn)的昆明和成都都對(duì)中國(guó)實(shí)際航空網(wǎng)絡(luò)影響較大，應(yīng)當(dāng)重點(diǎn)保護(hù).從表5與表7中可以得出，合肥和張家界連同太原、溫州成為對(duì)航空客運(yùn)和航空貨運(yùn)網(wǎng)絡(luò)運(yùn)行成本影響最小的四座城市.寧波和桂林因其客運(yùn)流量和貨物流量較小，被選為客運(yùn)RIN問(wèn)題下界的中斷點(diǎn).

在RIN問(wèn)題中，北京在客運(yùn)和貨運(yùn)方面都是最重要的航空城市，而上海在貨運(yùn)網(wǎng)絡(luò)中的重要性位居第二，廣州在客運(yùn)網(wǎng)絡(luò)中的重要性位居第二，武漢在這兩類航空網(wǎng)絡(luò)中仍處于第四的位置，這四座城市應(yīng)當(dāng)?shù)玫阶畲蟪潭鹊谋Ｗo(hù).昆明、成都和深圳則為以上四座城市外的重要節(jié)點(diǎn).合肥、張家界、太原和溫州的中斷將導(dǎo)致航空網(wǎng)絡(luò)運(yùn)行成本的最低損失，因而可適當(dāng)減少這四座城市的防御強(qiáng)度.寧波和桂林分別成為客運(yùn)和貨運(yùn)中網(wǎng)絡(luò)運(yùn)行成本影響力較小的城市.

實(shí)際航空樞紐情況下客運(yùn)和貨運(yùn)中斷后成本下界的范圍(客運(yùn)(9 3 342.38,101 253.25),貨運(yùn)(1 984.84,2 096.02))與以選址問(wèn)題 p=9時(shí)最優(yōu)解為基礎(chǔ)的中斷成本下界區(qū)間相近.中國(guó)航空至少需要成本下界數(shù)量的資金準(zhǔn)備來(lái)處理中斷問(wèn)題，同樣根據(jù)成本上界適當(dāng)調(diào)整金額以應(yīng)對(duì)更多中斷情況.

6 研究結(jié)論

針對(duì)節(jié)點(diǎn)完全性中斷，提出了考慮延遲懲罰的r中斷節(jié)點(diǎn)的成本問(wèn)題（RIN），由于節(jié)點(diǎn)的中斷往往隨機(jī)發(fā)生，而不一定是最壞情況，將問(wèn)題分為r中斷節(jié)點(diǎn)上界問(wèn)題（RIN-UB）和r中斷節(jié)點(diǎn)下界問(wèn)題（RIN-LB），并進(jìn)行建模，以求得節(jié)點(diǎn)中斷后的運(yùn)行成本區(qū)間.通過(guò)基于隨機(jī)初始解、基于流量初始解和基于流量和距離初始解的三種禁忌搜索算法（TS）對(duì)AP數(shù)據(jù)的RIN-UB問(wèn)題和RIN-LB問(wèn)題進(jìn)行求解，在測(cè)試結(jié)果中發(fā)現(xiàn)基于流量和距離的初始解由于其設(shè)計(jì)的合理性和全面性，能夠在最短時(shí)間內(nèi)達(dá)到最優(yōu)解，因而優(yōu)于其它兩種TS算法.

最后，本文將RIN問(wèn)題的模型及算法應(yīng)用于中國(guó)航空樞紐網(wǎng)絡(luò)的實(shí)例中，根據(jù)結(jié)果分析得出對(duì)于中國(guó)航空網(wǎng)絡(luò)較重要的關(guān)鍵城市以及相對(duì)影響較弱的城市，同時(shí)提出中國(guó)航空網(wǎng)絡(luò)最小準(zhǔn)備資金在不同情況下的數(shù)量區(qū)間，為資金合理分配和儲(chǔ)備提供參考.

由于軸輻式樞紐網(wǎng)絡(luò)的選址問(wèn)題已經(jīng)發(fā)展的比較成熟，因此以后要更注重p樞紐中心問(wèn)題和p樞紐覆蓋問(wèn)題的中斷研究，尤其是如今運(yùn)行成本對(duì)于決策影響的比重逐步減少，而客戶滿意和市場(chǎng)份額這兩大因素逐漸成為決策者所必須研究的課題.

[1]陶羿,朱建青,李明,等.軍事物流選址分配模型及遺傳算法優(yōu)化[J].信息工程大學(xué)學(xué)報(bào),2007(1):110-113. [TAO Y,ZHU J Q,LI M,et al.Optimization of the model of military logistics center location and allocation of ser?vice using Genetic Algorithm[J].Journal of Information Engineering University,2007(1):110-113.]

[2]Bryan DL,O’Kelly ME.Hub-and-spoke networks in air transportation:an analytical review[J].Journal of Region?al Science,1999(2):275-295.

[3]柏明國(guó),朱金福.全連通航線網(wǎng)絡(luò)和樞紐航線網(wǎng)絡(luò)的比較研究[J].系統(tǒng)工程理論與實(shí)踐,2006(9):113-117.[BAI M G,Zhu J F.Comparative study on fullyconnected and hub-and-spoke airline networks[J].Sys?tems Engineering-theory&Practice,2006(9):113-117.] [4]Grubesic TH,Murray A T.Vital nodes,interconnected infrastructures,and the geographies of network surviv?ability[J].Annals of the Association of American Geog? raphers,2006(1):64-83.

[5]McMasters A W,Mustin T M.Optimal interdiction of a supply network[J].Naval Research Logistics Quarterly, 1970(17):261-268.

[6]Smith J C,Lim C,Sudargho F.Survivable network de?sign under optimal and heuristic interdiction scenarios [J].Journal of Global Optimization,2007(38):181-199.

[7]Scaparra M P,Church R L.A bi-level mixed-integer program for critical infrastucture protection planning[J]. Computers&Operations Research,2008(6):1905-1923.

[8]楊珺，張敏，王世偉.基于p-中位模型的網(wǎng)絡(luò)關(guān)鍵設(shè)施識(shí)別問(wèn)題的算法設(shè)計(jì)與實(shí)現(xiàn)[J].管理學(xué)報(bào)，2008，21（4）：46-53.[YANG J,ZHANG M,WANG S W.Algo?rithms and analysis for the critical facilities identifica?tion problem in network based on p-median model[J]. Chinese Journal of Management,2008，21（4）：46-53.]

[9]楊珺，劉舒佶，王玲.考慮最壞中斷損失下的P-中位設(shè)施選址問(wèn)題的模型與算法研究[J].中國(guó)管理科學(xué)2011,19(4):120-129.[YANG J,LIU S J,WANG L.A bilevel programming model and heuristics for p-median location problem with r-interdiction worst loss[J].Chi?nese Journal of Management Science,2011,19(4):120-129.]

[10]翁克瑞.輻射式物流網(wǎng)絡(luò)設(shè)計(jì)的選址與路線優(yōu)化研究[M].成都：電子科技大學(xué)出版社，2009.[WENG K R. Location and route optimization based on hub-andspoke network design[M].Chengdu:University of Elec?tronic Science and Technology Press,2009.]

[11]翁克瑞.帶固定軸線成本的軸輻式網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題[J].運(yùn)籌學(xué)學(xué)報(bào),2012,16(1):88-96.[WENG K R.The sta?bility of the solutions of optimization hub-and-spoke network design problem with fixed hub arc costs[J].Op?erations Research Transactions,2012,V16(1):88-96.]

[12]Murray A T,Marisziw T C,Gruesic T H.Critical network infrastructure analysis:interdiction and system flow[J]. Journal of Geographical Systems,2007(9):103-117.

[13]Snyder L V,Daskin M S.Reliability models for facility location:The expected failure cost case[J].Transporta?tion Science,2005(3):400-416.

[14]Beasley J E Or-Library:Distributing test poblems by electronic mail[J].Journal of the Operational Research Society,1990(41):1069-1072.

Facility Interdiction Problem Based on Hub-and-Spoke Network with Delay Penalty

YANG Jun1,SHAO Lu-lu1,LIU Shu-ji2
（1 School of Management,Huazhong University of Science and Technol.,Wuhan 430074,China；2 Department of Industrial&System Engineering,University of Wisconsin-Madison,1513 UniversityAvenue,Madison,WI 53706,US）

system engineering;air transportation;interdiction model;heuristic algorithm;hub;network

1009-6744（2014）03-0117-09

U 8

A

2013-10-16

2014-01-18錄用日期：2014-02-14

國(guó)家自然科學(xué)基金資助項(xiàng)目(71172093，71320107001)；教育部人文社會(huì)科學(xué)研究青年基金項(xiàng)目(10YJC630331)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助（HUST：2013QN101）.

楊珺(1976-)，女，湖北武漢人,副教授，博士.*通訊作者:jun_yang@mail.hust.edu.cn

Absttract:With increasing airlines carrying out global air transport service based on the model of hub-andspoke network system,the hub-and-spoke network research gradually draws attention.Regarding hub location problem,this paper proposes the node complete interdiction problem facing the entire network with delay penalty.The problem is divided into two models which are designed to obtain the lower bound and the upper bound of the increased operation cost.The efficiency of three improved Tabu search algorithms are also compared with a data test.Finally,these two models of interdiction and advanced algorithms are applied in the network of aviation in China,followed by the outcomes analyzed.The critical cities of Chinese aviation are identified.Cities to be fortified with limited resources are classified by the grade of significance.The financial preparation is recommended in account of the outcomes as well.