一种电梯群控多目标调度方法

2001年11月系统工程理论与实践第11期　文章编号:100026788(2001)1120129205一种电梯群控多目标调度方法宗　群1,岳有军2　尚晓光1,雷小锋1(1.天津大学电气自动化与能源工程学院,天津300072;2.天津理工学院自动化工程系,天津300191)摘要:　针对电梯群控系统层间交通模式下用户对电梯需求多样化的特点,提出了一种适用于繁重层间交通模式的多目标调度方法,并采用遗传算法动态优化电梯调度方案Λ仿真实验表明这种电梯调度方法是有效的Λ关键词:　电梯群控系统;多目标;电梯调度中图分类号:　T P273 文献标识码:　A αA M u lti2ob ject D ispatch ing M ethod inE levato r Group Con tro l SystemZ ON G Q un1,YU E You2jun2,SHAN G X iao2guang1,L E I X iao2feng1(1.Schoo l of E lectric A u tom ati on and Pow er Engineering,T ian jin U n iversity,T ian jin300072,Ch ina;2.A u tom ati on D epartm en t,T ian jin In stitu te of T echno logy,T ian jin300191,Ch ina)Abstract:　T he task of E levato r Group Con tro l System(EGCS)is to tran spo rtpassengers effectively,enhance runn ing efficiency of elevato r and i m p rove servicequality.A i m ing at the vari ou s dem and of elevato r u sers under the conditi on of in terfloo rtraffic mode,th is paper pu ts fo rw ard a m u lti2ob ject dispatch ing m ethod w h ich issu itab le to heavy in terfloo r traffic mode.A nd the GA2based m ethod is u sed todynam ically op ti m ize elevato r dispatch ing schem e.Si m u lati on resu lts have show n thevalidity of the schem e.Keywords:　elevato r group con tro l system;m u lti2ob ject;elevato r dispatch ing1　前言电梯群控系统是在建筑物内控制三部或三部以上电梯并实现优化调度,从而有效地运送乘客改善服务质量的控制系统Λ在群控算法的研究中,人们发现建筑物内的交通模式在一天的不同时间内是变化的,例如在办公大楼内可能发生的交通模式有上高峰、下高峰、随机层间、两路交通模式、四路交通模式等等[1],仅用一种固定不变的派梯算法显然不能适应一天中建筑物内所有交通模式,群控系统必须适应建筑物内交通模式的变化[2]Λ在层间交通模式下,交通量较高峰模式小,因此对于使用群控系统的用户来说输送能力不如上下高峰时那样重要,而服务要求却是多样的Λ随着人工智能理论的发展,研究人员提出了多种智能派梯方法,主要有基于模糊控制的算法、基于专家系统的算法、基于神经网络的派梯算法、基于遗传算法的派梯算法[3-8],但目前在设计层间交通模式下的群控算法时仍然面临以下问题Λ1)在层间交通模式下难以确定最优派梯分配方案Ζ对于一个有n部电梯、h层的群控系统来说,可能的派梯方案最多时可达个n2h-2Ζ若从其中选出最优派梯方案,在电梯系统控制实时性要求下,这是一个很大的搜索空间Ζ2)在复杂交通环境下由于不同楼层人员分布不同、楼层用途不同而引起的不同楼层交通流有较大差α收稿日期:2000203227资助项目:天津市自然科学基金(993801211)异Ζ同时在层间交通模式下用户对电梯的使用要求是多样的,不仅集中于减少平均等待时间,还可能要求减少乘梯时间,减少轿厢内的拥挤度,而且某些重要楼层会提出比其它楼层优先服务的特殊服务要求[8]Ζ本文针对上述问题提出了一种适用于繁重层间交通模式采用遗传算法优化派梯方案的多目标调度方法Ζ2　多目标调度策略的提出在繁重层间交通模式下,如果允许所有楼层都提出“要求比其它楼层更少的等待时间”等特殊服务要求时必然会影响系统的性能,从而不能体现用户的特殊服务的优先权Ζ在本文所提出的派梯算法中只允许部分楼层提出特殊要求Ζ为实现上述控制目标,以等待时间、轿厢内拥挤度、乘梯时间等优先服务要求,则对于电梯i,其响应所有分派给它的呼梯的评价函数可以表达为5i=6h j=1k(j)t w f t w(t w ij,∃t w ij)+6h j=1k(j)tr f tr(tr ij,∃tr ij)+6h j=1k(j)w r f w r(w r ij)(1)式中,1ΦiΦn,0ΦjΦh,n为电梯部数,h为楼层高度,5i是派梯方案中分派给电梯i的呼梯的评价值Ζk(j)t w,k(j)tr,k(j)w r分别为楼层j等待时间权系数,乘梯时间权系数,拥挤度权系数Ζ当楼层j为有等待时间特殊要求的楼层时其值由用户确定,各控制目标的权系数体现各控制目标的相对重要性Ζf t w,f tr,f w r分别为等待时间估算函数,乘梯时间估算函数,轿厢拥挤度估算函数Ζ对于当前的派梯方案的评价函数为5e=[51,52,…,5n]=6n i=15i(2)3　基于遗传算法动态优化的电梯调度方法为实现在多目标要求下动态优化派梯方案,实现电梯的多目标最优调度,采用基于遗传算法的动态优化方法优化呼梯分配方案Ζ遗传算法是一种求解问题的高效并行全局搜索方法,在有多个呼梯的情况下可搜索到最优派梯方案,而传统的派梯算法在分派呼梯时总是逐个分派,串行处理,不能满足实现多目标最优调度的要求Ζ但是遗传算法的计算量较大,为保证采用遗传算法优化派梯的实时性,需要对遗传算法进行速度测试,在启动遗传算法搜索最优派梯方案时每次在速度允许范围内进行若干代搜索即停止搜索,按照最优个体派梯,这样虽然搜索到最优解的概率很小,但是当群控系统在遗传算法寻优结束并按照最优个体派梯后,若有新的外呼梯产生,则重新搜索最优派梯方案;若没有新的呼梯产生,则派梯算法可在现有派梯方案的基础上继续调用遗传算法搜索最优派梯方案Ζ在进行适用于优化电梯调度的遗传算法设计时主要解决以下问题Ζ图1　1)编码　根据派梯算法需要采用整数编码,与二进制编码相比采用整数编码能够直观表示呼梯的分配情况,便于判断新产生的呼梯分配方案是否合理,同时在遗传操作中避免非法电梯号的产生,简化了编码和译码环节Ζ外呼梯在染色体中的排列顺序,采用按照空间顺序和呼梯方向排列、编码Ζ设群控系统有5部电梯,电梯号0-4,有6个外呼梯,染色体如图所示,染色体长度为当前等待分配的外呼梯的个数Ζ2)初始群体生成　由于在初始群体生成时依据专家知识产生一部分较优个体能够加快搜索[9],所以依据专家规则产生一部分个体,随机产生一部分个体作为初始群体Ζ3)适应度函数设计　遗传算法在进化搜索中是依靠适应度函数值的大小来区分每个个体的优劣的,031系统工程理论与实践2001年11月适应度值大的个体将有更多的机会繁衍下一代Ζ在具体应用中适应度函数的设计要结合求解问题本身的要求而定,对于多目标派梯算法而言,适应度函数为F it (5e )=K 5e (3)这里5e >0,K 为常数Ζ遗传操作过程中快速淘汰不合理的派梯方案,将应用于遗传算法的多目标评价函数进行修正为5e =(1-t )6n i =15i +t C(4)这里t ・C 为罚函数,C 为取值很大的一个常数,t 为惩罚系数Ζ当派梯方案不合理时t =1,当派梯方案合理时t =0Ζ4)选择　为了保证派梯算法的稳定性,采用适应度比例方法与最佳个体保持方法相结合的选择算子Ζ采用最佳个体保存方法使遗传算法优化得到的派梯方案不会小于初始群体中的最优个体,从而保证了派梯算法的稳定性Ζ5)交叉和变异　在遗传操作中选用两点交叉算子,根据不同情况采用三种变异算子Ζ①位点变异算子,对群体中适应度小于平均适应度的个体实行此种变异操作Ζ②两点对换变异,对适应度大于平均适应度的个体实行此种变异操作Ζ③逆转算子,用于处理在遗传操作过程中出现的一种不合理的派梯方案,方法是将这个码串中的基因值做逆向排序Ζ在派梯算法运行过程中,需要判断启动遗传算法的条件,显然在呼梯较少的情况下启动遗传算法是不合理的,因此在有新的外呼梯产生时,若外呼梯个数少于一定数量的情况下用穷举法分别计算每个派梯方案,从中获取最优派梯方案Ζ在外呼梯个数大于等于一定数量时启动遗传算法Ζ4　仿真与结果分析为测试群控算法的性能,将派梯算法编写成DLL 函数,由电梯群控系统虚拟环境[10]调用进行仿真Ζ仿真实验中设定群控系统电梯配置参数如下:群控系统电梯数为5部,速度为2米 秒,加速度1.5米 秒2,加加速度1.5米 秒3,开门时间1.5秒,关门时间3秒,建筑物楼层高度为3米Ζ为了测试派梯算法需要,随机产生繁重层间交通流Ζ以下所有仿真都是在此系统参数和交通流下进行的Ζ1)采用遗传算法的派梯算法与传统的最小平均等待时间方法比较为验证采用遗传算法派梯的有效性,将采用遗传算法优化搜索的派梯算法与传统的最小平均等待时间方法比较Λ计算机为Pen tium 计算机,主频400M H z ,多目标派梯算法中遗传算法平均速度784代 s ,优化时间周期取1s ,为保证采用遗传算法优化派梯的实时性派梯算法每次计算450代Λ采用遗传算法的派梯算法仍然以最小平均等待时间为目标Λ传统的最小平均等待时间方法为[9]:5i =h (t w ij )(5)5e =m in (51,52,…,5n )(6)式中,t w ij 表示在第j 层对第i 部电梯估算等待时间;h (x )表示评价函数;5i 表示第i 部电梯的评价值;5e 表示将呼梯派给具有最小评价值的电梯Λ在相同的电梯配置和交通流下进行仿真,最小平均等待时间派梯算法的结果为:平均等待时间27.44s ,长候梯率27%Λ采用遗传算法的派梯算法的结果为:平均等待时间21.6s ,长候梯率17.2%Λ图2-3为采用两种派梯算法派梯的电梯运行曲线Λ从运行曲线可看出,采用最小平均等待时间方法在某些时段内电梯都集中在很小的一个区域内且运行方向一致,这在层间交通模式下是不合理的Λ2)多目标派梯算法的仿真结果与分析仿真实验中正常服务楼层控制目标要求为最小平均等待时间Λ特殊服务楼层设置为:5层拥挤度优先,8层等待时间优先,15层乘梯时间优先Λ图4-6为不同特殊服务楼层各控制目标效果比较Λ对于特殊服务楼层,从图中可以看出,特殊服务楼层所要求的指标都有不同程度的提高Λ由于特殊服务楼层的要求与非特殊服务楼层的服务的要求(等待时间)存在一定的矛盾,因此在有特殊服务楼层的情况下,系统的整体性131第11期一种电梯群控多目标调度方法图2　最小平均等待时间法电梯运行曲线图3　基于遗传算法派梯算法电梯运行曲线图能指标会有不同程度的下降Λ系统的平均等待时间为26.1秒,长候梯率为22.4%Λ图4　不同楼层的拥挤度比较图5　不同楼层的等待时间比较231系统工程理论与实践2001年11月图6　不同楼层的乘梯时间比较5　结束语本文提出了适用于层间交通模式下满足建筑物内重要楼层特殊需求的多目标派梯算法Λ采用基于遗传算法的动态优化方法来优化派梯方案,以实现在改善特殊服务楼层服务的同时优化系统整体性能Λ仿真结果表明多目标派梯算法是有效的Λ参考文献:[1]　Barney G C ,SM Do s San tao s ,Ed .E levato r T raffic A nalysis ,D esign and Con tro l [M ].IEE ,Peter peregrinu s ,L ondon ,1985.[2]　Jerem y B Kezer ,Jam es M Co llin s .E levato r D ispatch ing A ccomodating In terfloo r T raffic and Emp loying a V ariab le N um ber of E levato r [M ].U S Paten t 5274202,1993.[3]　Gran tham K ,Pang H .E levato r schedu ling system u sing b lack board arch itectu re [A ].IEE P roceedings [C ],1991,138(4).[4]　M ing Ho ,B ren t Robertson .E levato r group superviso ry con tro l u sing fuzzy logic [A ].CanadianConference on E lectrical and Compu ter Engineer [C ],part 2,1994.825-828.[5]　Ken ji Sasak i ,Sando r M arkon ,M asam iN akagaw a .E levato r group superviso ry con tro l system u singneu ral netw o rk s [J ].E levato r W o rld .1996,7(2):81-86.[6]　Yasuyuk i ,Sogaw a .Superviso ry con tro l fo r elevato r group by u sing fuzzy expert system w h ichaddress the riding ti m e [A ].IECON [C ],22nd ,part 1,1996.419-424.[7]　Chang Bum K i m ,Kyoung A .Seong ,H yung L ee 2Kw ang ,Jeong O K i m .D esign and i m p lem en tati onof a fuzzy elevato r group con tro l system [J ].IEEE T ran s.O n System ,M an and Cybernetics ,1998,28(3):109-122.[8]　A tsuya Fu jino ,To sh i m itsu Tob ita ,et al.A n elevato r group con tro l system w ith floo r 2attribu te con tro l m ethod and system op ti m izati on u sing genetic algo rithm s [J ].IEEE T ran s.O n Indu strial E lectron ics ,1997,44(4):1502-1507.[9]　A barzadeh 2T M Y ,Jam sh idiM .Inco rpo rating a 2p ri o ri expert know ledge in genetic algo rithm s [A ].P roceedings of the 1995IEEE In ternati onal Conference on Compu tati onal In telligence in Robo tics and A u tom ati on [C ].1997.300-305.[10]　宗群,尚晓光,岳有军.电梯群控系统虚拟仿真环境设计[J ].制造业自动化,1999,21(5):24-25.331第11期一种电梯群控多目标调度方法。