蚁群算法思想在电梯群控运行中的应用研究

申益洙 朱德文

摘要：文章对电梯群控各种运行条件运用蚁群算法思想进行分析，提出了电梯群控在各种运行條件下所应遵循的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