论文研究-具有时间约束的电梯节能调度算法.pdf,  针对电梯节能问题, 提出电梯能耗损失计算方法, 构建具有时间约束的电梯节能调度模型, 应用粒子群算法(particle swarm optimization, PSO)分别对已知目标楼层和预测目标楼层两种情况的电梯节能调度问题进行建模和求解. 通过数值仿真分析, 从等待时间和能耗两方面比较了三种算法(最近服务原则(nearest car,
第9期 刘耀武,等:具有时间约束的电娣节能调度算法 2341 用外部选层面板( destination hall call panel)乘客申请服务时航选定目标楼层,因此优化算法中目标楼层信 息是已知的:对于预测目标楼层情况,电梯系统的外鄙呼梯面板只有上下按钮,乘客进入轿厢后选定目标楼 层,因此优化算法中乘客的目标楼层是未知的.这里釆用客流统计对目标楼层进行预测,算法根据预测楼层 进行优化 ■14-16■12-14 14-16■12-14 ■10-12■8-10 ■10-12■8-10 0-2 ■z-4 日0-2 12 12 1234567891011121314 012345678 厢内人数 厢内人数 1011121314 图1电梯上行能耗 图2电梯下行能耗 3.2问题描述与建模 电梯群控问题本质上属于多车辆路径间题( multi- vehicle routing problem,MVP),但与简单多车辆路 径规划问题相比,电梯群控问题具有以下特点:(1)电梯群控中,所有褛层既可以是车场也可以是顾客点,车 场不唯一;(2)每一楼层的需求是可分的,乘客根据各自目标楼层不同选择乘坐不同电梯;(3)电梯轿厢服务 完乘客不一定凹到出发楼层运行路径不一定是封闭的:(4)每一楼层需要服务的乘客数是随机的,并且在服 务过程中可以同时有乘客进入和离开电梯.这些特点使电梯群控问题比多车辆路径问题更复杂,而多车辆路 径间题已经被证明是NP-Hard间题,因此电梯群控问题也具有NP-Hard性质.电梯群控间题可描述为:K 台电梯构成电梯组,每台电梯最大载重量Q.电梯响应呼棁信号接取乘客送至目标楼层,每个楼层可以被任 意电梯服务,楼层被同一电梯服务的人数不超过轿厢剩余载重容量,电梯可以停靠任意楼层.电梯从当前楼 层出发,满足每个楼层每个乘客的服务申请,停靠在完成服务楼层.根据前面的分析,电梯承载不同数量的乘 客运行不同楼层的能耗不同.因此,调度优化的目标是:对于当前已进入系统并未响应的乘客,如果其平均等 待时间满足约束,则最小化电梯组的能耗;否则,给予目标函数极大的惩罚值,使等待时间尽量的接近约束, 优先保证等待时间满足约束问题的数学模型可以描述如下: min ∑∑∑(em+ca)+Mx△t k∈vt∈N∈N ∑ pik ∑;i≥DkY∈N,M∈V 0<gk+pik-dlk≤QVi∈N,Wk ∑pk-∑lk=0Wk∈V ∑∑ 1∈N,Vk∈V i∈N if awt △t awt-t. if aut s xk=1,0Vi∈N,Vj∈N,Vk∈V 2342 系统工程理论与实践 第33卷 式中:N为楼层集合;V为电梯集合;Q是电梯的最大载重量;c为电梯k搭载qk位乘客从楼层i到楼 层j电梯的能耗:ed为一次开关门能耗;M是平均等待时间超过软约束的惩罚值;△t是惩罚值系数:r;是 楼层讠等待的乘客数;pi是楼层讠被电梯k服务的乘客数:dk是电梯k送至楼层讠的乘客数;qak是到达楼 层i时电梯k搭载的乘客数;aut是当前已经进入系统但尚未被响应的乘客的平均等待时间;t是平均等待 时间限制:x是决策变量,当电梯k服务褛层讠的乘客后行驶至楼层时,xk取值1,否则取值0 数学模型中,式(2)是目标函数,当满足软约束时,即△ts=0时,目标函数为电梯组的能耗最小;当不 满足软约束时,目标函数获得极大惩罚值,目标函数优先优化等待时间:式(3)表示从楼层i进入电梯的人数 等于楼层讠的申请人数;式(4)表示楼层i的乘客只能由经过楼层讠的电梯服务;(5)是电梯载重量限制,电 梯到达褛层讠完成登梯和下梯后电梯內的人数应大于等于0并不超过电梯最大载重:式(6)是电梯k的服 务平衡限制,电梯运行中进入电梯的人数与从电梯出来的人数相等;式(7)保证每个有申请的楼层都至少有 一个电梯服务;式(8)是针对楼层的电梯平衡限制,驶入楼层j的电梯数等于驶出楼层j的电梯数;式()是 惩罚值系数与等待时间的关系 4电梯节能群控粒子群算法设计 由于电梯群控过程中需要及时响应乘客的申请,这就要求群控算法能够在短时间内得岀优化调度方案. 粒子群算法是模拟鸟类觅食行为的群体智能算法、其具有操作简单、易实现和收敛速度快等特点.以前的研 究已经证明,与其他进化算法相比,粒子群算法能够迅速收敛,得到优化结果4.此外,电梯群控过程中,不 同吋段内呼梯信号数量的变化导致编码长度实时变化.增加了遗传算法等进化算法交叉变异的难度.粒子群 算法的速度更新方式简洁易操作,受编码长度变化影响较小.因此,本文釆用粒子群算法进行硏究,并在离散 二进制粒子群算法的基础上,结合已知目标楼层和预测目标楼层两种情况,设计了电梯节能群控的粒子群算 法 4.1算法整体设计 与基本粒子群算法不同,二进制粒子群算法的粒子采用0-1变量表示,粒子的速度必须通过公式转化为 慨率,表示粒子相应维度取值1的概率.对于电梯群控节能间题,其二进制粒子群算法的数学描述为:在 D维空间中,Np个粒子构成的种群表示群控问题的服务方案,也是节能优化问题的可行解空间;算法经过有 限次迭代最终收敛于全局最好位置.在第次迭代时,每个粒子的位置表示为X2()=(xn(1),x;2(1),…,;D() ri∈{1,0};每个位置对应一个与电梯系统能耗相关的适应度函数值F2(t);每个粒子按照各自的速度V(t) (vn1(t),t2(t),……,vD(t)运动其中vn(t)∈Vmin,Vaxl;对于单个粒子,P(t)=(pn1(t),p2(t),…,PD(t) 表示其在运动历史中适应值最好的位置,Pg(t)=(g(t),Pg2()…,PgD(切)表示整个和群经历的适应值最好 的位置:每个粒子按照如下公式更新自身的速度和位置: vid(t+1)=wvid(t)+ciri(pid(t)-wid())+c272(pad(t)-vid(t) Vmin, if Uid(t+ 1)< vmin (t+1) Inax 2 if vid(t+1)>Vmax 1, if sigvid(t+1))> random id(t+1)- 0, if sig(via(t+1))< random 其中,d表示粒子的维度(d∈(1,2,…,D);u是惯性囚子,表示前一次速度对当前速度的影响:c1和c都 是正的加速常数、分别调节向全局最好位置和个体最好位置运动的步长;m1和r2都是属于[0,1]的随机数; randon也是0,1的随机数,用以判断粒子位置是否变化;sig0是 Sigmoid函数: 1 sigvid(t) 1 +exp(-vid(t)) (13) 42编码方案 根据3.1中列岀的基本前提,只要确定每部电梯需要服务的楼层利电梯当前状态就可以规划出电梯下 步的路径.因此,原来的复杂问题可以转化为通过为进入系统的乘客指定服务电梯从而规划路径的问题.群 控系统内的电梯采用整数编号,粒子位置编码借鉴二进制粒子群算法的编码规则,将电梯编号转为二进制形 式.如图3所示为针对某4梯群控系统的编码: 第9期 刘耀武,等:具有时间约束的电娣节能调度算法 2343 ID 到达时间2.2 17.6 32.7 38.2 51.6 93.3 方向 向下 同下 向上 向上 向下 向上 到达楼层12 4 预测目 标楼层 10 粒了位 置编码 10 11 10 01 编码对应 电梯编号 表 编码 图3粒子位置编码及对应表 在编码中,每个乘客都对应两位0-1编码,表示服务该乘客的电梯编号.此外,为了后续计算的方便,编 码还与乘客的到达时间、方向和到达楼层信息相对应 43适应值计算 为了计算电梯服务乘客的等待时间和能耗,需要规划出电梯运行的具休路径.在本硏究中,已知目标楼 层的算法根据乘客目标楼层规划路径;预测目标楼层的算法恨据乘客的到达偻层和方冋预测乘客的目标楼 层,结合电梯当前运行状态规划电梯即将运行的路径.在某一优化时刻to,分配给一台电梯的乘客可以分为 四类 (1)已经进入电梯并确定目标楼层的乘客; (2)尚未进入电梯,方向与电梯当前方向相同,并且在电梯的运行方向上的乘客; (3)尚未进入电梯,方向与电梯当前方向相反的乘客; 4)尚未进入电梯,方向与电梯当前方向相同,但在电梯当前运行反方向上的乘客 前两类乘客是电梯的第一服务批次,第二批次是第三类乘客,第三批次是笫四类乘客·.同一批次内,电梯 按照乘客的到达楼层、目标楼层和预测目标楼层逐个服务,只有服务完同一批次的所有乘客才能服务下一批 次的乘客.当电梯在一个批次内出现超载时,则把超载的乘客后移至所有批次后,并按照前面的规则形成新 的批次 根据具体的运行路径可以计算每位乘客的等待时间和电梯系统的能耗,粒子i的适应值采用惩罚值的方 式将能耗与等待时间结合起来.设时刻t进入电梯系统但未被服务的乘客的平均等待时间为at2,平均等 待时间约束为t,电梯系统的能耗为E,则粒子i的适应度函数值F: auta t (14) Fi+M(aunti-t), anti> t 其中M为一个极大值,作为平均等待时间超过约束的惩罚.这样,算法实现优先选择等待时间不超过约束的 方案,并在不超过约束的方案中选择能耗最低的方案,在所有方案都超过约束时优先选择超过约束较小的方 案 4.4算法性能优化 为了使算法既能较快收敛又能避免陷λ局部收敛,本硏究对算法进行了如下优化: (1)加快收敛 sh和 Eberhart在文献[6]中指出,粒子群算法的惯性系数ω在.8,12]之间时收敛速度较快,较大 的ω可以加强算法的全局搜索能力较小的ω具有较强的局部搜索能力.文献[17]中采用的线性下降调整 方法适应了算法前后期的搜索特点,有效地改善了算法性能.因此,本算法按照如下公式调整在0.6,1.1 之间变化 (t)=11 0.5 lar number 其中 Mar nunmber是最大迭代次数. 2344 系统工程理论与实践 第33卷 另外.每当有新的乘客进入系统后,算法都会重新进行优化,此时上次优化后尚未被服务的乘客将再次 参与优化.试验表明上次分配的结果在新的优化中也往往较优,为了利用这种优势加快收敛,算法在原粒子 编码中添加新乘客的维度并指派电梯,保持其它维度不变,将构成的粒子作为新粒子群中的一员参与优化,如 图4所示 上次优化粒子 添加新乘客的粒子 图4优化方案的保存策略 (2)避免局部收敛 为了防止算法陷入局鄙收敛,当连续10代的全局最优结果相同时,算法重新生成一个新的粒子随机替 换粒子群中的一个现有粒子.如果替换后结昊仍然没有改进,并累积达到30代.则认为算法收敛 5仿真计算与结果分析 5.1参数设置 (1)建筑物及电梯系统参数 仿真计算的系统为配置4台电梯12层建筑物,楼层高度3m,电梯最高速度是2.5m/、加速度是0.8m/s2, 电梯完成一个完整的加速、减速为4s,开关门时间为4s,平均每个人进出电梯的时间是1.2s,电梯的最大载 重为1000kg(14人 (2)客流分布 仿真计算的乘客到达服从泊松过程,时间段为1小时,其间每5分钟乘客到达率改变一次,到达率如图 5所示 (3)粒子群算法参数 算法的加速常数c1和c2都取2.每次优化的粒子规模为50个,最大迭代次数200次,粒子的速度限制 在[-6,6]之间 52计算结果分析 按照上述参数设置,分别采用NC算法、已知目标楼层的PSO算法和预测目标楼层的PSO算法对群控 系统进行了一小时的仿真计算.对于PSO算法,分别以最小化等待时间(AWT")、等待时间约束30。下最小 化能耗(EC+AWT30)、等待时间约束60s下最小化能耗(EC+AWT60)、等待时间约東120s下最小化能 耗(EC+AWT120)和最小化能耗(EC)为优化目标进行计算,不同条件下的能耗比较如图6所示 12 0.25 0.1 253035434550 AWI ECTAWI30 ECtAWT6J ECTAWTIZU ←NC算法能耗 目砾楼层已知 预测目标楼层 图5一小时内乘客到达率 图6仿真计算能耗结果比较 计算结果表明,如果单纯以最小化等待时间为目标,已知目标楼层的PSO算法和预测目标楼层的PSO 算法的能耗都会比NC算法高,但在两种算法下,等待时间超过60s的乘客分别比NC算法减少了69%和 第9期 刘耀武,等:具有时间约束的电娣节能调度算法 2345 63%,整个过程的平均等待时间也分别比NC算法降低21.8%和21.4%.当优化目标中考虑能耗后,采用基 于粒子群算法旳群控算法都比NC算法节能,貝体的节能比例如表1所示 表1相对于NC算法的节能比例 EC+ AwT30 EC+ AwT60 EC+ AwT120 EC 已知目标楼层PSO 3.7% 18.2% 29.7% 35.7% 预测目标楼层PSO 1.1% 96% 19.5% 27.3% 随着等待时间约束的放松,新算法可以获得的节能效果逐步增加.当单纯以最小化能耗为目标时,两种 算法的节能比例分别可以达到35.7%和27.3‰.此外,已知日标楼层的PSO算法会比预测日标楼层的PSO 算法获得更好的节能效果,这说明目标楼层对算法的优化具有较大影响.本研究采用的统计预测方法还存在 较大的改达空问,在实际应用中可以采用更准确的预测机制或外部选择目标楼层面板技术( destination hall call panel)来进一步改进群控算法的性能. 在乘客的等待时间方面,通过设置等待时间约束可以使电梯在节能的同时保证可接受的等待时间.本研 究验诎了等待时间约東为30s、60s和120s时算法的效果,预测目标楼层的PSO算法的乘客等待时间分布 如图7所示.计算结果表明,设置等待时间约東后,有超过50%的乘客的等待时间小于30s.当优化目标是 最小化等待时间和等待时间约束30s下最小化能耗时,PSO算法的服务性能都优于NC算法,等待时间小 于60s的乘客数量都超过NC算法.在等待时间约束为60s时最小化能耗,新算法中等待时间超过60的乘 客会比NC算法多7.4%,但系统此时可以获得9.6%的节能.当等待时间约束为120s时,算法更侧重能耗优 化,等待时间超过120s的乘客会显著增加,但是算法仍然能够保证90%以上的乘客在等待时问约束内得到 服务 700 ■30=<awt<6 ■60=<awt<90 AWT EC+AWT30 EC+AWT60 EC+AWT120 图7不同条件下乘客等待时间分布 结论 为了硏究电梯群控系统的节能叫题,本文从能耗损失的角度提岀便于仿貞计算的电梯能耗计算方法,在 借崟经典多玍辆路径规划间题的基础上,构建了具冇等待时訚约朿的电梯群控节能模型,根据模型的特点,设 计了粒子群算法分别对已知目标偻层和预测目标偻层两种情况进行求解,并通过数值仿真比较了传统NC算 汏、已知目标楼层PSO算法和预测目标楼层PSO算法在等待时间和能耗方面的性能.硏究结果表明,与 NC算法相比,已知目标楼层的PSO算法和预测目标楼层的PSO算法在保证等待时间符合约束的同时,都 有效地实现了系统节能:当等待时间约束为60s时,两种情况下PSO算法分别可以节能18.2%和9.6%;如 果等待时间约束放宽至120s,两种情况下PSO算法分別可以节能29.7%和19.5%.此外,研究结果还表明 目标楼层的准确性对节能调度有亘要影响,同样使用粒子群算法进行优化,已知目标楼层情况下会比预测目 标楼层情况下多节能约10%.由于本文采用的预测机制并不精确,如果能够采用更精确的预测方法,可以缩 小两种情况的节能差距 参考文献 1 Barney G C. Elevator traffic handbook: Theory and practice M]. London: Taylor Francis, 2003 2 Rong A, Hakonen H, Lahdelma R. Estimated time of arrival(ETA) based elevator group control algorithm with 2346 系统工程理论与实践 第33卷 morc accuratc cstimationRl TU JCS Technical Report No 584, 2003 3 Kim C, Seong K A, Lee-Kwang H. Design and implementation of a fuzzy elevator group control s stem[C// Proc IEEE Trans Syst, Man Cybern, 1998: 277-287. 「]李中华,毛宗源,邬依林一种新的基于模糊控制的电梯群控策略[.控制与决策、2004,19(8):857-861 Li Z Il, Mao Z Y, Wu Y L. A novel strategy for elevator group supervisory control based on fuzzy controlJ Control and Decision, 2004, 19(8): 857-861 5 Tsuji s, Amano M, Hikita S. Application of the expert system to elevator group supervisory controlC/ IEEE Proc 5th Conf Artificial Intell Applicat, 1989: 287 294 Crites R H, Barto A G. Elevator group control using multiple reinforcement learning agents J. Machine Learning 1998,3:235-262 Fujino A, Tobita T, Segawa K, et al. An elevator group control system with floor-attribute control method and system optimization using genetic algorithms J. IEEE Trans Ind Electron, 1997, 44(4): 546-552 8 Cortes P, Larraneta J, Onieva L. Genetic algorithm for controllers in elevator groups: Analysis and simulation during lunch-peak traffic. Applied Soft Computing, 2004,4: 159-174 ⑨]宗群,牙淑红,工振世.基于排队论的上高峰电娣群控调度的硏究.系统工程与电子技术,2003,25(6):24-29 Zong Q, Ya s H, Wang Z s. Elevator group control dispatching method during up-peak traffic based on queuing theory [J]. Systems Engineering and Electronics, 2003, 25(6) 24-29 10宗群,岳有军,尚晓光,等.一种电梯群控多日标调度方法小.系统工程理论与实践2001,21(11:129-133 Zong Q, Yue Y J, Shang X G, et al. A Imlulti-object dispatching method in elevator group control systeInJ ystems Engineering Theory Practice 2001, 21(11):129-133 11 Tyni T, Ylinen J Evolutionary bi-objective optimisation in the elevator car routing problem[J. European Journal of Operational Research, 2006, 169: 960-977 [12 Schroeder J. The energy consumption of elevator- A comparative analysis J. Elevator Technology, Ellis Hor wood. 1986 13 Liu Y W, Hu Z Y, Su Q, et al. Energy saving of elevator group control based on optimal zoning strategy with interfloor trafficCl// Proceedings of 3rd International Conference on InforInation Managernent, Innovation Management and Industrial Engineering(ICIIT), 2010: 328-331 14 Angclinc P J. Evolutionary optimization versus particlc swarm optimization: Philosophy and porformance dif- ference[Cl//Porto V W, Saravanan N, Waagen D, et aL. Evolutionary Programming VII. Berlin, Germany Springer-Verlag, 1998: 601-610 15 Kennedy J, Eberhart R C. A discrete binary version of the particle swarm algorithm Cl// Proceedings of the World Multiconference on Systemics, Cybernetics and Informatics, Piscataway, N: IEEE Service Center, 1997: 4104-4109 16 Shi Y, Eberhart R C. A modified particle swarm optimizer Cl// Proceedings of the IEEE Congress on evolu tionary Computation, NJ: Piscataway, 1998: 69-173 17 Shi Y, Eberhart R C. Empirical study of particle swarm optimization[Cl// Proceedings of the 1999 Congress on Evolutionary Computation, N: Piscataway, IEEE Service Centre, 1999: 1945-1950