电梯调度算法研究

PAGEII材料清单一、毕业论文二、毕业论文任务书三、毕业论文开题申请表四、毕业论文开题报告正文电梯调度算法研究摘要：随着社会的进步，高层建筑和智能化建筑的不断出现，作为垂直运输工具的电梯也就得到了越来越广泛的应用，为了减少能源的消耗和缩短人们的候梯时间，一栋高楼会安装多部电梯。如此，如何合理安排几部电梯的运行是很有必要的。本文首先讲述了选题背景、目的和意义，就国内外对电梯调度算法的研究现状说明研究电梯调度算法的必要性；分析电梯系统的特性从而了解乘客对电梯系统的要求，进一步总结出传统电梯的调度方法；最后，对电梯调度算法进行改进，使电梯资源尽可能的被人类使用。关键字：电梯；调度算法；改进

High-riseelevatorschedulingalgorithmstudyAbstract:Withtheprogressofthesociety,high-risebuildingsandintelligentbuildingappearconstantly,asaverticaltransportelevatorismoreandmorewidelyused,inordertoreduceenergyconsumptionandshortensthehouladdertime,morethantallbuildingswillinstallelevators.So,howtoarrangetheoperationoftheelevatorsisverybenecessary.Thisarticlefirsttellsthebackground,purposeandsignificanceoftopics,bothathomeandabroadontheresearchstatusofelevatorschedulingalgorithmdemonstratesthenecessityofelevatorschedulingalgorithmresearch;Analysisofthecharacteristicsoftheelevatorsystemtounderstandthepassengerstotherequirementoftheelevatorsystem,furthersumsupthetraditionalelevatorschedulingmethod;Finally,theelevatorschedulingalgorithmwasimproved,maketheliftasfaraspossiblebyahumanresourceusage.Keyword:Theelevator;Schedulingalgorithm;Improve目录TOC\o"1-2"\h\z\u1.前言 11.1选题目的和意义 11.2研究背景 11.3本文的主要研究内容 32.电梯系统的分析 42.1电梯的起源 42.2电梯的发展 52.3乘客对电梯系统的要求 62.4电梯系统的特性 63.电梯调度算法的改进研究 93.1电梯的三种状态 93.2传统电梯调度算法 103.3电梯调度问题分析 123.4调度方法 134.总结与展望 164.1总结 164.2展望 16参考文献 17致谢 18PAGE191.前言1.1选题目的和意义随着科学技术的发展，现代的楼房也越来越高，几乎所有的高建筑物都有电梯。高层建筑和智能化建筑的不断出现，作为垂直运输工具的电梯也就得到了越来越广泛的应用，人们对电梯服务质量提出越来越高的要求，单台电梯往往不能满足建筑内的交通需求。为了减少能源的消耗和缩短人们的候梯时间，一栋高楼会安装多部电梯。所以为了使多部电梯合理运行，研究多电梯调度算法是很必要的。高层建筑越来越多的出现在我们生活中，利用电梯对高层建筑内的人员进行垂直运输，具有更高的运营效率，同时满足乘客生理和心理的需求，实现高效率的垂直输送。但是当高层建筑逐渐成为城市景观的同时，也带来了一系列安全问题，其中最主要的就是高层建筑如何应对发生火灾、地震、恐怖袭击等紧急情况下的威胁。高层建筑具有楼层多，内部装饰材料多，电气设备多，功能多，人员多，管道竖井多等特点，造成了高层建筑一旦发生火灾，火势蔓延迅速，人员疏散困难，火灾后的逃生是一个棘手的问题。高层建筑安装多台电梯，这被称为电梯群控系统。所谓电梯群控系统是指将建筑物中的多部电梯根据大楼的功能及楼层人口分布状况组成梯群，由微机控制系统统一管理电梯群的召唤和指令信号，根据系统设定的优化目标和建筑物中的实际交通状况产生最优派梯决策的控制系统。充分利用电梯群控技术的成果将电梯系统与城市建筑融为一体，最大程度地满足人们对生活及安全保证的需要。1.2研究背景1.2.1国内外电梯群控算法的研究现状早在1949年，纽约联合国大厦首次使用继电器逻辑组成的电梯群控系统，经历了由当初的预选控制到后来的分区控制；随着计算机技术的迅速发展，计算机群控代替了传统的继电器群控。同时国际上各大电梯公司相继推出了与自己群控系统相适应的控制算法，如：日立公司的时间最小／最大群控法，迅达公司的综合服务成本群控方法，奥的斯公司的相对时间因子群控方法，三菱公司的综合分散度群控方法等等。在我国，电梯群控的研究最早见于1990年，主要研究电梯群控系统和人工智能。近几年我国在这方面的工作主要表现在引进国外先进技术和产品上，在此基础上力争推出自己的产品。例如1994年，上海电梯有限公司制造出智能化电脑网络控制电梯GPS／GPM型，具有缩短候梯时间，设置服务楼层，消除错误指令及为用户提供保安召唤等功能。1996年，迅达电梯公司最新电梯技术，其中包括将“MicronicsVXTM／ATM”用于电梯的人工智能技术，使电梯群控系统能改变运行参数，具有学习功能。1997年，北京西意思英特电梯系统有限公司引进美国的电脑神经元智能控制技术和产品部件，在此基础上力争推出自己的产品。虽然我国电梯业大量引进国外先进技术，但是很多停留在产品引进上，对关键电梯群控技术仍未能消化或根本未能引进。因此国内这方面的研究仍落后于国外，有待进一步赶上。与此同时，我国部分高校和科研院所的学者，也已经就电梯群控的核心算法展开了研究，并已经取得了一定的理论成果。在分析电梯群控系统的基础上，将乘客候梯时间作为评价标准，提出了最小等候时间的群控算法；则采用动态分区及遗传进化的方法对电梯的群控算法进行了研究；考虑电梯群控系统排队服务的随机性，就电梯的交通高峰期提出采用马尔可夫排队论群控方法；将电梯看作一个近似的统计问题，对平均侯梯时间的统计近似算法进行了研究；则将电梯群控看作一个多目标规划问题，对其进行了研究。提出采用数字键盘基于模糊推理的电梯群控模型的研究方法现今随着人工智能的不断发展，国内外很多的研究人员将专家系统、模糊控制、人工神经网络以及计算机视觉等应用到电梯群控系统，使系统的性能进一步提高。1.2.2选题背景随着城市高层建筑和智能化建筑的增加，人们对电梯服务质量提出越来越高的要求，单台电梯往往不能满足建筑内的交通需求，为缩短人们的候梯时间，减少能量的损耗，需要合理安装多台电梯。安装在一起的多台电梯要求单台电梯的控制系统相互联动，且具有监控系统。但仅仅这种方式不能适应客流量的剧烈变化，无法改善在某段时间内必然出现的长候梯现象。对于电梯群的协调调度，要根据轿厢内的人数、上下方向的停站次数、层站及电梯厢内的呼梯信号以及电梯厢所在位置等因素来分析实时客流的变化情况，自动选择最适合客流的情况的输送方式。因此，多台电梯的优化调度系统应运而生。多电梯的调度系统是通过对电梯群的运行状态进行实时监测与分析，再根据不同的实际情况对各电梯进行优化调度和合理分配，进而实现电梯系统对乘客的服务质量和服务效率的改善和提高的目标。1.3本文的主要研究内容电梯调度算法优化问题在现代这个讲究安全的社会里，显得十分的重要。电梯调度算法优化问题即要找到更加合适的调度算法满足乘客的需求。本文的主要研究内容是电梯调度算法的改进，首先就是研究电梯系统，了解它有哪些特性，然后研究传统的电梯调度算法，再对电梯调度算法进行改进。

2.电梯系统的分析2.1电梯的起源最原始的电梯控制由司机操作，这样不但浪费人力资源而且很不经济。为了解决这个问题，最初采用了简单自动式控制方式，可自动记忆呼梯信号，响应首先呼叫的乘客的需求，但是不能同时记忆多个呼梯信号，使用起来很不方便，效率也低于人力操作的效率。后来出现了集选控制，它能记忆下所有的呼梯信号，在运行方向上依次响应，并且自动在运行方向的信号响应完后接着响应相反方向上的呼梯信号。由于在建筑物内，单台电梯常常是不能应付全部客流的，因此需要并排设置几台电梯，这样便产生了电梯相互联接的问题。某个建筑物内设置有多台并列的独自操作的电梯，由于人们往往会同时按下几台电梯的召唤按钮，使得几台电梯的轿厢去响应同一呼梯信号，降低了工作效率，增加了能耗，而且在频繁的需求下会造成轿厢聚集现象。因此，安装在一起的多台电梯的合理使用要求单台电梯的控制系统相互联动，且具有自动监控系统。于是出现了用集选方式控制的并列两台电梯的联动控制方式。但是，在大型的办公楼里，上班时的上行乘客、午饭时的上下行乘客、下班时的下行乘客非常多，轿厢需要频繁地往返运行，这时就显示了这种方式的不足之处，它不能适应这种客流量的剧烈的变化规律，难以克服轿厢的频繁往返，也无法改善在某段时间内必然出现的长候梯现象。显然单靠增加电梯的荷载、速度、台数不能改善这种现象。因此，关键问题在于对这群电梯的协调调度，要根掘轿厢内的人数，上下方向的停站次数，层站及轿厢内的呼梯信号以及轿厢所在位置等因素，来分析实时客流的变化情况，自动选择最遥宜于客流情况的输送方式。为解决这个问题，二十世纪四十年代，美国两大电梯制造公司Otis电梯公司和西屋电机公司研究出一种新的电梯控制方式，即电梯群控方式。它能根据客流情况的变化，高效率地对所有各层进行充分的服务，一经推出，这种控制方式的电梯需求量迅速增加。2.2电梯的发展很久之前，人们就使用一些原始的升降工具运送人和货物。公元前100年前后，我国古人发明了辘轳，它采用卷筒的回转运动完成升降动作，因而增加了提升物品的高度。公元前236年，希腊数学家Archimedes设计制作了由绞车和滑轮组构成的起重装置。这些升降工具的驱动力一般是人力或畜力。19世纪初，在欧美开始用蒸汽机作为升降工具的动力。1845年，威廉汤姆逊研制出1台液压驱动的升降机，其液压驱动的介质是水。尽管升降工具被一代代富有革新精神的工程师们进行不断改进，然而被工业界普遍认可的升降机仍未出现，直到1852年世界第1台安全升降机诞生。电梯驱动控制技术的发展经历了直流电机驱动控制，交流单速电机驱动控制，交流双速电机驱动控制，直流有齿轮、无齿轮调速驱动控制，交流调压调速驱动控制，交流变压变频调速驱动控制以及交流永磁同步电机变频调速驱动控制等阶段。随着第一个半自动化电梯控制器在19世纪20年代的使用，原始的服务员执守工作方式已减少为一个开关门的操作。直至l950年，由电力机械继电器系统组成的全自动电梯控制器的应用取消了服务员执守。至20世纪70年代，基于微处理器的电梯控制器得到广泛应用，使得更为复杂的调度算法的实施成为可能，由此产生了电梯群控的概念。电梯操纵控制方式经历了手柄开关操纵、按钮控制、信号控制、集选控制等过程，对于多台电梯则出现了并联控制、智能群控等。随着智能控制技术在电梯群控系统中的广泛应用，电梯交通系统和其他设施融为一体，智能建筑的整体功能得以充分发挥，对高层及超高层建筑电梯交通系统的研究表明，电梯交通系统设计的关键是满足乘客生理上和心理上的承受力。有效地解决高层建筑复杂的楼内垂直交通，寻求优化的控制策略，优化调度多部电梯以提高电梯的运行效率和服务质量生活在继续，科技在发展，电梯技术也在进步。电梯的材质由黑白道彩色，样式由直式到斜式，在操纵控制方面更是补补出新，电梯在操纵控制方式方面的发展经历了手柄开关操纵、按钮控制、信号控制、集选控制等过程，对于多台电梯出现了并联控制、智能群控。双层轿箱电梯展示出节省井道空间，提升运输能力的优势，变速式自动人行道扶梯大大节省了行人的时间。不同外形的扇形、三角形、半棱形、圆形观光电梯则使身处其中的乘客的视线不再封闭。如今，世界各国的电梯公司还在不断地进行电梯新品的研发、维修保养服务系统的完善，力求满足人们的对现代建筑交通日益增长的需求。1852年，美国纽约杨克斯（Yonkers）的机械工程师奥的斯先生（ElishaGravesOtis，1811年～1861年）发明了世界第1台安全升降机。它是配有安全装置的升降机。他将带有锯齿状的铁条固定在导轨上，在轿厢的上部设置了一个弹簧片，并将其与机械联动装置和制动棘爪连接起来。曳引绳固定在弹簧片的中心，曳引绳破断时弹簧片恢复原始形状，强迫机械联动装置动作，然后制动爪伸入锯齿状的铁条阻止电梯下落。工业用户（货梯）是安全升降机的首先使用者。2.3乘客对电梯系统的要求电梯的出现是为了方便人们的出行的，所以乘客对电梯的评价是很重要的。人们信赖电梯主要是根据电梯的安全性来的，作为人们出行的交通工具之一，电梯的安全性是及其重要的。乘客的要求既有生理的也有心理的。在生理上，我们每次乘坐电梯时，都会感觉不舒服，乘电梯上下行时，都会有超重和失重的感觉。这种感觉根据各个人的年龄和生理、心理的健康程度以及是否突然运行等因素有关。目前，人们还没有明确找出加减速度达到多大时构成对人体的危害，但电梯加减速度过快，对人体肯定不是很好。在心理上，虽然感觉很微妙，但人们对电梯的服务还是有一定的要求。同样的人在不同环境或者不同的人在同一环境在等待电梯和乘梯时间长短都是不同的。例如，乘客在上班时，对电梯服务没有太大要求，但当下班时就会希望电梯能快点到达自己的目的地。还比如回家时，对住宅的电梯也不会有很大要求。候梯和乘梯时间都是主要的心理上要求。2.4电梯系统的特性电梯系统是一类具有不确定性的复杂系统，工作特性有显著的特点：有乘客需求才运行，但不同于公交车没站都停靠，目的性很强。相对硬件系统而言，优化控制实现上的难度主要表现在软件系统设计方面。2.4(1)不确定性电梯系统中存在着大量的不确定性：建筑物内存在的与环境因素有关的变化的交通情况、呼梯信号的产生、呼梯者的目的层、层站的乘客数。（2）扰动性电梯系统不可避免地存在着不确定的扰动因素：乘客可能错误的登记了厅外呼叫而产生了不必要的停站；乘客可能错误的登记了目的层而造成了不必要的停站；乘客可能错误地操作造成了轿厢门的不能关闭而干扰正常的电梯运行。（3）信息的不完备性电梯系统中还存在着大量不准确因素；轿厢中的乘客数不能够准确的获得；乘客进入轿厢前，其目的层是不可知的；下一次呼叫产生的层站也是不知道的等等。（4）非线性电梯交通系统存在着非线性对同一组厅呼，在不同的时间标度下，轿厢的分配是不同的，轿厢分配的变化是不连续的：所能分配的轿厢数目是有限的；受系统所有轿厢数目限制：轿厢容量是有限的，当轿厢容量达到饱和点时，轿厢会不停而过；轿厢会在运行中频繁改变方向。以上所提到的电梯群控系统的不确定性、扰动性和信息的不完备性、非线性，说明电梯群控是一个非常复杂的控制系统。2.4（1）平均候梯时间要求最短候梯时间是指从乘客按下层站梯按钮到电梯系统派出的电梯到达该层让乘客进入轿厢所经过的时间。而平均候梯时间是指一段时间内，所有乘客的候梯时间的平均值，这是评价电梯控制系统性能的重要指标。统计表明，乘客的心理烦躁程度与候梯时间的平方成正比。当候梯时间超过一分钟时，即所谓长时间候梯时，心理烦躁程度急剧上升。所以，尽量减少长时间候梯率是电梯系统优良性能的重要指标之一。（2）平均乘梯时间要求短乘客的乘梯时间是指从乘客进入电梯到乘客到达目的层乘客离开的这段时间。乘客乘梯时间的增长往往会使乘客感觉不舒服、烦躁。如去建筑物顶层的乘客在乘梯时间长于90秒时，会对停靠变得极不刑烦，所以乘客的乘梯时间应保持在一个特定的期限之内。（3）系统能耗要求低单台电梯的能耗与所选电梯的驱动方式、机械性能等有关。如最初的电动机——发电机组能耗比较大，效率较低；而现在的VVVF驱动电梯的能耗和效率都比较高。电梯能耗的消耗特征是：电梯全速运行时所消耗的电能远远低于减速和加速时的电能消耗。电梯停靠的次数越多。所消耗的电能就越大。对电梯群控系统而言，电梯型号一经确定，单台电梯一次起停的电能消耗就已经确定。所以电梯群控系统节能主要依靠群控系统合理地安排与调度梯群对呼梯信号的响应，尽量减少起停次数，同时起停次数的减少也会延长梯群的整体寿命。（4）客流的输送能力要求高电梯的输送能力是电梯的重要指标之一。输送能力的不足往往会造成乘客的捌挤，平均候梯时间长等不良性能。特别是在上行高峰期，客流密度极大，需要电梯系统迅速将乘客送往各目的层。（5）长候梯率要求低长候梯时问一般是指候梯时间超过1分钟的候梯时间。长候梯率是指长候梯时间发生的百分率。统计表明，乘客的心理烦躁程度是与候梯时间的平方成正比的，当候梯时间超过60秒即所谓长候梯时，其心理烦躁程度急剧上升，所以应尽量减少长候梯的发生。（6）预测轿厢到达时间准确率要求高很多电梯系统配有电梯到达时间显示系统，如果预测时削不准确，则会造成乘客的不安和烦躁，也会降低系统的整体性能。以上七点是系统的主要性能评价指标，可知电梯系统是一个多目标控制系统，而且各个目标之削是相互矛盾的。如拥挤度要求小，会使平均候梯时间增长。平均候梯时间短则会使长时候梯发生率高。所以各个指标之间的相互平衡成为电梯系统的控制难点。

3.电梯调度算法的改进研究3.1电梯的三种状态我们将电梯分为三种状态，第一种状态，正在向下行使中，第二种状态，正在向上行驶中，第三种状态，处于停止中，如图3.1所示。由于第一种状态与第二种状态类似，故此，我们下面只讨论第一种和第三种状态是对电梯的调度。种状态即电梯正在向下行使，分为有人与没人两种情况。电梯静止电梯静止电梯向下运动电梯向上运动图3.1电梯的三种状态当第一种状态的电梯里有人时，那么电梯向着最近的目标层驶去，如果此时中途有人（当前所在楼层与目标层之间）的请求且电梯可以到达，那么改变电梯的目标层使电梯在有人处停止。如图3.2所示，此时电梯正在五楼且向上运行，一、而、八、十楼都有向上请求电梯的信号，但由于一楼和二楼的请求信号不在电梯当前所在楼层和电梯中乘客的目的地之间，所以一、二楼的请求暂时不予以考虑，只响应八、十楼向上的请求。与此同时，三、四、七、九、十二楼有请求向下的信号，电梯对这些信号暂时也不会予以考虑，只有电梯到达所有乘客中目的层最高的楼层后，才会向下运行，此时，向下的信号量才会一一响应。图3.2某单台电梯按键情况当第一种状态的电梯里（即正处于向下行使）没人时，假设此时的电梯所在的层数为i，那么搜索i-1到0层间是否有向下的请求，如果有那么将最近的一个请求所在楼层设为目标，如果没有，那么在搜索0到i-1层间是否向上的请求，如果有将最远的一个请求所在的楼层设为目标。第二种情况与第一种类似，再此不做多述。对于第三种情况的电梯即处于开门状态或者处于关门但是没有明确目标的电梯。同样分为有人与没人两种状态，若有人，那么找到这些人想去的最近的目标这位目标，若没人将目标设为整个楼层中请求最早的地方。3.2传统电梯调度算法3.2.1先来先服务算法(FCFS)先来先服务(FCFS-First

Come

First

Serve)算法，是一种随即服务算法，它不仅仅没有对寻找楼层进行优化，也没有实时性的特征，它是一种最简单的电梯调度算法。它根据乘客请求乘坐电梯的先后次序进行调度。此算法的优点是公平、简单，且每个乘客的请求都能依次地得到处理，不会出现某一乘客的请求长期得不到满足的情况。这种方法在载荷较轻松的环境下，性能尚可接受，但是在载荷较大的情况下，这种算法的性能就会严重下降，甚至恶化。人们之所以研究这种在载荷较大的情况下几乎不可用的算法，有两个原因：任何调度算法在请求队列长度为1时，请求速率极低或相邻请求的间隔为无穷大时使用先来先服务算法既对调度效率不会产生影响，而且实现这种算法极其简单；先来先服务算法可以作为衡量其他算法的标准。（1）最短寻找楼层时间优先算法(SSTF)最短寻找楼层时间优先(SSTF-Shortest

Seek

Time

First)算法，它注重电梯寻找楼层的优化。最短寻找楼层时间优先算法选择下一个服务对象的原则是最短寻找楼层的时间。这样请求队列中距当前能够最先到达的楼层的请求信号就是下一个服务对象。在重载荷的情况下，最短寻找楼层时间优先算法的平均响应时间较短，但响应时间的方差较大，原因是队列中的某些请求可能长时间得不到响应，出现所谓的“饿死”现象。（2）扫描算法(SCAN)扫描算法(SCAN)是一种按照楼层顺序依次服务请求，它让电梯在最底层和最顶层之间连续往返运行，在运行过程中响应处在于电梯运行方向相同的各楼层上的请求。它进行寻找楼层的优化，效率比较高，但它是一个非实时算法。扫描算法较好地解决了电梯移动的问题，在这个算法中，每个电梯响应乘客请求使乘客获得服务的次序是由其发出请求的乘客的位置与当前电梯位置之间的距离来决定的，所有的与电梯运行方向相同的乘客的请求在一次电向上运行或向下运行的过程中完成，免去了电梯频繁的来回移动。扫描算法的平均响应时间比最短寻找楼层时间优先算法长，但是响应时间方差比最短寻找楼层时间优先算法小，从统计学角度来讲，扫描算法要比最短寻找楼层时间优先算法稳定。（3）LOOK算法LOOK算法是扫描算法的一种改进。对LOOK算法而言，电梯同样在最底层和最顶层之间运行。但当LOOK算法发现电梯所移动的方向上不再有请求时立即改变运行方向，而扫描算法则需要移动到最底层或者最顶层时才改变运行方向。3.2.2实时电梯调度算法（1）最早截止期优先调度算法最早截止期优先(EDF-Earliest

Deadline

First)调度算法是最简单的实时电梯调度算法，它的缺点就是造成电梯任意地寻找楼层，导致极低的电梯吞吐率。它与FCFS调度算法类似，EDF算法是电梯实时调度算法中最简单的调度算法。它响应请求队列中时限最早的请求，是其它实时电梯调度算法性能衡量的基准和特例。（2）SCAN-EDF算法SCAN-EDF算法是SCAN算法和EDF算法相结合的产物。SCAN-EDF算法先按照EDF算法选择请求列队中哪一个是下一个服务对象，而对于具有相同时限的请求，则按照SCAN算法服务每一个请求。它的效率取决于有相同deadline的数目，因而效率是有限的。（3）PI算法PI(Priority

Inversion)算法将请求队列中的请求分成两个优先级，它首先保证高优先级队列中的请求得到及时响应，再搞优先级队列为空的情况下在相应地优先级队列中的请求。（4）FD-SCAN算法FD-SCAN(Feasible

Deadline

SCAN)算法首先从请求队列中找出时限最早、从当前位置开始移动又可以满足其时限要求的请求，作为下一次SCAN的方向。并在电梯所在楼层向该请求信号运行的过程中响应处在与电梯运行方向相同且电梯可以经过的请求信号。这种算法忽略了用SCAN算法相应其它请求的开销，因此并不能确保服务对象时限最终得到满足。3.3电梯调度问题分析高楼中电梯的数量和质量是在建楼初期根据高楼的功能以及预计进出楼的人流大小来设计和确定的，在高楼的使用中很难进行改造。然而在楼的后期使用中，实际交通流量可能会跟预先设计时的估计值有较大的不同，也许会大大超出预先设计的容量。此时，如何合理的调控使用现有电梯，以提高电梯的服务效率，尽量减少人流的乘梯等待时间和乘梯时间等，就成为电梯管理中的首要任务。在电梯的控制管理系统中最常见的是电梯不分区使用和分区使用这两种情况。所谓不分区使用是指每一部电梯都可以相应所有楼层的使用要求，可以在大楼的每一层上下客。分区调度是电梯群控的常见控制方法。要提高电梯的使用效率达到优化，就要考虑分区的效果。图3.3表示就是一个分成三个区的电梯系统，其中白色区域表示电梯的服务楼层，而灰色则表示电梯直达但不停站的楼层。分区是根据电梯台数和建筑物层数将电梯划分为几个运行区域，各部电梯仅响应本分区内的使用要求。图3.3电梯分区示意图3.4调度方法当对电梯系统采用分区域进行调度时，我们必须确定合适的分区点。把大楼分成两个区、每个区两部电梯时，采用穷举的方法可以很快的确定出分区点。但如果把一栋大楼分成很多个区，那么工作量和计算量就会比较大，对于该写字楼，我们可以采取动态规划的风阀来确定分区点。使用动态规划必须满足Bellman提出的最优化原理：“一个过程的最优策略具有这样的性质——无论初始状态和初始策略如何，对于先前决策所形成的状态而言，其以后的所有决策赢构成最优策略。”动态规划求解关键路径币不需要搜索所有路径，只要满足状态的无后效性，就可以自己算各阶段的关键路径。例如某写字楼有4部电梯，现在将其分为4个区来进行更有效的优化调度，如图3.4。图3.4某写字楼的电梯分区示意图按电梯上高峰动态分区的空间特征即区域特征划分动态规划的阶段，每一个阶段是由每个区域来表示的。每个阶段可分配的最低层楼到最高层楼是这个动态规划模型的状态。如果将写字楼的4部电梯分为4个区域，可设起始层为0用字母A表示，而最高层楼用E来表示为19楼。如此，从A到E就可分为4个阶段，可用字母k表示阶段变量，所以从A到E课分为A-B，B-C，C-D，D-E四个阶段，即k=1,2,3,4。令为已经决定的阶段所取的状态，对于分区而言，第k阶段代表的分区区间为[,].例如当时，则对应的楼层分区为第一层、第二层到第三层、第四层到第五层以及第六层到最高层这样的四个分区。为求得动态规划的最优策略，确定电梯系统的平均逗留时间尽量少作为优化的目标函数。例如，从A0到B3的连线可取值为，其中W（3,1）表示分区中最低楼层为第一层且共有3层楼时；B1到A5的连线可取值为。一般的从状态i到状态j的连线取值为，其中表示分区的最低楼层为第i+1层，m表示整栋楼所具有的楼层数。于是该动态规划问题就换成了最短路径问题。可以采用Dijkstra算法求得最短路径和对应的分区区间。除了上述利用动态规划对多路电梯进行分区，从而减少乘客的逗留时间或者乘梯时间。还可以利用楼层优先调度算法，来减少乘客的候梯时间。对于单电梯的调度，其调度算法不是很容易改进，所以可以考虑减少乘客的候梯时间。在不同时间和不同环境中，人们对电梯的要求是不一样的，所以可以根据这一点，可以设置楼层优先级。比如在上班时，一楼电梯的使用率是最高的，这时，可以将一楼设置为电梯优先楼层，电梯每次都会停在一楼。如此，乘客的候梯时间就会减少，从而减少平均候梯时间。还可以让电梯在上班的时间外停留在楼层的中间位置这个方法来减少平均等待时间，电梯如果是停在中间的话，中间上部分的乘客要使用电梯时，也就不会等很长时间，中间下部分的乘客也不会花费太多时间等待电梯。这样，平均候梯时间减少。

4.总结与展望4.1总结近些年来，高层建筑和智能化建筑的不断出现，作为垂直运输工具的电梯得到了越来越广泛的应用。电梯调度算法是电梯系统的关键。现在的电梯调度算法有很多，但是实时性上都有一定的缺陷，影响了电梯系统的实际应用。本文介绍了国内外的发展现状，明确了电梯调度算法的必要性。重点研究了电梯系统的特性，对传统的电梯调度算法做了大概了解，最后提出了对电梯调度算法的改进。提出分区的概念，然后通过分区对电梯进行分区设置，从而大大提高电梯的运行效率，这算是本文的优点。而且，在电梯的优化调度方案中，利用动态规划算法求解分区点的方法，具有一定的严密性和实用性。4.2展望随着信息技术在我国不断的发展，摩天高楼也成为了都市一道靓丽的风景。高楼的不断增高推动着电梯技术的前进。电梯系统存在层站候梯人数不确定及召唤产生随机性的难点。这两个主要未知因素的存在，影响电梯运行规则、策略的准确运用。人工智能技术的应用正是用来处理这两个未知因素造成的难题。可以想象，如果候梯人数及召唤信息可以提前获得，电梯群控系统就可以自动制定运行计划，实现电梯的有序运行，将可极大提高电梯的运送能力。在撰写论文时，在网上、学校图书馆、中国知网等都找了一些资料，论文完成得还行，不过本文受时间、个人水平的限制，对一些的问题还没来得及探讨和进一步的研究，希望能够在以后得以解决，如忽略了电梯的加速度的运行速度等等，还有待以后的研究人员来完善。

参考文献[1]崔英志.面向多媒体应用的磁盘调度算法研究[D].重庆理工大学,2010.[2]陈希,麦雪湖,魏景焕.基于非线性规划的电梯调度研究[J].自动化与仪器表,2011,01:7-9.[3]顾妍午.基于RPSO的分布式电梯群控系统调度算法的优化[J].计算机科学,2012,S1:466-473.[4]孙杨模.操作系统常见的几种算法举例分析[J].湖北三峡职业技术学院学报,2010,02:87-90.[5]王俊岭.基于集群间两级并行的海量遥感数据调度模型设计与实现[D].河南大学,2013.[5]陈玉仙.新一代电梯的调度算法研究[D].中南大学,2010.[6]王波,段军,卿晓霞,王文章.一种改进调度算法的电梯节能新技术[J].智能建筑电气技术,2010,06:44-47.[8]董骊.高层建筑电梯群控调度算法研究[D].中南大学,2008.[9]陈纪龙,司春景,化希耀.电梯模拟系统的研究与设计[J].喀什师范学院学报,2013,06:30-33.[10]贺燕燕.基于LabView的电梯群控模拟仿真系统研究[D].长安大学,2012.[11]卿晓霞,王波,段军.考虑等待时间的电梯运行模拟测试与节能分析[J].计算机工程与应用,2012,31:232-235.[12]秦啸,庞丽萍.双头磁盘系统电梯调度策略[J].计算机工程与设计,1998,06:6-12+61.[13]YCCho，ZGagov，WHKwon．ElevatorgroupcontrolwithaccurateestimationofHallcallwaitingtimes．Proceedingsof1999IEEEInternationalconferenceonRoboticsandAutomation，Detroit，2009，447--一452[14]王晶,牟晓牧,许鋆,王书宁.紧急疏散电梯调度算法[J].清华大学学报(自然科学版),2013,07:1041-1045.[15]李建民.基于交通模式识别的电梯调度算法研究[J].自动化与仪器仪表,2008,01:82-85.[16]宾峰,唐立军,周健.基于单片机控制的模拟电梯设计与实现[J].现代电子技术,2014,02:56-59+63.[17]RonaldJNorman.Object-OrientedSystemAnalysisandDesign．PrenticeHall，2010

致谢在本次毕业论文的写作过程中，遇到了很多的困难，遇到困难的时候得到了指导老师的指导和帮助。在此特别感谢我的指导老师对我的悉心指导和帮助，本文从选题、构思、提纲拟订、资料收集、论文写作及修改至最后定稿，老师能不厌其烦的指导和修改，对于我顺利的完成我的毕业论起到了关键的作用。与此同时，我还要感谢给过我帮助的同学，没有他们，我也不能很好的完成论文的写作。另外，我要感谢我学习的学院——数学与计算机科学学院，在这里我学到了很多知识，增长了见识，使我能够顺利完成本科学业。我会继续努力，继续前进。最后向所有关心过我、帮助过我的领导、老师、朋友和同学们表示衷心的感谢！PAGE1湖北文理学院毕业论文（设计）任务书毕业论文（设计）题目电梯调度算法研究学生姓名曾娟专业计算机科学与技术班级1011班指导老师王敏毕业论文（设计）的主要内容及要求：在学习和理解现代电梯技术的基础上，研究现代电梯系统和调度算法，对传统的电梯调度算法如FCFS算法、EDF算法、SCAN算法等进行分析，了解算法中的不足，从而寻求一种结合，使得当前的电梯调度算法能更好的满足现代人类生活的需求，使人的出行变的更加的方便，快捷，高效。撰写一篇正文内容不少于2500汉字的、规范的开题报告；撰写符合规范要求的毕业论文（正文内容不少于10000汉字）。格式要求参照《数学与计算机科学学院毕业论文（设计）规范化要求》。毕业论文（设计）应收集的资料及主要参考文献：现代电梯技术的工作原理的资料；电梯调度优化算法研究的资料；电梯系统研究和介绍文献资料湖北文理学院毕业论文（设计）开题申请表学生姓名曾娟指导老师王敏系（院）数计学院专业计算机科学与技术班级1011论文题目电梯调度算法研究开题申请随着科学技术的发展，现代的楼房也越来越高，几乎所有的高建筑物都有电梯。高层建筑和智能化建筑的不断出现，作为垂直运输工具的电梯也就得到了越来越广泛的应用，人们对电梯服务质量提出越来越高的要求，单台电梯往往不能满足建筑内的交通需求。为了减少能源的消耗和缩短人们的候梯时间，一栋高楼会安装多部电梯。高层建筑越来越多的出现在我们生活中，利用电梯对高层建筑内的人员进行垂直运输，具有更高的运营效率，同时满足乘客生理和心理的需求，实现高效率的垂直输送。所以为了使多部电梯合理运行，研究多电梯调度算法是很必要的。我在开题报告中详细讲解了此课题的研究方案，收集了大量的相关课题资料，该研究的准备工作已完成特此提出开题申请。申请人签名：年月日指导教师意见指导教师签名：年月日PAGE6开题报告正文电梯调度算法研究1课题研究的目的和意义随着科学技术的发展，现代的楼房也越来越高，几乎所有的高建筑物都有电梯。高层建筑和智能化建筑的不断出现，作为垂直运输工具的电梯也就得到了越来越广泛的应用，人们对电梯服务质量提出越来越高的要求，单台电梯往往不能满足建筑内的交通需求。为了减少能源的消耗和缩短人们的候梯时间，一栋高楼会安装多部电梯。所以为了使多部电梯合理运行，研究多电梯调度算法是很必要的。 高层建筑越来越多的出现在我们生活中，利用电梯对高层建筑内的人员进行垂直运输，具有更高的运营效率，同时满足乘客生理和心理的需求，实现高效率的垂直输送。但是当高层建筑逐渐成为城市景观的同时，也带来了一系列安全问题，其中最主要的就是高层建筑如何应对发生火灾、地震、恐怖袭击等紧急情况下的威胁。高层建筑具有楼层多，内部装饰材料多，电气设备多，功能多，人员多，管道竖井多等，造成了高层建筑一旦发生火灾，火势蔓延迅速，人员疏散困难，火灾后的逃生是一个棘手的问题。2.国内外电梯群控算法的研究现状早在1949年，纽约联合国大厦首次使用继电器逻辑组成的电梯群控系统，经历了由当初的预选控制到后来的分区控制；随着计算机技术的迅速发展，计算机群控代替了传统的继电器群控。同时国际上各大电梯公司相继推出了与自己群控系统相适应的控制算法，如：日立公司的时间最小／最大群控法，迅达公司的综合服务成本群控方法，奥的斯公司的相对时间因子群控方法，三菱公司的综合分散度群控方法等等。在我国，电梯群控的研究最早见于1990年，主要研究电梯群控系统和人工智能。近几年我国在这方面的工作主要表现在引进国外先进技术和产品上，在此基础上力争推出自己的产品。例如1994年，上海电梯有限公司制造出智能化电脑网络控制电梯GPS／GPM型，具有缩短候梯时间，设置服务楼层，消除错误指令及为用户提供保安召唤等功能。1996年，迅达电梯公司公诮最新电梯技术，其中包括将“MicronicVXTM／ATM”用于电梯的人工智能技术，使电梯群控系统能改变运行参数，具有学习功能。1997年，北京西意思英特电梯系统有限公司引进美国的电脑神经元智能控制技术和产品部件，在此基础上力争推出自己的产品。虽然我国电梯业大量引进国外先进技术，但是很多停留在产品引进上，对关键电梯群控技术仍未能消化或根本未能引进。因此国内这方面的研究仍落后于国外，有待进一步赶上。现今随着人工智能的不断发展，国内外很多的研究人员将专家系统、模糊控制、人工神经网络以及计算机视觉等应用到电梯群控系统，使系统的性能进一步提高。3.选题背景随着城市高层建筑和智能化建筑的增加，人们对电梯服务质量提出越来越高的要求，单台电梯往往不能满足建筑内的交通需求，为缩短人们的候梯时间，减少能量的损耗，需要合理安装多台电梯。安装在一起的多台电梯要求单台电梯的控制系统相互联动，且具有监控系统。但仅仅这种方式不能适应客流量的剧烈变化，无法改善在某段时间内必然出现的长候梯现象。对于电梯群的协调调度，要根据轿厢内的人数、上下方向的停站次数、层站及电梯厢内的呼梯信号以及电梯厢所在位置等因素来分析实时客流的变化情况，自动选择最适合客流的情况的输送方式。因此，多台电梯的优化调度系统应运而生。多电梯的调度系统是通过对电梯群的运行状态进行实时监测与分析，再根据不同的实际情况对各电梯进行优化调度和合理分配，进而实现电梯系统对乘客的服务质量和服务效率的改善和提高的目标。4.本文的主要研究内容电梯调度算法优化问题在现代这个讲究安全的社会里，显得十分的重要。电梯调度算法优化问题即要找到更加合适的调度算法满足乘客的需求。本文的主要研究内容是电梯调度算法的改进，首先就是研究电梯系统，了解它有哪些特性，然后研究传统的电梯调度算法，再对电梯调度算法进行改进。4.1电梯系统介绍4.1.1电梯的起源 最原始的电梯控制由司机操作，这样不但浪费人力资源而且很不经济。为了解决这个问题，最初采用了简单自动式控制方式，可自动记忆呼梯信号，响应首先呼叫的乘客的需求，但是不能同时记忆多个呼梯信号，使用起来很不方便，效率也低于人力操作的效率。后来出现了集选控制，它能记忆下所有的呼梯信号，在运行方向上依次响应，并且自动在运行方向的信号响应完后接着响应相反方向上的呼梯信号。由于在建筑物内，单台电梯常常是不能应付全部客流的，因此需要并排设置几台电梯，这样便产生了电梯相互联接的问题。某个建筑物内设置有多台并列的独自操作的电梯，由于人们往往会同时按下几台电梯的召唤按钮，使得几台电梯的轿厢去响应同一呼梯信号，降低了工作效率，增加了能耗，而且在频繁的需求下会造成轿厢聚集现象。因此，安装在一起的多台电梯的合理使用要求单台电梯的控制系统相互联动，且具有自动监控系统。于是出现了用集选方式控制的并列两台电梯的联动控制方式。但是，在大型的办公楼里，上班时的上行乘客、午饭时的上下行乘客、下班时的下行乘客非常多，轿厢需要频繁地往返运行，这时就显示了这种方式的不足之处，它不能适应这种客流量的剧烈的变化规律，难以克服轿厢的频繁往返，也无法改善在某段时间内必然出现的长候梯现象。显然单靠增加电梯的荷载、速度、台数不能改善这种现象。因此，关键问题在于对这群电梯的协调调度，要根掘轿厢内的人数，上下方向的停站次数，层站及轿厢内的呼梯信号以及轿厢所在位置等因素，来分析实时客流的变化情况，自动选择最遥宜于客流情况的输送方式。为解决这个问题，二十世纪四十年代，美国两大电梯制造公司Otis电梯公司和西屋电机