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

馬冰玉, 李紅梅, 羅太波

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

0 引言

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

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

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

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

記C(vi,vj)為從vi起按順時(shí)針?lè)较虻絭j的路徑,本文稱為子環(huán)路。對(duì)C(vi,vj)任意兩點(diǎn)vg,vh,設(shè)vg位于vh順時(shí)針?lè)较?記為vh

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

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

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

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

(2)當(dāng)vg權(quán)重同時(shí)按順時(shí)針和逆時(shí)針疏散,僅有一個(gè)劃分點(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的最大完成時(shí)間,簡(jiǎn)稱避難時(shí)間,有

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

(5)

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

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

(6)

綜上,C上求解k個(gè)避難點(diǎn)的選址問(wèn)題為

(7)

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

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

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

(8)

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

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

合流模式中,給定C(xl,xl+1),記φ(xl,vg)為C(xl,vg)的權(quán)重按逆時(shí)針?lè)较蚴枭⒌絰l的最大完成時(shí)間,有

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

(9)

vg=xl時(shí),φ(xl,vg)=0;記φ(vg+1,xl+1)為C(vg+1,xl+1)的權(quán)重按順時(shí)針?lè)较蚴枭⒌絰l+1的最大完成時(shí)間,有

φ(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時(shí),φ(vg+1,xl+1)=0。記φopt(xl,xl+1)為C(xl,xl+1)最優(yōu)避難時(shí)間,則

(11)

(12)

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

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

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

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

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

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

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

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

(13)

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

(14)

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

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

4 數(shù)值算例

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

4.1 算法求解示例

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

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

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

4.2 合流與分流模式的對(duì)比分析

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

統(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次。由于最大疏散完成時(shí)間受到所有頂點(diǎn)權(quán)重分布情況以及道路情況的綜合影響,通過(guò)頂點(diǎn)權(quán)重分布與頂點(diǎn)被選為避難點(diǎn)次數(shù)和頂點(diǎn)被選為劃分點(diǎn)次數(shù)的折線關(guān)系圖可知,避難點(diǎn)選擇過(guò)程中對(duì)權(quán)重更大的頂點(diǎn)有比較一致的傾向性,即存在頂點(diǎn)權(quán)重越大該頂點(diǎn)被選為避難點(diǎn)的次數(shù)越多這一趨勢(shì),但這個(gè)傾向性在劃分點(diǎn)的選擇過(guò)程中并不具備。

5 結(jié)論

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