基于遗传算法的多目标电梯紧急疏散问题①

高慧生,许清风,房志明,黄 楠

1(上海理工大学 管理学院,上海 200093)

2(上海市建筑科学研究院,上海 200032)

高层建筑数量逐年增加[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={0,1,2,···,n},疏散时在每个楼层f∈F的人数是pi∈N,这一过程所需时间即为紧急电梯疏散的总时间tsum,它由电梯疏散准备时间tp、电梯运行时间te、人员从大厅疏散至安全地方时间t0组成.

其中,tp和t0为固定值,只能通过减小te使得总疏散时间降低.

电梯大厅出发到回到大厅的时间为一次往返,所用时间为tr,设J={1,2,···,j},其中第jϵJ次往返时间为,则电梯运行时间满足以下关系：

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

其中,tT只与本次往返的最高楼层有关,此处为不计算电梯启、停时间的地面层至最高楼层的运行时间,满足：

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

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

其中,电梯加速度为a,最大额定速度为vmax,d为楼层间距.ts满足：

其中,td为电梯开关门时间,ϑ为电梯运行低效率系数,本文忽略电梯停靠延时,ti和tu分为人员进出电梯的时间,与进、出电梯的人员数量Ni、Nu有关：

其中,tio、tiu是每个人进出电梯的时间.因此trj简化为：

te满足：

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

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

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

令zj=表示第j次往返所去往最高楼层号,显然：

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

2 模型简化

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

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

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

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

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

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

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

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

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

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

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

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

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

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

设情形1 与情形2 的时间差值为Wl：

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

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

2.2 计算时间复杂度

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

综上分析,每个楼层停靠多次时,由于电梯启停和开关门损失的时间会导致总疏散时间增加；其次,多次停靠会显著增加编码时长,极大减低程序运行效率.为简化计算本文中每个楼层仅停靠一次本文将极小化电梯往返时间和电梯数量问题简化为式(22),即,问题2：

其中,Z为非负整数集,M是一个充分大的正整数.当=1 时,yij为 1 才能使约束条件成立；当=0 时,yij为1 或0 都满足约束条件.

表1 两种情况的时间复杂度计算

3 问题求解

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

Step 1.设定电梯额定容量为c,初始各个楼层人员数量为ai(0≤ai≤c,iϵ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/s2,电梯额定容量为6 层,开关门会时间之和为5.3 s,人员进、出电梯时间分别为1 和0.6 s,初始是时刻各楼层人数为随机产生额的[0,15]内的随机整数.

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

表2 两种算法的仿真结果对比

图1 某次迭代过程

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

5 结论

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