周衛(wèi)紅，裴 箏，和曉萍，李 晨，陸偉春

(1.云南民族大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，云南昆明650500;2.鄭州大學(xué)西亞斯國際學(xué)院，河南新鄭451150)

電梯群控系統(tǒng)指安裝在建筑物內(nèi)的3臺或者3臺以上的一組電梯作為一個有機(jī)整體，使用一個自動控制系統(tǒng)調(diào)度每一臺電梯的運(yùn)行.當(dāng)前大部分電梯調(diào)度算法，如靜態(tài)或動態(tài)分區(qū)的最小等待時間、目標(biāo)層登記算法等，集中在減少乘客的等待與運(yùn)行時間上，忽略了系統(tǒng)的耗能［1－2］.節(jié)能方面［3］，當(dāng)前的研究集中于單通道優(yōu)化來減少不必要的能耗，如無傳動牽引和能量反饋技術(shù)，沒有注意減少群控調(diào)度的能耗，實(shí)際上，在電梯群系統(tǒng)中，單通道節(jié)能模型中由于對乘客呼叫不合理的調(diào)度降低了節(jié)能的效能，因此研究電梯群控節(jié)能調(diào)度算法是有必要的.

電梯群控是調(diào)度一組多臺電梯服務(wù)于用戶的呼叫，屬于典型的組合優(yōu)化問題.我們采用仿生學(xué)的優(yōu)化算法——蟻群算法來解決這個離散組合優(yōu)化問題，蟻群算法適于解決離散組合優(yōu)化問題［4－5］，其良好的全局優(yōu)化能力與快速收斂能力適于電梯群控調(diào)度，蟻群算法已經(jīng)解決了許多調(diào)度問題，如TSP，車間調(diào)度，無線傳感器網(wǎng)絡(luò)的路由問題［6－8］等.

本文提出一種基于蟻群算法的電梯群調(diào)度算法，首先，以建立能耗目標(biāo)函數(shù)作為優(yōu)化目標(biāo)，建立一個基于圖的搜索機(jī)制的蟻群算法控制模型.模型中，每一只螞蟻代表每一臺電梯，每一蟻群代表代表一組電梯，圖中的不同結(jié)點(diǎn)代表從不同樓層乘客的呼叫服務(wù).每一個結(jié)點(diǎn)都會被蟻群遍歷，其次，把最少能耗的調(diào)度策略問題轉(zhuǎn)化為尋找最短路徑動態(tài)的TSP問題，模型約束條件來自于結(jié)點(diǎn)之間能量分配、電梯運(yùn)行邏輯、電梯選擇概率等，并對算法的收斂性進(jìn)行了研究，最后的仿真結(jié)果表明了調(diào)度算法的有效性.

1 能量目標(biāo)函數(shù)

以節(jié)能為導(dǎo)向的調(diào)度算法目標(biāo)是盡量減少耗能，首先，以電梯群的能耗為蟻群算法的優(yōu)化目標(biāo)函數(shù).電梯群的能耗由2個部分組成:啟動與停止耗能;勻速運(yùn)行的耗能.即E=Ea+Ev，這里，E代表整體的能耗，Ea代表加速與減速的能耗，Ev代表勻速的能耗［9］.

其中n代表電梯群的電梯數(shù)量，Ea、Ev是第r臺電梯的啟停和運(yùn)行的耗能.Ea、Ev按公式(2)、(3)計(jì)算.

其中p(r，s)表示第r臺電梯收到的啟停于第s層的請求的數(shù)量，q(r)表示第r臺電梯響應(yīng)呼叫的總數(shù)，并假設(shè)每臺電梯啟停耗能是個常量Ec.

其中nl(r，s，t)表示第r部電梯響應(yīng)從t層到s層請求的乘客總?cè)藬?shù)為乘客的平均質(zhì)量.h(r，s，t)是該電梯從t層到s層的位移.

綜合式(2)、(3)，模型中電梯群控總的能耗目標(biāo)函數(shù)由(4)式計(jì)算:

2 蟻群算法調(diào)度策略

蟻群算法能有效解決多節(jié)點(diǎn)(TSP)問題中的最短路徑優(yōu)化難題，電梯群控調(diào)度系統(tǒng)和這些問題很相似，所以非常適合采用蟻群算法來解決.當(dāng)然這里結(jié)點(diǎn)與路徑的涵義被延伸并增加了一些特殊的約束條件.

2.1 蟻群算法模型

設(shè)n臺電梯服務(wù)于m層的建筑物，根據(jù)調(diào)度電梯為各層服務(wù)的原則，蟻群模型將服務(wù)分為2層，向上服務(wù)層和向下服務(wù)層，ant1～antn代表n部電梯，u1～up代表向上服務(wù)的層，而點(diǎn)d1～dq代表向下服務(wù)的層，每一調(diào)度方案就是一個拓?fù)鋱D，螞蟻訪問所有呼叫點(diǎn)，也就是調(diào)度群中的電梯服務(wù)于每個呼叫層，例如，螞蟻1→u1→u2→dq，，就是表示螞蟻 1 按順序完成向上請求u1，u2，再完成向下請求dq，優(yōu)化就是從中找出一條最短路徑，對比用蟻群算法解決的TSP問題，在這個模型中每條路徑的長度的含義已改變了.路徑長度被定義為每種調(diào)度方案的能耗，因此最短路徑代表耗能最少，即最優(yōu)解.

2.2 約束條件

當(dāng)用蟻群算法解決電梯群控問題時，有必要討論模型的約束條件，其主要取決于電梯當(dāng)前的運(yùn)行狀態(tài)與運(yùn)行邏輯.將所有的呼叫層分為2個部分:上層呼叫與下層呼叫，節(jié)點(diǎn)的設(shè)置遵循“向上呼叫升序，向下呼叫降序”的原則并依據(jù)呼叫交通流的信號采樣設(shè)置時間間隔.與圖1相對應(yīng)，有u1＜u2＜…＜up，d1＜ d2… ＜ dq.在蟻群優(yōu)化的過程中，蟻群將按 u1，u2，…，uq、dq，…，d2，d1的順序設(shè)置路徑.為簡化算法，采用禁忌表避免多部電梯被調(diào)到同一呼叫層.

2.3 群控調(diào)度優(yōu)化

2.3.1 信息素更新

τij代表信息素，i代表電梯序列號，j代表呼叫節(jié)點(diǎn)的數(shù)目.路徑ij表示第i臺電梯將服務(wù)于第j個節(jié)點(diǎn)，信息素初始值設(shè)置為相同的最小值常量A，設(shè)置最小值的目的是為避免在迭代中丟失優(yōu)化結(jié)果，當(dāng)某些蟻群(電梯群)(ant1～antn)成功找到一條可行性調(diào)度方案，每條經(jīng)過路徑的信息素將按(5)式信息素更新.

其中C是一個常量，ΓK是第K組電梯群的調(diào)度方案總的能耗.

2.3.2 電梯選擇概率

其中allowedk是第k群電梯的可選呼叫節(jié)點(diǎn)集是第i臺電梯服務(wù)于第j層起停呼叫層服務(wù)的能耗，α，β是系數(shù).

2.4 算法流程圖

算法流程如圖1所示.

2.5優(yōu)化機(jī)制

蟻群算法是通過迭代尋求優(yōu)化結(jié)果，對于每一組電梯，每一呼叫層由哪臺電梯服務(wù)的機(jī)會是由決定，而由 τij和 1/決定.τij不斷更新其值，低能耗可行性路徑上的信息素越來越大.而1/確保對每呼叫層響應(yīng)的電梯最小的能耗，在迭代后，根據(jù)蟻群算法的正反饋機(jī)制，就能找到優(yōu)化的低能耗調(diào)度方案.圖1是蟻群控制策略節(jié)能的流程圖，在左邊的圖，算法加載了每個電梯的當(dāng)前情況和呼叫層、結(jié)點(diǎn)集、初始化的信息素，在每次迭代中，將產(chǎn)生一個調(diào)度方案，由公式(5)計(jì)算總的Γk，更新信息素.每一個調(diào)度方案的產(chǎn)生都需要右邊的步驟.

在文獻(xiàn)［9］的基礎(chǔ)上，我們對蟻群模型進(jìn)行了改進(jìn)，建立了新的上行高峰流和下行高峰流的更為精細(xì)的調(diào)度策略，因?yàn)樯闲懈叻辶髦写嬖诔丝椭饾u減少而在下行高峰流乘客逐漸增加的規(guī)律，本文改進(jìn)的蟻群算法考慮到這個因素，進(jìn)行了相關(guān)的優(yōu)化設(shè)置.

3 算法的收斂性

蟻群算法的收斂證明［10］如下:

引理 信息素τij有上界τmax=C/(Γmin·ρ).

證明 假設(shè)信息素的初始值為τ0，一次迭代后，其最大的增量是c/Γmin，因此最大的信息素是(1－ρ)τ0+c/Γmin，第2次迭代后，信息素的值為(1 －ρ)2τ0+(1 － ρ)τ0+c/Γmin，按此計(jì)算，由于信息素的揮發(fā)，經(jīng)過θ次迭代，信息素將會變小或者等于:

因?yàn)? ＜ρ≤1，τmax收斂于 C/(Γmin·ρ).

定理 p*(θ)表示經(jīng)過θ次迭代至少找到一條優(yōu)化方案的概率，當(dāng)給一個足夠大的θ，有公式

證明 由于信息素是介于τmax和τmin之間，令η=1/，因此η有1個上界和下界.電梯選擇概率最小值為

其中D是某一時刻可供選擇的呼叫層的數(shù)量，任意的調(diào)度方案包括最優(yōu)方案，可以以一定的概率得到，這里n代表呼叫的數(shù)量，因此只要一個螞蟻找到優(yōu)化方案就得到最優(yōu)解.對于p*(θ)的下界是由公式(θ)=1－(1－)θ推導(dǎo)得到，只要θ充分大，概率值可能大于1－ε(ε＞0是個任意小的量)，所以有

以上的結(jié)果表明本文算法能以概率1得到低能耗的調(diào)度方案.

4 試驗(yàn)仿真

為了驗(yàn)證算法的有效性，仿真是在虛擬電梯的環(huán)境下完成的，表1給出了各參量的數(shù)值.能量目標(biāo)初始參量(由OTIS電梯提供):啟停耗能22.5 kJ，箱體800 kg，平衡錘900 kg，乘客平均65 kg.仿真對于3種60 min的上行高峰流，任意間層交通流，下行高峰流交通流，與靜態(tài)調(diào)度算法、最小等待時間調(diào)度算法以及文獻(xiàn)［9］的算法進(jìn)行性能比較.本文改進(jìn)算法中，蟻群算法的參數(shù)值是 α=1，β=5，ρ=0.99，迭代次數(shù)200，等待時間的極限值為60 s，模擬的結(jié)果如表2.

結(jié)果表明蟻群算法與其它3種算法相比，在3種交通流的情況下，本文提出的改進(jìn)蟻群算法能有效地減少能耗，特別是在上行與下行的高峰期.然而在任意層間模式中，效果不明顯，另外算法為了追求低能耗犧牲了一些等待時間，例如在高峰期的等待時間有點(diǎn)長，但還是在可接受的范圍內(nèi)，這也是設(shè)置閾值的原因，目的是在沒有太多時間損耗的情況下盡可能減少能耗.

表1 仿真電梯參量值說明

表2 仿真試驗(yàn)結(jié)果

5 結(jié)語

采用蟻群算法解決電梯群控制的節(jié)能問題，首先建立能量目標(biāo)函數(shù)，其次提出以節(jié)能為導(dǎo)向的蟻群算法，建立蟻群電梯模型，提出基于信息素和選擇概率函數(shù)的收斂優(yōu)化機(jī)制.仿真結(jié)果表明，和已有的電梯群控算法相比，基于蟻群的算法在電梯群控中能有效地減少能耗.

［1］TAI J Z，YANG S Y，TAN H.Dispatching approach optimization of elevator group control system with destination floor guidance usingfuzzy neural network［C］//Proceeding of 8th World Congress on Intelligent Control and Automation(WCICA 2008).IEEE，2008:7085－7088.

［2］BARNEY G，SANTOS S D.Elevator traffic analysis，design and control［M］.Stevenage，U.K:Peregrinus，1985.

［3］LEE S，BAHN H.An energy－aware elevator group control system［C］//Proceeding in 3rd IEEE International Conference on Industrial Informatics.IEEE，2005:639 －643.

［4］DORIGO M，CARO G D，GAMBARDELLA L M.Ant algorithms for discrete optimization［J］.Artificial Life，1999，5(2):137 －172.

［5］YAGMAHAN B，YENISEY M M.A multi－objective ant colony system algorithm for flow shop scheduling problem［J］.Expert Systems with Applications，2010，37(2):1361 －1368.

［6］PURIS A，BELLO R，HERRERA F.Analysis of the efficacy of a Two－Stage methodology for ant colony optimization:Case of study with TSP and QAP［J］.Expert Systems with Applications，2010，37(7):5443 －5453.

［7］DHURANDHER S K，MISRA S，OBAIDAT M S，et al.An ant colony optimization approach for reputation and quality－of－service－based security in wireless sensor networks［J］.Security and Communication Networks，2009，2(2):215 －224.

［8］KADONO D，IZUMI T，OSHITA F.An ant colony optimization routing based on robustness for ad hoc networks with GPSs［J］.AD HOC Networks，2010，8(1):63 －76.

［9］ZHANG J L，TANG J，ZONG Q，LI J F.Energy－ saving scheduling strategy for elevator group control system based on ant colony optimization［C］//Proceedings of 2nd IEEE Youth Conference on Information，Computer and Telecommunications.IEEE，2010:37 －40.

［10］STUTZLE T，DORIGO M.A short convergence proof for a class of ant colony optimization algorithm［J］.IEEE Transactions on Evolutionary Computation，2012，6(2):358 －365.