蟻群算法思想在電梯群控運行中的應用研究

申益洙 朱德文

摘要：文章對電梯群控各種運行條件運用蟻群算法思想進行分析，提出了電梯群控在各種運行條件下所應遵循的6條常識性的約束規則，得到定理1、2和3，并加以證明，為電梯群控系統進行智能算法設計和實際應用以及轎廂的最優調度提供了必要條件。

關鍵詞：蟻群算法；電梯群控系統；約束規則；最優調度；轎廂調度 文獻標識碼：A

中圖分類號：TP391 文章編號：1009-2374（2016）18-0044-03 DOI：10.13535/j.cnki.11-4406/n.2016.18.023

電梯群控系統控制算法是指在特定的交通模式下電梯運行所遵循的控制策略。將智能算法和群智能理論應用到電梯群控系統中，有兩個問題需要解決：（1）所用電梯系統基礎參數要符合實際，而不能脫離實際工程；（2）要符合電梯群控的基本運行常識，而不能任意假設。在此基礎上才能更好地研究和應用智能算法。電梯群控系統中的轎廂在運行中不管采用上行交通、下行交通服務方式，還是采用層間交通、空閑交通服務方式，還是各種交通服務方式的組合，都要遵從基本的運行約束規則，由此出發才能應用和發展智能算法理論，否則將使智能算法脫離電梯群控轎廂運行的實際情況，而達不到對轎廂實施最優調度的目的。本文對電梯群控各種運行條件運用蟻群算法思想進行分析，提出了電梯群控在各種運行條件下所應遵循的6條常識性的約束規則，并證明了3條定理性的約束規則。這為電梯群控系統進行智能算法研究和實際應用準備了必要條件，也為電梯群控系統實際設計和配置打下了基礎。

1 電梯群控在各種運行條件下的常識性約束規則

對于某個層站呼叫來說，怎樣從電梯群控系統的各個轎廂中選擇1臺合適的（最優的）轎廂與之響應呢？除了遵守電梯運行常識性的規則外，一般來說，可按下面的常識性約束規則進行配置。

（a）同向運行的C2距離

j層近，取C2 （b）同向運行的C2距離

j層遠，取C2

約束規則1：對于某個在第j層的層站呼叫cj（1≤j≤n），都在同向運行轎廂C1、C2運行方向的前面或后面，且呼叫方向與之相同（或相反），則一般來說，取距離j層近的轎廂（或距離j層遠的轎廂）為配置轎廂（圖1）。

約束規則2：對于某個在第j層的層站呼叫cj（1≤j≤n），在同向運行轎廂C1的前面，而在同向運行轎廂C2的后面或在同向運行轎廂C1的后面，在同向運行轎廂C2的前面且呼叫方向與之相同，則一般來說，取轎廂C1或C2為配置轎廂；且呼叫方向與之相反，則一般來說，取轎廂C2或C1為配置轎廂。

約束規則3：對于某個在第j層的層站呼叫cj，在相向運行轎廂C1和C2的同一側，則一般來說，取層站呼叫在運行方向前面的轎廂（此時不管呼叫方向與該運行方向相同或相反）為配置轎廂。

約束規則4：對于某個在第j層層站呼叫cj，在相向運行轎廂C1和C2中間，則一般來說，取與呼叫方向同向的轎廂為配置轎廂。

約束規則5：對于某個在第j層的層站呼叫cj，在反向運行轎廂C1和C2的同側，呼叫方向背離或面向兩轎廂，則一般來說，取與呼叫方向同向的或反向的轎廂為配置轎廂。

約束規則6：對于某個在第j層的層站呼叫cj，在反向運行轎廂C1和C2的中間，呼叫方向上行或下行，則一般來說，取與呼叫方向反向的轎廂為配置轎廂。

2 蟻群算法思想的運用

蟻群算法以及包括它的群智能算法是極有潛力的智能算法。要想在電梯群控系統中應用蟻群算法，必須使蟻群算法適應和遵守電梯群控系統中的某些基本規則和常識，不能離開這些規則而亂用蟻群算法。

m臺轎廂相當于m只螞蟻，蟻巢相當于基站，螞蟻所在的節點相當于轎廂所在的層站，層站呼叫cj相當于螞蟻要尋找的食物。我們要探求的是：哪臺轎廂響應層站呼叫cj，即哪臺轎廂到達cj處所用時間最短，這相當于蟻群算法尋找到達食物點的最短路徑。所不同的是：蟻群算法通常尋找從蟻巢到食物點的最短路徑，而且有大量的螞蟻在尋找；電梯群控的“螞蟻”通常是分散的，即各臺轎廂或者說各臺轎廂所在的層站，找出某臺轎廂到cj處的最短路徑，即轎廂最短運行時間。而且轎廂臺數是有限的：2臺、3臺，1組群控電梯才8臺轎廂。這些能夠完全說明：電梯群控最優調度轎廂響應層站呼叫cj的問題，相當于蟻群算法問題。電梯群控問題也相當于蟻群算法中的TSP問題。在TSP問題中，每只螞蟻都要經過各個節點（城市）一次；在電梯群控問題中，從梯群{Ck}中任意取出2臺轎廂C1、C2，找出次優的1臺轎廂到層站呼叫cj的較短路徑；再任意取出第3臺轎廂和剛才的次優轎廂進行比較，找出第2次次優轎廂到層站呼叫cj的較短路徑；繼續下去，最后從梯群{Ck}中找出1臺最優轎廂Ck到層站呼叫cj的較短路徑。推廣地說，在某段時間內，所有層站呼叫記為呼叫集{cj}，記作R：R={cj}。具體問題是：對呼叫集{cj}中的某個層站呼叫cj，從梯群{Ck}中找出最優調度轎廂的問題。與此同時，在蟻群算法中通過螞蟻釋放出的信息素的強化與揮發，通過正反饋和分布式計算，通過較強的魯棒性及與其他方法的結合，通過大量螞蟻的行動而找到最短路徑（圖2）。在這里，信息素或其他參數是用ij路徑上的狀態轉移概率和局部或全局信息素更新規則來描述的，很多情況下是用整條路徑上的全局信息素更新規則來描述。這些狀態轉移概率和更新規則在各種情況下有不同的形式，甚至有還未發掘出的形式，這就使我們有可能運用蟻群算法思想創造性地推廣到更多的應用領域。在電梯群控中，某轎廂所在位置Cik（i=1，2，…，n；k=1，2，…，m）與層站呼叫樓層形成的路徑上的信息素，就是對應的路徑ij的距離，即對應轎廂Cik響應層站呼叫cj的運行時間。最短路徑就是對應最短運行時間（圖3）。

3 電梯群控運行約束條件的詳細分析

定理性約束規則1：對于某個在第j層的層站呼叫cj（1≤j≤n），都在同向運行轎廂C1、C2運行方向的前面，且呼叫方向與之相同或相反，C1、C2運行到第j層的運行時間分別為t1、t2，則當t1

定理1：在定理性約束規則1的定義下，如果有：

cj2-cj1>h（i2-i1）/[Ve（tpo+td）] （1）

則取轎廂C1為配置轎廂。

式中：h為層距；Ve為轎廂額定速度；tpo為每個乘客出轎廂時間；td為轎廂開關門單元時間。

證明：第1種情形，在第j層的層站呼叫cj方向與轎廂C1、C2的運行方向相同的情形下，在定理性約束規則1的定義下，當t1其中t1、t2分別為在第i1、i2層的轎廂C1、C2運行到第j層的運行時間。t1可用下式表示：

t1=Tr1+Tpo1+Td1 （2）

式中：Tr為轎廂C1由第i1層運行到層站呼叫樓層第j層的行車時間；Tpo1為從第i1層到第j層在轎廂C1內的乘客將要離梯的時間；Td1為從第i1層到第j層的轎廂C1的開關門時間。

Tr1≈h（j-i1）/Ve

Tpo1=tpocj1

Td1=tdcj1

式中：tpo為每個乘客出轎廂時間；td為轎廂開關門單元時間。

代入式（2）得：

t1=h（j-i1）/Ve+tpocj1+tdcj1=h（j-i1）/Ve+cj1（tpo+td）

同理，在第i2層的轎廂C2運行到第j層的運行時間t2為：

t2=h（j-i2）/Ve+cj2（tpo+td） （3）

t1