李紅梅 鄧 潔 羅太波 齊捧虎

(1.西北大學(xué) 經(jīng)濟(jì)管理學(xué)院,陜西 西安 710127;2.西安電子科技大學(xué) 經(jīng)濟(jì)與管理學(xué)院,陜西 西安 710126)

0 引言

回顧過(guò)去的近二十年,各類自然災(zāi)害、事故災(zāi)難、公共衛(wèi)生事件以及社會(huì)安全事件在全球各個(gè)國(guó)家和地區(qū)頻繁發(fā)生,給世界各國(guó)人民的生命和財(cái)產(chǎn)安全、公共安全以及社會(huì)秩序等帶來(lái)了不同程度的影響。健全的城市應(yīng)急管理系統(tǒng)能有效地降低甚至預(yù)防突發(fā)事件帶來(lái)的巨大損失,而應(yīng)急避難點(diǎn)選址是應(yīng)急管理中極為重要的一部分,合理的應(yīng)急避難點(diǎn)選址可以高效的完成緊急情況下疏散任務(wù),降低突發(fā)事件的危害,同時(shí)預(yù)防二次災(zāi)難的發(fā)生。已有的應(yīng)急避難點(diǎn)多是根據(jù)當(dāng)時(shí)城市的規(guī)模和需求建設(shè)的,然而隨著我國(guó)城市的快速發(fā)展,城市規(guī)模不斷擴(kuò)大,城市人口數(shù)量劇增,已有的應(yīng)急避難點(diǎn)已經(jīng)不能滿足城市發(fā)展的需求。如何在已有避難點(diǎn)的基礎(chǔ)上規(guī)劃新增應(yīng)急避難點(diǎn),成為了許多城市亟須解決的問(wèn)題。災(zāi)害自身的不確定性導(dǎo)致在規(guī)劃應(yīng)急避難點(diǎn)時(shí)很難對(duì)潛在疏散點(diǎn)的疏散人數(shù)進(jìn)行準(zhǔn)確的估算,大部分情況只能給出區(qū)間估計(jì);與此同時(shí),由于緊急避難時(shí)大量人口瞬間涌入道路,難免導(dǎo)致疏散過(guò)程中出現(xiàn)堵塞等情況,這些問(wèn)題都增加了新增應(yīng)急避難點(diǎn)選址的難度。本文考慮在城市的不斷發(fā)展變化導(dǎo)致原有避難點(diǎn)系統(tǒng)無(wú)法應(yīng)對(duì)當(dāng)前情況下,研究如何對(duì)新增應(yīng)急避難點(diǎn)進(jìn)行選址以達(dá)到一定的優(yōu)化目標(biāo)。考慮到疏散點(diǎn)人數(shù)的不確定性,結(jié)合應(yīng)急避難疏散的特殊需求,為更加貼近現(xiàn)實(shí)疏散目標(biāo),本文采用最小最大后悔準(zhǔn)則作為選址方案的評(píng)價(jià)準(zhǔn)則,以此保障即使在最壞的情況下選址方案也有可接受的表現(xiàn)。

國(guó)際上最早的應(yīng)急避難設(shè)施選址問(wèn)題是Toregas 等[1]在1971 年提出的,他們研究如何建立數(shù)量最少的應(yīng)急救援點(diǎn),以便在規(guī)定時(shí)間內(nèi)能夠給所有需要應(yīng)急服務(wù)的需求點(diǎn)提供救援,即為后來(lái)的集合覆蓋問(wèn)題(set covering problem)。早期的應(yīng)急避難點(diǎn)選址模型主要包括了覆蓋模型(covering problem)、中心點(diǎn)模型(center problem)和中值點(diǎn)模型(median problem)。關(guān)于覆蓋問(wèn)題的相關(guān)研究可以參考綜述性文獻(xiàn)[2];有關(guān)中心點(diǎn)和中值點(diǎn)問(wèn)題的研究可以參考綜述性文獻(xiàn)[3-4]。對(duì)于新增設(shè)施的選址問(wèn)題,最早的研究是基于中心點(diǎn)選址問(wèn)題而來(lái),稱為有條件的選址問(wèn)題[5-6](conditional location problem)。他們首先研究了在網(wǎng)絡(luò)中已有q(q≥1)個(gè)設(shè)施的情況下,如何新建p=1 個(gè)設(shè)施以使得目標(biāo)函數(shù)最優(yōu)。Chen 和Handler[7]考慮平面上有條件的p-中心點(diǎn)選址問(wèn)題(p≥1) 并給出了一種逐次逼近算法用以求解。Chen[8]在前面研究的基礎(chǔ)上進(jìn)一步考慮了平面上有條件的p-中心點(diǎn)選址問(wèn)題和中值點(diǎn)選址問(wèn)題并給出了求解思路。之后Chen 和Handler[9]提出了另一種算法用以解決平面上有條件的p-中心點(diǎn)選址問(wèn)題。Drezner[10]則提出通過(guò)解決O(logn) 個(gè)傳統(tǒng)的中心點(diǎn)選址問(wèn)題求解有條件的p-中心點(diǎn)選址問(wèn)題的算法。后來(lái)Drezner[11]又提出了求解有條件的p-中值點(diǎn)選址問(wèn)題的啟發(fā)式算法。值得一提的是文獻(xiàn)[10-11]中的方法同時(shí)適用于平面和網(wǎng)絡(luò)兩種情況。Berman 和Simchi-Levi[12]將網(wǎng)絡(luò)上的有條件的p-中心點(diǎn)/中值點(diǎn)選址問(wèn)題轉(zhuǎn)換為求解傳統(tǒng)的(p+1)-中心點(diǎn)/中值點(diǎn)選址問(wèn)題。Berman 和Drezner[13]提出了另一種簡(jiǎn)潔的求解方法,通過(guò)建立合適的最短路矩陣將網(wǎng)絡(luò)上有條件的p-中心點(diǎn)/中值點(diǎn)選址問(wèn)題轉(zhuǎn)換為傳統(tǒng)的p-中心點(diǎn)/中值點(diǎn)問(wèn)題求解。Chen和Chen[14]在文獻(xiàn)[7]的基礎(chǔ)上提出了一種新的逐次逼近算法求解有條件的p-中心點(diǎn)選址問(wèn)題。

本文研究一般網(wǎng)絡(luò)圖上已有若干個(gè)應(yīng)急避難點(diǎn)時(shí)新增一個(gè)應(yīng)急避難點(diǎn)的選址問(wèn)題。但與以往研究不同,考慮到突發(fā)事件的不確定性,疏散網(wǎng)絡(luò)中各頂點(diǎn)的權(quán)重通常難以確定,但其所屬區(qū)間范圍一般可以知道,因此本文研究的疏散網(wǎng)絡(luò)中頂點(diǎn)權(quán)重以區(qū)間數(shù)據(jù)的形式給定。同時(shí),考慮到應(yīng)急環(huán)境下大量人流短時(shí)間迅速轉(zhuǎn)移易形成局部堵塞,本文對(duì)疏散網(wǎng)絡(luò)中的道路引入容量參數(shù),以此表示路段的通行能力。同時(shí)關(guān)于考慮疏散人數(shù)不確定和疏散中堵塞時(shí)間成本的選址問(wèn)題也有相關(guān)研究,稱為sink 選址問(wèn)題。Sink 選址問(wèn)題最初由Cheng 等[15]提出,他們考慮在一條具有個(gè)n頂點(diǎn)的路上選擇1 個(gè)點(diǎn)作為應(yīng)急避難點(diǎn)的1-sink 選址問(wèn)題,并給出了時(shí)間復(fù)雜度為O(nlog2n) 的算法,之后有多個(gè)改進(jìn)的算法[16][17],目前最優(yōu)的算法時(shí)間復(fù)雜度為O(n)[18];文獻(xiàn)[18]中同時(shí)將求解一條路上2 個(gè)sink 的選址問(wèn)題的時(shí)間復(fù)雜度由O(n3logn)[19]改進(jìn)到了O(nlog4n);對(duì)于一條路上k個(gè)sink 的選址問(wèn)題也有學(xué)者進(jìn)行了研究并給出了求解算法[20][21]。針對(duì)樹上1 個(gè)sink 的選址問(wèn)題,Higashikawa 等[22]給出了時(shí)間復(fù)雜度為O(n2log2n) 的算法,Bhattacharya 和Kameda[18]進(jìn)一步設(shè)計(jì)了時(shí)間復(fù)雜度為O(nlogn) 的算法;Golin 和Sandeep[23]設(shè)計(jì)了求解樹上k 個(gè)sink 選址問(wèn)題的算法,時(shí)間復(fù)雜度為O(max(k2,log2n)k2n2log5n)。Xu 和Li[24]針對(duì)圈上1 個(gè)sink 選址問(wèn)題給出了時(shí)間復(fù)雜度為O(n3logn)的算法,Benkoczi 等[25]給出了時(shí)間復(fù)雜度為O(n2) 的算法。一般網(wǎng)絡(luò)圖上的sink 選址問(wèn)題研究成果有限,Li 和Xu[26]假設(shè)所有人就近避難,考慮1 個(gè)sink 的選址,給出了時(shí)間復(fù)雜度為O(m2n3) 求解算法。以上相關(guān)研究的優(yōu)化目標(biāo)都是最大完成時(shí)間的最大后悔值最小,也有學(xué)者考慮以總完成時(shí)間的最大后悔值最小為目標(biāo),針對(duì)路上1 個(gè)sink 的選址問(wèn)題給出了相應(yīng)的求解算法[27-28]。需要說(shuō)明的是,在以上最小最大后悔sink 選址問(wèn)題研究中,均包含了以下假設(shè):(1)疏散網(wǎng)絡(luò)中所有的邊都具有相同的容量;(2)應(yīng)急避難點(diǎn)入口為無(wú)限大,權(quán)重到達(dá)即完成避難,不考慮進(jìn)入時(shí)間,因此若一個(gè)應(yīng)急避難點(diǎn)建立在某個(gè)頂點(diǎn)上,該頂點(diǎn)上的權(quán)重可視為在瞬間完成避難。(3)同一個(gè)頂點(diǎn)上的權(quán)重應(yīng)當(dāng)經(jīng)由相同的疏散路徑到達(dá)同一個(gè)應(yīng)急避難點(diǎn);(4)疏散過(guò)程中不允許出現(xiàn)權(quán)重對(duì)流。在討論本文研究問(wèn)題的過(guò)程中,將沿用這些假設(shè)。

本文在已有研究的基礎(chǔ)上,考慮疏散人數(shù)的不確定性和疏散過(guò)程中人流堵塞帶來(lái)的時(shí)間成本,假設(shè)在一般圖G=(V,E) 中上已存在k-1(k≥2) 個(gè)應(yīng)急避難點(diǎn),對(duì)如何新增一個(gè)(第k個(gè))應(yīng)急避難點(diǎn)的選址問(wèn)題展開研究。鑒于在災(zāi)難發(fā)生時(shí),群眾習(xí)慣去往距離自己最近的避難點(diǎn)進(jìn)行避難[26],因此本文假設(shè)所有權(quán)重均以就近避難作為選擇避難點(diǎn)和避難路徑的原則。同時(shí),與之前的相關(guān)研究一樣,假設(shè)疏散網(wǎng)絡(luò)中所有的邊都具有相同的容量。目標(biāo)函數(shù)的設(shè)定以最大完成時(shí)間(所有權(quán)重到達(dá)避難點(diǎn)的時(shí)間)為基礎(chǔ),采用魯棒優(yōu)化的思想,以最壞場(chǎng)景為目標(biāo),尋求使得最大完成時(shí)間的最大后悔值最小的新增避難點(diǎn)選址方案。

1 問(wèn)題定義與性質(zhì)分析

1.1 問(wèn)題定義

在一般網(wǎng)絡(luò)連通圖G=(V,E) 上,頂點(diǎn)集V=(v1,v2,…,vn) 表示網(wǎng)絡(luò)中避難者的分布點(diǎn),邊集E表示網(wǎng)絡(luò)中的道路集合,且| E|=m。對(duì)于邊e∈E,l(e) 為該道路的長(zhǎng)度,且每條道路具有相同的通行能力c,也即單位時(shí)間能夠進(jìn)入道路的最大權(quán)重?cái)?shù)。對(duì)于任意頂點(diǎn)vi∈V,該頂點(diǎn)需要避難的人數(shù)在災(zāi)害發(fā)生前是不確定的,僅知道人數(shù)區(qū)間為,且;在災(zāi)害發(fā)生時(shí),該頂點(diǎn)需要避難的人數(shù)從客觀上是確定值。假設(shè)某頂點(diǎn)vi上有wi單位的權(quán)重要進(jìn)入邊e,由于道路通行能力c ＜wi,那么頂點(diǎn)vi上的部分權(quán)重需要等待一定的時(shí)間才能進(jìn)入道路,即產(chǎn)生堵塞。令場(chǎng)景集合S表示所有可能的權(quán)重wi的笛卡爾積(1 ≤i≤n)。當(dāng)場(chǎng)景s∈S給定時(shí),wi(s) 表示該場(chǎng)景下頂點(diǎn)vi的權(quán)重。定義τ為單位權(quán)重在各路段上移動(dòng)單位距離所需的時(shí)間。G中任意兩點(diǎn)x和y的最短距離為d(x,y),且恒有d(x,y)=d(y,x)。本文假設(shè)圖中任意兩點(diǎn)間的最短路徑和路徑長(zhǎng)度已知。由于G是連通圖,即m≥n-1,但是當(dāng)m=n-1 時(shí),一般圖G成為樹圖,因此,假設(shè)m≥n。

不失一般性,假設(shè)圖G中已有k-1 個(gè)避難點(diǎn),其在網(wǎng)絡(luò)圖中對(duì)應(yīng)的位置分別記為x1,x2,…,xk-1。圖中每個(gè)頂點(diǎn)的避難者根據(jù)最短路徑選擇距離最近的避難點(diǎn)避難(若一個(gè)頂點(diǎn)與多個(gè)避難點(diǎn)間的最短路徑距離相同,則選擇排序靠前的避難點(diǎn);若一個(gè)頂點(diǎn)與一個(gè)避難點(diǎn)間有多條距離相同的最短路徑,則選擇最靠右的路徑)。在實(shí)際中,為了不出現(xiàn)混亂,假設(shè)各頂點(diǎn)的權(quán)重在向避難點(diǎn)撤離時(shí)視為一個(gè)整體且不允許出現(xiàn)交叉流?，F(xiàn)在需要在現(xiàn)有避難點(diǎn)的基礎(chǔ)上再增加一個(gè)避難點(diǎn),假設(shè)其選擇的位置為xk。對(duì)于vi,x(vi) 表示頂點(diǎn)vi在原有k-1 個(gè)避難點(diǎn)中選擇的避難點(diǎn)位置。如果d(vi,xk)≥d(vi,x(vi)),則該頂點(diǎn)選擇的避難點(diǎn)位置保持不變;如果d(vi,xk)＜d(vi,x(vi)),則該頂點(diǎn)選擇的避難點(diǎn)位置變?yōu)閤k。記X(xk)={x1,x2,…,xk-1,xk} 表示第k個(gè)避難點(diǎn)選址在xk時(shí),所有避難點(diǎn)位置的集合。在場(chǎng)景s下,定義F(X(xk),s)為第k個(gè)避難點(diǎn)選址在xk處時(shí),所有權(quán)重完成撤離的時(shí)間。用xopt(s) 表示場(chǎng)景s下第k個(gè)避難點(diǎn)的最優(yōu)選址位置(面對(duì)場(chǎng)景s,在該選址方案下,所有權(quán)重完成撤離的時(shí)間最小),則X(xopt(s))表示第k個(gè)應(yīng)急避難點(diǎn)選在最優(yōu)位置xopt(s) 時(shí)的所有避難點(diǎn)集合,即X(xopt(s))={x1,x2,…,xk-1,xopt(s)},相應(yīng)的,F(X(xopt(s)),s)為場(chǎng)景s下,該選址方案下圖G中所有權(quán)重完成撤離的時(shí)間。在場(chǎng)景s下,應(yīng)急避難點(diǎn)選在xk處的后悔值定義為:

應(yīng)急避難點(diǎn)選在xk處的最大后悔值定義為Rmax(X(xk))=。場(chǎng)景稱為應(yīng)急避難點(diǎn)選在xk處的最壞場(chǎng)景,即。該問(wèn)題的目標(biāo)是找到第k個(gè)避難點(diǎn)的最優(yōu)選址,使得其最大后悔值Rmax(X(xk)) 達(dá)到最小,即

1.2 性質(zhì)分析

通過(guò)對(duì)圖和路徑的分析,基于不同的選址位置,先把一般網(wǎng)絡(luò)圖分解成多項(xiàng)式個(gè)樹圖,而后分析最壞場(chǎng)景的結(jié)構(gòu),找到所有的可能最壞場(chǎng)景。

當(dāng)新的應(yīng)急避難點(diǎn)選在某一點(diǎn)xk時(shí),圖G中的每個(gè)頂點(diǎn)將根據(jù)就近原則選擇自身要到達(dá)的避難點(diǎn)并確定對(duì)應(yīng)的到達(dá)路徑。此時(shí),可以把圖G分解為k個(gè)以x1,x2,…,xk-1,xk為根節(jié)點(diǎn)的相互獨(dú)立的樹,不妨記為T(x1),T(x2),…,T(xk-1),T(xk)。注意這里的k個(gè)樹一定是相互獨(dú)立的;否則不妨假設(shè)某兩個(gè)樹圖T(xi) 和T(xj)(i,j∈[1,k],i≠j) 存在公共頂點(diǎn)vl,但是vl根據(jù)就近原則選擇避難點(diǎn)時(shí),必然選擇唯一的一個(gè)避難點(diǎn)和到達(dá)路徑,這與假設(shè)相矛盾,因此,由圖G分解而成的k個(gè)樹圖一定相互獨(dú)立。以圖1為例,圖G中有三個(gè)避難點(diǎn),首先,圖中各頂點(diǎn)根據(jù)就近原則選擇自身要到達(dá)的避難點(diǎn),假設(shè)選擇x1的頂點(diǎn)有{v1,v2,v3},選擇x2的頂點(diǎn)有{v4,v5},選擇x3的頂點(diǎn)有{v6}。然后,把圖G分解為分別以三個(gè)避難點(diǎn)為根節(jié)點(diǎn)的相互獨(dú)立的樹圖。

圖1 一般網(wǎng)絡(luò)圖到樹的轉(zhuǎn)換示意圖Figure 1 Illustration of a general network to tree networks with given sinks

記F(xi,s)表示場(chǎng)景s下,樹T(xi)中所有權(quán)重完成撤離的時(shí)間(1 ≤i≤k),那么有

下面介紹F(xi,s)(1≤i≤k)的計(jì)算過(guò)程,不妨以F(xk,s)為例。對(duì)于任意xk∈G,記δ(xk)={中e=(xk,vi)存在},表示樹T(xk)中所有與xk相鄰的頂點(diǎn)集合。對(duì)于任意vi∈T(xk),vi的撤離路徑一定經(jīng)過(guò)頂點(diǎn)vj∈δ(xk)。T(xk)中以vi為根的子樹記為T(xk,vi),相應(yīng)的,表示場(chǎng)景s下,T(xk,vi)中所有權(quán)重完成撤離的時(shí)間。因此,在場(chǎng)景s下有

假設(shè)T(xk,vi) 中有n′個(gè)頂點(diǎn),記為u1,u2,…,un′(=vi),且d(xk,ui) ≤d(xk,ui-1),2 ≤i≤n′。Kamiyama 等[29]已經(jīng)證明了在d(xk,ui) 保持不變,且道路通行能力相同時(shí),如果將xk和ui(1≤i≤n′)移至一條直線上,那么保持不變(如圖2 所示)。因此有

圖2 樹到路的轉(zhuǎn)換示意圖Figure 2 Illustration of a tree network to a path network

注意本文假設(shè)避難點(diǎn)的容量是無(wú)限大的,并且如果避難點(diǎn)位于頂點(diǎn)處,則該頂點(diǎn)的所有權(quán)重完成撤離的時(shí)間為零。

在給定場(chǎng)景s下,考慮當(dāng)xk位于邊e=(vp,vq) 上時(shí),對(duì)于任意vi∈V到達(dá)避難點(diǎn)的最短路徑有三種可能:(1)vi選擇的避難點(diǎn)為x(vi)(vi在原有k-1 個(gè)避難點(diǎn)中選擇的避難點(diǎn)位置),記做路徑P1;(2)vi選擇的避難點(diǎn)為xk,且經(jīng)過(guò)vp到達(dá),記做路徑P2;(3)vi選擇的避難點(diǎn)為xk,且經(jīng)過(guò)vq到達(dá),記做路徑P3。為了后面分析的需要,引入敏感點(diǎn)的概念。

定義1邊e=(vp,vq) 上,當(dāng)xk∈(vp,x′]和xk∈(x′,vq)時(shí),如果至少存在一個(gè)頂點(diǎn)vi∈V使得vi選擇的撤離路徑不同,則稱x′為邊e上的一個(gè)敏感點(diǎn)。

令gi=| d(vi,vp)-d(vi,vq)|,hi=d(vi,x(vi))-d(vi,vp)。接下來(lái),將根據(jù)避難點(diǎn)xk在邊e=(vp,vq) 上的不同選址情況,對(duì)邊上的敏感點(diǎn)進(jìn)行詳細(xì)分析。

情形1若gi=0,分三種子情形討論。

(1)如果hi≤0,那么邊e上沒(méi)有敏感點(diǎn);

(2)如果0＜hi≤,當(dāng)xk∈(vp,vp +hi)時(shí),vi選擇P2;當(dāng)xk∈[vp+hi,vq -hi]時(shí),vi選擇P1;當(dāng)xk∈(vq -hi,vq) 時(shí),vi選擇P3;

(3)如果hi＞,當(dāng)xk∈時(shí),vi選擇P2;當(dāng)xk∈時(shí),vi選擇P3。

即在情形1 下,vp +hi、vq -hi、vp +為邊e上的敏感點(diǎn)。

情形2若0＜gi≤d(vp,vq),分兩種子情形進(jìn)行討論。

(1)當(dāng)d(vi,vp)＜d(vi,vq) 時(shí),①如果hi≤0 且hi -gi≤0,那么邊e上沒(méi)有敏感點(diǎn);②如果hi＞0 且hi -gi≤0,當(dāng)xk∈(vp,vp +hi)時(shí),vi選擇P2;當(dāng)xk∈[vp +hi,vq)時(shí),vi選擇P1。③如果0＜hi≤且0＜hi -gi≤,當(dāng)xk∈(vp,vp +hi) 時(shí),vi選擇P2;當(dāng)xk∈[vp +hi,vq -hi +gi]時(shí),vi選擇P1;當(dāng)xk∈(vq -hi +gi,vq)時(shí),vi選擇P3。④如果hi＞,當(dāng)xk∈時(shí),vi選擇P2;當(dāng)xk∈時(shí),vi選擇P3。

(2)當(dāng)d(vi,vp)＞d(vi,vq) 時(shí),①如果hi +gi≤0,那么邊e上沒(méi)有敏感點(diǎn)。②如果hi +gi＞0且hi≤0,當(dāng)xk∈(vp,vq -hi -gi]時(shí),vi選擇P1;當(dāng)xk∈(vq -hi -gi,vq) 時(shí),vi選擇P3。③如果0＜hi+gi≤且0＜hi≤,當(dāng)xk∈(vp,vp+hi) 時(shí),vi選擇P2;當(dāng)xk∈[vp+hi,vq -hi -gi]時(shí),vi選擇P1;當(dāng)xk∈(vq -hi -gi,vq) 時(shí),vi選擇P3。④如果hi＞,當(dāng)xk∈時(shí),vi選擇P2;

當(dāng)xk∈時(shí),vi選擇P3。

即在情形2 下,vp +hi、vq -hi +gi、vp +、vq-hi -gi、vp +為邊e上的敏感點(diǎn)。

情形3若gi ＞d(vp,vq),同樣分下面兩種子情形進(jìn)行討論。

(1)當(dāng)d(vi,vp)＜d(vi,vq) 時(shí),①如果hi≤0,那么邊e上沒(méi)有敏感點(diǎn)。②如果0＜hi≤d(vp,vq),當(dāng)xk∈(vp,vp +hi) 時(shí),vi選擇P2;當(dāng)xk∈[vp+hi,vq) 時(shí),vi選擇P1。③如果d(vp,vq)＜hi,那么邊e上沒(méi)有敏感點(diǎn)。

(2)當(dāng)d(vi,vp)＞d(vi,vq) 時(shí),①如果hi +gi≤0,那么邊e上沒(méi)有敏感點(diǎn)。②如果0＜hi +gi≤d(vp,vq),當(dāng)xk∈(vp,vq -hi -gi]時(shí),vi選擇P1;當(dāng)xk∈(vq -hi -gi,vq) 時(shí),vi選擇P3。③如果d(vp,vq)＜hi+gi,那么邊e上沒(méi)有敏感點(diǎn)。

即在情形3 下,vp+hi、vq -hi -gi為邊e上的敏感點(diǎn)。

通過(guò)以上對(duì)敏感點(diǎn)的分析,可以得到下面的引理。

引理1若選定一條邊e,e上所有敏感點(diǎn)構(gòu)成集合Ce,那么Ce包含O(n) 個(gè)元素,且計(jì)算出Ce的時(shí)間復(fù)雜度為O(n)。

完成對(duì)敏感點(diǎn)的分析后,接下來(lái)分析最壞場(chǎng)景的結(jié)構(gòu)特征。在給定場(chǎng)景s下,若應(yīng)急避難點(diǎn)選在xk處,假設(shè)G中所有權(quán)重完成撤離的時(shí)間由T(xk) 中所有權(quán)重完成撤離的時(shí)間決定,而T(xk) 中所有權(quán)重完成撤離的時(shí)間由子樹T(xk,vi)中所有權(quán)重完成撤離的時(shí)間決定,即

根據(jù)已有研究的結(jié)果[22-23],樹上的sink 選址問(wèn)題轉(zhuǎn)換為路上的sink 選址問(wèn)題后,最壞場(chǎng)景的結(jié)構(gòu)特征能夠保留。定義可能最壞場(chǎng)景如下:

定義2給定第k個(gè)避難點(diǎn)的選址xk后,考慮任意一棵子樹T(xj,vi),其中1 ≤j≤k,vi∈δ(xj),假設(shè)該子樹中有n′個(gè)頂點(diǎn),記為u1,u2,…,un′(=vi),且d(xj,ui) ≤d(xj,ui-1),2 ≤i≤n′。如果場(chǎng)景s(xk) 滿足對(duì)于頂點(diǎn)ul(1 ≤l≤n′),有wf(s(xk))=,且wf(s(xk))=,對(duì)于所有的頂點(diǎn)vg?T(xj,vi),有wg(s(xk))=,則稱s(xk) 為避難點(diǎn)選在xk時(shí)的一個(gè)可能最壞場(chǎng)景。

根據(jù)定義可知,選定一個(gè)xk后就有一系列關(guān)于xk的可能最壞場(chǎng)景,記xk的所有可能最壞場(chǎng)景組成的集合為D(xk),D(xk) 包含O(n) 個(gè)元素[22]。

引理2若避難點(diǎn)選在xk處,那么對(duì)于任意s∈S,存在一個(gè)可能最壞場(chǎng)景s(xk)∈D(xk),使得R(X(xk),s(xk))≥R(X(xk),s)。

引理2 是顯然成立的,這里不再給出證明。由引理2 可知,對(duì)于任意xk∈G,避難點(diǎn)選在xk處的最壞場(chǎng)景一定在D(xk) 中。記D=表示避難點(diǎn)xk選在G中任意位置時(shí)所有可能最壞場(chǎng)景組成的集合。接下來(lái),將對(duì)D的結(jié)構(gòu)進(jìn)行詳細(xì)分析。

引理3D包含O(mn2) 個(gè)場(chǎng)景。

證明:由于G有n個(gè)頂點(diǎn),m條邊,給定一條邊e,Ce包含O(n)個(gè)元素,且給定xk后,D(xk)包含O(n)個(gè)場(chǎng)景,所以,D包含O(mn2) 個(gè)場(chǎng)景。

圖3 xk∈e=(vp,vq)時(shí)的示意圖Figure 3 Illustration of where xk∈e=(vp,vq)

圖4 xk∈e=(vp,vq)時(shí)的F(xk,s)及y1,y2,y3 示意圖Figure 4 Illustration of F(xk,s) and y1,y2,y3 where xk∈e=(vp,vq)

引理5給定一條邊e和一個(gè)場(chǎng)景s,Ye包含O(n) 個(gè)元素。

2 算法設(shè)計(jì)

2.1 最優(yōu)避難點(diǎn)選址

根據(jù)引理4,給定任意一個(gè)場(chǎng)景s,最優(yōu)避難點(diǎn)選址為:

引理6給定一個(gè)場(chǎng)景s,當(dāng)避難點(diǎn)選定在xk時(shí),得到F(X(xk),s) 的時(shí)間復(fù)雜度為O(n)。

證明:場(chǎng)景s下,若避難點(diǎn)選定在xk。首先,所有頂點(diǎn)選擇自身到達(dá)的避難點(diǎn)后,圖G將分解為k個(gè)樹圖T(x1),T(x2),…,T(xk-1),T(xk),其時(shí)間復(fù)雜度為O(n),記子樹T(xi)中的頂點(diǎn)數(shù)為ni(1≤i≤k)。下面,以T(xk)中所有權(quán)重完成撤離的時(shí)間F(xk,s) 為例(其余樹中所有權(quán)重完成撤離的時(shí)間同理可得),有

結(jié)合上一節(jié)的性質(zhì)分析和引理6,給定一個(gè)確定的場(chǎng)景s,求解最大完成時(shí)間最小的選址方案(即最優(yōu)選址方案) 的算法如表1 所示,易知該算法的時(shí)間復(fù)雜度為O(mn2)。針對(duì)確定場(chǎng)景下求解最優(yōu)選址方案的問(wèn)題,本小節(jié)給出下面的定理。

表1 確定場(chǎng)景下最優(yōu)選址方案求解算法Table 1 The optimal sink location algorithm

定理1給定一個(gè)場(chǎng)景s,一般網(wǎng)絡(luò)圖中,就近原則下新增應(yīng)急避難點(diǎn)的最優(yōu)選址問(wèn)題可在O(mn2) 時(shí)間求解。

2.2 最小最大后悔避難點(diǎn)選址

由引理3 可知,D包含O(mn2) 個(gè)場(chǎng)景。避難點(diǎn)xk在理論上有無(wú)窮多種選址方案,但當(dāng)xk落在特定范圍內(nèi)時(shí)(范圍分界點(diǎn)包括頂點(diǎn)和敏感點(diǎn)),疏散網(wǎng)絡(luò)對(duì)應(yīng)的樹圖是保持不變的。因此,根據(jù)xk的不同取值,可以將D分為O(mn)組場(chǎng)景,每組場(chǎng)景包含O(n) 個(gè)元素,即D(xk)。

引理7若避難點(diǎn)選定在xk且給定場(chǎng)景D(xk),那么對(duì)所有s∈D(xk),F(X(xk),s) 可以通過(guò)O(n2) 時(shí)間得到。

證明:給定xk,D(xk) 中包含O(n) 個(gè)場(chǎng)景。結(jié)合引理6可得上面的結(jié)論。

引理8對(duì)于所有xk∈V和所有s∈D(xk),得到F(X(xk),s) 的時(shí)間為O(n3)。

證明:由于圖G中有n個(gè)頂點(diǎn),每個(gè)頂點(diǎn)對(duì)應(yīng)的可能最壞場(chǎng)景D(xk) 包含有O(n) 個(gè)元素,結(jié)合引理6 得證。

引理9對(duì)于所有xk∈{V+,V-}和所有s∈D(xk),得到F(X(xk),s) 的時(shí)間為O(mn2)。

證明:由于這里的虛擬頂點(diǎn)與邊相關(guān)聯(lián),共需考慮2m個(gè)虛擬頂點(diǎn)。針對(duì)每個(gè)虛擬頂點(diǎn)需要考慮O(n) 個(gè)場(chǎng)景,結(jié)合引理6 可證。

引理10在給定邊e上,對(duì)于所有xk∈Ce和所有s∈D(xk),得到F(X(xk),s) 的時(shí)間為O(n3)。

證明:由于給定邊e后,Ce包含O(n) 個(gè)元素,且每個(gè)敏感點(diǎn)需考慮O(n) 個(gè)場(chǎng)景,結(jié)合引理6 可證。

引理12若給定邊e=(vp,vq),針對(duì)所有s∈D,Ye以及對(duì)于所有yi∈Ye的F(X(yi),s) 通過(guò)O(mn4) 時(shí)間得到。

通過(guò)上述引理,可以得到:(1)對(duì)于所有xk∈V和所有s∈D(xk),得到F(X(xk),s) 的時(shí)間為O(n3)(引理8);(2)對(duì)于所有xk∈{V+,V-}和所有s∈D(xk),得到F(X(xk),s)的時(shí)間為O(mn2)(引理9);(3) 基于引理10,由于G中有m條邊,因此,對(duì)于所有xk∈和所有s∈D(xk),F(X(xk),s) 通過(guò)O(mn3) 時(shí)間可得;(4) 基于引理12,對(duì)所有s∈D和所有e∈E,Ye及其對(duì)應(yīng)的F(X(yi),s) 通過(guò)O(m2n4) 時(shí)間可得。

對(duì)于任意s,X(xopt(s))=和F(X(xopt(s)),s)通過(guò)O(mn2)時(shí)間可得(算法見(jiàn)表1)。由于需要考慮O(mn2)個(gè)場(chǎng)景,因此,對(duì)于所有s∈D,X(xopt(s))和F(X(xopt(s)),s)可以通過(guò)O(m2n4)時(shí)間得到,即引理13。

引理13對(duì)于所有s∈D,X(xopt(s)) 和F(X(xopt(s)),s) 通過(guò)O(m2n4) 時(shí)間可得。

接下來(lái)考慮如何求得最大后悔值最小的選址方案?？赡艿淖顗膱?chǎng)景的結(jié)構(gòu)已經(jīng)明確,計(jì)算得到任意點(diǎn)在所有可能最壞場(chǎng)景的后悔值,通過(guò)比較即可找到其對(duì)應(yīng)的最大后悔值,最后給出對(duì)應(yīng)最大后悔值最小的點(diǎn)。由于網(wǎng)絡(luò)圖G中有無(wú)窮多備選點(diǎn),將其分為兩部分進(jìn)行討論分析:(1)避難點(diǎn)xk位于頂點(diǎn)時(shí),計(jì)算每個(gè)頂點(diǎn)處的最大后悔值,找到最大后悔值最小的選址點(diǎn);(2)避難點(diǎn)xk位于邊上時(shí),把每條邊分為O(n) 個(gè)區(qū)間,采用線性規(guī)劃的方法計(jì)算每個(gè)區(qū)間中對(duì)應(yīng)最大后悔值最小的點(diǎn),進(jìn)而通過(guò)比較找到每條邊上對(duì)應(yīng)最大后悔值最小的選址點(diǎn)。最后,比較兩部分得到整體的最小最大后悔值選址點(diǎn)。

首先,考慮xk選在頂點(diǎn)處的情形。根據(jù)前面的分析(引理8、定理1) 可知,在O(n3) 時(shí)間可以得到F(X(xk),s)(對(duì)于所有xk∈V和所有s∈D(xk)),在O(mn4)時(shí)間可以得到F(X(xopt(s)),s)(對(duì)于所有s∈)。若xk選在vi∈V,對(duì)于所有s∈D(vi),R(X(vi),s) 通過(guò)O(n) 時(shí)間可得,Rmax(X(vi))=通 過(guò)O(n) 時(shí) 間 可得。因此,對(duì)于所有的vi∈V,Rmax(X(vi)) 通過(guò)O(n2) 時(shí)間可得。如果對(duì)于任意vi∈V,有Rmax(X(v*)) ≤Rmax(X(vi)),則X(v*) 為xk選在頂點(diǎn)時(shí)最大后悔值最小的避難點(diǎn)集。因此,可得引理14。

引理14X(v*) 和Rmax(X(v*)) 可通過(guò)O(mn4) 時(shí)間得到。

接下來(lái),需要考慮xk選在邊e=(vp,vq) 上的情形。由敏感點(diǎn)的定義可以將邊e=(vp,vq) 分為O(n) 個(gè)區(qū)間,而且對(duì)于所有xk∈(ci,ci+1](0 ≤i≤t),D(xk) 是一樣的。所以當(dāng)xk∈(ci,ci+1]時(shí),要得到Rmax(X(xk))只需考慮D(xk)中的O(n) 個(gè)場(chǎng)景,記為{s1,s2,…,sn}。例如,圖G中原有一個(gè)避難點(diǎn)x1,現(xiàn)在增加一個(gè)避難點(diǎn)x2,且x2選在邊e=(vp,vq)上時(shí),在場(chǎng)景s下,令R(xi,s)=F(xi,s)-F(X(xopt(s)),s)(i=1,2),則R(X(x2),s)=max{R(x1,s),R(x2,s)}。當(dāng)x2∈(ci,ci+1]時(shí),在場(chǎng)景s下,R(x1,s)為定值,R(x2,s)為分段線性函數(shù)。那么x2∈(ci,ci+1]時(shí),Rmax(X(x2)) 的結(jié)構(gòu)如圖5 所示,圖中不同線型代表不同場(chǎng)景,粗線表示最大后悔值。

圖5 x2∈(ci,ci+1]時(shí)最大后悔值Rmax(X(x2))的結(jié)構(gòu)示意圖Figure 5 Illustration of Rmax(X(x2)) where x2∈(ci,ci+1]

由于R(X(xk),s)=F(X(xk),s)-F(X(xopt(s)),s),根據(jù)前面的分析(引理9、引理10) 可知,在O(mn3) 時(shí)間可以得到F(X(xk),s)(對(duì)于所有xk∈和所有s∈D(xk)),F(X(xopt(s)),s)(對(duì)于所有s∈D) 可在O(m2n4) 時(shí)間求得(引理13)。那么R(X(xk),sj) (1 ≤j≤n) 通過(guò)O(n) 時(shí)間可得。記z*i∈(ci,ci+1]表示對(duì)于任意xk∈(ci,ci+1]都有≤Rmax(X(xk))。那么和可以通過(guò)建立線性規(guī)劃模型求解。設(shè)H為變量,建立線性規(guī)劃模型如下:

所以當(dāng)xk∈(ci,ci+1]時(shí),對(duì)于所有s∈D(xk),通過(guò)O(n)時(shí)間可得。因?yàn)檫卐=(vp,vq) 包含O(n)個(gè)區(qū)間,所以,對(duì)于邊e=(vp,vq) 和所有s∈D(xk),通過(guò)O(n2) 的時(shí)間可得。

引理15對(duì)所有邊e∈E,可以通過(guò)O(m2n4) 時(shí)間得到。

定理2一般網(wǎng)絡(luò)圖中,就近原則下新增應(yīng)急避難點(diǎn)的魯棒選址問(wèn)題可以通過(guò)O(m2n4) 時(shí)間求解。

至此,一般圖上新增應(yīng)急避難點(diǎn)的最小最大后悔選址方案的求解算法歸結(jié)如表2 所示。

表2 最小最大后悔選址方案求解算法Table 2 The minimax regret sink location algorithm

3 數(shù)值算例分析

這部分先給出一個(gè)數(shù)值算例并按步驟求解,以此展示本文多項(xiàng)式算法的求解過(guò)程。之后,基于權(quán)重區(qū)間的組距進(jìn)行了敏感性分析,探討最大完成時(shí)間的最大后悔值與不同頂點(diǎn)權(quán)重組距之間的關(guān)系。此外,采用各個(gè)頂點(diǎn)權(quán)重區(qū)間的中值(平均分布下的期望權(quán)重)作為各頂點(diǎn)的權(quán)重值進(jìn)行選址,進(jìn)一步比較中值場(chǎng)景下最優(yōu)選址的最大后悔值與最小最大后悔值之間的關(guān)系。

3.1 算法求解示例

如圖6 所示,一般網(wǎng)絡(luò)圖G=(V,E) 中包含9 個(gè)頂點(diǎn),V={v1,v2,v3,v4,v5,v6,v7,v8,v9}。圖中每條邊的長(zhǎng)度見(jiàn)標(biāo)注在邊上,|E|=17。圖中各頂點(diǎn)的權(quán)重Wi=(1 ≤i≤9) 見(jiàn)各個(gè)頂點(diǎn)旁的區(qū)間值。圖G中已有兩個(gè)避難點(diǎn)x1和x2,x1位于頂點(diǎn)v6處;x2位于邊(v4,v5) 上,其與頂點(diǎn)v4的距離為5。要在圖G中再增加一個(gè)避難點(diǎn)x3使得最大完成時(shí)間的最大后悔值最小化。設(shè)單位權(quán)重在各路段上移動(dòng)單位距離所需的時(shí)間τ=1,每條邊具有相同的通行能力c,且c=1。算例分兩部分求解該問(wèn)題。首先找到所有的可能最壞場(chǎng)景,并計(jì)算各個(gè)可能最壞場(chǎng)景下的最優(yōu)選址;然后分別計(jì)算新增應(yīng)急避難點(diǎn)在頂點(diǎn)和邊上的最優(yōu)選址,最后比較兩者最優(yōu)后悔值的大小,確定整體最大后悔值最小的選址。

圖6 一般網(wǎng)絡(luò)示意圖-1Figure 6 Example 1 of a general network

(1)計(jì)算所有可能最壞場(chǎng)景下的最優(yōu)選址及撤退時(shí)間

首先,根據(jù)Floyd-Warshall 算法得到圖G中任意兩點(diǎn)之間的最短路徑。然后,找到每個(gè)頂點(diǎn)初始選擇的避難點(diǎn)和最短路徑(如表3 所示)。最后,通過(guò)三步計(jì)算找到最優(yōu)避難點(diǎn)和其對(duì)應(yīng)的撤離完成時(shí)間:①找到邊上的敏感點(diǎn);② 找到所有的可能最壞場(chǎng)景;③計(jì)算所有可能最壞場(chǎng)景下的最優(yōu)避難點(diǎn)及撤離完成時(shí)間。

通過(guò)表3,可以看到原來(lái)各個(gè)頂點(diǎn)選擇的應(yīng)急避難點(diǎn)及對(duì)應(yīng)的疏散路徑。其中選擇應(yīng)急避難點(diǎn)x1的頂點(diǎn)為{v1,v2,v3,v6,v8,v9},選擇應(yīng)急避難點(diǎn)x2的頂點(diǎn)為{v4,v5,v7}。

表3 各頂點(diǎn)初始選擇的避難點(diǎn)和最短路徑Table 3 The original sink point and evacuation route of each vertex

表4 給出了當(dāng)x3選擇不同位置時(shí),網(wǎng)絡(luò)圖被劃分為不同樹圖的分界點(diǎn)(稱敏感點(diǎn))。相鄰敏感點(diǎn)之間最終形成的樹圖結(jié)構(gòu)是一樣的。

表4 圖G 中各邊上的敏感點(diǎn)Table 4 The sensitive points of G

表5 列出了所有可能的最壞場(chǎng)景。在該算例中,最終的可能最壞場(chǎng)景有12 個(gè),即當(dāng)x3選在不同位置時(shí),使其后悔值最大的必然是其中一個(gè)場(chǎng)景。

表5 所有的可能最壞場(chǎng)景Table 5 The potential worst case scenarios

表6 表示所有可能最壞場(chǎng)景下的最優(yōu)選址對(duì)應(yīng)的撤離完成時(shí)間,當(dāng)x3選在不同位置時(shí),不同最壞場(chǎng)景下的選址撤退時(shí)間與該場(chǎng)景下最優(yōu)選址撤退時(shí)間之差則為后悔值。

表6 所有可能最壞場(chǎng)景下的最優(yōu)選址對(duì)應(yīng)的撤離完成時(shí)間Table 6 Optimal maximum completion times under potential worst case scenarios

(2)最大后悔值最小的避難點(diǎn)選址

把最壞場(chǎng)景限制在一個(gè)有限集合內(nèi),則可以計(jì)算x3選在不同位置時(shí)各個(gè)最壞場(chǎng)景下的后悔值,找出最大后悔值最小的位置?？赡艿倪x址位置分為兩部分計(jì)算:

①當(dāng)x3位于頂點(diǎn)時(shí),通過(guò)計(jì)算每個(gè)場(chǎng)景下的后悔值,從而得到各頂點(diǎn)處的最大后悔值 (如表7 所示)。因此,由表7可得最大后悔值最小的避難點(diǎn)位于頂點(diǎn)v4處,其對(duì)應(yīng)的最大后悔值為12。

表7 各頂點(diǎn)處的最大后悔值Table 7 The maximum regret of vertex location

② 當(dāng)x3位于邊上時(shí),邊上的敏感點(diǎn)將每條邊分為若干個(gè)區(qū)間,在每個(gè)區(qū)間內(nèi)通過(guò)線性規(guī)劃的方法得到所有場(chǎng)景下最大后悔值最小的點(diǎn)z和其對(duì)應(yīng)的最大后悔值(如表8 所示)。因此,由表8 可得最大后悔值最小的避難點(diǎn)位于邊(v4,v7) 上,其與頂點(diǎn)v4距離為2.5,對(duì)應(yīng)的最大后悔值為9.5。

表8 各邊所有場(chǎng)景下最大后悔值最小點(diǎn)zTable 8 The minimax regret locations of edges

通過(guò)比較表7 和表8 可以看出,圖G中使得最大后悔值最小的避難點(diǎn)x3應(yīng)當(dāng)位于邊(v4,v7) 上,其與頂點(diǎn)v4距離為2.5,對(duì)應(yīng)的最大后悔值為9.5。

3.2 敏感性分析算例

這部分主要分析頂點(diǎn)權(quán)重的變化對(duì)選址結(jié)果的影響。具體包括:分析了三種不同組距變化情形下,最大完成時(shí)間的最大后悔值隨頂點(diǎn)權(quán)重組距的變化情況;采用權(quán)重中值作為期望意義下的權(quán)重,分析該場(chǎng)景下最優(yōu)選址方案與最小最大后悔選址方案的變化差異。以圖7 所示的網(wǎng)絡(luò)圖為例,圖中共有15 個(gè)頂點(diǎn),各邊上的數(shù)字表示該邊的權(quán)重(長(zhǎng)度);圖中已有兩個(gè)應(yīng)急避難點(diǎn),其中x1位于頂點(diǎn)v2上,x2位于邊(v4,v7) 的中點(diǎn)。由于城市發(fā)展擴(kuò)張,現(xiàn)需要在該網(wǎng)絡(luò)圖中新增一個(gè)應(yīng)急避難點(diǎn)以使得新的最大完成時(shí)間的最大后悔值最小。

圖7 一般網(wǎng)絡(luò)示意圖-2Figure 7 Example 2 of a general network

(1)限制最大組距的情形

稱di=為頂點(diǎn)vi的對(duì)應(yīng)的權(quán)重組距;稱dmax=為最大組距。在這部分算例中,在不同的最大組距dmax限制下,為所有頂點(diǎn)隨機(jī)生成權(quán)重區(qū)間(取整數(shù)),分別計(jì)算其對(duì)應(yīng)的最小最大后悔值,計(jì)算結(jié)果如圖8 所示。

圖8 限制最大組距的最小最大后悔值變化示意圖Figure 8 The minimax regret values with different dmax

根據(jù)算例結(jié)果可以看出,最小最大后悔值不會(huì)隨著最大組距的增大而增大,即單純的控制最大組距并不能有效的控制最小最大后悔值。

(2)權(quán)重組距相同的情形

在這部分算例中,各個(gè)頂點(diǎn)的權(quán)重組距相同,即對(duì)所有的頂點(diǎn)vi都有di=d,但各個(gè)頂點(diǎn)權(quán)重區(qū)間是不同的(隨機(jī)生成)。在權(quán)重組距d變化時(shí),分別計(jì)算對(duì)應(yīng)的最小最大后悔值的變化;同時(shí),假設(shè)采用各頂點(diǎn)權(quán)重區(qū)間的中值作為該頂點(diǎn)期望意義下的權(quán)重估計(jì),計(jì)算期望的最優(yōu)選址方案的最大后悔值。結(jié)果如圖9 所示。

圖9 不同組距下的最小最大后悔值及期望最優(yōu)選址的最大后悔值變化示意圖Figure 9 The minimax regret values and the maximum regtret of expected optimal locations with different d

在各點(diǎn)權(quán)重組距相同的情形下,最小最大后悔值隨著組距的增加而增大,采用區(qū)間中值作為頂點(diǎn)權(quán)重時(shí),最優(yōu)選址方案對(duì)應(yīng)的最大后悔值也是隨著組距的增大而增大。通過(guò)對(duì)比最小最大后悔值與期望最優(yōu)選址的最大后悔值可以發(fā)現(xiàn),隨著組距的減小,兩者的差距也越來(lái)越小。

(3)權(quán)重組距不同的情形

圖10 不同組距擴(kuò)大值的最小最大后悔值及期望最優(yōu)選址的最大后悔值變化示意圖Figure 10 The minimax regret values and the maximum regtret of expected optimal locations with different dexp

在區(qū)間權(quán)重組距不同的情形下,當(dāng)所有的權(quán)重組距同步增大時(shí),最小最大后悔值也逐步增大。通過(guò)對(duì)比最小最大后悔值與期望最優(yōu)選址對(duì)應(yīng)的最大后悔值可以發(fā)現(xiàn),隨著權(quán)重組距的減小,兩者的差距也越來(lái)越小。

通過(guò)以上三組算例分析可知,只優(yōu)化最大組距并不能有效的減小最小最大后悔值,即關(guān)注于變化最大的疏散點(diǎn)的權(quán)重估計(jì)并不是好的方向,這是由于最小最大后悔值對(duì)應(yīng)的最壞場(chǎng)景中不一定包含最大組距對(duì)應(yīng)的頂點(diǎn);但是,縮小所有頂點(diǎn)權(quán)重的組距則能夠有效的減小最小最大后悔值,這是由于所有權(quán)重區(qū)間擴(kuò)大后必然包括了未擴(kuò)前所有的可能場(chǎng)景,也即包括了其最大后悔值場(chǎng)景。同時(shí),當(dāng)所有權(quán)重組距相對(duì)較小時(shí),采用權(quán)重區(qū)間的中間值(權(quán)重平均分布的期望值)作為權(quán)重估計(jì)得到的最優(yōu)選址的后悔值與最小最大后悔值接近,而當(dāng)權(quán)重組距較大時(shí),則兩者差距明顯;根據(jù)這個(gè)結(jié)果,在進(jìn)行疏散點(diǎn)的權(quán)重估計(jì)時(shí),達(dá)到一定的估計(jì)區(qū)間范圍即可,不必一味地追求精準(zhǔn)權(quán)重?cái)?shù)據(jù),在疏散點(diǎn)人流變化不太大的情況下,直接利用經(jīng)驗(yàn)估計(jì)值作為該疏散點(diǎn)的權(quán)重也可以取得較好的效果。

4 結(jié)論

本文基于就近原則研究了新增應(yīng)急避難點(diǎn)的選址問(wèn)題。針對(duì)該問(wèn)題,先通過(guò)敏感點(diǎn)的尋找,把一般圖分解成基于不同敏感點(diǎn)的樹圖;而后分析各個(gè)樹圖的性質(zhì),找到所有的可能最壞場(chǎng)景;基于所有的可能最壞場(chǎng)景,找到避難點(diǎn)落在頂點(diǎn)時(shí)的最小最大后悔值選址點(diǎn),采用線性規(guī)劃的方法求解各條邊上的最小最大后悔值選址點(diǎn),最后比較得到整體的最小最大后悔值選址點(diǎn)。針對(duì)權(quán)重確定的情形,給出了計(jì)算復(fù)雜度為O(mn2) 的多項(xiàng)式求解算法;針對(duì)權(quán)重處于區(qū)間值的情形,設(shè)計(jì)了計(jì)算復(fù)雜度為O(m2n4) 的多項(xiàng)式求解算法。

通過(guò)數(shù)值算例分析可知(1)如果要達(dá)到有效減小最小最大后悔值的目標(biāo),只控制最大組距不能達(dá)到預(yù)期效果,即通過(guò)縮小單個(gè)權(quán)重的組距并不能有效的減小目標(biāo)值,只能通過(guò)同時(shí)縮小所有頂點(diǎn)權(quán)重才能有效達(dá)成目標(biāo);(2)當(dāng)權(quán)重組距較小時(shí),用頂點(diǎn)權(quán)重區(qū)間的中間值替代區(qū)間權(quán)重,采用求解速度更快的確定性求解算法,可獲得較好的效果;而當(dāng)組距較大時(shí),采用確定性求解算法求解,獲得的結(jié)果與最優(yōu)解差距較大,同時(shí)差距會(huì)隨著組距的增大而增大。

由于新增多個(gè)應(yīng)急設(shè)施問(wèn)題是NP-難的,因此只能設(shè)計(jì)近似算法進(jìn)行求解。在新增設(shè)施數(shù)量較小時(shí),可結(jié)合本文對(duì)一般圖的分解性質(zhì),基于組合數(shù),采用本文的求解思想進(jìn)行求解。在后續(xù)的研究中,可以針對(duì)道路通行能力不同的情形展開研究,優(yōu)化目標(biāo)除了考慮最大完成避難時(shí)間外,也將考慮各個(gè)應(yīng)急避難點(diǎn)的負(fù)載均衡。