高层建筑数量逐年增加^[1], 当发生火灾、恐怖袭击、地震等时, 相当数量的人员需要安全及时地疏散至建筑外的安全区域. 楼梯间作为应急疏散通道被大多数人选择^[2], 但随着(超)高层建筑的建筑高度的增加, 人员安全撤离需要的时间也显著增加. 在580 m的建筑中, 人群仅通过楼梯间安全疏散平均需要36±6.04 min^[3], 在疏散过程中由于疏散距离远, 人们会因年龄、性别、健康状况、拥挤、烟雾等造成疏散速度缓慢^[4-9], 特别是老、弱、病、残等特殊人群仅通过楼梯间紧急疏散是不现实的^{[10, 11]}. 由于电梯系统的安全性(耐火、耐高温、防烟)技术的提高^[12], 在紧急情况时使用电梯应急疏散成为可能^{[13, 14]}, 同时(超)高层建筑在设计、运营时也会考虑电梯辅助疏散技术^[15]. 在非紧急情况时, 许多学者建立了考虑不同条件的电梯群控模型: 文献[16]考虑了电梯群系统的耗能总数最优的调度算法, 文献[17]考虑最短距离的电梯群控算法. 然而在紧急疏散时的电梯电镀目标是最小化所有人员的疏散时间, 考虑疏散时间最短的单电梯紧急疏散调度问题(ELVAC)已经被很多学者进行研究, 主要包括: 两站停靠法(Two-Stop approach, TS)^[18], 逐层疏散算法(Floor-by-Floor algorithm, FbF)^[19]等, 王晶等^[20]建立了非线性约束的整数规划模型, 通过划分子集的方法证明该问题是NP难, 采用两阶段启发式算法得到楼层号的组合方式, 求解模型. 王晶等^[21]通过线性化最高楼层约束改为整数线性规划, 采用3阶段启发式算法求解模型, 该算法的主要改进方法是: 交换2个往返所访问的楼层、合并对同一楼层的多次访问和增加电梯往返次数. 但为了追求满载而对同一楼层的多次访问可能会使得总疏散时间增大; 考虑到多个电梯并行疏散的情况, 增加往返次数会受到电梯数量的限制. 随着楼层数量的增加, 求解时间也会显著增加, 在有限时间内不一定能获得最优解.

事实上, 部分电梯运行参数仅与人员数量和电梯自身结构有关, 如: 开关门时间、启停损失时间、人员起落时间等, 这些固定参数可以单独计算, 避免求解模型时多次计算导致的时间损失. 在建立模型时, 本文结合实际情况中电梯数量的限制, 建立了考虑电梯数量和疏散时间最优的多目标非线性规划模型. 由于仅考虑电梯疏散时间最短的单目标非线性约束整数规划问题^[20]已经被证明是NP难问题, 本文模型也不能在有限时间内获得的最优解, 因此采用遗传算法求解. 通过对不同数量楼层的数值模拟实验, 验证了该算法的性能.

1 问题建模

使用电梯辅助疏散时, 人员需要安全迅速地疏散至大厅后转移至安全区域, 分布在其他楼层(待疏散层)的人员, 需要电梯不断往返和楼梯间人群垂直疏散直至所有人都到达大厅. 一座有n层楼建筑的楼层号集合为 $F = \left\{ {0,1,2 ,\cdots, {{n}}} \right\}$ , 疏散时在每个楼层 $f\in F$ 的人数是 ${p}_{i}\in {{N}}$ , 这一过程所需时间即为紧急电梯疏散的总时间 ${t_{\rm {sum}}}$ , 它由电梯疏散准备时间 ${t_p}$ 、电梯运行时间 ${t_e}$ 、人员从大厅疏散至安全地方时间 ${t_0}$ 组成.

${t_{\rm {sum}}} = {t_p} + {t_e} + {t_0}$

(1)

其中, ${t_p}$ 和 ${t_0}$ 为固定值, 只能通过减小 ${t_e}$ 使得总疏散时间降低.

电梯大厅出发到回到大厅的时间为一次往返, 所用时间为 ${t_r}$ , 设 $J = \left\{ {1,2, \cdots, j} \right\}$ , 其中第j $ \epsilon $ J次往返时间为 $t_r^j$ , 则电梯运行时间满足以下关系:

${t_e} = \sum\nolimits_{j \in J} {t_{\rm{r}}^{\rm{j}}} $

(2)

由于各个楼层中人员数量不能达到满载, 电梯在每次往返中可能在多个楼层停靠, 设第j次往返时停靠楼层好为 ${F_i} = \left\{ {1,2, \cdots, m} \right\}$ , 显然k $ \le n$ 且为本次往返最高楼层. 为了提高运输效率, 电梯从大厅上行运行至本次往返停靠的最高楼层, 再下行依次停靠其他楼层, 直至大厅. 假设一次往返中上行运行时间为 ${t_T}$ , 电梯停止和启动损失时间 ${t_l}$ , 电梯停靠时间为 ${t_s}$ (包括电梯开关门时间、人员进出电梯时间、和电梯保持开门时间), 则第j次往返时间 ${t_r}$ 满足以下条件:

$t_r^j = 2{t_T} + {t_s} + 2(n + 1){t_l}$

(3)

其中, ${t_T}$ 只与本次往返的最高楼层 $F_k^j$ 有关, 此处为不计算电梯启、停时间的地面层至最高楼层的运行时间, 满足:

$ {t}_{T}=\frac{{F}_{k}^{j} \cdot L-2{L}_{l}}{{v}_{\max}}$

(4)

$F_k^j$ 为本次电梯停靠最高楼层号, L为楼层间距, ${L_l}$ 为一次启动或停止过程中运加速运行距离. n是第j次停靠次数之和(每次停靠存在启、停两个过程), 不单独考虑相邻楼层的情况, 电梯每次停止或启动时满足以下关系:

$ {t}_{l}=\dfrac{{v}_{\max}\dfrac{{v}_{\max} -0}{a}-\dfrac{{v}_{\max}{}^{2}}{2a}}{{v}_{\max}}=\dfrac{{v}_{\max}}{a}\left(1-\dfrac{{v}_{\max}}{2}\right)$

(5)

在两个相邻楼层停靠时, 满足:

${t_l} = \frac{v}{t} = \frac{{\sqrt {2ad/2} }}{a}$

(6)

其中, 电梯加速度为a, 最大额定速度为 ${v_{\max}}$ , $d$ 为楼层间距. ${t_s}$ 满足:

${t_s} = ({t_i} + {t_u} + {t_d})(1 + \vartheta )$

(7)

其中, $ {t}_{d}$ 为电梯开关门时间, $\vartheta $ 为电梯运行低效率系数, 本文忽略电梯停靠延时, ${t_i}$ 和 ${t_u}$ 分为人员进出电梯的时间, 与进、出电梯的人员数量N_i、N_u有关:

${t_i} = {t_{io}}{N_i},\;{t_u} = {t_{uo}}{N_u}$

(8)

其中, ${t_{io}}$ 、 ${t_{iu}}$ 是每个人进出电梯的时间. 因此 $t_r^j$ 简化为:

$ \begin{split}{t}_{r}^{j}=&2\dfrac{{F}_{k}^{j}·L}{{v}_{\max}}+\left({t}_{io}{N}_{i}+{t}_{uo}{N}_{u}+{t}_{d}\right)\left(1+\vartheta \right)\\ &+2\left({{k}}+1\right)\dfrac{{v}_{\max}}{a}\left(1-\dfrac{{v}_{\max}}{2}\right)\end{split}$

(9)

$ {t_e}$ 满足:

$ \begin{split} &{{t_e}_r^j = 2\mathop \sum\limits_j {\mkern 1mu} \frac{{F_k^j\cdot L}}{{{v_{\max}}}} + (1 + \vartheta )\mathop \sum\limits_j {\mkern 1mu} \left( {{t_{io}}{N_i} + {t_{uo}}{N_u} + {t_d}} \right) }\\ &\;\;\;\;\;\;\;\;\;+ \mathop \sum\limits_j {\mkern 1mu}{(2n + 1)\dfrac{{{v_{\max}}}}{a}\left(1 - \dfrac{{{v_{\max}}}}{2}\right)} \end{split}\!\!\!\!\!\!\!\!\!\!\!\!\!$

(10)

其中, 人员进出时间 $\displaystyle\sum\limits_j {\left( {{t_{io}}{N_i} + {t_{uo}}{N_u}} \right)}$ 只与建筑物中需疏散人员数量有关, ${\displaystyle {\sum\limits _j}n}$ 为所有需要疏散人员的楼层数量之和. 上式可以进一步整合为:

${t_e} = \sum\nolimits_j {(\alpha F_k^j + \beta \left( {n + 1} \right)) + \gamma N + \delta } $

(11)

其中, ${\rm{\alpha }} = 2\dfrac{L}{{{v_{\max}}}}$ , $\beta = 2\dfrac{{{v_{\max}}}}{a}\left(1 - \dfrac{{{v_{\max}}}}{2}\right)$ , $\gamma = 1 + \vartheta \left( {{t_{io}} + {t_{uo}}} \right)$ , ${\rm{\delta }} = \gamma {t_d} + \beta $ . N为定值, 根据式(9)极小化 ${t_e}$ 可得:

$ \min \;{t}_{e}={\displaystyle {\sum }_{j}\alpha {F}_{k}^{j}+\beta n}$

(12)

仅考虑疏散时间的优化目标是最小化所有往返最高楼层号和停靠次数的线性组合. 电梯在运行时还需要考虑其他条件限制: 电梯上行时不停靠任何楼层直到本次往返最高楼层, 电梯下行时才有人员进出电梯, 设变量 $x_j^i$ 代表第 $j$ 次往返疏散的楼层 $i$ 的乘客人数, 每次往返人数都不超过额定容量:

$ {\displaystyle {\sum }_{i\epsilon I}{x}_{j}^{i}\le c}$

(13)

所有人员等待疏散不发生移动, 每个楼层的人员数量为:

$\sum\nolimits_{j \in J} {x_j^i = {p_i}} $

(14)

引入0-1变量 ${y_{ij}}$ 表示楼层 $i$ 在第j次往返中电梯是否停靠, ${y_{ij}}$ =1 表示停靠, ${y_{ij}}$ =0表示未停靠. 则 ${y_{ij}}$ 为第j次往返所停靠的楼层个数:

$\sum\nolimits_{i \in I} {{y_{ij}} = k\left( j \right)} $

(15)

令 ${{\textit{z}}_j} = F_k^j$ 表示第j次往返所去往最高楼层号, 显然:

$i{y_{ij}} \le {{\textit{z}}_j}$

(16)

文献[21]中改进启发式算法优化策略中通过增加电梯往返次数, 优化疏散时间, 但由于建筑中电梯数量约束和不同电梯容量、速度的差异, 还应减少电梯往返次数j. 记满足电梯额定容量约束式(13)、每个楼层人员数量约束(14)、电梯停靠约束(15)、最高楼层号约束(16)的解集合T分别为Ω₁、Ω₂、Ω₃、Ω₄, 考虑电梯运行约束及电梯数量限制, 考虑极小化电梯往返时间和往返次数的问题如式(17), 即, 问题1:

$\begin{split} &\min\left\{ { \alpha \displaystyle\sum\nolimits_j {{{\textit{z}}_j}} + \beta \displaystyle\sum\nolimits_i {\displaystyle\sum\nolimits_j {{y_{ij}}} } |}\right\} \\ &{{\rm {s.t.}}\;\;{\rm{ }}i \in I,j \in J,T \in {\Omega _m},m = 1,2,3,4 } \end{split}$

(17)

2 模型简化

在不考虑待楼层号对疏散公平性的影响时, 紧急电梯调度问题实际是最优化不同楼层号的组合, 使得总疏散时间最小和使用电梯数量最少. 文献[20]通过以下方法来获得最优解:

(1)交换不同往返的楼层组合;

(2)合并对同一楼层的多次停靠;

(3)增加电梯往返个数减少楼层停靠次数.

这些交换策略可以通过遗传算法对不同染色体的选择来确定最优解. 遗传算法可以通过随机搜索获得全局最优解, 主要包括以下策略:

(1)编码: 本文采用整数编码方法, 按照楼层编号构建一组楼层号顺序组合进行求解.

(2)选择: 计算疏散时间和电梯数量作为适应度;

(3)交叉: 交叉不同个体的染色体, 改变楼层号的组合方式;

(4)变异: 通过对不同染色体变异, 避免得到局部最优解.

通过以上方式遗传算法可以跳出局部最优解, 获得全局优化.

2.1 电梯满载对总疏散时间的影响　　

在电梯疏散时, 单次电梯往返可以使电梯满载运行来提高疏散效率, 减少疏散时间; 但为了追求电梯的满载运行可能会使得某些楼层停靠多次造成运行时间的增加. 事实上, 在楼层i有 ${p_i}$ ( ${p_i}$ >0)个人需要疏散时存在以下2种情况:

已疏散其他楼层人员但尚未达到额定容量时, 为满足电梯满载需要在楼层i处多次停靠, 假设停靠q次(a_i ≥ p > 1), 疏散该楼层的全部人员需要时间为 t₁满足:

${t_1} = 2q({t_l} + {t_d}) + {p_i}({t_{uo}} + {t_{io}})$

(18)

2)一次往返时仅疏散楼层i, 疏散该楼层的全部人员需要时间为t₂满足:

$ {t}_{2}=2\dfrac{i \cdot L}{{v}_{\max}}+4{t}_{l}+{p}_{i}({t}_{uo}+{t}_{io})+2{t}_{d}$

(19)

设情形1与情形2的时间差值为W_l:

${W_l} = {t_1} - {t_2} = 2({t_l} + {t_d})p - 2\frac{L}{{{v_{\max}}}}i - 2{t_l} - 4{t_d}$

(20)

按照文献[20]中实例计算:

${W_l} = 14.4q + 2.13i - 25$

(21)

电梯开关门和启动、停止时的加减速都会造成时间损失, 根据式(17)计算可得, 在25层以下任何因满载造成的两次以上停靠都会使总疏散时间增加, 在低楼层时应尽量避免任何因满载而多次停靠的方式.

2.2 计算时间复杂度

在一座有n个楼层的建筑中假设所有楼层的人数都不大于c, 疏散时需要m次电梯往返, 每个楼层中的人数a_i满足 $0 \le {a_i} \le c$ , 平均期望人数为c/2. 采用遗传算法求解时, 种群估摸为N_p, 最大迭代次数为M_gen. 每个楼层仅停靠一次时, 每次往返时需要被访问一次, 编码的时间复杂度为O(nm); 停靠多次时, 每个楼层最糟糕的情况是需要被访问c/2, 此时的最坏时间复杂度为O(min(m, c/2)n²). 其他过程的时间复杂度如表1所示, 每个楼层停靠多次时会显著增加程序计算时间.

综上分析, 每个楼层停靠多次时, 由于电梯启停和开关门损失的时间会导致总疏散时间增加; 其次, 多次停靠会显著增加编码时长, 极大减低程序运行效率. 为简化计算本文中每个楼层仅停靠一次 $\displaystyle\sum\nolimits_{i \in I} {\displaystyle\sum\nolimits_{j \in J} {{y_{ij}}} } = 1$ , 本文将极小化电梯往返时间和电梯数量问题简化为式(22), 即, 问题2:

$\begin{split} &\min \;\;\left\{ {\alpha \displaystyle\sum\nolimits_{j \in J} {{{\textit{z}}_j} + \beta \displaystyle\sum\nolimits_{i \in I} {\displaystyle\sum\nolimits_{j \in J} {{y_{ij}}} } } } \right\} \\ &{\rm {s.t.}}\;\;\;\displaystyle\sum\nolimits_i {x_j^i} \le c,i \in I;\\ &\;\;\;\;\;\;\;\;\;\displaystyle\sum\nolimits_i {x_j^i = {P_i},{\rm{ }}} i \in I;\\ &\;\;\;\;\;\;\;\;\;\displaystyle\sum\nolimits_i {\displaystyle\sum\nolimits_j {{y_{ij}}} } = {\rm{1,}}i \in I,j \in J;\\ &\;\;\;\;\;\;\;\;\;x_j^i \le M{y_{ij}},i{y_{ij}} \le {{\textit{z}}_j},i \in I,j \in J;\\ &\;\;\;\;\;\;\;\;\;x_j^i \in {\mathbb{Z}},{y_{ij}} \in [0,1],i \in I,j \in J; \end{split} $

(22)

其中, ${\mathbb{Z}}$ 为非负整数集, M是一个充分大的正整数. 当 $x_j^i$ =1时, ${y_{ij}}$ 为1才能使约束条件成立; 当 $x_j^i$ =0时, ${y_{ij}}$ 为1或0都满足约束条件.

3 问题求解

由于仅考虑电梯疏散时间最短的单目标非线性约束整数规划问题^[20]已经被证明是NP难问题, 本文模型不能在有限时间内获得的最优解, 本节给出一种遗传算法对问题2进行求解. 存在人数大于c时的楼层时, 电梯必须进行一次往返疏散, 待所有楼层人数小于c时在开始计算最小化疏散时间和往返次数. 算法流程如下:

Step 1. 设定电梯额定容量为c, 初始各个楼层人员数量为a_i (0 $ \le $ a_i $ \le $ c, $ i\epsilon I$ ).

Step 2. 编码(采用整数编码方式, 即所有楼层号的组合数列)、初始化种群, k=1.

Step 3. 计算适应度(根据染色体计算总疏散时间, 其倒数作为适应度函数; 根据该染色体计算所需电梯数往返次数), k是否小于最大进化次数, 若是, 转Step 7, 否则, 转Step 4.

Step 4. 依据适应度选择父母, 适应度高的个体被选中的概率高, 适应度低的个体被淘汰.

Step 5. 用父母的染色体按照一定的方法进行交叉, 生成子代.

Step 6. 对子代染色体进行变异, 由交叉和变异产生新一代种群, k=k+1, 转Step 3.

Step 7. 返回所有往返停靠的楼层层号集合, 算法结束.

具体参数设置如下: 群体大小为150, 遗传算法的终止进化代数根据不同楼层数量而变化以减少计算时间, 交叉概率为0. 95, 变异概率为0. 1. 该算法的运行结果即紧急疏散问题的电梯调度策略. 根据各往返楼层层号集合中最大值计算电梯运行时间; 固定时间单独计算可减少程序运行时间, 包括: 根据集合中元素个数计算启停损失时间, 人员进出电梯时间和电梯开关门时间, 以此可计算出总疏散时间.

4 仿真实例

为了对比不同算法的性能, 本节对现有启发式算法^[20]和本文算法在同样仿真环境进行对比.使用1部电梯进行实验, 假设平均楼层间距为4.606, 假定电梯额定速度为3 m/s, 加速度为1.2 m/s², 电梯额定容量为6层, 开关门会时间之和为5.3 s, 人员进、出电梯时间分别为1和0.6 s, 初始是时刻各楼层人数为随机产生额的[0, 15]内的随机整数.

为了检验不同最高疏散楼层对算法的影响, 随机生成9组各楼层乘客初始状态, 两种算法均使用Matlab软件进行求解. 通过对不同最高疏散楼层设置不同迭代次数, 可以减少计算耗时, 最大迭代次数远大于取得最优值的迭代数, 某次实验结果如表2和图1所示. 图1中仅计算电梯运行时间, 不包含固定时间.

仿真结果表明: 本算法在楼层数量较多时可以获得更优解. 在楼层数较少时(算例1,2,3), 两种算法相差不大; 在楼层数量为60层时(算例4,5,6), 相同运行总楼层时遗传算法可以减少往返次数, 节省电梯使用数量; 当楼层数量较多时(算例7,8,9), 遗传算法可以显著减低运行总楼层数, 减少疏散时间. 随着楼层数量的逐渐变多, 遗传算法的全局最优搜索方式可以获得更优解.

5 结论

在紧急疏散时, 通过电梯辅助疏散技术可以提高疏散效率, 紧急疏散电梯调度算法已经被证明时NP难问题, 本文在此基础上, 建立了多目标紧急电梯调度模型, 最小化疏散时间和电梯往返次数; 通过分析楼层多次停靠对总疏散时间的影响, 并增加了楼层运行约束降低时间复杂度, 采用可以搜索全局最优解的遗传算法求解模型, 对固定参数(进出电梯时间、停靠损失时间)单独计算减少程序运行时间. 设定每个楼层的人群数量小于电梯额定容量, 设置楼层数量不同的疏散场景模拟, 并对比了本文算法和启发式算法, 实验结果表明: 在楼层数较少时(30层), 两种算法相差不大; 在楼层数量为60层时, 相同运行总楼层时遗传算法可以减少往返次数, 节省电梯使用数量; 当楼层数量较多时(90层), 遗传算法可以显著减低运行总楼层数, 减少疏散时间. 随着楼层数量的逐渐变多, 遗传算法的全局最优搜索方式可以获得更优解.