環形路上可分流的多避難點選址模型及算法

馬冰玉, 李紅梅, 羅太波

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

0 引言

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

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

1 問題描述與模型構建

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

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

圖1 子環路與虛擬點示意圖

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

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

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

(2)當vg權重同時按順時針和逆時針疏散,僅有一個劃分點,即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的劃分分別將權重疏散到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的劃分將權重疏散到x的避難時間,即

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

(6)

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

(7)

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

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

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

(8)

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

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

合流模式中,給定C(xl,xl+1),記φ(xl,vg)為C(xl,vg)的權重按逆時針方向疏散到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)的權重按順時針方向疏散到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)最優避難時間,則

(11)

(12)

根據上式可得如下關于最優解性質。

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

根據以上引理和性質,求解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根據算法A1,C(xl,xl+1)上劃分情景的確定問題可在O(n)內求解。

3 k個避難點選址問題的算法設計

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

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

(13)

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

(14)

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

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

4 數值算例

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

4.1 算法求解示例

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

圖3 環形路示意圖

圖4 環形路最優解示意圖

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

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

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

5 結論

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