基于遺傳算法的多目標(biāo)電梯緊急疏散問題①

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

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

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

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

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

1 問題建模

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

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

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

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

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

為本次電梯?？孔罡邩菍犹?L為樓層間距,Ll為一次啟動或停止過程中運(yùn)加速運(yùn)行距離.n是第j次?？看螖?shù)之和(每次?？看嬖趩?、停兩個過程),不單獨考慮相鄰樓層的情況,電梯每次停止或啟動時滿足以下關(guān)系：

在兩個相鄰樓層停靠時,滿足：

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

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

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

te滿足：

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

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

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

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

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

2 模型簡化

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

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

(2)合并對同一樓層的多次?？?；

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

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

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

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

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

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

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

2.1 電梯滿載對總疏散時間的影響

在電梯疏散時,單次電梯往返可以使電梯滿載運(yùn)行來提高疏散效率,減少疏散時間；但為了追求電梯的滿載運(yùn)行可能會使得某些樓層?？慷啻卧斐蛇\(yùn)行時間的增加.事實上,在樓層i有pi(pi＞0)個人需要疏散時存在以下2 種情況：

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

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

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

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

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

2.2 計算時間復(fù)雜度

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

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

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

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

3 問題求解

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

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

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

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

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

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

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

Step 7.返回所有往返?？康臉菍訉犹柤?算法結(jié)束.

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

4 仿真實例

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

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

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

圖1 某次迭代過程

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

5 結(jié)論

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