陳玉仙，羅三定

（1.長沙航空職業(yè)技術(shù)學院，湖南 長沙 410124；2.中南大學信息科學與工程學院，湖南 長沙 410083）

1 引言

電梯調(diào)度問題是一類典型的NP 完全問題。由于電梯運行環(huán)境的復雜性和各部電梯相互之間運行規(guī)則的耦合性，使得獲取最優(yōu)的調(diào)度方案變得非常困難[1，2.。一般而言，電梯調(diào)度算法所遵循的方案中包括了“先到先服務”和“不達最終目的層不換向”等主要原則。這些原則的制定在一定意義上簡化了電梯調(diào)度的算法。然而，隨著高層建筑數(shù)量的增加，人們的出行對電梯的依賴性也逐漸增大，常規(guī)的電梯調(diào)度算法開始變得不適應突增的客流需求。同時，隨著樓宇自動化技術(shù)的不斷完善，各種信號檢測技術(shù)為發(fā)展電梯調(diào)度算法提供了技術(shù)保障。在這個意義上，新的電梯調(diào)度規(guī)則更注重于從全局意義上去協(xié)調(diào)電梯運行決策，盡可能充分利用電梯運載能力來滿足乘客出行的整體要求[3～5]。

一般而言，由于缺乏良好的信息融合技術(shù)，傳統(tǒng)的電梯調(diào)度中存在如下問題：

（1）調(diào)度系統(tǒng)未能敏捷地反映客流信息的變化。電梯可能出現(xiàn)滿載情況，在這種情況下當電梯經(jīng)過某一外呼樓層時，若不存在對應于該樓層的內(nèi)呼信號，電梯不應停留。但是，在傳統(tǒng)的控制系統(tǒng)中，電梯常常開門候客，從而降低了乘梯效率。

（2）多部電梯之間未能準確配合。當某一樓層存在外呼信號時，可能出現(xiàn)多部電梯同時響應的情況，這時先到的電梯已將乘客運輸完畢。由于外呼信號有時并沒能及時解除，可能另一部電梯也會在此樓層停留，出現(xiàn)了不必要的啟停情況。

（3）電梯運行未能顧及客流整體趨勢的變化。由于乘客達到電梯服務區(qū)時間的隨機性，可能導致在一個時刻進入轎廂的人數(shù)較小，而當電梯啟動時，客流量又出現(xiàn)猛增。這時電梯如果仍按原計劃運行將導致平均候梯時間的急劇上升，電梯服務效率下降。

我們注意到，上述諸種情況出現(xiàn)的原因大多是因為調(diào)度算法無法敏捷地反映客流情況的變化。隨著乘梯信息采集技術(shù)的進一步發(fā)展，為電梯決策系統(tǒng)提供了較為準確的客流形勢判斷。同時，硬件技術(shù)的進步為本文所提出的算法提供了良好的技術(shù)保障[6～9]。

2 電梯系統(tǒng)建模

為了詳細闡述文中所提出的算法，本節(jié)對單部電梯的控制規(guī)則進行舉例說明，由此可以推廣到多部電梯。本文將平均候梯時間（AWT）和平均乘梯時間（ART）兩個性能指標作為主要優(yōu)化的指標，將它們的加權(quán)平均函數(shù)作為代價函數(shù)，建立數(shù)學模型，并根據(jù)實時數(shù)據(jù)來計算代價函數(shù)的變化量，進而根據(jù)計算結(jié)果，判斷電梯的運行情況。從以下的分析可以看出：本文所提出的調(diào)度算法有效地顧及了客流信息的全局變化。例如，對第1節(jié)所提出的第三種問題，可以通過適度地延長電梯停留時間，改變電梯的調(diào)度策略就能夠改進服務質(zhì)量。

為了盡量減小派梯的滯后性對綜合性能指標的影響，本算法采用時變的采樣周期，即本采樣周期與電梯所處的位置相關(guān)，當電梯位于兩樓層的中間（即中間層）時系統(tǒng)要判斷電梯運行到下一整數(shù)層是否停，如果停，則電梯要在適當位置開始減速；否則，電梯繼續(xù)勻速運行。當電梯到達整數(shù)層停下來時，系統(tǒng)會根據(jù)此刻的所有信息判斷電梯的運動方向。由此思想建立的電梯停止代價函數(shù)計算式如式（1）所示。設(shè)電梯當前所處樓層為f 層，大樓總共高N 層。

各變量說明如下：

C0：電梯停時的代價函數(shù)（0表示電梯靜止）；λi：權(quán)系數(shù)。λ1：乘客候梯時間的權(quán)系數(shù)；λ2：乘客乘梯時間的權(quán)系數(shù)；T（r）：電梯運行時第r個采樣周期；spi，j：從i層到j(luò) 層的呼梯請求人數(shù)；p（i）：轎廂中到i層的乘客數(shù)。

一部電梯靜止時的代價函數(shù)綜合考慮了候梯時間和乘梯時間兩個性能指標，根據(jù)實際物理意義知：C0≥0，當C0＝0時，說明此時既沒有轎廂外的呼梯請求，轎廂中也沒有乘客。據(jù)此，電梯上行及下行時的代價函數(shù)如式（2）～式（3）所示：

其中，C1為電梯上行時的代價函數(shù)（1表示電梯向上運行）；C-1為電梯下行時的代價函數(shù)（-1表示電梯向下運行）；tfup為電梯?？吭趂層時，f層向上的乘客進入轎廂所需時間。其計算公式如式（4）所示：

其中，T3為每個乘客進、出轎廂所需時間。

tfdown為電梯停靠在f 層時，f 層向下的乘客進入轎廂所需的時間。其計算公式如式（5）所示。

T1為電梯從n層上行到（n＋1）層?；驈膎層下行至（n-1）層停所需的時間；T2為轎廂的開關(guān)門時間總和，即開門時間為T2／2，關(guān)門時間為T2／2。

ω（ω＞1）表示乘客未到達目的層，而電梯返向時轎廂中乘客的心理影響因子。

當有乘客在轎廂中已被返向一次后，如果即將發(fā)生第二次被返向時，ω→∞。即：每個乘客在一次乘梯過程中最多只發(fā)生一次返向現(xiàn)象。

單部電梯調(diào)度算法的程序流程圖如圖1所示。當電梯位于中間層時，根據(jù)采樣得到的相關(guān)信息，進行下一個整數(shù)層電梯是否?？康呐袛?；當電梯停于整數(shù)層時，再一次進行采樣，對電梯的運動狀態(tài)（上行、下行或停止）做出判斷。當所有請求均響應完畢后，電梯?？吭趯獦菍樱却罄m(xù)的呼梯請求。

Figure 1 Flowchart of scheduling algorithm for one elevator圖1 單部電梯調(diào)度算法流程圖

電梯位于中間層時的判斷過程對應的程序流程圖如圖2 所示。在圖2 中，當電梯位于中間層時，首先判斷轎廂中是否有乘客到達下一整數(shù)層，如果有，則電梯在下一整數(shù)層停靠（在適當位置電梯將開始減速，直至到下一整數(shù)層時速度減為0）；如果沒有，那么電梯將檢測轎廂是否滿載，如果滿載，則不停；如果未滿載，則將此時的所有信息代入電梯上、下行的代價函數(shù)表達式中進行計算，如果計算結(jié)果中，代價函數(shù)變化量較小的值對應的運行方向與電梯當前運行方向一致，則電梯在下一整數(shù)層不停靠；否則，電梯將停靠在下一整數(shù)層。這樣，電梯位于中間層的判斷過程結(jié)束。

Figure 2 Flowchart of decision program for elevator in middle floor圖2 電梯位于中間層時的判斷過程程序流程圖

電梯停靠于整數(shù)層后，系統(tǒng)根據(jù)此時的采樣數(shù)據(jù)判斷電梯下一時刻的運行狀態(tài)，其判斷過程的程序流程圖如圖3所示。在圖3中，電梯在整數(shù)層?？亢?，如果采樣到此時所有響應均已響應完畢，則電梯停止在當前層；如果采樣到仍有請求未完成響應，則需計算上、下行代價函數(shù)，如果上行代價函數(shù)小于下行代價函數(shù)，則電梯向上運行；否則，電梯向下運行。

Figure 3 Flowchart of decision program for elevator in integer floor圖3 電梯位于整數(shù)層時下一時刻運行狀態(tài)判斷過程的程序流程圖

3 調(diào)度算法比較研究

3.1 分步調(diào)度算法與先到先服務調(diào)度算法的對比分析

“先到先服務”是調(diào)度算法中一種最常用的規(guī)則。它通過對對象到達目的地的先后次序進行排隊，根據(jù)排隊結(jié)果對處于隊列位置靠前的對象進行優(yōu)先服務。一般而言，除非有特定的情形出現(xiàn)，對象到達服務點的時間越早，所享受服務的優(yōu)先權(quán)也就越高。對于電梯調(diào)度而言，“先到先服務”是指對所產(chǎn)生呼梯請求的先后時刻進行排序，系統(tǒng)將優(yōu)化響應那些產(chǎn)生時刻較早的呼梯請求。這種調(diào)度規(guī)則相對而言較為簡明、實施方便，但缺乏對系統(tǒng)所有信息的綜合考慮。該規(guī)則對局部范圍的系統(tǒng)優(yōu)化有一定作用，但當系統(tǒng)規(guī)模較大時其優(yōu)化性能將顯著降低[10～12]。

本課題在程序流程圖1～圖3的基礎(chǔ)上，以電梯停止、上行、下行的代價函數(shù)為判斷依據(jù)，以平均候梯時間（AWT）、平均乘梯時間（ART）、電梯啟停次數(shù)（RNC）和長時間候梯率（LWP）作為性能指標，編寫計算機程序?qū)Ρ疚奶岢龅乃惴ㄟM行仿真驗證。其中，電梯樓層設(shè)為10層，隨機產(chǎn)生各樓層進出電梯人數(shù)及呼叫信號。相關(guān)仿真參數(shù)如下：

電梯的額定速度v為1.5m／s，電梯的加、減速度a 為0.7m／s2，電梯的開、關(guān)門時間T2為4s，（每個）乘客出、入轎廂的時間T3為1.2s，標準樓層層距L 為3.30m，轎廂核定載客人數(shù)P核為15人。

為了較為客觀地研究本文所提算法的性能，避免個別參數(shù)數(shù)值大小對電梯性能產(chǎn)生干擾，課題組通過多次仿真研究，分析電梯性能改善的統(tǒng)計特性。

下面以一個實例說明本文所提算法的優(yōu)勢。

設(shè)當電梯?？坑? 樓時，9 樓出現(xiàn)了10 人下到1樓的請求，0.5 秒后10 樓出現(xiàn)了2 人下到1樓的請求，此后5分鐘內(nèi)沒有其它的請求。

所以，轎廂從n 層上行到n＋1層（或從n＋1層下行到n 層）停時所需時間為：T1＝t1＋t2＋t3＝15／7＋4／75＋15／7＝4.34 s。

設(shè)電梯從n層上行到n＋m 層（或從n＋m 層下行到n 層）停，中間沒有停站時所需時間為：t4＝4.34＋（[（n＋m）-n-1]l）／v＝4.34＋（m-1）×3.30／1.5s。

按照先到先服務的調(diào)度算法，電梯的調(diào)度過程如圖4～圖6所示。在圖4 中，左側(cè)為電梯轎廂，中間分別用上行和下行兩列數(shù)字來表示各樓層候梯乘客呼梯請求方向，某一層無呼梯請求時，將顯示0；有呼梯請求時將顯示發(fā)出請求的乘客數(shù)，候梯乘客數(shù)旁的圓圈的半徑與候梯乘客數(shù)成正比。右側(cè)為各樓層乘客的目的樓層按鍵，乘客每按下一次按鍵，系統(tǒng)將記錄一個呼梯乘客。當呼梯乘客進入轎廂后，對應的呼梯請求將被清零。圖4中顯示電梯位于8樓，轎廂內(nèi)無乘客，9樓有10人請求向下到1樓，10樓有2人請求下到1樓。

Figure 4 Sketch map for elevator in the 8th floor圖4 電梯位于8樓時示意圖

圖5顯示電梯到達9 樓后停下，10個乘客進入轎廂。

Figure 5 Sketch map for elevator in the 9th floor圖5 電梯位于9樓時的示意圖

圖6顯示電梯載著9樓要下行的10個乘客向1樓運行。

Figure 6 Sketch map for elevator running from the 9th floor to the 1st floor圖6 電梯從9樓向1樓運行時的示意圖

從圖4～圖6可以看出，電梯響應這些請求的運行路徑為：

這個調(diào)度過程中的相關(guān)性能指標計算如下。9樓10個乘客的總的候梯時間為：

9樓10個乘客的總的乘梯時間為：

10樓2個乘客的總的候梯時間為：

10樓2個乘客的總的乘梯時間為：

由此，可得到此次調(diào)度的平均候梯時間和平均乘梯時間分別為：

此次調(diào)度過程中電梯的啟停次數(shù)為4次。

因為10樓2個乘客的候梯時間為83.92s，故此次調(diào)度過程的長候梯率為：

綜上，此次基于先到先服務規(guī)則的調(diào)度過程的性能指標如下所示：平均候梯時間（AWT）：30.94s，平均乘梯時間（ART）：27.94s，啟停次數(shù)（RNC）：4次，長時間候梯率（LWP）：17%。

依據(jù)本文算法，電梯的調(diào)度過程如圖7和圖8所示。圖7顯示電梯經(jīng)過9樓直接到達10樓?？亢?，10樓向下的2個乘客進入轎廂；圖8 顯示，電梯從10樓向下運行到9樓?？亢螅?樓向下的10個乘客全部進入轎廂。此后，電梯將向1樓運行。

Figure 7 Sketch map for elevator running from the 9th floor to the 10th floor圖7 電梯經(jīng)過9樓直接到達10樓的運行示意圖

Figure 8 Sketch map for elevator running from the 10th floor to the 9th floor圖8 電梯從10樓下到9樓的運行示意圖

由于該算法對電梯運行過程實行分步優(yōu)化，能夠綜合考慮不同樓層之間的呼叫關(guān)聯(lián)。故此時的電梯的運行路徑修正為：8樓-10樓-9樓-1樓。

計算此次調(diào)度過程中的性能指標（此次計算過程同先到先服務算法中性能指標的計算過程相同，這里不再贅述），結(jié)果如下：平均候梯時間（AWT）：29.53s，平均乘梯時間（ART）：29.93s，啟停次數(shù)（RNC）：3次，長時間候梯率（LWP）：0%。

針對此次呼梯請求，兩種不同的調(diào)度過程對應的性能指標如表1所示。

Table 1 Performance comparison between step-by-step scheduling algorithm and first-in，first-serving scheduling algorithm表1 分步調(diào)度算法與先到先服務調(diào)度算法的性能指標對比

比較可以看出，本文提出的分步調(diào)度算法對電梯調(diào)度過程中的平均候梯時間（AWT）、長時間候梯率（LWP）及能量損耗（對應啟停次數(shù)（RNC））三個方面的性能指標均有所改善。由實例分析可得：本文算法與先到先服務算法相比平均候梯時間減小了4.56%，能量損耗減小了20%，完全避免了長時間候梯現(xiàn)象的發(fā)生。

3.2 分步調(diào)度算法與不達最終目的層不換向調(diào)度算法的對比分析

電梯基本運行參數(shù)與上一節(jié)一致。現(xiàn)當轎廂載有2個到10樓的乘客運行至3.5層時，采集到此時1樓有10個乘客向上呼梯至10樓。

根據(jù)不達最終目的層不換向調(diào)度算法的相關(guān)原理，電梯的調(diào)度過程如圖9～圖10 所示。圖9顯示轎廂中有2個乘客要上行至10樓，電梯正向上運行至4樓，此時1樓出現(xiàn)了上行至10樓的10個呼梯請求；圖10顯示轎廂依然載著2個乘客向上運行至10樓。此時電梯的運行路徑為：3樓-10樓-1樓-10樓。

計算此次調(diào)度過程中的性能指標（計算同先到先服務算法中性能指標的計算，過程不再贅述），結(jié)果如下：平均候梯時間（AWT）：50.68s，平均乘梯時間（ART）：28.83s，啟停次數(shù)（RNC）：3次，長時間候梯率（LWP）：83.3%。

基于本文所提出的分步調(diào)度算法，結(jié)合引言中所提出的相關(guān)策略，電梯的運行路徑更正為：3樓-4樓-1樓-10樓（仿真過程同3.1節(jié)中分步調(diào)度算法的仿真，此次不再贅述）。這種運行策略通過犧牲少數(shù)人的乘梯時間換取了乘客整體乘梯效率的改善[13～15]。同理可計算出此次調(diào)度過程中的性能指標數(shù)值如下：平均候梯時間（AWT）：24.23s，平均乘梯時間（ART）：36.59s，啟停次數(shù)（RNC）：3次，長時間候梯率（LWP）：0%。

Figure 9 Sketch map for elevator running between 3rdfloor and 4thfloor圖9 電梯運行至3.5樓時的狀態(tài)示意圖

Figure 10 Sketch map for elevator running to the 10th floor圖10 電梯向10樓運行的示意圖

針對此次呼梯請求，兩種不同的調(diào)度過程對應的性能指標如表2所示。

Table 2 Performance comparison between step-by-step scheduling algorithm and holding original running direction unless reaching final objective floor scheduling algorithm表2 分步調(diào)度算法與不達最終目的層不換向調(diào)度算法性能指標對比

由表2可以看出，本文提出的分步調(diào)度算法對電梯調(diào)度過程中的平均候梯時間（AWT）、長時間候梯率（LWP）兩個方面的性能指標有所改善。由實例分析可得，本文算法與不達最終目的層不換向的算法相比平均候梯時間減小了52.19%，并完全避免了長時間候梯現(xiàn)象的發(fā)生。

4 結(jié)束語

本文提出了一種基于數(shù)據(jù)融合的分步調(diào)度派梯方案。建立了電梯運行的數(shù)學模型并構(gòu)造了對應的調(diào)度算法。分別與傳統(tǒng)的“先到先服務算法”和“不達最終目的層不換向算法”進行了比較。仿真結(jié)果表明，本文所提出的調(diào)度算法的性能指標較之傳統(tǒng)算法有了一定的改善，在一定程度上證實了本算法的優(yōu)越性。

[1]Yang Zhen-shan，Shao Cheng.On the present situation and developing trends of elevator group supervisory control technologies[J].Control and Decision，2005，2.（12）：1321-1322.（in Chinese）

[2]Gina B.Vertical transportation in tall building[J].Elevator World，2003（5）：66-75.

[3]Zong Qun，Dou Li-qian，Liu Wen-jing，et al.Elevator group control scheduling based on robust optimization ＆ multi-agent coordination[J].Computer Integrated Manufacturing Systems，2008，14（3）：563-567.（in Chinese）

[4]Zhu Chang-ming，Bi Xiao-liang.Survey on elevator group control system[J].Urban Research，2003（S1）：1-6.（in Chinese）

[5]Dong Li.Research on elevator group control scheduling algorithm in high-rise construction[D].Changsha：Central South University，2008.（in Chinese）

[6]Xu Jin.The intrusion detection system based on data fusion[D].Xi'an：Xidian University，2006.（in Chinese）

[7]Shen Juan-juan，Chen Yao-wu.Internet based elevator remote monitoring system design[J].Modern Machinery，2006（4）：71-73.（in Chinese）

[8]Dai Bi-feng.The elevator synthesis information transmission system based on wireless network technology[D].Dalian：Dalian Maritime University，2008.（in Chinese）

[9]Yang Tao.The dynamic and best method of EGCS according to field knowledge[D].Chongqing：Chongqing University，2003.（in Chinese）

[10]Cortes P，Larraneta J，Onieva L.Genetic algorithm for controllers in elevator groups：Analysis and simulation during lunchpeak traffic[J].Applied Soft Computing，2004（4）：159-174.

[11]Friese P，Rambau J.Online-optimization of multi-elevator transport systems with reoptimization algorithms based on set-partitioning models[J].Discrete Applied Mathematics，2006（154）：1908-1931.

[12]Zong Qun，Cai Yu.Elevator dispatching method in idle traffic mode based on elevator traffic probability simulation model[J].Control and Decision，2002，17（3）：339-342.（in Chinese）

[13]Yang Zhen-shan，Shao Cheng，Ma Hai-feng.Prediction of traffic demand for elevator group control system using iterative learning[J].Control and Decision，2008，2.（3）：302-305.（in Chinese）

[14]Zong Qun，Tong Ling，Xue Li-hua.Research on intelligent optimal dispatching method in elevator group control systems[J].Control and Decision，2004，19（8）：939-942.（in Chinese）

[15]Zhu De-wen，F(xiàn)u Guo-jiang.Elevator group control technology[M].Beijing：China Electric Power Press，2006.（in Chinese）

附中文參考文獻：

[1]楊禎山，邵誠.電梯群控技術(shù)的現(xiàn)狀與發(fā)展方向[J].控制與決策，2005，2.（12）：1321-1322.

[3]宗群，竇立謙，劉文靜.魯棒優(yōu)化與多智能體協(xié)調(diào)的電梯群控調(diào)度[J].計算機集成制造系統(tǒng)，2008，14（3）：563-567.

[4]朱昌明，畢曉亮.電梯智能群控系統(tǒng)研究概況[J].現(xiàn)代城市研究，2003（S1）：1-6.

[5]董驪.高層建筑電梯群控調(diào)度算法研究[D].長沙：中南大學，2008.

[6]徐進.基于數(shù)據(jù)融合的入侵檢測系統(tǒng)[D].西安：西安電子科技大學，2006.

[7]沈娟娟，陳耀武.網(wǎng)絡(luò)化電梯遠程監(jiān)控系統(tǒng)設(shè)計[J].現(xiàn)代機械，2006（4）：71-73.

[8]戴必鋒.基于無線網(wǎng)絡(luò)技術(shù)的電梯綜合信息傳輸系統(tǒng)[D].大連：大連海事大學，2008.

[9]楊濤.基于領(lǐng)域知識的電梯動態(tài)最佳群控方法[D].重慶：重慶大學，2003.

[12]宗群，蔡昱.基于電梯交通流概率仿真模型的空閑交通模式電梯調(diào)度方法[J].控制與決策，2002，17（3）：339-342.

[13]楊禎山，邵誠，馬海豐.電梯群控系統(tǒng)交通需求的迭代學習預測方法[J].控制與決策，2008，2.（3）：302-305.

[14]宗群，童玲，薛麗華.電梯群控系統(tǒng)智能優(yōu)化調(diào)度方法的研究[J].控制與決策，2004，19（8）：939-942.

[15]朱德文，付國江.電梯群控技術(shù)[M].北京：中國電力出版社，2006.