路段通行能力不同的避難點(diǎn)選址模型及算法

趙 容，劉克艷，任佩瑜

(四川大學(xué)商學(xué)院，四川 成都 610065)

路段通行能力不同的避難點(diǎn)選址模型及算法

趙 容，劉克艷，任佩瑜

(四川大學(xué)商學(xué)院，四川 成都 610065)

研究應(yīng)對(duì)突發(fā)事件的避難點(diǎn)選址問題。假定一條直線型動(dòng)態(tài)路徑網(wǎng)絡(luò)上有n個(gè)頂點(diǎn)，由n-1條邊相連，每個(gè)頂點(diǎn)有一個(gè)權(quán)重，每條邊有一個(gè)容量。邊的容量表示路段通行能力，是單位時(shí)間內(nèi)允許進(jìn)入該路段的最大聚集量。目標(biāo)是在此網(wǎng)絡(luò)中選擇k個(gè)避難點(diǎn)，并為每個(gè)頂點(diǎn)指定一個(gè)避難點(diǎn)，使得所有頂點(diǎn)的權(quán)重到達(dá)各自避難點(diǎn)的最大時(shí)間最小。首先根據(jù)問題的性質(zhì)，通過建立動(dòng)態(tài)表結(jié)構(gòu)，結(jié)合二分法的思想，在O(nlogn)時(shí)間內(nèi)求解單個(gè)避難點(diǎn)選址問題。然后在此基礎(chǔ)上，針對(duì)k-避難點(diǎn)選址問題，通過更新動(dòng)態(tài)表，結(jié)合動(dòng)態(tài)規(guī)劃方法，設(shè)計(jì)了時(shí)間復(fù)雜度為O(knlogn)的遞歸算法求解。

道路通行能力；動(dòng)態(tài)網(wǎng)絡(luò)；動(dòng)態(tài)規(guī)劃；應(yīng)急管理

1 引言

應(yīng)急設(shè)施選址是應(yīng)急管理中一項(xiàng)極其重要的內(nèi)容，合理的應(yīng)急設(shè)施選址能夠有效預(yù)防和降低突發(fā)事件的危害。Toregas等[1]在1971年首先提出應(yīng)急設(shè)施選址問題，研究如何建立數(shù)量最少的應(yīng)急救援點(diǎn)，在規(guī)定時(shí)間內(nèi)給所有需要應(yīng)急服務(wù)的需求點(diǎn)提供救援。此外還有集合覆蓋模型[2]和絕對(duì)中心點(diǎn)模型[3]等。這些模型都采用靜態(tài)網(wǎng)絡(luò)，只考慮距離因素，而在應(yīng)急疏散過程中，由于道路通行能力的限制，在通往避難點(diǎn)的過程中，受災(zāi)者可能會(huì)因?yàn)槎氯馁M(fèi)大量時(shí)間，此時(shí)到達(dá)避難點(diǎn)的時(shí)間不能簡(jiǎn)單地用權(quán)重與距離的乘積來表示，更應(yīng)考慮道路通行能力等因素。

Cheng等[4]以2011年3月發(fā)生的東日本大地震為研究背景，將動(dòng)態(tài)網(wǎng)絡(luò)應(yīng)用到應(yīng)急避難點(diǎn)選址問題中，相比靜態(tài)網(wǎng)絡(luò)，動(dòng)態(tài)網(wǎng)絡(luò)中的邊有長(zhǎng)度和容量屬性，其中容量表示單位時(shí)間允許通過該邊的最大量。動(dòng)態(tài)網(wǎng)絡(luò)中的避難點(diǎn)選址問題可以描述為：將城市交通網(wǎng)絡(luò)抽象為一個(gè)動(dòng)態(tài)網(wǎng)絡(luò)，網(wǎng)絡(luò)中頂點(diǎn)的權(quán)重對(duì)應(yīng)初始時(shí)刻該點(diǎn)需要疏散的人數(shù)，如某棟建筑里的人數(shù)。網(wǎng)絡(luò)中邊的容量對(duì)應(yīng)路段通行能力，表示單位時(shí)間內(nèi)允許進(jìn)入該路段的最大權(quán)重。

由于緊急避難時(shí)人群密度較大，可以認(rèn)為人群行走速度一致。在各路段通行能力一致時(shí)，受災(zāi)者到達(dá)避難點(diǎn)的時(shí)間由兩部分組成：一是受災(zāi)者通過頂點(diǎn)進(jìn)入路段時(shí)的擁堵時(shí)間；二是行走時(shí)間。問題的目標(biāo)是在這樣的動(dòng)態(tài)網(wǎng)絡(luò)中建立若干避難點(diǎn)，并為每個(gè)頂點(diǎn)指定一個(gè)避難點(diǎn)，使得在災(zāi)害發(fā)生時(shí)所有頂點(diǎn)的權(quán)重能盡快到達(dá)各自的避難點(diǎn)。假設(shè)各頂點(diǎn)的權(quán)重在給定的區(qū)間內(nèi)取值，以疏散完成時(shí)間的最大后悔值最小(Min-max regret)為目標(biāo)，Higashikawa等[5]和Wang Haitao[6]改進(jìn)了文獻(xiàn)[4]中的數(shù)據(jù)結(jié)構(gòu)，求解算法復(fù)雜度由O(nlog2n)降為O(nlogn)。李紅梅[7]、倪冠群[8]、Arumugam[9]將其擴(kuò)展到不確定型2-避難點(diǎn)和不確定型k-避難點(diǎn)選址問題，分別給出了自己的求解算法。隨后Bhattacharya[10]改進(jìn)了前面文獻(xiàn)的算法，針對(duì)最小最大后悔值準(zhǔn)則下的單個(gè)避難點(diǎn)選址問題給出了時(shí)間復(fù)雜度為O(n)的算法，針對(duì)2-避難點(diǎn)選址問題給出了時(shí)間復(fù)雜度為O(nlog4n)的算法，都是目前最優(yōu)的結(jié)果。同時(shí)也有很多學(xué)者將動(dòng)態(tài)路徑網(wǎng)絡(luò)上的避難點(diǎn)選址問題擴(kuò)展到不同的網(wǎng)絡(luò)結(jié)構(gòu)，如樹圖[11]，環(huán)狀圖[12]，方格網(wǎng)[13]和就近原則下的一般網(wǎng)絡(luò)結(jié)構(gòu)[14]。假設(shè)各頂點(diǎn)的權(quán)重是確定的值，以疏散完成時(shí)間最小(Min-max)為目標(biāo)，針對(duì)路徑動(dòng)態(tài)網(wǎng)絡(luò)上的k-避難點(diǎn)選址問題，倪冠群等[15]基于“二分思想”提出了時(shí)間復(fù)雜度為O(nlogkn)的算法，適用于k值比較小的情形，Higashikawa等[16]基于動(dòng)態(tài)規(guī)劃的方法設(shè)計(jì)了時(shí)間復(fù)雜度為O(knlogn)的算法，隨后進(jìn)行優(yōu)化將復(fù)雜度降為O(kn)[17]。針對(duì)樹圖上的單個(gè)避難點(diǎn)選址問題，Mamada等[18]設(shè)計(jì)了時(shí)間復(fù)雜度為O(nlog2n)的算法。

以上研究的基本假設(shè)是各路段通行能力一致。本文考慮各路段通行能力不同的情形。在路徑網(wǎng)絡(luò)上，避難點(diǎn)左右兩邊的權(quán)重互不影響，可以分別計(jì)算左右兩邊的疏散完成時(shí)間，取較大值即為所有權(quán)重的疏散完成時(shí)間。在向避難點(diǎn)疏散的過程中，會(huì)在左右兩邊分別產(chǎn)生一個(gè)最大擁堵點(diǎn)，左右兩邊的疏散完成時(shí)間將由這個(gè)最大擁堵點(diǎn)決定。當(dāng)各路段通行能力相同時(shí)，將避難點(diǎn)向左移動(dòng)(未越過該點(diǎn))左邊最大擁堵點(diǎn)不變，這意味著移動(dòng)避難點(diǎn)后可以在O(1)內(nèi)求得新的疏散完成時(shí)間；而當(dāng)各路段通行能力不同時(shí)，將避難點(diǎn)的向左(右)移動(dòng)時(shí)，兩邊的最大擁堵點(diǎn)的位置也會(huì)隨之變化。這使得上述研究[4-17]中采用的平衡二叉樹的結(jié)構(gòu)不再適用。本文根據(jù)新問題中擁堵點(diǎn)和疏散完成時(shí)間之間的關(guān)系，設(shè)計(jì)由擁堵點(diǎn)序列、與之對(duì)應(yīng)的疏散時(shí)間以及該擁堵點(diǎn)和避難點(diǎn)間路段的最小通行能力構(gòu)成的動(dòng)態(tài)表結(jié)構(gòu)，通過查找動(dòng)態(tài)表求得左右兩邊的疏散完成時(shí)間，然后根據(jù)左右兩邊疏散完成時(shí)間的單調(diào)性，采用二分查找算法求解單個(gè)避難點(diǎn)選址問題?；趯?duì)單個(gè)避難點(diǎn)選址問題的分析，針對(duì)k-避難點(diǎn)選址問題，通過更新動(dòng)態(tài)表，采用動(dòng)態(tài)規(guī)劃算法求解。

2 問題描述與基本模型

給定路徑網(wǎng)絡(luò)P=(V,E)，設(shè)路徑上依次排列有頂點(diǎn)v1,v2,…,vn構(gòu)成頂點(diǎn)集V，頂點(diǎn)vi和vi+1由路段ei連接，所有路段的集合為E={e1,e2,…,en-1}。對(duì)于vi∈V，定義權(quán)重ωi為該頂點(diǎn)的權(quán)重，對(duì)于ei∈E，定義容量ci為該路段的通行能力，表示單位時(shí)間內(nèi)允許流入路段ei的最大權(quán)重。定義τ為權(quán)重在各路段上流動(dòng)單位距離所需的時(shí)間。設(shè)區(qū)間[vi,vj]中有一個(gè)避難點(diǎn)x，各權(quán)重在向避難點(diǎn)疏散的過程中不允許出現(xiàn)交叉流。定義區(qū)間[vi,x]中的疏散點(diǎn)屬于避難點(diǎn)x的左邊，區(qū)間[x,vj]中的疏散點(diǎn)屬于避難點(diǎn)x的右邊。特別地，當(dāng)x=vl時(shí)，vl處的權(quán)重視為立即到達(dá)避難點(diǎn)x。

根據(jù)以上定義，初始時(shí)刻，權(quán)重集中在各頂點(diǎn)處。疏散過程開始時(shí)，所有頂點(diǎn)處的權(quán)重同時(shí)向各自指定的避難點(diǎn)流動(dòng)。這時(shí)首先有了頂點(diǎn)處的權(quán)重進(jìn)入路段的時(shí)間，頂點(diǎn)v處的權(quán)重ω進(jìn)入容量為c的路段的時(shí)間為ω/c。它們?nèi)窟M(jìn)入路段后即變?yōu)榱髁繛閏，總量為ω的權(quán)重，這里的流量表示單位時(shí)間內(nèi)通過路段橫截面的權(quán)重。由于各路段通行能力不同，權(quán)重到達(dá)避難點(diǎn)的時(shí)間除了從頂點(diǎn)處進(jìn)入路段的時(shí)間和行走時(shí)間外，還有第三部分時(shí)間，是權(quán)重從通行能力高的路段進(jìn)入通行能力低的路段時(shí)的擁堵時(shí)間。根據(jù)以上討論，流量為c的權(quán)重ω通過容量為ce的路段e時(shí)，可能出現(xiàn)以下2種情形：

(1)c≤ce。如下圖1中a圖所示，流量為c的權(quán)重ω通過路段e時(shí)不會(huì)遇到堵塞，即沒有等待時(shí)間，所有權(quán)重始終以速度1/τ流動(dòng)，它們通過路段e的時(shí)間為leτ。

圖1 流量為c的權(quán)重ω通過路段e的兩種情形

由以上討論可知，流量為c的權(quán)重ω通過長(zhǎng)度為le、容量為ce的路段e的時(shí)間te可以表示為：

(1)

圖2 權(quán)重ω1到達(dá)避難點(diǎn)x的過程中各路段流量

根據(jù)以上定義，對(duì)于區(qū)間[vi,vj]，用Li(x)表示x左邊的疏散完成的時(shí)間，Rj(x)表示x右邊的疏散完成的時(shí)間，Θi,j(x)表示區(qū)間[vi,vj]中所有的點(diǎn)的疏散完成時(shí)間。

(2)

(3)

Θi,j(x)=max{Li(x)，Rj(x)}

(4)

用x=(x1,…,xk)表示k個(gè)避難點(diǎn)的位置坐標(biāo)，用d=(d1,…,dk-1)表示對(duì)應(yīng)劃分點(diǎn)的角標(biāo)，如下圖3所示，劃分點(diǎn)vdi-1和vdi指定了區(qū)間[vdi-1+1,vdi]中的權(quán)重全部疏散到避難點(diǎn)xi。問題的目標(biāo)是在路徑P上選擇k個(gè)避難點(diǎn)，同時(shí)確定k-1個(gè)劃分點(diǎn)，將頂點(diǎn)集V劃分為k個(gè)子集，使得k個(gè)子集中的所有疏散點(diǎn)到達(dá)各自避難點(diǎn)的最大時(shí)間最小。

圖3 避難點(diǎn)及其劃分點(diǎn)

用Θi(x,d)表示區(qū)間[vdi-1+1,vdi]中的權(quán)重全部到達(dá)避難點(diǎn)xi的時(shí)間，路徑P上所有權(quán)重的疏散完成的時(shí)間則可以表示為

Θ(x,d)=max{Θi(x,d)|i=1,…,k}。路徑P上的k-避難點(diǎn)選址問題可以表示為：

Pk：minmax{Θ(x,d)|x∈Pk,d∈{1,...,n}k-1}

3 單個(gè)避難點(diǎn)選址問題

本節(jié)主要介紹如何在區(qū)間[vi,vj]內(nèi)求解單個(gè)避難點(diǎn)的選址問題。由(4)式可知，此問題可以表示為：

P1：min{Θi,j(x)|x∈[vi,vj]}。

根據(jù)第1節(jié)的描述，首先有如下引理1。

圖4 路段通行能力相同與不同時(shí)圖形比較

引理2Li(x)隨x的增加而增加，Rj(x)隨x的增加而減小。

引理3 問題P1存在唯一解。

證明：由(4)式和引理2可知Θi,j(x)在區(qū)間[vi,vj]內(nèi)是關(guān)于x的凸函數(shù)，所以存在唯一xopt=argmin{Θi,j(x)|x∈[vi,vj]}。

引理4 設(shè)x∈[vi,vj]，若Li(x)≤Rj(x)，則xopt≥x；若Li(x)≥Rj(x)，則xopt≤x。

證明：根據(jù)(4)式和引理2可知，Θi,j(x)是關(guān)于x的凸函數(shù)，當(dāng)Li(x)≥Rj(x)時(shí)，若將x向右移動(dòng)，則Li(x)將繼續(xù)增加，由(4)式可知，Θi,j(x)=Li(x)也將隨之增加，所以xopt≤x。同理可證，若Li(x)≤Rj(x)，則xopt≥x。

引理4表明通過反復(fù)比較Li(vl)和Rj(vl)可將xopt的取值范圍限定在某個(gè)區(qū)間[vk,vk+1]內(nèi)。而在區(qū)間(vk,vk+1)內(nèi)，避難點(diǎn)左右兩邊的最大擁堵點(diǎn)的位置將保持不變，這時(shí)的情形同文獻(xiàn)[4]，可以在O(1)時(shí)間內(nèi)直接求得xopt。

算法A：求TL(i,j)，見表1。

表1 TL(i,j)的算法流程

表2 區(qū)間[vi,vj]的左動(dòng)態(tài)表TL(i,j)

引理5 由動(dòng)態(tài)表TL(i,j)可以在O(logn)時(shí)間內(nèi)求得任意L(i,k)(i≤k≤j)。

綜上，即證由動(dòng)態(tài)表TL(i,j)可在O(logn)時(shí)間內(nèi)求得任意L(i,k)(i≤k≤j)。

定理1：?jiǎn)栴}P1可在O(nlogn)時(shí)間內(nèi)求解。

運(yùn)行一次算法A可得TL(i,j)，同理可在O(nlogn)時(shí)間內(nèi)求得TR(i,j)。由引理5可知，根據(jù)動(dòng)態(tài)表TL(i,j)和TR(i,j)可在O(logn)時(shí)間內(nèi)求得任意L(i,k)和R(k,j)。引理4表明采用二分法求解問題P1時(shí)，需要計(jì)算L(i,k)和R(k,j)的次數(shù)為O(logn)。所以在已求得動(dòng)態(tài)表TL(i,j)和TR(i,j)后，可在O(log2n)時(shí)間內(nèi)求解問題P1。

綜上，即證問題P1可在O(nlogn)時(shí)間內(nèi)求解。

4 k-避難點(diǎn)選址問題

問題Pk滿足最優(yōu)性原理，本節(jié)采用動(dòng)態(tài)規(guī)劃算法進(jìn)行求解。設(shè)區(qū)間[vi,vj]內(nèi)建立的p個(gè)最優(yōu)避難點(diǎn)的位置坐標(biāo)為p維向量x*(p,i,j)，與之對(duì)應(yīng)的最優(yōu)劃分點(diǎn)的角標(biāo)為p-1維向量d*(p,i,j)，它們的最小疏散完成時(shí)間為opt(p,i,j)。根據(jù)以上定義，求解問題Pk即求解opt(k,1,n)。根據(jù)第2節(jié)的討論有如下遞歸表達(dá)式：

(5)

用d(p,i,j)表示表示d*(p,i,j)的第p-1個(gè)值，即第p-1個(gè)和第p個(gè)避難點(diǎn)間的劃分點(diǎn)，同樣x(p,i,j)表示x*(p,i,j)的第p個(gè)值，x(1,d+1,j)表示區(qū)間[vd+1,vj]中的單個(gè)最優(yōu)選址位置，則x*(p+1,i,j)和d*(p+1,i,j)可表示為：

x*(p+1,i,j)=(x*(p,i,d),x(1,d+1,j))

d*(p+1,i,j)=(d*(p,i,j),d(p+1,i,j))

(6)

由引理2可以推出d(p,i,j)和x(p,i,j)隨j的減小而減小，證明同Higashikawa等[17]。

性質(zhì)1 對(duì)2≤p≤k，d(p,i,j-1)≤d(p,i,j)。

性質(zhì)2 對(duì)1≤p≤k，x(p,i,j-1)≤x(p,i,j)。

由第2節(jié)的討論可知，求解單個(gè)避難點(diǎn)選址問題時(shí)，本文所采用的數(shù)據(jù)結(jié)構(gòu)與Higashikawa等[17]不同。同樣這里在求解k-避難點(diǎn)選址問題時(shí)，采用的遞歸順序也與Higashikawa等[17]不同。根據(jù)建立的避難點(diǎn)的個(gè)數(shù)不同將它們分為k層，即1,2,…,k。在每一層采用與Higashikawa等[17]中所述的相反的順序遞歸，即按照opt(1,1,n),…,opt(1,1,1);opt(2,1,n),…,opt(2,1,1);…;opt(k,1,n)的順序求解。根據(jù)遞歸表達(dá)式(5)，每一層都可以由上一層的所有值和opt(1,1,n),…,opt(1,n-1,n)求得。采用這樣的逆序遞歸時(shí)只需計(jì)算一次opt(1,2,n),…,opt(1,n-1,n)，然后在每一層遞歸中都可以用到它們，如此減少了更新的次數(shù)，也減少了更新的方向。由于采用逆序，在每一層內(nèi)更新時(shí)，只需由L(α,β)向2個(gè)方向更新，即L(α-1,β)和L(α,β-1)。具體如下圖5所示。

圖5 由opt(p,1,n)計(jì)算opt(p,1,n-1)示意圖

如圖5所示，用dn表示d(p,1,n)，xn表示x(p,1,n)，dn-1、xn-1同理。由第2節(jié)的討論可知，只要確定了xopt所屬的區(qū)間即可在O(1)時(shí)間內(nèi)求解，而確定xopt所屬區(qū)間的方法是運(yùn)用引理4，通過反復(fù)比較L(i,l)和R(l,j)得到。設(shè)xn屬于區(qū)間[vx[n],vx[n]+1)，xn-1屬于區(qū)間[vx[n-1],vx[n-1]+1)。根據(jù)(5)式，由opt(p,1,n)計(jì)算opt(p,1,n-1)可以通過逐步比較opt(p-1,1,dn)和opt(1,dn+1,n-1)，opt(p-1,1,dn+1)和opt(1,dn+2,n-1)等求得。根據(jù)遞歸順序可知，在計(jì)算第p層時(shí)，所有p-1層的opt(p-1,1,j)已知，只需進(jìn)一步由opt(1,dn+1,n)計(jì)算opt(1,dn+1,n-1)…和opt(1,dn+2,n)…，根據(jù)第2節(jié)的分析，左邊涉及的是由L(dn+1,[xn])更新到L(dn-1+1,[xn-1])。由性質(zhì)1和2可知，dn-1≤dn，xn-1≤xn。所以在整個(gè)計(jì)算過程中L(i,j)只有2個(gè)更新方向，即L(i-1,j)和L(i,j-1)。引理5已表明可由動(dòng)態(tài)表TL(i,j)在O(logn)時(shí)間內(nèi)求得任意L(i,k)。下面主要說明如何由動(dòng)態(tài)表TL(i,j)在O(logn)時(shí)間內(nèi)更新為TL(i-1,j)。

算法B1：由TL(i,j)求TL(i-1,j)，見表3。

表3 TL(i-1,j)的算法流程

根據(jù)以上討論，設(shè)計(jì)如下算法B自下而上地求得opt(k,1,n)、d*(k,1,n)和x*(k,1,n)，即是問題Pk的解。

算法B：求解問題Pk，見表4。

表4 Pk的算法流程

定理2采用遞歸算法B求解問題Pk的時(shí)間復(fù)雜度為O(knlogn)。

證明：第(1)步中，采用算法A建立動(dòng)態(tài)表的時(shí)間復(fù)雜度為O(nlogn)。由定理1的證明可知根據(jù)動(dòng)態(tài)表求解opt(1,1,n)的時(shí)間復(fù)雜度為O(log2n)。由引理2和4可知，x(1,1,n)≤x(1,2,n)，所以按opt(1,2,n),…,opt(1,n-1,n)的順序求解時(shí)至多調(diào)用動(dòng)態(tài)表O(n)次，由引理5可知，通過動(dòng)態(tài)表計(jì)算L(i,j)和R(i,j)的時(shí)間復(fù)雜度為O(logn)。所以求解opt(1,1,n),…,opt(1,n-1,n)的時(shí)間復(fù)雜度為O(nlogn)。同理依次求解opt(1,1,n-1),…,opt(1,1,2)的時(shí)間復(fù)雜度也是O(nlogn)。即證第(1)步的計(jì)算時(shí)間復(fù)雜度為O(nlogn)。

第(2)步中，根據(jù)遞歸表達(dá)式(5)，由前一次循環(huán)得到的opt(p-1,1,n),…,opt(p-1,1,p)和第1步得到的opt(1,1,n),…,opt(1,n-1,n)求解opt(p,1,n)的時(shí)間復(fù)雜度為O(logn)。在依次求解opt(p,1,n),opt(p,1,n-1),…,opt(p,1,p)時(shí)，由性質(zhì)1和2可知：d(p,1,j-1)≤d(p,1,j)，x(p,1,j-1)≤x(p,1,j)。所以d(p,1,j)至多變化n-p次，至多減少n-1，對(duì)于x(p,1,j)所屬的區(qū)間同理。根據(jù)建立的動(dòng)態(tài)表TL(dn+1,[xn])，對(duì)于x(p,1,j)的變化不需更新表，可以直接在表中查找。對(duì)于d(p,1,j)的變化，d(p,1,j)每減少1則需要運(yùn)行算法B1更新一次動(dòng)態(tài)表。所以每一次循環(huán)中動(dòng)態(tài)表TL(dn+1,[xn])需要更新O(n)次，即每一次循環(huán)中更新動(dòng)態(tài)表的時(shí)間復(fù)雜度為O(nlogn)。由引理4可知，d(p,1,j)每減少1需要對(duì)L(dj+1,x[j])和R(x[j],j)進(jìn)行O(1)次比較，所以每一次循環(huán)中需要通過動(dòng)態(tài)表計(jì)算L(i,j)和R(i,j)的次數(shù)為O(n)，即每一次循環(huán)中計(jì)算L(i,j)和R(i,j)的時(shí)間復(fù)雜度為O(nlogn)。第(2)步中有k-1次循環(huán)，即證算法B的第(2)步的時(shí)間復(fù)雜度為O(knlogn)。

綜上，采用遞歸算法B求解問題Pk的時(shí)間復(fù)雜度為O(knlogn)，即證。

本文從理論上擴(kuò)展了動(dòng)態(tài)網(wǎng)絡(luò)中的k-避難點(diǎn)選址問題，在已有的權(quán)重確定、通行能力為1的直線型動(dòng)態(tài)網(wǎng)絡(luò)(動(dòng)態(tài)路徑網(wǎng)絡(luò))中的k-避難點(diǎn)選址問題的基礎(chǔ)上，研究了權(quán)重確定、各路段通行能力為任意常數(shù)的動(dòng)態(tài)路徑網(wǎng)絡(luò)中的k-避難點(diǎn)選址問題。目前針對(duì)權(quán)重確定、通行能力為1的直線型動(dòng)態(tài)網(wǎng)絡(luò)中的k-避難點(diǎn)選址問題的研究中設(shè)計(jì)的求解算法復(fù)雜度分別為O(nlogkn)[15]、O(knlogn)[16]和O(kn)[17]，本文主要在Higashikawa等[17]的基礎(chǔ)上進(jìn)行了拓展，根據(jù)新問題的性質(zhì)，放棄了原有的平衡二叉樹結(jié)構(gòu)，采用一種動(dòng)態(tài)鏈表結(jié)構(gòu)儲(chǔ)存，求解思路仍是儲(chǔ)存擁堵點(diǎn)信息，只是本文因?yàn)楦髀范稳萘坎煌范稳萘繉?duì)最大擁堵點(diǎn)的計(jì)算有影響，所以儲(chǔ)存了決定對(duì)應(yīng)疏散完成時(shí)間的容量值。如此，在采用動(dòng)態(tài)規(guī)劃算法求解k-避難點(diǎn)問題時(shí)，雖然每次迭代更新時(shí)不能同文獻(xiàn)[17]一樣通過一次比較獲得，但根據(jù)動(dòng)態(tài)表建立的序列可以在O(logn)時(shí)間內(nèi)插入新的值。最后本文設(shè)計(jì)的求解k-避難點(diǎn)選址問題的遞歸算法的時(shí)間復(fù)雜度為O(knlogn)。

5 結(jié)語(yǔ)

現(xiàn)有研究避難點(diǎn)選址問題的文獻(xiàn)多沒有考慮道路通行能力及由此帶來的擁堵問題，使得避難點(diǎn)的選址位置在實(shí)際中并不適用。而在考慮道路通行能力的文獻(xiàn)中都假設(shè)各段道路通行能力相同，與實(shí)際的道路情況不符，且缺乏變通。本文在后者的基礎(chǔ)上，放松了各路段通行能力一致的假設(shè)，通過建立關(guān)于最大擁堵點(diǎn)的動(dòng)態(tài)表結(jié)構(gòu)，結(jié)合動(dòng)態(tài)規(guī)劃的方法，解決了在確定型路徑動(dòng)態(tài)網(wǎng)絡(luò)中建立k個(gè)避難點(diǎn)使得路徑上所有權(quán)重到達(dá)各自避難點(diǎn)的最大時(shí)間最小的問題，為后續(xù)研究提供參考。

[1] Toregas C,Swain R,Revelle C,et al.The location of emergency service facilities [J].Operations Research,1971,19(6):1363-1373.

[2] Adel A A,A.White J A.Probabilistic formation of the emergency service location problem [J].Journal of Operational Research Society,1978,29(12):1167-1179.

[3] Shier D,Dearing P.Optimal locations for a class of nonlinear single-facility location problems on a network [J].Operations Research,1983,31(2):292-303.

[4] Cheng S,Higashikawa Y,Katoh N,et al.Minimax regret 1-sink location problems in dynamic path networks [C]//Proceedings of the 10th International Comference on Theory and Applincations of models of Computation Hongkong,China,May 20-22,2013.

[5] Higashikawa Y,Augustine J,Cheng S,et al.Minimax regret 1-sink location problem in dynamic path networks[J].Theoretical Computer Science，2015,24-36.

[6] Wang Haitao.Minmax regret 1-facity location on uncertain path networks [J].European Journal of Operational Research,2014,239(3): 636-643.

[7] Li Hongmei,Xu Yinfeng,Ni Guanqun.Minimax regret vertex 2-sink location problem in dynamic path networks [J].Journal of Combinatorial Optimization,2014.

[8] Ni Guanqun,Xu Yinfeng,Dong Yucheng.Minimax regret k-sink location problem in dynamic path networks [C]//Proceedinys of the 10th International Conference on Algorithmic Aspects in Information and Management,Vancouver,Canada,July 8-11,2014.

[9] Arumugam G,Augustine J,Golin,et al.A polynomial time algorithm for minimax-regret evacuation on a dynamic path [J].Computerscience，2014,588(c):1404-5448.

[10] Bhattacharya B,Kameda T.Improved algorithms for computing minmax regret sinks on dynamic path and tree networks [J].Theoretical Computer Science,2014,607:411-425.

[11] Higashikawa Y,Golin M,Katoh N.Minimax regret sink location problem in dynamic tree networks with uniform capacity [M].2014,8344:125-137.

[12] Xu Xinfeng,Li Hongmei.Minimax regret 1-sink location problem in dynamic cycle networks [J].Information Processing Letters,2015,115(2):163-169.

[13] Naoyuki K,Katoh N.The universally quickest transshipment problem in a certain class of dynamic networks with uniform path-lengths [J].Discrete Applied Mathematics,2014,178:89-100.

[14] Li Hongmei,Xu Yinfeng.Minimax regret 1-sink location problem with accessibility in dynamic general networks [J].European Journal of Operational Research,2015,250(2):360-366.

[15] 倪冠群,徐寅峰,徐久平.考慮道路通行能力的應(yīng)急避難點(diǎn)選址模型及算法 [J].中國(guó)管理科學(xué),2015,23(1):82-88.

[16] Higashikawa Y,Golin M,Katoh N.Multiple sink location problems in dynamic path networks [J].Theoretical Computer Science,2015,607:2-15.

[17] Higashikawa Y,Golin M,Katoh N.Improved algorithms for multiple sink location problems in dynamic path networks [J].Computer Science,2014:1405-2014.

[18] Mamada S,Uno T,Makino K,et al.An algorithm for the optimal sink location problem in dynamic tree networks [J].Discrete Applied Mathematics,2006,154(16):2387-2401.

Abstract： From the viewpoint of disaster prevention from city planning and evacuation planning,it is important to establish effective evacuation planning systems against large scale disasters.Considering the different roads have different capacity,the k-sink location problem in dynamic network with different capacity is proposed.

In our model,each vertex supplies with a certain nonnegative value and each edge has a capacity representing the least upper bound for the units flowing into the edge per unit time.It is found that the time for a vertex weightωto go through the edgeewhich have a capacityceand a lengthleisleτ+ω/ce-ω/c,whereτis a constant representing the time required for traversing the unit distance of per unit weight and c is the flow ofω.Our goal is to findksinks andk-1 divides which minimize the maximum time for all units flowing into the corresponding sink that the divides have provided.First,the 1-sink location problem is analyzed and it is found the monotonicity and unimodality of the evacuation completion time.Then based on some new properties,the linked list data structure is used to store the completion time and the minimum road capacity on their way to the sink of the maximum congestion points,which make the solution process easier.On this basis,anO(nlogn) time algorithm is developed to solve the 1-sink location problem.Finally,anO(knlogn) time recursive algorithm is developed to solve thek-sink location problem based on dynamic programming,wherenis the number of vertices in the given network.

Since we are the first to analyze the sink location problem in dynamic network with different capacity,our research may be useful to the further research such as the sink location problem in dynamic tree network with different capacity and the sink location problem in dynamic network with interval weight and different capacity.

Keywords： road capacity;dynamic network;dynamic programming;emergency management

Min-max Multiple Sink Location Problem in Dynamic Path Networks with Different Traffic Capacity Constraint

ZHAORong,LIUKe-yan,RENPei-yu

(Business School,Sichuan University,Chengdu 610065,China)

C931;O221

A

1003-207(2017)09-0133-08

10.16381/j.cnki.issn1003-207x.2017.09.015

2016-02-25；

2016-06-08

國(guó)家自然科學(xué)基金資助項(xiàng)目(71371130,71501019)；四川旅游發(fā)展研究中心項(xiàng)目(LYC16-16)；賽爾網(wǎng)絡(luò)下一代互聯(lián)網(wǎng)技術(shù)創(chuàng)新項(xiàng)目

任佩瑜(1952-)，男(漢族)，重慶人，四川大學(xué)商學(xué)院教授，博士生導(dǎo)師，研究方向：管理科學(xué)與工程，E-mail:renpeiyu@scu.edu.cn.