陈玉仙，罗三定

（1.长沙航空职业技术学院，湖南 长沙 410124；2.中南大学信息科学与工程学院，湖南 长沙 410083）

1 引言

电梯调度问题是一类典型的NP 完全问题。由于电梯运行环境的复杂性和各部电梯相互之间运行规则的耦合性，使得获取最优的调度方案变得非常困难[1，2.。一般而言，电梯调度算法所遵循的方案中包括了“先到先服务”和“不达最终目的层不换向”等主要原则。这些原则的制定在一定意义上简化了电梯调度的算法。然而，随着高层建筑数量的增加，人们的出行对电梯的依赖性也逐渐增大，常规的电梯调度算法开始变得不适应突增的客流需求。同时，随着楼宇自动化技术的不断完善，各种信号检测技术为发展电梯调度算法提供了技术保障。在这个意义上，新的电梯调度规则更注重于从全局意义上去协调电梯运行决策，尽可能充分利用电梯运载能力来满足乘客出行的整体要求[3～5]。

一般而言，由于缺乏良好的信息融合技术，传统的电梯调度中存在如下问题：

（1）调度系统未能敏捷地反映客流信息的变化。电梯可能出现满载情况，在这种情况下当电梯经过某一外呼楼层时，若不存在对应于该楼层的内呼信号，电梯不应停留。但是，在传统的控制系统中，电梯常常开门候客，从而降低了乘梯效率。

（2）多部电梯之间未能准确配合。当某一楼层存在外呼信号时，可能出现多部电梯同时响应的情况，这时先到的电梯已将乘客运输完毕。由于外呼信号有时并没能及时解除，可能另一部电梯也会在此楼层停留，出现了不必要的启停情况。

（3）电梯运行未能顾及客流整体趋势的变化。由于乘客达到电梯服务区时间的随机性，可能导致在一个时刻进入轿厢的人数较小，而当电梯启动时，客流量又出现猛增。这时电梯如果仍按原计划运行将导致平均候梯时间的急剧上升，电梯服务效率下降。

我们注意到，上述诸种情况出现的原因大多是因为调度算法无法敏捷地反映客流情况的变化。随着乘梯信息采集技术的进一步发展，为电梯决策系统提供了较为准确的客流形势判断。同时，硬件技术的进步为本文所提出的算法提供了良好的技术保障[6～9]。

2 电梯系统建模

为了详细阐述文中所提出的算法，本节对单部电梯的控制规则进行举例说明，由此可以推广到多部电梯。本文将平均候梯时间（AWT）和平均乘梯时间（ART）两个性能指标作为主要优化的指标，将它们的加权平均函数作为代价函数，建立数学模型，并根据实时数据来计算代价函数的变化量，进而根据计算结果，判断电梯的运行情况。从以下的分析可以看出：本文所提出的调度算法有效地顾及了客流信息的全局变化。例如，对第1节所提出的第三种问题，可以通过适度地延长电梯停留时间，改变电梯的调度策略就能够改进服务质量。

为了尽量减小派梯的滞后性对综合性能指标的影响，本算法采用时变的采样周期，即本采样周期与电梯所处的位置相关，当电梯位于两楼层的中间（即中间层）时系统要判断电梯运行到下一整数层是否停，如果停，则电梯要在适当位置开始减速；否则，电梯继续匀速运行。当电梯到达整数层停下来时，系统会根据此刻的所有信息判断电梯的运动方向。由此思想建立的电梯停止代价函数计算式如式（1）所示。设电梯当前所处楼层为f 层，大楼总共高N 层。

各变量说明如下：

C0：电梯停时的代价函数（0表示电梯静止）；λi：权系数。λ1：乘客候梯时间的权系数；λ2：乘客乘梯时间的权系数；T（r）：电梯运行时第r个采样周期；spi，j：从i层到j 层的呼梯请求人数；p（i）：轿厢中到i层的乘客数。

一部电梯静止时的代价函数综合考虑了候梯时间和乘梯时间两个性能指标，根据实际物理意义知：C0≥0，当C0＝0时，说明此时既没有轿厢外的呼梯请求，轿厢中也没有乘客。据此，电梯上行及下行时的代价函数如式（2）～式（3）所示：

其中，C1为电梯上行时的代价函数（1表示电梯向上运行）；C-1为电梯下行时的代价函数（-1表示电梯向下运行）；tfup为电梯停靠在f层时，f层向上的乘客进入轿厢所需时间。其计算公式如式（4）所示：

其中，T3为每个乘客进、出轿厢所需时间。

tfdown为电梯停靠在f 层时，f 层向下的乘客进入轿厢所需的时间。其计算公式如式（5）所示。

T1为电梯从n层上行到（n＋1）层停或从n层下行至（n-1）层停所需的时间；T2为轿厢的开关门时间总和，即开门时间为T2／2，关门时间为T2／2。

ω（ω＞1）表示乘客未到达目的层，而电梯返向时轿厢中乘客的心理影响因子。

当有乘客在轿厢中已被返向一次后，如果即将发生第二次被返向时，ω→∞。即：每个乘客在一次乘梯过程中最多只发生一次返向现象。

单部电梯调度算法的程序流程图如图1所示。当电梯位于中间层时，根据采样得到的相关信息，进行下一个整数层电梯是否停靠的判断；当电梯停于整数层时，再一次进行采样，对电梯的运动状态（上行、下行或停止）做出判断。当所有请求均响应完毕后，电梯停靠在对应楼层，等待后续的呼梯请求。

Figure 1 Flowchart of scheduling algorithm for one elevator图1 单部电梯调度算法流程图

电梯位于中间层时的判断过程对应的程序流程图如图2 所示。在图2 中，当电梯位于中间层时，首先判断轿厢中是否有乘客到达下一整数层，如果有，则电梯在下一整数层停靠（在适当位置电梯将开始减速，直至到下一整数层时速度减为0）；如果没有，那么电梯将检测轿厢是否满载，如果满载，则不停；如果未满载，则将此时的所有信息代入电梯上、下行的代价函数表达式中进行计算，如果计算结果中，代价函数变化量较小的值对应的运行方向与电梯当前运行方向一致，则电梯在下一整数层不停靠；否则，电梯将停靠在下一整数层。这样，电梯位于中间层的判断过程结束。

Figure 2 Flowchart of decision program for elevator in middle floor图2 电梯位于中间层时的判断过程程序流程图

电梯停靠于整数层后，系统根据此时的采样数据判断电梯下一时刻的运行状态，其判断过程的程序流程图如图3所示。在图3中，电梯在整数层停靠后，如果采样到此时所有响应均已响应完毕，则电梯停止在当前层；如果采样到仍有请求未完成响应，则需计算上、下行代价函数，如果上行代价函数小于下行代价函数，则电梯向上运行；否则，电梯向下运行。

Figure 3 Flowchart of decision program for elevator in integer floor图3 电梯位于整数层时下一时刻运行状态判断过程的程序流程图

3 调度算法比较研究

3.1 分步调度算法与先到先服务调度算法的对比分析

“先到先服务”是调度算法中一种最常用的规则。它通过对对象到达目的地的先后次序进行排队，根据排队结果对处于队列位置靠前的对象进行优先服务。一般而言，除非有特定的情形出现，对象到达服务点的时间越早，所享受服务的优先权也就越高。对于电梯调度而言，“先到先服务”是指对所产生呼梯请求的先后时刻进行排序，系统将优化响应那些产生时刻较早的呼梯请求。这种调度规则相对而言较为简明、实施方便，但缺乏对系统所有信息的综合考虑。该规则对局部范围的系统优化有一定作用，但当系统规模较大时其优化性能将显著降低[10～12]。

本课题在程序流程图1～图3的基础上，以电梯停止、上行、下行的代价函数为判断依据，以平均候梯时间（AWT）、平均乘梯时间（ART）、电梯启停次数（RNC）和长时间候梯率（LWP）作为性能指标，编写计算机程序对本文提出的算法进行仿真验证。其中，电梯楼层设为10层，随机产生各楼层进出电梯人数及呼叫信号。相关仿真参数如下：

电梯的额定速度v为1.5m／s，电梯的加、减速度a 为0.7m／s2，电梯的开、关门时间T2为4s，（每个）乘客出、入轿厢的时间T3为1.2s，标准楼层层距L 为3.30m，轿厢核定载客人数P核为15人。

为了较为客观地研究本文所提算法的性能，避免个别参数数值大小对电梯性能产生干扰，课题组通过多次仿真研究，分析电梯性能改善的统计特性。

下面以一个实例说明本文所提算法的优势。

设当电梯停靠于8 楼时，9 楼出现了10 人下到1楼的请求，0.5 秒后10 楼出现了2 人下到1楼的请求，此后5分钟内没有其它的请求。

所以，轿厢从n 层上行到n＋1层（或从n＋1层下行到n 层）停时所需时间为：T1＝t1＋t2＋t3＝15／7＋4／75＋15／7＝4.34 s。

设电梯从n层上行到n＋m 层（或从n＋m 层下行到n 层）停，中间没有停站时所需时间为：t4＝4.34＋（[（n＋m）-n-1]l）／v＝4.34＋（m-1）×3.30／1.5s。

按照先到先服务的调度算法，电梯的调度过程如图4～图6所示。在图4 中，左侧为电梯轿厢，中间分别用上行和下行两列数字来表示各楼层候梯乘客呼梯请求方向，某一层无呼梯请求时，将显示0；有呼梯请求时将显示发出请求的乘客数，候梯乘客数旁的圆圈的半径与候梯乘客数成正比。右侧为各楼层乘客的目的楼层按键，乘客每按下一次按键，系统将记录一个呼梯乘客。当呼梯乘客进入轿厢后，对应的呼梯请求将被清零。图4中显示电梯位于8楼，轿厢内无乘客，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可以看出，电梯响应这些请求的运行路径为：

这个调度过程中的相关性能指标计算如下。9楼10个乘客的总的候梯时间为：

9楼10个乘客的总的乘梯时间为：

10楼2个乘客的总的候梯时间为：

10楼2个乘客的总的乘梯时间为：

由此，可得到此次调度的平均候梯时间和平均乘梯时间分别为：

此次调度过程中电梯的启停次数为4次。

因为10楼2个乘客的候梯时间为83.92s，故此次调度过程的长候梯率为：

综上，此次基于先到先服务规则的调度过程的性能指标如下所示：平均候梯时间（AWT）：30.94s，平均乘梯时间（ART）：27.94s，启停次数（RNC）：4次，长时间候梯率（LWP）：17%。

依据本文算法，电梯的调度过程如图7和图8所示。图7显示电梯经过9楼直接到达10楼停靠后，10楼向下的2个乘客进入轿厢；图8 显示，电梯从10楼向下运行到9楼停靠后，9楼向下的10个乘客全部进入轿厢。此后，电梯将向1楼运行。

Figure 7 Sketch map for elevator running from the 9th floor to the 10th floor图7 电梯经过9楼直接到达10楼的运行示意图

Figure 8 Sketch map for elevator running from the 10th floor to the 9th floor图8 电梯从10楼下到9楼的运行示意图

由于该算法对电梯运行过程实行分步优化，能够综合考虑不同楼层之间的呼叫关联。故此时的电梯的运行路径修正为：8楼-10楼-9楼-1楼。

计算此次调度过程中的性能指标（此次计算过程同先到先服务算法中性能指标的计算过程相同，这里不再赘述），结果如下：平均候梯时间（AWT）：29.53s，平均乘梯时间（ART）：29.93s，启停次数（RNC）：3次，长时间候梯率（LWP）：0%。

针对此次呼梯请求，两种不同的调度过程对应的性能指标如表1所示。

Table 1 Performance comparison between step-by-step scheduling algorithm and first-in，first-serving scheduling algorithm表1 分步调度算法与先到先服务调度算法的性能指标对比

比较可以看出，本文提出的分步调度算法对电梯调度过程中的平均候梯时间（AWT）、长时间候梯率（LWP）及能量损耗（对应启停次数（RNC））三个方面的性能指标均有所改善。由实例分析可得：本文算法与先到先服务算法相比平均候梯时间减小了4.56%，能量损耗减小了20%，完全避免了长时间候梯现象的发生。

3.2 分步调度算法与不达最终目的层不换向调度算法的对比分析

电梯基本运行参数与上一节一致。现当轿厢载有2个到10楼的乘客运行至3.5层时，采集到此时1楼有10个乘客向上呼梯至10楼。

根据不达最终目的层不换向调度算法的相关原理，电梯的调度过程如图9～图10 所示。图9显示轿厢中有2个乘客要上行至10楼，电梯正向上运行至4楼，此时1楼出现了上行至10楼的10个呼梯请求；图10显示轿厢依然载着2个乘客向上运行至10楼。此时电梯的运行路径为：3楼-10楼-1楼-10楼。

计算此次调度过程中的性能指标（计算同先到先服务算法中性能指标的计算，过程不再赘述），结果如下：平均候梯时间（AWT）：50.68s，平均乘梯时间（ART）：28.83s，启停次数（RNC）：3次，长时间候梯率（LWP）：83.3%。

基于本文所提出的分步调度算法，结合引言中所提出的相关策略，电梯的运行路径更正为：3楼-4楼-1楼-10楼（仿真过程同3.1节中分步调度算法的仿真，此次不再赘述）。这种运行策略通过牺牲少数人的乘梯时间换取了乘客整体乘梯效率的改善[13～15]。同理可计算出此次调度过程中的性能指标数值如下：平均候梯时间（AWT）：24.23s，平均乘梯时间（ART）：36.59s，启停次数（RNC）：3次，长时间候梯率（LWP）：0%。

Figure 9 Sketch map for elevator running between 3rdfloor and 4thfloor图9 电梯运行至3.5楼时的状态示意图

Figure 10 Sketch map for elevator running to the 10th floor图10 电梯向10楼运行的示意图

针对此次呼梯请求，两种不同的调度过程对应的性能指标如表2所示。

Table 2 Performance comparison between step-by-step scheduling algorithm and holding original running direction unless reaching final objective floor scheduling algorithm表2 分步调度算法与不达最终目的层不换向调度算法性能指标对比

由表2可以看出，本文提出的分步调度算法对电梯调度过程中的平均候梯时间（AWT）、长时间候梯率（LWP）两个方面的性能指标有所改善。由实例分析可得，本文算法与不达最终目的层不换向的算法相比平均候梯时间减小了52.19%，并完全避免了长时间候梯现象的发生。

4 结束语

本文提出了一种基于数据融合的分步调度派梯方案。建立了电梯运行的数学模型并构造了对应的调度算法。分别与传统的“先到先服务算法”和“不达最终目的层不换向算法”进行了比较。仿真结果表明，本文所提出的调度算法的性能指标较之传统算法有了一定的改善，在一定程度上证实了本算法的优越性。

[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，Fu Guo-jiang.Elevator group control technology[M].Beijing：China Electric Power Press，2006.（in Chinese）

附中文参考文献：

[1]杨祯山，邵诚.电梯群控技术的现状与发展方向[J].控制与决策，2005，2.（12）：1321-1322.

[3]宗群，窦立谦，刘文静.鲁棒优化与多智能体协调的电梯群控调度[J].计算机集成制造系统，2008，14（3）：563-567.

[4]朱昌明，毕晓亮.电梯智能群控系统研究概况[J].现代城市研究，2003（S1）：1-6.

[5]董骊.高层建筑电梯群控调度算法研究[D].长沙：中南大学，2008.

[6]徐进.基于数据融合的入侵检测系统[D].西安：西安电子科技大学，2006.

[7]沈娟娟，陈耀武.网络化电梯远程监控系统设计[J].现代机械，2006（4）：71-73.

[8]戴必锋.基于无线网络技术的电梯综合信息传输系统[D].大连：大连海事大学，2008.

[9]杨涛.基于领域知识的电梯动态最佳群控方法[D].重庆：重庆大学，2003.

[12]宗群，蔡昱.基于电梯交通流概率仿真模型的空闲交通模式电梯调度方法[J].控制与决策，2002，17（3）：339-342.

[13]杨祯山，邵诚，马海丰.电梯群控系统交通需求的迭代学习预测方法[J].控制与决策，2008，2.（3）：302-305.

[14]宗群，童玲，薛丽华.电梯群控系统智能优化调度方法的研究[J].控制与决策，2004，19（8）：939-942.

[15]朱德文，付国江.电梯群控技术[M].北京：中国电力出版社，2006.