路段通行能力不同的避难点选址模型及算法

赵 容，刘克艳，任佩瑜

(四川大学商学院，四川 成都 610065)

路段通行能力不同的避难点选址模型及算法

赵 容，刘克艳，任佩瑜

(四川大学商学院，四川 成都 610065)

研究应对突发事件的避难点选址问题。假定一条直线型动态路径网络上有n个顶点，由n-1条边相连，每个顶点有一个权重，每条边有一个容量。边的容量表示路段通行能力，是单位时间内允许进入该路段的最大聚集量。目标是在此网络中选择k个避难点，并为每个顶点指定一个避难点，使得所有顶点的权重到达各自避难点的最大时间最小。首先根据问题的性质，通过建立动态表结构，结合二分法的思想，在O(nlogn)时间内求解单个避难点选址问题。然后在此基础上，针对k-避难点选址问题，通过更新动态表，结合动态规划方法，设计了时间复杂度为O(knlogn)的递归算法求解。

道路通行能力；动态网络；动态规划；应急管理

1 引言

应急设施选址是应急管理中一项极其重要的内容，合理的应急设施选址能够有效预防和降低突发事件的危害。Toregas等[1]在1971年首先提出应急设施选址问题，研究如何建立数量最少的应急救援点，在规定时间内给所有需要应急服务的需求点提供救援。此外还有集合覆盖模型[2]和绝对中心点模型[3]等。这些模型都采用静态网络，只考虑距离因素，而在应急疏散过程中，由于道路通行能力的限制，在通往避难点的过程中，受灾者可能会因为堵塞耗费大量时间，此时到达避难点的时间不能简单地用权重与距离的乘积来表示，更应考虑道路通行能力等因素。

Cheng等[4]以2011年3月发生的东日本大地震为研究背景，将动态网络应用到应急避难点选址问题中，相比静态网络，动态网络中的边有长度和容量属性，其中容量表示单位时间允许通过该边的最大量。动态网络中的避难点选址问题可以描述为：将城市交通网络抽象为一个动态网络，网络中顶点的权重对应初始时刻该点需要疏散的人数，如某栋建筑里的人数。网络中边的容量对应路段通行能力，表示单位时间内允许进入该路段的最大权重。

由于紧急避难时人群密度较大，可以认为人群行走速度一致。在各路段通行能力一致时，受灾者到达避难点的时间由两部分组成：一是受灾者通过顶点进入路段时的拥堵时间；二是行走时间。问题的目标是在这样的动态网络中建立若干避难点，并为每个顶点指定一个避难点，使得在灾害发生时所有顶点的权重能尽快到达各自的避难点。假设各顶点的权重在给定的区间内取值，以疏散完成时间的最大后悔值最小(Min-max regret)为目标，Higashikawa等[5]和Wang Haitao[6]改进了文献[4]中的数据结构，求解算法复杂度由O(nlog2n)降为O(nlogn)。李红梅[7]、倪冠群[8]、Arumugam[9]将其扩展到不确定型2-避难点和不确定型k-避难点选址问题，分别给出了自己的求解算法。随后Bhattacharya[10]改进了前面文献的算法，针对最小最大后悔值准则下的单个避难点选址问题给出了时间复杂度为O(n)的算法，针对2-避难点选址问题给出了时间复杂度为O(nlog4n)的算法，都是目前最优的结果。同时也有很多学者将动态路径网络上的避难点选址问题扩展到不同的网络结构，如树图[11]，环状图[12]，方格网[13]和就近原则下的一般网络结构[14]。假设各顶点的权重是确定的值，以疏散完成时间最小(Min-max)为目标，针对路径动态网络上的k-避难点选址问题，倪冠群等[15]基于“二分思想”提出了时间复杂度为O(nlogkn)的算法，适用于k值比较小的情形，Higashikawa等[16]基于动态规划的方法设计了时间复杂度为O(knlogn)的算法，随后进行优化将复杂度降为O(kn)[17]。针对树图上的单个避难点选址问题，Mamada等[18]设计了时间复杂度为O(nlog2n)的算法。

以上研究的基本假设是各路段通行能力一致。本文考虑各路段通行能力不同的情形。在路径网络上，避难点左右两边的权重互不影响，可以分别计算左右两边的疏散完成时间，取较大值即为所有权重的疏散完成时间。在向避难点疏散的过程中，会在左右两边分别产生一个最大拥堵点，左右两边的疏散完成时间将由这个最大拥堵点决定。当各路段通行能力相同时，将避难点向左移动(未越过该点)左边最大拥堵点不变，这意味着移动避难点后可以在O(1)内求得新的疏散完成时间；而当各路段通行能力不同时，将避难点的向左(右)移动时，两边的最大拥堵点的位置也会随之变化。这使得上述研究[4-17]中采用的平衡二叉树的结构不再适用。本文根据新问题中拥堵点和疏散完成时间之间的关系，设计由拥堵点序列、与之对应的疏散时间以及该拥堵点和避难点间路段的最小通行能力构成的动态表结构，通过查找动态表求得左右两边的疏散完成时间，然后根据左右两边疏散完成时间的单调性，采用二分查找算法求解单个避难点选址问题。基于对单个避难点选址问题的分析，针对k-避难点选址问题，通过更新动态表，采用动态规划算法求解。

2 问题描述与基本模型

给定路径网络P=(V,E)，设路径上依次排列有顶点v1,v2,…,vn构成顶点集V，顶点vi和vi+1由路段ei连接，所有路段的集合为E={e1,e2,…,en-1}。对于vi∈V，定义权重ωi为该顶点的权重，对于ei∈E，定义容量ci为该路段的通行能力，表示单位时间内允许流入路段ei的最大权重。定义τ为权重在各路段上流动单位距离所需的时间。设区间[vi,vj]中有一个避难点x，各权重在向避难点疏散的过程中不允许出现交叉流。定义区间[vi,x]中的疏散点属于避难点x的左边，区间[x,vj]中的疏散点属于避难点x的右边。特别地，当x=vl时，vl处的权重视为立即到达避难点x。

根据以上定义，初始时刻，权重集中在各顶点处。疏散过程开始时，所有顶点处的权重同时向各自指定的避难点流动。这时首先有了顶点处的权重进入路段的时间，顶点v处的权重ω进入容量为c的路段的时间为ω/c。它们全部进入路段后即变为流量为c，总量为ω的权重，这里的流量表示单位时间内通过路段横截面的权重。由于各路段通行能力不同，权重到达避难点的时间除了从顶点处进入路段的时间和行走时间外，还有第三部分时间，是权重从通行能力高的路段进入通行能力低的路段时的拥堵时间。根据以上讨论，流量为c的权重ω通过容量为ce的路段e时，可能出现以下2种情形：

(1)c≤ce。如下图1中a图所示，流量为c的权重ω通过路段e时不会遇到堵塞，即没有等待时间，所有权重始终以速度1/τ流动，它们通过路段e的时间为leτ。

图1 流量为c的权重ω通过路段e的两种情形

由以上讨论可知，流量为c的权重ω通过长度为le、容量为ce的路段e的时间te可以表示为：

(1)

图2 权重ω1到达避难点x的过程中各路段流量

根据以上定义，对于区间[vi,vj]，用Li(x)表示x左边的疏散完成的时间，Rj(x)表示x右边的疏散完成的时间，Θi,j(x)表示区间[vi,vj]中所有的点的疏散完成时间。

(2)

(3)

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

(4)

用x=(x1,…,xk)表示k个避难点的位置坐标，用d=(d1,…,dk-1)表示对应划分点的角标，如下图3所示，划分点vdi-1和vdi指定了区间[vdi-1+1,vdi]中的权重全部疏散到避难点xi。问题的目标是在路径P上选择k个避难点，同时确定k-1个划分点，将顶点集V划分为k个子集，使得k个子集中的所有疏散点到达各自避难点的最大时间最小。

图3 避难点及其划分点

用Θi(x,d)表示区间[vdi-1+1,vdi]中的权重全部到达避难点xi的时间，路径P上所有权重的疏散完成的时间则可以表示为

Θ(x,d)=max{Θi(x,d)|i=1,…,k}。路径P上的k-避难点选址问题可以表示为：

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

3 单个避难点选址问题

本节主要介绍如何在区间[vi,vj]内求解单个避难点的选址问题。由(4)式可知，此问题可以表示为：

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

根据第1节的描述，首先有如下引理1。

图4 路段通行能力相同与不同时图形比较

引理2Li(x)随x的增加而增加，Rj(x)随x的增加而减小。

引理3 问题P1存在唯一解。

证明：由(4)式和引理2可知Θi,j(x)在区间[vi,vj]内是关于x的凸函数，所以存在唯一xopt=argmin{Θi,j(x)|x∈[vi,vj]}。

引理4 设x∈[vi,vj]，若Li(x)≤Rj(x)，则xopt≥x；若Li(x)≥Rj(x)，则xopt≤x。

证明：根据(4)式和引理2可知，Θi,j(x)是关于x的凸函数，当Li(x)≥Rj(x)时，若将x向右移动，则Li(x)将继续增加，由(4)式可知，Θi,j(x)=Li(x)也将随之增加，所以xopt≤x。同理可证，若Li(x)≤Rj(x)，则xopt≥x。

引理4表明通过反复比较Li(vl)和Rj(vl)可将xopt的取值范围限定在某个区间[vk,vk+1]内。而在区间(vk,vk+1)内，避难点左右两边的最大拥堵点的位置将保持不变，这时的情形同文献[4]，可以在O(1)时间内直接求得xopt。

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

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

表2 区间[vi,vj]的左动态表TL(i,j)

引理5 由动态表TL(i,j)可以在O(logn)时间内求得任意L(i,k)(i≤k≤j)。

综上，即证由动态表TL(i,j)可在O(logn)时间内求得任意L(i,k)(i≤k≤j)。

定理1：问题P1可在O(nlogn)时间内求解。

运行一次算法A可得TL(i,j)，同理可在O(nlogn)时间内求得TR(i,j)。由引理5可知，根据动态表TL(i,j)和TR(i,j)可在O(logn)时间内求得任意L(i,k)和R(k,j)。引理4表明采用二分法求解问题P1时，需要计算L(i,k)和R(k,j)的次数为O(logn)。所以在已求得动态表TL(i,j)和TR(i,j)后，可在O(log2n)时间内求解问题P1。

综上，即证问题P1可在O(nlogn)时间内求解。

4 k-避难点选址问题

问题Pk满足最优性原理，本节采用动态规划算法进行求解。设区间[vi,vj]内建立的p个最优避难点的位置坐标为p维向量x*(p,i,j)，与之对应的最优划分点的角标为p-1维向量d*(p,i,j)，它们的最小疏散完成时间为opt(p,i,j)。根据以上定义，求解问题Pk即求解opt(k,1,n)。根据第2节的讨论有如下递归表达式：

(5)

用d(p,i,j)表示表示d*(p,i,j)的第p-1个值，即第p-1个和第p个避难点间的划分点，同样x(p,i,j)表示x*(p,i,j)的第p个值，x(1,d+1,j)表示区间[vd+1,vj]中的单个最优选址位置，则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]。

性质1 对2≤p≤k，d(p,i,j-1)≤d(p,i,j)。

性质2 对1≤p≤k，x(p,i,j-1)≤x(p,i,j)。

由第2节的讨论可知，求解单个避难点选址问题时，本文所采用的数据结构与Higashikawa等[17]不同。同样这里在求解k-避难点选址问题时，采用的递归顺序也与Higashikawa等[17]不同。根据建立的避难点的个数不同将它们分为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)的顺序求解。根据递归表达式(5)，每一层都可以由上一层的所有值和opt(1,1,n),…,opt(1,n-1,n)求得。采用这样的逆序递归时只需计算一次opt(1,2,n),…,opt(1,n-1,n)，然后在每一层递归中都可以用到它们，如此减少了更新的次数，也减少了更新的方向。由于采用逆序，在每一层内更新时，只需由L(α,β)向2个方向更新，即L(α-1,β)和L(α,β-1)。具体如下图5所示。

图5 由opt(p,1,n)计算opt(p,1,n-1)示意图

如图5所示，用dn表示d(p,1,n)，xn表示x(p,1,n)，dn-1、xn-1同理。由第2节的讨论可知，只要确定了xopt所属的区间即可在O(1)时间内求解，而确定xopt所属区间的方法是运用引理4，通过反复比较L(i,l)和R(l,j)得到。设xn属于区间[vx[n],vx[n]+1)，xn-1属于区间[vx[n-1],vx[n-1]+1)。根据(5)式，由opt(p,1,n)计算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)等求得。根据递归顺序可知，在计算第p层时，所有p-1层的opt(p-1,1,j)已知，只需进一步由opt(1,dn+1,n)计算opt(1,dn+1,n-1)…和opt(1,dn+2,n)…，根据第2节的分析，左边涉及的是由L(dn+1,[xn])更新到L(dn-1+1,[xn-1])。由性质1和2可知，dn-1≤dn，xn-1≤xn。所以在整个计算过程中L(i,j)只有2个更新方向，即L(i-1,j)和L(i,j-1)。引理5已表明可由动态表TL(i,j)在O(logn)时间内求得任意L(i,k)。下面主要说明如何由动态表TL(i,j)在O(logn)时间内更新为TL(i-1,j)。

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

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

根据以上讨论，设计如下算法B自下而上地求得opt(k,1,n)、d*(k,1,n)和x*(k,1,n)，即是问题Pk的解。

算法B：求解问题Pk，见表4。

表4 Pk的算法流程

定理2采用递归算法B求解问题Pk的时间复杂度为O(knlogn)。

证明：第(1)步中，采用算法A建立动态表的时间复杂度为O(nlogn)。由定理1的证明可知根据动态表求解opt(1,1,n)的时间复杂度为O(log2n)。由引理2和4可知，x(1,1,n)≤x(1,2,n)，所以按opt(1,2,n),…,opt(1,n-1,n)的顺序求解时至多调用动态表O(n)次，由引理5可知，通过动态表计算L(i,j)和R(i,j)的时间复杂度为O(logn)。所以求解opt(1,1,n),…,opt(1,n-1,n)的时间复杂度为O(nlogn)。同理依次求解opt(1,1,n-1),…,opt(1,1,2)的时间复杂度也是O(nlogn)。即证第(1)步的计算时间复杂度为O(nlogn)。

第(2)步中，根据递归表达式(5)，由前一次循环得到的opt(p-1,1,n),…,opt(p-1,1,p)和第1步得到的opt(1,1,n),…,opt(1,n-1,n)求解opt(p,1,n)的时间复杂度为O(logn)。在依次求解opt(p,1,n),opt(p,1,n-1),…,opt(p,1,p)时，由性质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，对于x(p,1,j)所属的区间同理。根据建立的动态表TL(dn+1,[xn])，对于x(p,1,j)的变化不需更新表，可以直接在表中查找。对于d(p,1,j)的变化，d(p,1,j)每减少1则需要运行算法B1更新一次动态表。所以每一次循环中动态表TL(dn+1,[xn])需要更新O(n)次，即每一次循环中更新动态表的时间复杂度为O(nlogn)。由引理4可知，d(p,1,j)每减少1需要对L(dj+1,x[j])和R(x[j],j)进行O(1)次比较，所以每一次循环中需要通过动态表计算L(i,j)和R(i,j)的次数为O(n)，即每一次循环中计算L(i,j)和R(i,j)的时间复杂度为O(nlogn)。第(2)步中有k-1次循环，即证算法B的第(2)步的时间复杂度为O(knlogn)。

综上，采用递归算法B求解问题Pk的时间复杂度为O(knlogn)，即证。

本文从理论上扩展了动态网络中的k-避难点选址问题，在已有的权重确定、通行能力为1的直线型动态网络(动态路径网络)中的k-避难点选址问题的基础上，研究了权重确定、各路段通行能力为任意常数的动态路径网络中的k-避难点选址问题。目前针对权重确定、通行能力为1的直线型动态网络中的k-避难点选址问题的研究中设计的求解算法复杂度分别为O(nlogkn)[15]、O(knlogn)[16]和O(kn)[17]，本文主要在Higashikawa等[17]的基础上进行了拓展，根据新问题的性质，放弃了原有的平衡二叉树结构，采用一种动态链表结构储存，求解思路仍是储存拥堵点信息，只是本文因为各路段容量不同，而路段容量对最大拥堵点的计算有影响，所以储存了决定对应疏散完成时间的容量值。如此，在采用动态规划算法求解k-避难点问题时，虽然每次迭代更新时不能同文献[17]一样通过一次比较获得，但根据动态表建立的序列可以在O(logn)时间内插入新的值。最后本文设计的求解k-避难点选址问题的递归算法的时间复杂度为O(knlogn)。

5 结语

现有研究避难点选址问题的文献多没有考虑道路通行能力及由此带来的拥堵问题，使得避难点的选址位置在实际中并不适用。而在考虑道路通行能力的文献中都假设各段道路通行能力相同，与实际的道路情况不符，且缺乏变通。本文在后者的基础上，放松了各路段通行能力一致的假设，通过建立关于最大拥堵点的动态表结构，结合动态规划的方法，解决了在确定型路径动态网络中建立k个避难点使得路径上所有权重到达各自避难点的最大时间最小的问题，为后续研究提供参考。

[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] 倪冠群,徐寅峰,徐久平.考虑道路通行能力的应急避难点选址模型及算法 [J].中国管理科学,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

国家自然科学基金资助项目(71371130,71501019)；四川旅游发展研究中心项目(LYC16-16)；赛尔网络下一代互联网技术创新项目

任佩瑜(1952-)，男(汉族)，重庆人，四川大学商学院教授，博士生导师，研究方向：管理科学与工程，E-mail:renpeiyu@scu.edu.cn.