環(huán)形路上可分流的多避難點選址模型及算法

馬冰玉, 李紅梅, 羅太波

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

0 引言

近年來,地震、洪水、爆炸等重大突發(fā)公共事件頻繁發(fā)生,造成了嚴重的人員傷亡。在災(zāi)難發(fā)生時,為最大限度減少人員傷亡,應(yīng)使所有避難者在盡量短的時間內(nèi)完成避難。應(yīng)急避難點的位置直接影響疏散效率。有效的選址策略不僅需要考慮道路的容量和疏散過程中的堵塞時間成本,還需考慮路網(wǎng)結(jié)構(gòu)特征的影響。已有的應(yīng)急避難點選址研究大部分集中在路圖和樹圖,而作為大部分城市道路的重要組成部分,環(huán)形路目前只受到極少學者的關(guān)注。

關(guān)于環(huán)形路上的選址問題目前研究較少,且已有研究都假設(shè)同一頂點的避難者只能疏散到相同避難點(即合流模式)。在實際疏散過程中,為提高疏散效率,當某一頂點的避難人數(shù)過多時,可能需要將同一頂點的避難者分別疏散到不同避難點。因此,本文基于同一頂點避難者可疏散到不同避難點的假設(shè)(即分流模式),考慮道路容量和疏散過程中動態(tài)堵塞的影響,研究環(huán)形路上k個避難點的選址問題,以最大完成時間最小為目標。

1 問題描述與模型構(gòu)建

給定一個環(huán)形路C=(V,E),其中V={v1,v2,…,vn}為頂點集,假設(shè)所有頂點按順時針方向依次排列;E={e1,e2,…,en}為邊集,對任意邊ei(1≤i≤n)有ei=(vi,vi+1),特別地,i=n時,en=(vn,v1)。定義l(ei)∈R+為ei的長度;定義w(vi)∈R+為vi的權(quán)重,表示位于該頂點的待疏散人數(shù);假設(shè)所有的道路容量相同,即單位時間內(nèi)允許進入ei的最大權(quán)重相同,記為c∈R+;定義τ∈R+為環(huán)形路上單位權(quán)重移動單位距離所需的時間。假設(shè)避難點只能落在頂點,本文要求在環(huán)形路上確定k(1≤k

記C(vi,vj)為從vi起按順時針方向到vj的路徑,本文稱為子環(huán)路。對C(vi,vj)任意兩點vg,vh,設(shè)vg位于vh順時針方向,記為vh

圖1 子環(huán)路與虛擬點示意圖

性質(zhì)1以最大完成時間最小為目標,C上權(quán)重向避難點疏散時,所有疏散路徑都不交叉。

性質(zhì)2任意給定C(xl,xl+1),劃分點有且僅有兩種情形:

(1)當vg所有權(quán)重按逆時針疏散,且vg+1所有權(quán)重按順時針疏散,僅存在兩個劃分點,即dl,1=vg,dl,2=vg+1;

(2)當vg權(quán)重同時按順時針和逆時針疏散,僅有一個劃分點,即dl,3=vg。

θ-(xl,xl+1,ul)=max{θ-(xl,xl+1,ul,vh)|vh∈(xl,dl)}

(1)

(2)

θ+(xl,xl+1,ul) =max{θ+(xl,xl+1,ul,vh)|vh∈(dl,xl+1)}

(3)

(4)

因此,記θ(xl,xl+1,ul)為C(xl,xl+1)按ul的劃分分別將權(quán)重疏散到xl,xl+1的最大完成時間,簡稱避難時間,有

θ(xl,xl+1,ul)=max{θ-(xl,xl+1,ul),θ+(xl,xl+1,ul)}

(5)

x=(x1,x2,…,xk)和u=(u1,u2,…,uk)給定時,記θ(x,u)為C按u的劃分將權(quán)重疏散到x的避難時間,即

θ(x,u)=max{θ(xl,xl+1,ul)|1≤l≤k}

(6)

綜上,C上求解k個避難點的選址問題為

(7)

分析上述模型構(gòu)建過程,將求解C上k個避難點選址問題分解為確定若干個C(xl,xl+1)劃分情景的問題,其中1≤l≤k,即通過確定子環(huán)路C(xl,xl+1)的最優(yōu)劃分點及相應(yīng)的最優(yōu)劃分權(quán)重,使得C(xl,xl+1)避難時間最小。

2 子環(huán)路C(xl,xl+1)劃分情景的確定

給定C(xl,xl+1),記θopt(xl,xl+1)為C(xl,xl+1)的最優(yōu)避難時間,則有

(8)

引理2給定C(xl,xl+1),θopt(xl,xl+1)存在唯一解。

由引理1和2,可直接得到以下引理。

合流模式中,給定C(xl,xl+1),記φ(xl,vg)為C(xl,vg)的權(quán)重按逆時針方向疏散到xl的最大完成時間,有

φ(xl,vg)=max{φ(xl,vg-1)+w(vg)/c,L(xl,vg)τ+w(vg)/c}

(9)

vg=xl時,φ(xl,vg)=0;記φ(vg+1,xl+1)為C(vg+1,xl+1)的權(quán)重按順時針方向疏散到xl+1的最大完成時間,有

φ(vg+1,xl+1)=max{φ(vg+2,xl+1)+w(vg+1)/c,L(vg+1,xl+1)τ+w(vg+1)/c}

(10)

vg+1=xl+1時,φ(vg+1,xl+1)=0。記φopt(xl,xl+1)為C(xl,xl+1)最優(yōu)避難時間,則

(11)

(12)

根據(jù)上式可得如下關(guān)于最優(yōu)解性質(zhì)。

性質(zhì)4給定C(xl,xl+1),設(shè)α*為公式(12)中α的解,則

根據(jù)以上引理和性質(zhì),求解C(xl,xl+1)劃分情景的確定問題有求解算法A1:

步驟1不妨令xl=vp,xl+1=vq,在合流模式下,令vg按順時針順序依次取vp,vp+1,…,vq-1,計算φ(xl,vg);并令vg按逆時針順序依次取vq,vq-1,…,vp+1,計算φ(vg,xl+1)。

定理1根據(jù)算法A1,C(xl,xl+1)上劃分情景的確定問題可在O(n)內(nèi)求解。

3 k個避難點選址問題的算法設(shè)計

在求解C上k個避難點的選址問題時,若k=1,可在算法A1的基礎(chǔ)上進行求解;若k>1,可設(shè)計動態(tài)規(guī)劃算法進行求解。當k=1時,由于避難點只位于頂點上,所以x的位置最多存在n種可能。通過比較每一種可能下的避難時間,選擇最小值為C的最優(yōu)避難時間,最小值對應(yīng)頂點為最優(yōu)避難點。

定理2環(huán)路C上1個避難點的選址問題可在O(n2)時間內(nèi)求解。

(13)

遞推公式的邊界條件表示為:

(14)

步驟1令xl和xl+1為C上任意一點,根據(jù)算法A1,計算求得所有C(xl,xl+1)的最優(yōu)劃分情景和最優(yōu)避難時間。

定理3根據(jù)算法A2,環(huán)路C上k(k>1)個避難點的選址問題可在O(kn3)時間求解。

4 數(shù)值算例

首先隨機生成一個環(huán)形路,給出相應(yīng)的計算過程展示算法A2的關(guān)鍵步驟;之后在不同的k值下,比較合流與分流模式對最大疏散完成時間的影響。

4.1 算法求解示例

給定C=(V,E),如圖3所示。圖中內(nèi)圈數(shù)字表示對應(yīng)頂點權(quán)重w(vi),外圈數(shù)字表示對應(yīng)邊的路長l(ei);假設(shè)道路容量c=1,通行速度τ=1。在分流模式下,要求在環(huán)形路上確定5個避難點位置,使最大疏散完成時間最小。

圖3 環(huán)形路示意圖

圖4 環(huán)形路最優(yōu)解示意圖

4.2 合流與分流模式的對比分析

在這部分算例中,針對不同的k(1～10)值,分別計算合流模式與分流模式對應(yīng)的最優(yōu)選址方案以及最大完成時間。結(jié)果表明對于任意的避難點數(shù)量k,分流模式下的最大疏散完成時間都優(yōu)于合流模式下的最大疏散完成時間。與合流模式相比,當避難點數(shù)量較少時,能被劃分的點也相對較少,因此改進的效果有限;同樣,當避難點數(shù)量較多時,由于大部分權(quán)重較大的點被選做避難點,導致劃分點的權(quán)重較小,因此改進的效果也相對較小;而當避難點的數(shù)量適中時,也即在算例中避難點數(shù)量為6,7,8時,分流所帶來的效率提升最為顯著。

統(tǒng)計在10次試驗中所有頂點被選為避難點或劃分點的次數(shù)后發(fā)現(xiàn),在所有的最優(yōu)選址方案中,大部分權(quán)重較大的頂點被選為避難點,或者其權(quán)重被劃分去往不同的避難點。頂點v13被選為避難點的次數(shù)最多,達到7次,其次是v10(6次)和v6(5次);其中v13的權(quán)重是所有頂點權(quán)重中最大的。被選為劃分點次數(shù)最多的是v4,v7和v12,均達到5次。由于最大疏散完成時間受到所有頂點權(quán)重分布情況以及道路情況的綜合影響,通過頂點權(quán)重分布與頂點被選為避難點次數(shù)和頂點被選為劃分點次數(shù)的折線關(guān)系圖可知,避難點選擇過程中對權(quán)重更大的頂點有比較一致的傾向性,即存在頂點權(quán)重越大該頂點被選為避難點的次數(shù)越多這一趨勢,但這個傾向性在劃分點的選擇過程中并不具備。

5 結(jié)論

已有的應(yīng)急避難點選址問題相關(guān)研究多假設(shè)同一頂點的避難者只能經(jīng)由相同的疏散路徑疏散到相同的避難點,而該假設(shè)會影響實際中的疏散效率。本文放寬該假設(shè),允許同一頂點的避難者經(jīng)不同路徑疏散到不同避難點,考慮道路容量和疏散過程中的堵塞成本,研究了環(huán)形路上的k-避難點選址問題。通過將環(huán)形路上的選址問題等價為有限個路徑上的選址問題,并結(jié)合動態(tài)規(guī)劃思想,本文給出了時間復雜度為O(kn3)的求解算法。進一步通過數(shù)值分析可知,由于分流模式能夠把權(quán)重較大頂點對應(yīng)的避難者派往不同的避難點,因此相較于合流模式,分流模式能夠有效的提高疏散效率。相關(guān)的理論模型和算法為實際中的避難點規(guī)劃提供了一定的理論指導。在災(zāi)害發(fā)生時,由于各個頂點的人數(shù)很難準確獲得,后期的研究將考慮權(quán)重不確定的魯棒優(yōu)化模型。