高慧生,許清風(fēng),房志明,黃 楠

1(上海理工大學(xué) 管理學(xué)院,上海 200093)

2(上海市建筑科學(xué)研究院,上海 200032)

高層建筑數(shù)量逐年增加[1],當(dāng)發(fā)生火災(zāi)、恐怖襲擊、地震等時(shí),相當(dāng)數(shù)量的人員需要安全及時(shí)地疏散至建筑外的安全區(qū)域.樓梯間作為應(yīng)急疏散通道被大多數(shù)人選擇[2],但隨著(超)高層建筑的建筑高度的增加,人員安全撤離需要的時(shí)間也顯著增加.在580 m 的建筑中,人群僅通過(guò)樓梯間安全疏散平均需要36±6.04 min[3],在疏散過(guò)程中由于疏散距離遠(yuǎn),人們會(huì)因年齡、性別、健康狀況、擁擠、煙霧等造成疏散速度緩慢[4-9],特別是老、弱、病、殘等特殊人群僅通過(guò)樓梯間緊急疏散是不現(xiàn)實(shí)的[10,11].由于電梯系統(tǒng)的安全性(耐火、耐高溫、防煙)技術(shù)的提高[12],在緊急情況時(shí)使用電梯應(yīng)急疏散成為可能[13,14],同時(shí)(超)高層建筑在設(shè)計(jì)、運(yùn)營(yíng)時(shí)也會(huì)考慮電梯輔助疏散技術(shù)[15].在非緊急情況時(shí),許多學(xué)者建立了考慮不同條件的電梯群控模型：文獻(xiàn)[16]考慮了電梯群系統(tǒng)的耗能總數(shù)最優(yōu)的調(diào)度算法,文獻(xiàn)[17]考慮最短距離的電梯群控算法.然而在緊急疏散時(shí)的電梯電鍍目標(biāo)是最小化所有人員的疏散時(shí)間,考慮疏散時(shí)間最短的單電梯緊急疏散調(diào)度問(wèn)題(ELVAC)已經(jīng)被很多學(xué)者進(jìn)行研究,主要包括：兩站?？糠?Two-Stop approach,TS)[18],逐層疏散算法(Floor-by-Floor algorithm,FbF)[19]等,王晶等[20]建立了非線性約束的整數(shù)規(guī)劃模型,通過(guò)劃分子集的方法證明該問(wèn)題是NP 難,采用兩階段啟發(fā)式算法得到樓層號(hào)的組合方式,求解模型.王晶等[21]通過(guò)線性化最高樓層約束改為整數(shù)線性規(guī)劃,采用3 階段啟發(fā)式算法求解模型,該算法的主要改進(jìn)方法是：交換2 個(gè)往返所訪問(wèn)的樓層、合并對(duì)同一樓層的多次訪問(wèn)和增加電梯往返次數(shù).但為了追求滿載而對(duì)同一樓層的多次訪問(wèn)可能會(huì)使得總疏散時(shí)間增大；考慮到多個(gè)電梯并行疏散的情況,增加往返次數(shù)會(huì)受到電梯數(shù)量的限制.隨著樓層數(shù)量的增加,求解時(shí)間也會(huì)顯著增加,在有限時(shí)間內(nèi)不一定能獲得最優(yōu)解.

事實(shí)上,部分電梯運(yùn)行參數(shù)僅與人員數(shù)量和電梯自身結(jié)構(gòu)有關(guān),如：開關(guān)門時(shí)間、啟停損失時(shí)間、人員起落時(shí)間等,這些固定參數(shù)可以單獨(dú)計(jì)算,避免求解模型時(shí)多次計(jì)算導(dǎo)致的時(shí)間損失.在建立模型時(shí),本文結(jié)合實(shí)際情況中電梯數(shù)量的限制,建立了考慮電梯數(shù)量和疏散時(shí)間最優(yōu)的多目標(biāo)非線性規(guī)劃模型.由于僅考慮電梯疏散時(shí)間最短的單目標(biāo)非線性約束整數(shù)規(guī)劃問(wèn)題[20]已經(jīng)被證明是NP 難問(wèn)題,本文模型也不能在有限時(shí)間內(nèi)獲得的最優(yōu)解,因此采用遺傳算法求解.通過(guò)對(duì)不同數(shù)量樓層的數(shù)值模擬實(shí)驗(yàn),驗(yàn)證了該算法的性能.

1 問(wèn)題建模

使用電梯輔助疏散時(shí),人員需要安全迅速地疏散至大廳后轉(zhuǎn)移至安全區(qū)域,分布在其他樓層(待疏散層)的人員,需要電梯不斷往返和樓梯間人群垂直疏散直至所有人都到達(dá)大廳.一座有n層樓建筑的樓層號(hào)集合為F={0,1,2,···,n},疏散時(shí)在每個(gè)樓層f∈F的人數(shù)是pi∈N,這一過(guò)程所需時(shí)間即為緊急電梯疏散的總時(shí)間tsum,它由電梯疏散準(zhǔn)備時(shí)間tp、電梯運(yùn)行時(shí)間te、人員從大廳疏散至安全地方時(shí)間t0組成.

其中,tp和t0為固定值,只能通過(guò)減小te使得總疏散時(shí)間降低.

電梯大廳出發(fā)到回到大廳的時(shí)間為一次往返,所用時(shí)間為tr,設(shè)J={1,2,···,j},其中第j?J次往返時(shí)間為,則電梯運(yùn)行時(shí)間滿足以下關(guān)系：

由于各個(gè)樓層中人員數(shù)量不能達(dá)到滿載,電梯在每次往返中可能在多個(gè)樓層?？?設(shè)第j次往返時(shí)?？繕菍雍脼镕i={1,2,···,m},顯然k≤n且為本次往返最高樓層.為了提高運(yùn)輸效率,電梯從大廳上行運(yùn)行至本次往返停靠的最高樓層,再下行依次?？科渌麡菍?直至大廳.假設(shè)一次往返中上行運(yùn)行時(shí)間為tT,電梯停止和啟動(dòng)損失時(shí)間tl,電梯?？繒r(shí)間為ts(包括電梯開關(guān)門時(shí)間、人員進(jìn)出電梯時(shí)間、和電梯保持開門時(shí)間),則第j次往返時(shí)間tr滿足以下條件：

其中,tT只與本次往返的最高樓層有關(guān),此處為不計(jì)算電梯啟、停時(shí)間的地面層至最高樓層的運(yùn)行時(shí)間,滿足：

為本次電梯停靠最高樓層號(hào),L為樓層間距,Ll為一次啟動(dòng)或停止過(guò)程中運(yùn)加速運(yùn)行距離.n是第j次?？看螖?shù)之和(每次?？看嬖趩ⅰ⑼蓚€(gè)過(guò)程),不單獨(dú)考慮相鄰樓層的情況,電梯每次停止或啟動(dòng)時(shí)滿足以下關(guān)系：

在兩個(gè)相鄰樓層?？繒r(shí),滿足：

其中,電梯加速度為a,最大額定速度為vmax,d為樓層間距.ts滿足：

其中,td為電梯開關(guān)門時(shí)間,?為電梯運(yùn)行低效率系數(shù),本文忽略電梯停靠延時(shí),ti和tu分為人員進(jìn)出電梯的時(shí)間,與進(jìn)、出電梯的人員數(shù)量Ni、Nu有關(guān)：

其中,tio、tiu是每個(gè)人進(jìn)出電梯的時(shí)間.因此trj簡(jiǎn)化為：

te滿足：

僅考慮疏散時(shí)間的優(yōu)化目標(biāo)是最小化所有往返最高樓層號(hào)和停靠次數(shù)的線性組合.電梯在運(yùn)行時(shí)還需要考慮其他條件限制：電梯上行時(shí)不?？咳魏螛菍又钡奖敬瓮底罡邩菍?電梯下行時(shí)才有人員進(jìn)出電梯,設(shè)變量代表第j次往返疏散的樓層i的乘客人數(shù),每次往返人數(shù)都不超過(guò)額定容量：

所有人員等待疏散不發(fā)生移動(dòng),每個(gè)樓層的人員數(shù)量為：

引入0-1 變量yij表示樓層i在第j次往返中電梯是否?？?yij=1 表示?？?yij=0 表示未停靠.則yij為第j次往返所?？康臉菍觽€(gè)數(shù)：

令zj=表示第j次往返所去往最高樓層號(hào),顯然：

文獻(xiàn)[21]中改進(jìn)啟發(fā)式算法優(yōu)化策略中通過(guò)增加電梯往返次數(shù),優(yōu)化疏散時(shí)間,但由于建筑中電梯數(shù)量約束和不同電梯容量、速度的差異,還應(yīng)減少電梯往返次數(shù)j.記滿足電梯額定容量約束式(13)、每個(gè)樓層人員數(shù)量約束(14)、電梯?？考s束(15)、最高樓層號(hào)約束(16)的解集合T分別為Ω1、Ω2、Ω3、Ω4,考慮電梯運(yùn)行約束及電梯數(shù)量限制,考慮極小化電梯往返時(shí)間和往返次數(shù)的問(wèn)題如式(17),即,問(wèn)題1：

2 模型簡(jiǎn)化

在不考慮待樓層號(hào)對(duì)疏散公平性的影響時(shí),緊急電梯調(diào)度問(wèn)題實(shí)際是最優(yōu)化不同樓層號(hào)的組合,使得總疏散時(shí)間最小和使用電梯數(shù)量最少.文獻(xiàn)[20]通過(guò)以下方法來(lái)獲得最優(yōu)解：

(1)交換不同往返的樓層組合；

(2)合并對(duì)同一樓層的多次停靠；

(3)增加電梯往返個(gè)數(shù)減少樓層停靠次數(shù).

這些交換策略可以通過(guò)遺傳算法對(duì)不同染色體的選擇來(lái)確定最優(yōu)解.遺傳算法可以通過(guò)隨機(jī)搜索獲得全局最優(yōu)解,主要包括以下策略：

(1)編碼：本文采用整數(shù)編碼方法,按照樓層編號(hào)構(gòu)建一組樓層號(hào)順序組合進(jìn)行求解.

(2)選擇：計(jì)算疏散時(shí)間和電梯數(shù)量作為適應(yīng)度；

(3)交叉：交叉不同個(gè)體的染色體,改變樓層號(hào)的組合方式；

(4)變異：通過(guò)對(duì)不同染色體變異,避免得到局部最優(yōu)解.

通過(guò)以上方式遺傳算法可以跳出局部最優(yōu)解,獲得全局優(yōu)化.

2.1 電梯滿載對(duì)總疏散時(shí)間的影響

在電梯疏散時(shí),單次電梯往返可以使電梯滿載運(yùn)行來(lái)提高疏散效率,減少疏散時(shí)間；但為了追求電梯的滿載運(yùn)行可能會(huì)使得某些樓層停靠多次造成運(yùn)行時(shí)間的增加.事實(shí)上,在樓層i有pi(pi＞0)個(gè)人需要疏散時(shí)存在以下2 種情況：

已疏散其他樓層人員但尚未達(dá)到額定容量時(shí),為滿足電梯滿載需要在樓層i處多次?？?假設(shè)?？縬次(ai≥p＞1),疏散該樓層的全部人員需要時(shí)間為t1滿足：

2)一次往返時(shí)僅疏散樓層i,疏散該樓層的全部人員需要時(shí)間為t2滿足：

設(shè)情形1 與情形2 的時(shí)間差值為Wl：

按照文獻(xiàn)[20]中實(shí)例計(jì)算：

電梯開關(guān)門和啟動(dòng)、停止時(shí)的加減速都會(huì)造成時(shí)間損失,根據(jù)式(17)計(jì)算可得,在25 層以下任何因滿載造成的兩次以上?？慷紩?huì)使總疏散時(shí)間增加,在低樓層時(shí)應(yīng)盡量避免任何因滿載而多次?？康姆绞?

2.2 計(jì)算時(shí)間復(fù)雜度

在一座有n個(gè)樓層的建筑中假設(shè)所有樓層的人數(shù)都不大于c,疏散時(shí)需要m次電梯往返,每個(gè)樓層中的人數(shù)ai滿足 0≤ai≤c,平均期望人數(shù)為c/2.采用遺傳算法求解時(shí),種群估摸為Np,最大迭代次數(shù)為Mgen.每個(gè)樓層僅?？恳淮螘r(shí),每次往返時(shí)需要被訪問(wèn)一次,編碼的時(shí)間復(fù)雜度為O(nm)；?？慷啻螘r(shí),每個(gè)樓層最糟糕的情況是需要被訪問(wèn)c/2,此時(shí)的最壞時(shí)間復(fù)雜度為O(min(m,c/2)n2).其他過(guò)程的時(shí)間復(fù)雜度如表1所示,每個(gè)樓層?？慷啻螘r(shí)會(huì)顯著增加程序計(jì)算時(shí)間.

綜上分析,每個(gè)樓層?？慷啻螘r(shí),由于電梯啟停和開關(guān)門損失的時(shí)間會(huì)導(dǎo)致總疏散時(shí)間增加；其次,多次?？繒?huì)顯著增加編碼時(shí)長(zhǎng),極大減低程序運(yùn)行效率.為簡(jiǎn)化計(jì)算本文中每個(gè)樓層僅?？恳淮伪疚膶O小化電梯往返時(shí)間和電梯數(shù)量問(wèn)題簡(jiǎn)化為式(22),即,問(wèn)題2：

其中,Z為非負(fù)整數(shù)集,M是一個(gè)充分大的正整數(shù).當(dāng)=1 時(shí),yij為 1 才能使約束條件成立；當(dāng)=0 時(shí),yij為1 或0 都滿足約束條件.

表1 兩種情況的時(shí)間復(fù)雜度計(jì)算

3 問(wèn)題求解

由于僅考慮電梯疏散時(shí)間最短的單目標(biāo)非線性約束整數(shù)規(guī)劃問(wèn)題[20]已經(jīng)被證明是NP 難問(wèn)題,本文模型不能在有限時(shí)間內(nèi)獲得的最優(yōu)解,本節(jié)給出一種遺傳算法對(duì)問(wèn)題2 進(jìn)行求解.存在人數(shù)大于c時(shí)的樓層時(shí),電梯必須進(jìn)行一次往返疏散,待所有樓層人數(shù)小于c 時(shí)在開始計(jì)算最小化疏散時(shí)間和往返次數(shù).算法流程如下：

Step 1.設(shè)定電梯額定容量為c,初始各個(gè)樓層人員數(shù)量為ai(0≤ai≤c,i?I).

Step 2.編碼(采用整數(shù)編碼方式,即所有樓層號(hào)的組合數(shù)列)、初始化種群,k=1.

Step 3.計(jì)算適應(yīng)度(根據(jù)染色體計(jì)算總疏散時(shí)間,其倒數(shù)作為適應(yīng)度函數(shù)；根據(jù)該染色體計(jì)算所需電梯數(shù)往返次數(shù)),k是否小于最大進(jìn)化次數(shù),若是,轉(zhuǎn)Step 7,否則,轉(zhuǎn)Step 4.

Step 4.依據(jù)適應(yīng)度選擇父母,適應(yīng)度高的個(gè)體被選中的概率高,適應(yīng)度低的個(gè)體被淘汰.

Step 5.用父母的染色體按照一定的方法進(jìn)行交叉,生成子代.

Step 6.對(duì)子代染色體進(jìn)行變異,由交叉和變異產(chǎn)生新一代種群,k=k+1,轉(zhuǎn)Step 3.

Step 7.返回所有往返?？康臉菍訉犹?hào)集合,算法結(jié)束.

具體參數(shù)設(shè)置如下：群體大小為150,遺傳算法的終止進(jìn)化代數(shù)根據(jù)不同樓層數(shù)量而變化以減少計(jì)算時(shí)間,交叉概率為0.95,變異概率為0.1.該算法的運(yùn)行結(jié)果即緊急疏散問(wèn)題的電梯調(diào)度策略.根據(jù)各往返樓層層號(hào)集合中最大值計(jì)算電梯運(yùn)行時(shí)間；固定時(shí)間單獨(dú)計(jì)算可減少程序運(yùn)行時(shí)間,包括：根據(jù)集合中元素個(gè)數(shù)計(jì)算啟停損失時(shí)間,人員進(jìn)出電梯時(shí)間和電梯開關(guān)門時(shí)間,以此可計(jì)算出總疏散時(shí)間.

4 仿真實(shí)例

為了對(duì)比不同算法的性能,本節(jié)對(duì)現(xiàn)有啟發(fā)式算法[20]和本文算法在同樣仿真環(huán)境進(jìn)行對(duì)比.使用1 部電梯進(jìn)行實(shí)驗(yàn),假設(shè)平均樓層間距為4.606,假定電梯額定速度為3 m/s,加速度為1.2 m/s2,電梯額定容量為6 層,開關(guān)門會(huì)時(shí)間之和為5.3 s,人員進(jìn)、出電梯時(shí)間分別為1 和0.6 s,初始是時(shí)刻各樓層人數(shù)為隨機(jī)產(chǎn)生額的[0,15]內(nèi)的隨機(jī)整數(shù).

為了檢驗(yàn)不同最高疏散樓層對(duì)算法的影響,隨機(jī)生成9 組各樓層乘客初始狀態(tài),兩種算法均使用Matlab 軟件進(jìn)行求解.通過(guò)對(duì)不同最高疏散樓層設(shè)置不同迭代次數(shù),可以減少計(jì)算耗時(shí),最大迭代次數(shù)遠(yuǎn)大于取得最優(yōu)值的迭代數(shù),某次實(shí)驗(yàn)結(jié)果如表2和圖1所示.圖1中僅計(jì)算電梯運(yùn)行時(shí)間,不包含固定時(shí)間.

表2 兩種算法的仿真結(jié)果對(duì)比

圖1 某次迭代過(guò)程

仿真結(jié)果表明：本算法在樓層數(shù)量較多時(shí)可以獲得更優(yōu)解.在樓層數(shù)較少時(shí)(算例1,2,3),兩種算法相差不大；在樓層數(shù)量為60 層時(shí)(算例4,5,6),相同運(yùn)行總樓層時(shí)遺傳算法可以減少往返次數(shù),節(jié)省電梯使用數(shù)量；當(dāng)樓層數(shù)量較多時(shí)(算例7,8,9),遺傳算法可以顯著減低運(yùn)行總樓層數(shù),減少疏散時(shí)間.隨著樓層數(shù)量的逐漸變多,遺傳算法的全局最優(yōu)搜索方式可以獲得更優(yōu)解.

5 結(jié)論

在緊急疏散時(shí),通過(guò)電梯輔助疏散技術(shù)可以提高疏散效率,緊急疏散電梯調(diào)度算法已經(jīng)被證明時(shí)NP 難問(wèn)題,本文在此基礎(chǔ)上,建立了多目標(biāo)緊急電梯調(diào)度模型,最小化疏散時(shí)間和電梯往返次數(shù)；通過(guò)分析樓層多次?？繉?duì)總疏散時(shí)間的影響,并增加了樓層運(yùn)行約束降低時(shí)間復(fù)雜度,采用可以搜索全局最優(yōu)解的遺傳算法求解模型,對(duì)固定參數(shù)(進(jìn)出電梯時(shí)間、?？繐p失時(shí)間)單獨(dú)計(jì)算減少程序運(yùn)行時(shí)間.設(shè)定每個(gè)樓層的人群數(shù)量小于電梯額定容量,設(shè)置樓層數(shù)量不同的疏散場(chǎng)景模擬,并對(duì)比了本文算法和啟發(fā)式算法,實(shí)驗(yàn)結(jié)果表明：在樓層數(shù)較少時(shí)(30 層),兩種算法相差不大；在樓層數(shù)量為60 層時(shí),相同運(yùn)行總樓層時(shí)遺傳算法可以減少往返次數(shù),節(jié)省電梯使用數(shù)量；當(dāng)樓層數(shù)量較多時(shí)(90 層),遺傳算法可以顯著減低運(yùn)行總樓層數(shù),減少疏散時(shí)間.隨著樓層數(shù)量的逐漸變多,遺傳算法的全局最優(yōu)搜索方式可以獲得更優(yōu)解.