单电梯紧急疏散调度问题求解
王晶, 王书宁     
清华大学 自动化系, 北京 100084
摘要:该文研究单电梯紧急疏散调度问题, 即在紧急情况下, 如何调度楼内可用的1部电梯, 以在最短时间内将各楼层已知人员全部疏散的问题。在已有整数规划模型及求解方法的基础上, 通过增加电梯运行约束以及线性化非线性约束等方法, 将问题表达为等价的整数线性规划问题, 并提出改进的启发式算法, 算法的核心思想在于使每个往返疏散的人数尽可能多且楼层被访问次数尽可能少。数值实验表明: 该算法比现有算法具有更好的疏散效果。
关键词紧急疏散    电梯调度    整数线性规划    子集和问题    
Solutions of the single elevator scheduling problem for emergency evacuations
WANG Jing, WANG Shuning     
Department of Automation, Tsinghua University, Beijing 100084, China
Abstract:This study considers the minimization of the evacuation time for a single elevator for emergency conditions when all the evacuees are waiting in the elevator halls before the evacuation begins. Integer programming (IP) and a heuristic algorithm are used to formulate the problem as an equivalent integer linear programming problem that includes the elevator operation constraints and linearizes the nonlinear constraints. The heuristic algorithm maximizes the number of evacuees evacuated in each roundtrip while minimizing the number of visits to the floors. Numerical tests verify the improved evacuation speed given by this algorithm relative to existing algorithms.
Key words: emergency evacuation    elevator dispatching    integer linear programming    subset-sum problem    

近些年高层建筑越来越多, 紧急情况下如何快速撤离大楼内人员的问题即紧急疏散问题逐渐引起关注。通常紧急情况时大楼内电梯会被关闭, 人们被指示通过楼梯疏散撤离到安全区域。然而通过楼梯疏散存在很多问题如很容易造成拥堵, 楼层很高时人们会体力不支, 楼内的老、弱、病、残、幼儿通过楼梯撤离困难等[1,2]。电梯具有快速和便捷等优点, 可以弥补这些不足[3,4,5]。随着电梯系统耐火耐高温等技术的提高, 紧急情况时通过电梯疏散成为可能[6,7]。目前已有很多学者致力于研究合理调度电梯以在最短的时间内疏散大楼内所有人员的问题[8,9,10], 即紧急疏散电梯调度问题(elevator scheduling for emergency evacuation, ESEE)。

[9]给出紧急疏散电梯调度的常用算法, 包括两站停靠策略(two-stop approach, TS)和逐层疏散算法(floor-by-floor algorithm, FbF)等。TS策略是指电梯不断往返于疏散层和待疏散楼层之间, 直到所有人被疏散完毕, 电梯每次离开疏散层后仅停靠1个待疏散楼层, 并再次返回疏散层。FbF算法是指电梯从疏散层去往待疏散的最高楼层, 并按待疏散楼层高低顺序逐层疏散, 满载后返回疏散层, 重复上述步骤, 直到所有人被疏散完毕。TS策略在待疏散楼层人数接近电梯额定容量整数倍时效率较高, FbF算法在待疏散楼层人数较少时效率较高。文[10]考虑单电梯紧急疏散调度问题(single elevator scheduling for emergency evacuation, S-ESEE), 假设当火灾等紧急情况发生时, 所有待疏散乘客都已到达各个楼层电梯间等待疏散, 各楼层待疏散人数已知, 而且有1部停靠在疏散层的消防电梯可以正常使用。根据文[11]中疏散时间的计算方法, 文[10]构建了S-ESEE的整数规划模型, 证明问题计算复杂度是NP(non-deterministic polynomial)难, 并给出一种有效的启发式求解方法。不足之处是该整数规划中含有非线性约束, 且没有考虑电梯运行约束的影响, 因而模型复杂而且不够准确。

本文改进文[10]的问题建模及求解。通过将非线性约束转换为线性约束, 并增加电梯运行约束以使建模更准确, 构建了问题的整数线性规划模型。进一步分析并证明问题可以简化为求解不考虑电梯运行约束的简化问题, 提出求解该简化问题的3阶段启发式算法, 并通过数值仿真验证了该算法的性能。

1 问题建模 1.1 优化目标与约束条件

不失一般性, 假设大楼的楼层间距固定且疏散层在最低层, 因此可以将楼层号集合记为I={0,1,…,n}, 其中楼层0为大厅层即疏散层, 楼层n为最高楼层。初始时刻每个待疏散楼层i∈I\{0}的人数记为di∈N。电梯的额定容量记为Q∈N。电梯开和关门时间分别记为tdo和tdc。每位乘客进和出电梯所需时间分别记为tpi和tpo。电梯从楼层i运行到楼层j且不在经过的楼层停靠称为电梯从楼层i直达楼层j, 运行时间tij与运行距离呈近似线性关系, 由于楼层间距相等, tij与运行的楼层数也呈近似线性关系:

${t_{ij}} = a|i - j| + b,\forall i \ne j.$ (1)
其中ab为正实数。当乘客在楼层i进出电梯时, 电梯在该楼层的停靠时间ts,i包括电梯开门时间, 乘客进出电梯时间和电梯关门时间
${t_{s,i}} = {t_{do}} + {t_{pi}}{n_{pi,i}} + {t_{po}}{n_{po,i}} + {t_{dc}}.$ (2)
其中npi,inpo,i分别为在楼层i进和出电梯的乘客人数。

Te表示疏散大楼内所有人所需的总疏散时间。为了计算Te, 本文将电梯从疏散层出发直到再次返回疏散层记为电梯的一次往返(roundtrip), 所用的时间称为往返时间(roundtrip time), 则Te为所有往返时间的总和。记紧急疏散中往返编号的集合为V={1,2,…,m}, 其中m为疏散所需要的往返总数。下面考虑电梯的各个往返以及往返时间。为方便描述, 对任意i∈I, v∈V, 引入以下变量:

1)xiv∈N, 表示在第v次往返中楼层i进出电梯人数。

2)yiv∈{0,1}, 如果电梯在第v次往返中访问楼层i(当xiv>0时称为电梯在第v次往返中访问了楼层i)则yiv为1, 否则yiv为0。

在紧急疏散问题中, 由于所有乘客的目标楼层均为疏散层, 因此在疏散层只有乘客出电梯, 在其他各层只有乘客进电梯。在第v次往返中, xiv(i∈I\0)为在楼层i进电梯的人数, x0v为在疏散层出电梯的人数, 且满足在该次往返中疏散总人数守恒的约束, 即

${x_{0v}} = \sum\limits_{i = 1}^n {{x_{iv}}} ,\forall v \in V.$ (3)
由文[10]可知总疏散时间为
${T_e} = \alpha \sum\limits_{v \in V} {f_1^v} + \beta \sum\limits_{v \in V} {{N_v}} + \gamma \sum\limits_{v \in V} {{x_{ov}}} $ (4)
其中,α=2a,β=b+tdo+tdc,γ=tpi+tpo,$f_1^v$和Nv分别为电梯在第v次往返中访问的最高楼层号和楼层个数, 即${N_v} = \sum\limits_{i \in I}^{} {{y_{iv}}} $。式(4)第3项中$\sum\limits_{v \in V}^{} {{x_{ov}}} $为各次往返中被疏散的乘客总人数即$\sum\limits_{v \in V}^{} {{x_{ov}}} = \sum\limits_{i = 1}^n {{d_i}} $,其为定值, 因此最小化总疏散时间的S-ESEE优化目标等价于最小化所有往返的最高楼层号之和与访问的楼层总数的线性组合, 记为Tm, 即
${T_m} = \alpha \sum\limits_{v \in V} {f_1^v} + \beta \sum\limits_{v \in V} {\sum\limits_{i \in I} {{y_{iv}}} } .$ (5)
综上分析, 本文将最小化Tm作为S-ESEE问题的优化目标。

下面考虑S-ESEE问题的约束条件。

首先, 如果电梯在第v次往返中访问楼层i, 那么最高层号$f_1^v$不能小于i。本文将该约束称为最高楼层约束。文[10]中将该约束描述为非线性约束$f_1^v$≥iyiv,$\forall i \in I,\forall v \in V$, 本文将其线性化:

$f_1^v \ge i + n(yiv - 1),\forall i \in I,\forall v \in V.$ (6)
可以看出, 当yiv =1时, 式(6)成为$f_1^v$≥i; 当yiv =0时, 该约束对任意$f_1^v$∈I不起作用。如果$f_1^v$=0, 说明电梯在第v次往返中没有访问任何楼层, 本文将此往返称为空往返, 易知空往返疏散的人数为0。

其次, 所有往返执行完后, 每个待疏散楼层的乘客都必须被疏散完。因此, 存在以下乘客数目约束

$\sum\limits_{v = 1}^m {{x_{iv}}} = {d_i},\forall i \in I\backslash \left\{ 0 \right\}.$ (7)

再次, 在任意时刻电梯的负载都不能超过其额定容量。由各个往返疏散的总人数x0v都不大于Q, 结合式(3)及xiv和yiv的关系可知

$\left\{ \begin{array}{l} {x_{ov}} = \sum\limits_{i = 1}^n {{X_{iv}},\forall v \in V} \\ {x_{iv}} \le Q{y_{iv}},\forall i \in I,\forall v \in V \end{array} \right.$ (8)
本文将该约束称为电梯容量约束。

最后, 当电梯在某楼层(疏散层除外)停靠时, 只有当该楼层的所有人都已进入电梯或者电梯已经满载后, 才能离开该楼层。文[10]没有考虑该约束, 本文为了建模更准确, 引入该约束并将该约束称为电梯运行约束, 具体表示为

$\sum\limits_{k = 1}^v {{X_{ik}}} = {d_i},\forall {y_{iv}} = 1,i \in I\backslash \left\{ 0 \right\},v \in V.$ (9a)
$\sum\limits_{k = i}^n {{X_{kv}}} = Q,\forall {y_{iv}} = 1,i \in I\backslash \left\{ 0 \right\},v \in V.$ (9b)

基于以上讨论, 可以把S-ESEE问题建模为一个整数线性规划问题。记Γ为决策变量$f_1^v$、xiv和yiv组成的向量, 其中$f_1^v$∈I,xiv∈N,yiv∈{0,1}, $\forall v \in V$,i∈I。记满足最高楼层约束式(6)、乘客数目约束式(7)、电梯容量约束式(8)和电梯运行约束式(9)的向量Γ的集合分别为Ω1、 Ω2、 Ω3和Ω4, 则得到上述整数线性规划问题的简洁形式为

$\mathop {\min }\limits_\Gamma \left\{ {\alpha \sum\limits_{v \in V} {f_1^v} + \beta \sum\limits_{v \in V} {\sum\limits_{i \in I} {{y_{iv}}} } |s.t.\Gamma \in \Omega ,i = 1,2,3,4} \right\}$ (10)
称式(10)为S-ESEE的原始优化问题, 记为P0

1.2 模型简化

在P0中去除式(9), 可得到以下优化问题:

$\mathop {\min }\limits_\Gamma \left\{ {\alpha \sum\limits_{v \in V}^{} {f_1^v} + \beta \sum\limits_{v \in V}^{} {\sum\limits_{i = 1}^{} {{y_{iv}}} |s.t.\Gamma \in {\Omega _i},i = 1,2,3} } \right\}$

本文把该问题称为S-ESEE的简化优化问题, 记为P1。假设已经得到P1的一个可行解, 记为$\hat \Gamma $, 其对应分量为$\hat f_1^v,{\hat x_{iv}}$和${\hat y_{iv}},v \in V,i \in I$。将“电梯第v次往返中经过楼层i”简称为i,v, 那么对任意i∈I\{0}, v∈V, 定义$\hat \Gamma $在i,v处的电梯运行约束误差为
${e_{iv}}(\hat \Gamma ) = \left\{ \begin{array}{l} \min \left\{ {Q - \sum\limits_{k = i}^n {{{\hat x}_{kv}}} ,di - \sum\limits_{k = 1}^v {{{\hat x}_{ik}}} } \right\},{{\hat y}_{iv}} = 1;\\ 0,{{\hat y}_{iv}} = 0. \end{array} \right.$ (11)
当${e_{iv}}(\hat \Gamma ) > 0$时, 称$\hat \Gamma $在i,v处存在电梯运行约束误差, 也称$\hat \Gamma $在楼层i处和往返v中均存在电梯运行约束误差。还可以看出,${e_{iv}}(\hat \Gamma ) > 0$只与${\hat x_{jk}}$有关,i≤j≤n,1≤k≤v。将$\hat \Gamma $中存在电梯运行约束误差的往返的集合记为S$\hat \Gamma $, 即

$s(\hat \Gamma ) = \left\{ {v|{e_{iv}}(\hat \Gamma ) > 0,i \in I\backslash \left\{ 0 \right\},v \in V} \right\}.$


由式(7)可知${e_{im}}(\hat \Gamma ) = 0,\forall i \in I\backslash \left\{ 0 \right\}$即$\hat \Gamma $在第m次往返中不存在电梯运行约束误差, 从而 $m \notin S(\hat \Gamma )$。又因m为最大往返序号, 故S$\hat \Gamma $中所有元素均小于m。再令

$v(\hat \Gamma ) = \left\{ \begin{array}{l} \min \left\{ {v,v \in S(\hat \Gamma )} \right\},S(\hat \Gamma ) \ne \emptyset ;\\ m,S(\hat \Gamma ) = \emptyset \end{array} \right.$


可以看出, 当$S(\hat \Gamma ) \ne \emptyset$时,$v(\hat \Gamma ) < m$;当且仅当$S(\hat \Gamma ) \ne \emptyset$时,v$\hat \Gamma $=m。后者意味着eiv$\hat \Gamma $=0,$\forall i \in I\backslash \left\{ 0 \right\},\forall v \in V%,此时$\hat \Gamma $满足式(9), 即$\hat \Gamma $∈Ω4。由以上分析可知, 当且仅当v$\hat \Gamma $=m时,$\hat \Gamma $为P0的可行解。

如果$\hat \Gamma \notin {\Omega _4}$, 那么存在电梯运行约束误差的往返集合S$\hat \Gamma $非空, 选择v$\hat \Gamma $为S$\hat \Gamma $中的最小往返, 易知v$\hat \Gamma $<m,选择i$\hat \Gamma $为第v$\hat \Gamma $次往返中存在电梯运行约束误差的最高楼层号, 即

$i(\hat \Gamma ) = \max \left\{ {i|s.t.{e_{iv}}(\hat \Gamma ) > 0,i \in I\backslash \left\{ 0 \right\},v = v(\hat \Gamma )} \right\}$


为便于叙述, 记$\hat i = i(\hat \Gamma ),v = v(\hat \Gamma )$。结合eiv的定义式(11)易知${e_{\hat i\hat v}}(\hat \Gamma ) > 0$。记

$B(\hat \Gamma ) = \left\{ {(i,v)|1 \le v \le \hat v,i \in I\backslash \left\{ 0 \right\}} \right\} \cup \left\{ {(i,\hat v)|\hat i < i \le n} \right\}$


有eiv$\hat \Gamma $=0,-G26.jpg"/>。在这种情况下, 本文可以通过对$\hat \Gamma $的有关分量进行简单调整, 从而获得P1的新可行解, 其目标函数值不大于$\hat \Gamma $的目标函数值, 其电梯运行约束误差相对$\hat \Gamma $有以下改进
$\left\{ \begin{array}{l} {e_{\hat i\hat v}}(\tilde \Gamma ) < {e_{\hat i\hat v}}(\hat \Gamma );\\ {e_{\hat i\hat v}}(\tilde \Gamma ) = 0,\forall (i,v) \in B(\hat \Gamma ). \end{array} \right.$ (12)
记$\tilde i = i(\tilde \Gamma ),\tilde v = v(\tilde \Gamma )$。当${e_{iv}}(\tilde \Gamma ) > 0$时,$\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over v} = \hat v$且$\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over i} = \hat i$, 这说明$\hat \Gamma $中存在电梯运行约束误差的最小往返序号$\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over v} $和往返$\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over v} $中存在电梯运行约束误差的最高楼层号$\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over i} $都不变, 但由于${e_{iv}}(\tilde \Gamma ) < {e_{iv}}(\hat \Gamma )$能保证$\hat \Gamma $在$(\hat i,\hat v)$的电梯运行约束误差严格减小, 因此多次调整后总能使得${e_{iv}}(\tilde \Gamma ) = 0$。当${e_{iv}}(\tilde \Gamma ) = 0$时, 或者$\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over v} = \hat v,\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over i} < \hat i$成立, 或者$\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over v} > \hat v$成立, 其中前者意味着$\hat \Gamma $中$\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over v} $不变, 而且往返$\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over v} $中存在电梯运行约束误差的最高楼层严格降低, 因此多次调整后总能使得该次往返所有楼层都不存在电梯运行误差, 从而使得$\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over v} > \hat v$; 后者意味着$\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over v} $严格增加, 当$\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over v} $增大到m时,$\hat \Gamma $满足电梯运行约束。基于以上分析可知, 一旦上面的结果成立, 一定可以从$\hat \Gamma $出发, 经过有限次上述简单调整, 获得原始优化问题P0的一个可行解, 其目标函数不大于$\hat \Gamma $的目标函数值。

下面具体介绍对$\hat \Gamma $的调整方法。令p为可行解$\hat \Gamma $的第$\hat v$次往返停靠的最低楼层,q为访问楼层$\hat i$的最后一个往返。容易看出$p \le \hat i,q > \hat v$, 其中第2个不等式成立是因为第${\hat v}$次往返后在楼层${\hat i}$还有待疏散人员。再令

$A = \left\{ {(i,v)|i \in \left\{ {0,\hat i,p} \right\},v \in \left\{ {\hat v,q} \right\}} \right\};$ (13)
$\Delta x = \left\{ \begin{array}{l} \min \left\{ {{{\hat x}_{p\hat v}},{{\hat x}_{\hat iq}}} \right\},p < \hat i;\\ \min \left\{ {Q - \sum\limits_{i = \hat i}^n {{{\hat x}_{\hat iv}},{{\hat x}_{\hat iq}}} } \right\},p = \hat i. \end{array} \right.$ (14)
易知Δx>0。利用这些符号, 本文给出由$\hat \Gamma $获得${\tilde \Gamma }$的调整方法, 即按以下方式确定${\tilde \Gamma }$的所有分量$\tilde f_1^v$、${{\tilde x}_{iv}}$和${{\tilde y}_{iv}},i \in I,v \in V$

1) 首先确定${{\tilde x}_{iv}}$和${{\tilde y}_{iv}}$,$i \in I,v \in V$。

a) 对所有$\begin{array}{l} {{\tilde x}_{iv}}\\ i \in I \end{array}$: 令${{\tilde x}_{iv}}$=${{\hat x}_{iv}}$,${{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{iv}}$=0${{\hat y}_{iv}}$,$v \in V$且$(i,v) \in \tilde A$;

b) 对$i = \hat i$: 令${{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over x} }_{\hat i\hat v}} = {{\hat x}_{\hat i\hat v}} + \Delta x,{{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over x} }_{\hat iq}} = {{\hat x}_{\hat iq}} - \Delta x,{{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{\hat i\hat v}} = {{\hat y}_{\hat i\hat v}} = 1$,若${{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over x} }_{\hat iq}}$=0 则令${{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{\hat iq}}$=0, 否则令${{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{\hat iq}}$=${{\hat y}_{\hat iq}}$;

c) 如果$p \ne \hat i$, 对i=p: 令${{\tilde x}_{p\hat v}} = {{\hat x}_{p\hat v}} + \Delta x,{{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over x} }_{pq}} = {{\hat x}_{pq}} + \Delta x,{{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{p\hat v}} = 1$, 若${{\tilde x}_{p\hat v}}$=0则令${{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{p\hat v}}$=0,否则令${{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{p\hat v}}$=${{\hat y}_{p\hat v}}$;

d) 对i=0: 如果$p = \hat i$则令${{\tilde x}_{0\hat v}} = {{\hat x}_{0\hat v}} + \Delta x,{{\tilde x}_{0q}} = {{\hat x}_{0q}} - \Delta x,{{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{0\hat v}} = {{\hat y}_{0\hat v}} = 1$, 若${{\tilde x}_{0q}}$=0则令${{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{0q}}$=0, 否则令${{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{0q}}$=${{\hat y}_{0q}}$; 如果$p \ne \hat i$则令${{\tilde x}_{0\hat v}} = {{\hat x}_{0\hat v}},{{\tilde x}_{0q}} = {{\hat x}_{0q}},{{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{0\hat v}} = {{\hat y}_{0\hat v}} = 1,{{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{0\hat q}} = {{\hat y}_{0v\hat q}} = 1$。

2) 然后利用得到的${{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{iv}}$($i \in I,v \in V$)确定$\tilde f_1^v$($v \in V$)。

a) 对所有$v \in V$\$\left\{ {\hat v,q} \right\}$: 令

$\tilde f_1^v$=$\hat f_1^v$

b) 对$v = \hat v$: 若${{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{0\hat v}}$=0则令$\tilde f_1^{\hat v}$=0, 否则令

$\tilde f_1^{\hat v} = \max \left\{ {i|{{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{i\hat v}} = 1,1 \le i \le \hat f_1^{\hat v}} \right\}$;

c)对v=q: 若${{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{0q}}$=0则令$\tilde f_1^q = $0, 否则令

$\tilde f_1^q = $$\max \left\{ {i|{{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{iq}} = 1,1 \le i \le \hat f_1^q} \right\}$。

将上述变换记为∏, 即${ ilde \Gamma }$=∏$\hat \Gamma $。不难验证,${ ilde \Gamma }$满足最高楼层约束、乘客数目约束和电梯容量约束, 即${ ilde \Gamma }$∈Ωi,i=1,2,3。

上述调整后, 对任意i,v∈B$\hat \Gamma $, 由于eiv${ ilde \Gamma }$只与${{\tilde x}_{jk}}$(i≤j≤n,1≤k≤v)有关, 而这些${{\tilde x}_{jk}}$满足${{\tilde x}_{jk}}$=${{\hat x}_{jk}}$, 从而eiv${ ilde \Gamma }$=eiv$\hat \Gamma $,$\forall (i,v) \in B(\hat \Gamma )$; 又因为eiv$\hat \Gamma $=0,$\forall (i,v) \in B(\hat \Gamma )$, 所以eiv${ ilde \Gamma }$=0$\forall (i,v) \in B(\hat \Gamma )$, 即${ ilde \Gamma }$在任意(i,v)∈B$\hat \Gamma $处的电梯运行约束误差都为零。对$(\hat i,v)$, 有

${e_{\hat i\hat v}}(\tilde \Gamma ) = \min \left\{ {Q - \sum\limits_{k = i}^n {{{\tilde x}_{kv}}} ,{d_i} - \sum\limits_{k = 1}^v {{{\tilde x}_{ik}}_i} } \right\} = \min \left\{ {Q - \sum\limits_{k = i}^n {{{\hat x}_{kv}}} - \Delta x,{d_i} - \sum\limits_{k = 1}^v {{{\tilde x}_{ik}}_i} - \Delta x} \right\} = {e_{\hat i\hat v}}(\hat \Gamma ) - \Delta x$

由Δx>0可知,${e_{\hat i\hat v}}(\tilde \Gamma ) < {e_{\hat i\hat v}}(\hat \Gamma )$。又由式(14), (7)和(8)可知,${e_{\hat i\hat v}}(\tilde \Gamma ) \ge 0$。${ ilde \Gamma }$和$\hat \Gamma $中与优化目标相关的变量有如下关系:

$\tilde f_1^v = \hat f_1^v,\forall v \in V\backslash \left\{ {\hat v,q} \right\};\tilde f_1^{\hat v} \le \hat f_1^{\hat v};\tilde f_1^q = \hat f_1^q;$

${{\tilde y}_{iv}} = {{\hat y}_{iv}},\forall i \in I,v \in V,(i,v) \in \tilde A;\sum\limits_{(i,v) \in \tilde A} {{{\tilde y}_{iv}}} \le \sum\limits_{(i,v) \in \tilde A} {{{\hat y}_{iv}}} $

其中最后一个不等式成立是因为: 1)当$p = \hat i$时, 有

${{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{iv}} \le {{\hat y}_{iv}},\forall (i,v) \in \tilde A$;

2)当$p < \hat i$时, 有

${{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{iv}} \le {{\hat y}_{iv}},\forall (i,v) \in \tilde A\backslash \left\{ {(p,q)} \right\}$

${{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{pq}} \ge {{\hat y}_{pq}}$,

由式(14)可知, 此时必有${{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{p\hat v}} = 0$或${{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{\hat iq}} = 0$成立, 而${{\hat y}_{p\hat v}} = {{\hat y}_{\hat iq}} = 1$, 因而

$\sum\limits_{(i,v) \in \tilde A\backslash \left\{ {(p,q)} \right\}} {{{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over y} }_{iv}}} < \sum\limits_{(i,v) \in \tilde A\backslash \left\{ {(p,q)} \right\}} {{{\hat y}_{iv}}} $。

由式(5)可知${ ilde \Gamma }$的目标函数值不大于$\hat \Gamma $, 即通过变换∏得到的新解目标函数值不增大。这样, 经过调整得到的${ ilde \Gamma }$仍为P1的可行解, 其目标函数值不大于$\hat \Gamma $的目标函数值, 而其电梯运行约束误差相对$\hat \Gamma $有以下改进:

${e_{\hat i\hat v}}(\hat \Gamma ) > {e_{\hat i\hat v}}(\tilde \Gamma ) \ge 0,{e_{iv}}(\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over \Gamma } ) = {e_{\hat i\hat v}}(\hat \Gamma ) = 0,\forall (i,v) \in B(\hat \Gamma )$,

如式(12)所示。

综上分析可知, 从简化优化问题P1的任一可行解$\hat \Gamma $出发, 经过有限次简单调整, 可以获得原始优化问题P0的一个可行解, 其目标函数值不大于$\hat \Gamma $的目标函数值。因此,可以通过求解P1得到P0的最优解。可见,S-ESEE问题可以简化为求解P1

2 启发式算法

[10]中提出一种求解整数规划问题的两阶段启发式算法(2 stage heuristic algorithm, 2sHA): 第1阶段用满载直达往返疏散人数不小于电梯额定容量Q的楼层, 直到所有楼层待疏散人数都小于Q; 第2阶段对剩余待疏散楼层按启发式方法求解疏散策略。文[10]中的整数规划问题等价于P1, 因此2sHA算法也适用于求解P1。本文证明第1阶段不会影响得到最优疏散策略, 并提出求解P1的三阶段启发式算法(3sHA), 其中第1和2阶段与2sHA算法相同, 第3阶段进一步改进第2阶段得到的疏散策略。

2.1 阶段1对最优策略的影响

紧急疏散时可能出现待疏散楼层人数不小于电梯额定容量的情况, 这时可以指派电梯从疏散层去往该楼层满载后直接返回疏散层。本文将这样只访问1个楼层, 且疏散人数等于电梯额定容量的往返称为满载直达往返。也就是说, 当di≥Q,i∈I\{0}时, 楼层i可以被满载直达往返疏散, 而且该楼层最多可以被[di/Q]个满载直达往返疏散。假设已经得到P1的一个可行解$\hat \Gamma $, 其对应分量为$\hat f_1^v$、${{\hat x}_{iv}}$和${{\hat y}_{iv}}$, 其中v∈V,i∈I。对任意di≥Q的楼层i∈I\{0}, 令

$\begin{array}{l} {S^i}(\hat \Gamma ) = \left\{ {v|0 < {{\hat x}_{iv}} < Q,v \in V} \right\};\\ Ni(\hat \Gamma ) = \left\{ \begin{array}{l} \sum\limits_{v \in {S^i}(\hat \Gamma )} {{{\hat x}_{iv}}} ,{S^i}(\hat \Gamma ) \ne \emptyset ;\\ 0,{S^i}(\hat \Gamma ) = \emptyset . \end{array} \right. \end{array}$


其中,Si$\hat \Gamma $为访问楼层i的非满载直达往返集合,Ni$\hat \Gamma $为楼层i被Si$\hat \Gamma $中往返疏散的总人数。若Ni$\hat \Gamma $<Q则Ni$\hat \Gamma $=di-[di/Q]Q, 这说明楼层i已被尽可能多地满载直达往返疏散。

若Ni$\hat \Gamma $≥Q则访问楼层i的满载直达往返个数少于[di/Q]。令$\hat i = i$, 并令${\hat v}$为Si$\hat \Gamma $中访问的最高楼层最低的往返。由于${{\hat x}_{\hat i\hat v}}$<Q且Ni$\hat \Gamma $≥Q, 因此除往返${\hat v}$外一定还有其他非满载直达往返访问楼层${\hat i}$, 即

${S^{\hat i}}(\hat \Gamma )\backslash \left\{ {\hat v} \right\} \ne \emptyset $。

若电梯在第${\hat v}$次往返中只访问楼层${\hat i}$则令$p = \hat i$, 否则令p为电梯在该次往返中访问的除${\hat i}$外的任一待疏散楼层。任选$q \in {S^i}(\hat \Gamma )\backslash \left\{ {\hat v} \right\}$, 由往返${\hat v}$的最高楼层号最小可知, 楼层p不大于往返q的最高楼层, 即0<p≤f1q。令

$\Delta x = \left\{ \begin{array}{l} \min \left\{ {{{\hat x}_{p\hat v}},{{\hat x}_{\hat iq}}} \right\},p \ne \hat i;\\ \min \left\{ {Q - {{\hat x}_{\hat i\hat v}},{{\hat x}_{\hat iq}}} \right\},p = \hat i. \end{array} \right.$


易知Δx>0。利用重新定义的${\hat v}$、${\hat i}$、p、q和Δx, 按节1.2中的变换∏调整$\hat \Gamma $, 得到${ ilde \Gamma }$=∏$\hat \Gamma $。不难验证变换∏不使得新解${ ilde \Gamma }$目标函数值增大, 且${ ilde \Gamma }$仍为问题P1的可行解, 又由Δx>0可知,${ ilde \Gamma }$中分量${{ ilde x}_{\hat i\hat v}}$相对${{\hat x}_{\hat i\hat v}}$有以下改进:${{ ilde x}_{\hat i\hat v}}$<${{\hat x}_{\hat i\hat v}}$≤Q。由于${{ ilde x}_{\hat i\hat v}}$严格大于${{\hat x}_{\hat i\hat v}}$, 经过有限次调整必可使${{ ilde x}_{\hat i\hat v}}$增大到Q, 这时${ ilde \Gamma }$中的第${\hat v}$次往返是满载直达往返, 因此${ ilde \Gamma }$中楼层i被非满载直达往返疏散的总人数为Ni${ ilde \Gamma }$=Ni$\hat \Gamma $-Q。因此, 一定可以从$\hat \Gamma $出发, 经过有限次简单调整, 获得P1的新可行解${ ilde \Gamma }$, 其目标函数值不大于$\hat \Gamma $的目标函数值, 且Ni${ ilde \Gamma }$<Q。

基于以上分析可知, 一定存在这样的最优解, 使每个待疏散楼层都被尽可能多地满载直达往返疏散。可见, 第1阶段不会影响得到最优疏散策略。

2.2 改进的三阶段启发式算法

由于阶段1中的满载直达往返已达最优, 没有改进空间, 因此其疏散策略不需要调整。本节提出一些策略以改进文[10]阶段2的可行解, 从而减少总疏散时间, 例如交换2个往返所访问的楼层以减小电梯总运行距离, 合并对同一楼层的多次访问或增加电梯往返个数以减小楼层被访问次数。

1) 任务交换策略。

当往返p中疏散的最高楼层fp1的人数等于往返q中疏散的非最高楼层f的人数且f<fp1≤fq1时, 将往返p中楼层fp1的任务与往返q中楼层f的任务交换后, 2个往返中楼层被访问的总次数不会增多, 往返q中的最高楼不变, 但往返p中新的最高楼层max{f,fp2}严格降低, 其中fp2为调整前往返p中访问的次高楼层, 有fp2<fp1。由式(5)可知, 交换后总疏散时间严格减小。因此, 当存在上述情况时, 可以通过交换2个往返中不同楼层的任务以减少总疏散时间。本文将此策略称为任务交换策略。

2) 任务合并策略。

如果往返p和q都访问待疏散楼层i, 往返p为非满载往返且其剩余容量不小于往返q中楼层i的被疏散人数, 那么往返q中楼层i的访问任务可以合并到往返p中, 这样在保证合并后2个往返的最高楼层不增高且其他楼层被访问次数不变的前提下楼层i被访问次数减1, 从而使合并后总疏散时间严格减小。当大楼内总疏散人数不为Q的整数倍时, 必然有非满载往返, 并存在上述情况发生的可能性。这样, 本文提出以下任务合并策略: 对非满载往返p访问的每个楼层, 若存在往返q(q≠p), 且其疏散的楼层i的人数不大于往返p中电梯剩余容量, 则将往返q中该楼层的任务合并到往返p中。

3) 增加电梯往返个数策略。

阶段2采用mmin个电梯往返疏散, 而用最少电梯往返疏散不一定能得到最优解, 比如: 当n=4,d1=3,d2=d3=d4=Q-1,Q>3时,mmin=3, 用4个直达往返疏散和用mmin个满载往返疏散的最高楼层号之和分别为10和9, 而楼层被访问次数之和分别为8和9。可见用mmin+1个往返的最高楼层号之和 比用mmin个往返的大1, 但楼层被访问次数少1, 由式(5)可知, 当β-α>0时, 用mmin+1个直达非满载往返所需的总疏散时间比用mmin个满载非直达往返的更短。因此, 本文考虑在必要时增加电梯往返个数。

如果阶段2得到的疏散策略中楼层i被多个往返访问, 需要判断增加1个对该楼层的直达往返疏散该楼层是否会使得总疏散时间减小。记访问楼层i的往返集合记为Si。增加直达往返后, 直达往返疏散楼层i的时间代价为(αi+2β)。此时Si中往返的疏散时间之和减少αFs+βSi, 其中Fs为Si中往返不再访问楼层i后最高楼层号之和的减少量,|Si|为Si中往返的个数即楼层i被访问次数的减小量。这样, 当(αi+2β)-(αFs+β|Si|)<0时, 增加往返个数会使总疏散时间减小。本着尽可能减少楼层被电梯访问次数的原则, 本文提出如下增加电梯往返个数策略: 对每个楼层i, 若(αi+2β)-(αFs+β|Si|<0, 则将楼层i从所有往返中删除, 并增加一个新的直达往返疏散楼层i的待疏散乘客。

容易验证, 按以上3种策略调整得到的新解仍为P1的可行解, 即这些调整不改变解的可行性。

3 仿真实例

本节对提出的三阶段启发式算法3sHA进行性能测试。由于3sHA算法在阶段1用满载直达往返疏散di不小于Q的楼层, 满载直达往返所需的时间已达到最优, 所以本节只需对di均小于Q的情况进行测试。

在配置2.0 GB内存,2.61GHzAMDAthlon64X25000+处理器的计算机上利用MatlabR2010a平台进行数值实验。设大楼总层数为n+1,其中疏散层是楼层0,最高楼层为楼层n,电梯数量为1部,Q为16,式(5)中α=2.2,β=8.3。

对n=10和n=20这2种情况分别生成7组di(i=1,2,…,n),其中第1—5组中di均为0到(Q-1)之间的随机整数,第6—7组中di均为[Q/2]到(Q-1)之间的随机整数。

为了检验本文提出算法的效果,表1给出CPLEX、TS、FbF、2sHA和3sHA求解结果。CPLEX求解为用CPLEX软件直接求解整数线性规划P1,其结果为问题的最优解,但求解速度随问题规模的增大而变慢。当n=20时很难在可接受时间内求得最优解,因此只给出了n=10的最优结果以作比较。

表1中,m为电梯非空往返个数,F为电梯所有往返最高楼层号之和,N为待疏散楼层被电梯访问次数总和,Tm为目标函数,tc为算法运行时间。由于疏散层被访问次数等于非空往返个数,因此大楼内所有楼层被访问次数总和为m+N, 从而有Tm=αF+βm+N。

表1 启发式算法效果比较
算例算法mF N Tm/s tc/s
n=10 20 10 20 10 20 10 20 10 20
1 CPLEX 6 35 9 204.5 17.2
TS 9 19 47 202 9 19 256.4 767.4 <1 <1
FbF 6 12 34 131 14 30 244.8 645.2 <1 <1
2sHA 6 12 41 156 11 24 234.7 649.2 <1 <1
3sHA 6 12 34 135 11 21 225.9 577.5 <1 <1
2 CPLEX 3 20 8 137.5 1.2
TS 8 17 50 194 8 17 246 715.8 <1 <1
FbF 3 8 20 104 9 23 146 492.3 <1 <1
2sHA 3 8 23 117 8 18 144.1 478.4 <1 <1
3sHA 3 8 23 106 8 17 144.1 445.7 <1 <1
3CPLEX 5 27 10 186.9 8.9
TS 9 19 53 208 9 19 269.6 780.6 <1 <1
FbF 5 9 27 98 12 26 203.9 513.1 <1 <1
2sHA 5 9 35 109 10 21 204.5 494.8 <1 <1
3sHA 5 9 35 109 10 21 204.5 494.8 <1 <1
4CPLEX 6 32 13 223.4 106.1
TS 10 20 55 210 10 20 291 802 <1 <1
FbF 6 11 32 115 14 30 240.4 601.5 <1 <1
2sHA 6 11 41 142 13 24 251.7 609.9 <1 5.8
3sHA 6 11 41 135 13 24 251.7 594.5 <1 5.8
5CPLEX 7 39 17 230.3 40.6
TS 10 19 55 198 10 19 291 758.6 <1 <1
FbF 7 10 37 96 14 27 259.9 525.7 <1 <1
2sHA 7 10 49 119 14 23 286.3 542.3 <1 <1
3sHA 7 10 42 113 10 22 236.9 520.6 <1 <1
6 CPLEX 8 47 11 264.9 118.1
TS 10 20 55 210 10 20 291 802 <1 <1
FbF 8 15 45 158 17 34 311.5 764.1 <1 <1
2sHA 8 15 57 184 15 29 320.9 778.8 <1 45.6
3sHA 8 15 51 174 11 24 273.7 714.3 <1 45.6
7 CPLEX 8 45 12 269 187.9
TS 10 20 55 210 10 20 291 802 <1 <1
FbF 8 15 43 159 17 32 307.1 749.3 <1 <1
2sHA 8 15 51 178 15 29 307.7 765.6 <1 128.6
3sHA 8 15 45 164 12 27 269 717.8 <1 128.6

由算法原理可知TS的m为初始待疏散楼层个数Nf, FbF的m为所需的最少电梯往返个数mmin。从表1可以看出: 当mmin越接近Nf时, TS算法越优; 反之, 当mmin越小时, FbF算法越优。算例1—5中, 当n=10时FbF算法的Tm与3sHA的相近, 均优于TS算法; 其他情况中, 与TS、FbF和2sHA算法相比, 3sHA的Tm最优, 且N接近Nf即大多数待疏散楼层只被电梯访问一次。算例6—7中, 当n=20时2sHA和3sHA的Tc会变长, 这是由于这2例中m和n都增大, 使阶段2的计算复杂度增加。

4 结 论

本文改进疏散开始时刻各楼层待疏散人数已知的单电梯紧急疏散调度问题建模及求解。将问题建模成整数线性规划问题, 并将其简化为不含电梯运行约束的问题, 达到降低问题求解难度的目的。本文证明对于待疏散人数不小于电梯额定容量的楼层, 用尽可能多的满载直达往返疏散可以得到最优解。同时, 对已有的两阶段启发式算法提出改进策略, 提出有效的三阶段启发式算法。数值仿真表明: 三阶段启发式算法比已有算法具有更好的综合性能, 特别是在待疏散楼层人数较小且楼层数较大时该算法性能更佳。

致谢 本文得到清华大学—东芝能源与环境研究中心资助。

参考文献
[1] Heyes E, Spearpoint M.Lifts for evacuation-human behaviour considerations [J]. Fire and Materials, 2012, 36(4): 297-308.
[2] Hakonen H.Simulation of Building Traffic and Evacuation by Elevators [D]. Helsinki, Finland: Helsinki University of Technology, 2003.
[3] Proulx G, Heyes E, Hedman G, et al. The use of elevators for egress [C]//Proc 4th International Symposium on Human Behaviour in Fire. Cambridge, UK: Robinson College, 2009: 97-110.
[4] Kuligowski E.Elevators for occupant evacuation and fire department access [C]//Proc CIB-CTBUH International Conference on Tall Buildings. Kuala Lumpur, Malaysia: CIB, 2003: 193-200.
[5] Klote J, Deal S, Donoghue E, et al. Fire evacuation by elevators [J]. Elevator World, 1993, 41(6): 66-70.
[6] Kuligowski E, Bukowski R.Design of occupant egress system for tall buildings [C]//Proc 16th CIB World Building Congress: Building for the Future. Toronto, Canada: CIB, 2004.
[7] Klote J H, Levin B M, Groner N E. Emergency elevator evacuation systems [C]//Proc 2nd Symposium on Elevators, Fire, and Accessibility. Baltimore, USA: ASME, 1995: 131-149.
[8] Luh P, Xiong B, Chang S.Group elevator scheduling with advance information for normal and emergency modes [J]. IEEE Transactions on Automation Science and Engineering, 2008, 5(2): 245-258.
[9] Siikonen M L, Sorsa J S. Elevator evacuation algorithms [C]//Peacock R D, Kuligowski E D, Averill J D. Pedestrian and Evacuation Dynamics. New York: Springer-Verlag, 2011: 637-647.
[10] 王晶, 牟晓牧, 许鋆, 等. 紧急疏散电梯调度算法 [J]. 清华大学学报: 自然科学版, 2013, 53(7): 1041-1045.Wang Jing, Mu Xiaomu, Xu Jun, et al. Elevator scheduling algorithm for emergency evacuation [J]. J Tsinghua Univ (Sci & Technol), 2013, 53(7): 1041-1045.(in Chinese)
[11] Klote J. A method for calculation of elevator evacuation time [J]. Journal of Fire Protection Engineering, 1993, 5(3): 83-95.