馬冰玉, 李紅梅, 羅太波

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

0 引言

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

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

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

給定一個環(huán)形路C=(V,E),其中V={v1,v2,…,vn}為頂點(diǎn)集,假設(shè)所有頂點(diǎn)按順時針方向依次排列;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)重,表示位于該頂點(diǎn)的待疏散人數(shù);假設(shè)所有的道路容量相同,即單位時間內(nèi)允許進(jìn)入ei的最大權(quán)重相同,記為c∈R+;定義τ∈R+為環(huán)形路上單位權(quán)重移動單位距離所需的時間。假設(shè)避難點(diǎn)只能落在頂點(diǎn),本文要求在環(huán)形路上確定k(1≤k

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

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

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

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

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

(2)當(dāng)vg權(quán)重同時按順時針和逆時針疏散,僅有一個劃分點(diǎ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個避難點(diǎn)的選址問題為

(7)

分析上述模型構(gòu)建過程,將求解C上k個避難點(diǎn)選址問題分解為確定若干個C(xl,xl+1)劃分情景的問題,其中1≤l≤k,即通過確定子環(huán)路C(xl,xl+1)的最優(yōu)劃分點(diǎn)及相應(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,計(jì)算φ(xl,vg);并令vg按逆時針順序依次取vq,vq-1,…,vp+1,計(jì)算φ(vg,xl+1)。

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

3 k個避難點(diǎn)選址問題的算法設(shè)計(jì)

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

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

(13)

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

(14)

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

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

4 數(shù)值算例

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

4.1 算法求解示例

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

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

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

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

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

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

5 結(jié)論

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