基于遺傳算法的多目標電梯緊急疏散問題①

高慧生,許清風,房志明,黃 楠

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次?？看螖抵?每次?？看嬖趩ⅰ⑼蓚€過程),不單獨考慮相鄰樓層的情況,電梯每次停止或啟動時滿足以下關系：

在兩個相鄰樓層?？繒r,滿足：

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

其中,td為電梯開關門時間,?為電梯運行低效率系數,本文忽略電梯?？垦訒r,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)、電梯?？考s束(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 層以下任何因滿載造成的兩次以上?？慷紩箍偸枭r間增加,在低樓層時應盡量避免任何因滿載而多次?？康姆绞?

2.2 計算時間復雜度

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

綜上分析,每個樓層?？慷啻螘r,由于電梯啟停和開關門損失的時間會導致總疏散時間增加；其次,多次停靠會顯著增加編碼時長,極大減低程序運行效率.為簡化計算本文中每個樓層僅?？恳淮伪疚膶O小化電梯往返時間和電梯數量問題簡化為式(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 難問題,本文在此基礎上,建立了多目標緊急電梯調度模型,最小化疏散時間和電梯往返次數；通過分析樓層多次?？繉偸枭r間的影響,并增加了樓層運行約束降低時間復雜度,采用可以搜索全局最優解的遺傳算法求解模型,對固定參數(進出電梯時間、停靠損失時間)單獨計算減少程序運行時間.設定每個樓層的人群數量小于電梯額定容量,設置樓層數量不同的疏散場景模擬,并對比了本文算法和啟發式算法,實驗結果表明：在樓層數較少時(30 層),兩種算法相差不大；在樓層數量為60 層時,相同運行總樓層時遺傳算法可以減少往返次數,節省電梯使用數量；當樓層數量較多時(90 層),遺傳算法可以顯著減低運行總樓層數,減少疏散時間.隨著樓層數量的逐漸變多,遺傳算法的全局最優搜索方式可以獲得更優解.