数学建模_电梯调度问题.doc

写字楼电梯调度问题摘要 随着社会的发展，人们对电梯的需求量也在不断增加，电梯问题也随之而来。本文着重探讨如何合理地调控使用现有电梯，提高电梯的服务效率。 针对该写字楼在工作日里每天早晚高峰时期均是非常拥挤，而且等待电梯的时间明显增加的现象，分别在不同的约束条件下建立了优化的电梯调运模型。 本文采用侧重于乘客等待电梯时间的优化的“时间最小最大”群控方法，依据“电梯运行周期与运行总时间之比等于电梯在一个周期内运送的乘客数与乘客总数之比”的“比例”原则,先对电梯常见的几种运行模式进行具体分析，得到最优的运行模式某部电梯直达某高层以上（分段运行方案）。然后对高层写字楼电梯运行管理建立数学模型，进行定量分析求解。由于电梯数目固定，为使电梯能尽可能地把各层楼的人流快速送到，减少候梯时间，故只能通过优化电梯的调度方案，减少每部电梯运行过程中的停靠次数来缩短电梯平均往返运行时间，以达到提高电梯运行效率的目的。通过计算机仿真电梯运行情况，我们得到分区越多，电梯平均往返时间越短，电梯运行越高效。因此对楼层进行分区，每部电梯分别服务特定楼层，我们将整个楼层分为六个服务区，每区分配一部电梯。通过对各区域电梯平均往返时间的计算，得出每一区域运送完所有人员所需时间，将各个区域作为动态规划的各个阶段，每个区域的最高楼层作为各阶段的状态变量，以时间作为权值，建立了两个模型。 在模型一中，以各电梯运完所负责楼层人员所需时间的和最小为目标建模，建模过程中，先给出一个可行解，在此基础上，通过限制条件：各电梯完成运送所用时间不应相差太大；来简化模型筛选数据，最终，建立动态规划中最短路问题的模型，利用matlab与lingo，得出运送完所有人员所需时间最短条件下的最优路径，“无地下部分”下，即得到楼层最优分配方案为：服务区i123456服务楼层2-56-910-1314-1617-1920-22所需时间309646206300583546865393总时间29930平均时间4988.3在模型二中，以使的最大值最小为目标建模，通过不断地筛选数据，简化模型，最终得到9种方案，接着采用枚举法选出其中的最优解，最优解为：服务区i123456服务楼层2-67-1011-1314-1617-1920-22所需时间458546474966583546865393总时间30112平均时间5018.7最长用时为5835s； 最后，本文给出了模型的评价与改进；关键词：动态规划、分段运行、最短路、筛选数据1. 问题的重述现代高层写字楼中一般都配套了多台电梯，每天上下班的一段时间内，乘电梯的人会增加很多，造成拥挤，人们为了等候电梯不得不等待很长时间。所以人们希望有一个合理有效的电梯调度运行方案。 那么如何选择台电梯的运行方式呢？使得写字楼内各楼层的办公人员能正常工作和出行，不会造成过度拥挤，而且等待电梯的时间也很短。在一般高层写字楼中，经常采用的电梯运行方式有分层次或单双层的运行方式，或者某部电梯直达某高层以上的方法，试从尽力满足客户需求这个角度，具体评价这些方案的优劣。实际问题探讨：商业中心某写字楼有二十二层地上建筑楼层和两层地下停车场，6部电梯，每部电梯最大载重是20个正常成人的体重总和。工作日里每天早晚高峰时期均是非常拥挤，而且等待电梯的时间明显增加。请你针对早晚高峰期的电梯调度问题建立数学模型，以期获得合理的优化方案。楼层人数楼层人数楼层人数12345678无 208 177 222 130 181 191 236910111213141516236139272272272270300264171819202l22200200200200207207表l 各楼层办公人数（个）一览表1、 请给出若干合理的模型评价指标。2）暂不考虑该写字楼的地下部分，每层楼层的平均办公人数经过调查已知（见表1）。假设每层楼之间电梯的平均运行时间是3秒，最底层(地上一层)平均停留时间是20秒，其他各层若停留，则平均停留时间为10秒，电梯在各层的相应的停留时间内乘梯人员能够完成出入电梯。请你针对这样的简化情况，建立你的数学模型（列明你的假设），给出一个尽量最优的电梯调度方案，并利用所提评价指标进行比较。3）将你在第2问中所建立的数学模型进一步实际化，以期能够尽量适用于实际情况，用于解决现实的电梯调度问题。二、问题的分析2.1 问题一的分析 电梯运行方案的评价指标有多种,比如有乘客等待电梯的平均时间、乘客等待电梯的最大时间、乘客从起始层到达目的层所需平均时间、乘客从起始层到达目的层所需最大时间、等等，考虑到如何在上下班的电梯乘坐高峰期,及时的将所有等待的乘客快速运至目的地,尽快疏散等候区的乘客目标更有实际意义。这里我们选择各个电梯运送完乘客所用时间的和(即的和)为一个指标，同时选用各个电梯运送完乘客所用时间的最大值(即的最大值)为另一个指标。2.2 问题二的分析 我们考虑到高峰时期出现电梯非常拥挤、而且等待电梯的时间明增加这种现象的原因有以下两个方面：一，电梯数目不足；二，电梯调度不科学，没有被科学有效地利用。在上下班高峰时段，在电梯数目固定、电梯运行时间既定的情况下,合理的安排电梯停靠楼层的方案变成了提高电梯运行效率的唯一出路。电梯运行效率低下主要是由于电梯运行过程中停靠次数过多造成的，因此需分析电梯停靠次数与其运行周期的关系，为此，我们用计算机模拟电梯运行情况。考虑到上班时人群由一层分散至其他各层的过程与下班时人群由各层集中至一层的过程的对称,因此我们只需分析上班高峰和闲时的情况。通过对上班高峰时段的电梯运行情况建立数学模型进行描述,对高层写字楼人员流动高峰时段的几种电梯运行方案进行比较,制定电梯在上下班客流高峰期的最佳调度方案。2.3 问题三的分析 将问题二中所建立的数学模型进一步实际化，就需要考虑到写字楼的地下部分3、 模型的假设和符号说明3.1 模型的假设（1）所有人员均乘电梯上楼，不走楼梯。（2）只有上行人员，认为所有人员只上不下。（3）电梯每次上行均在启动层满载,运行过程不发生故障；（4）在无地下部分时，第1层无乘客出电梯，在允许到达的其余各层均有乘客出电梯；3.2 符号说明：电梯单循环最大运送层数，等于楼层数减1；：电梯最大载客量，即电梯容量；：第层楼的工作人员的人数（即电梯需要向每层楼运送乘客的人数）；：每层楼之间电梯的平均运行时间；：电梯每停一次的平均停留时间；：电梯在最底层(地上一层)平均停留时间；：号电梯一个运行周期的时间；：号电梯运行的总时间： 服务区总数目： 服务区序数： 第i个服务区楼层数： 服务区i分配的电梯数： 服务区i中电梯运行周期： 服务区i分配楼层的最高层： 服务区i总人数： 服务区i所有人员运送完毕所需总时间四、模型的建立与求解4.1 常见的几种电梯运行方案的比较 为简化描述同时不失一般性,我们假设有两台电梯同时独立运行。电梯运行方案的比较有多种标准 ,这里我们考虑到如何在上下班的电梯乘坐高峰期,及时的将所有等待的乘客快速运至目的地,尽快疏散等候区的乘客目标更有实际意义,因此我们采用侧重于乘客等待电梯时间的优化的“时间最小最大”群控方法。即使最后被运送的乘客的等待时间T最短,即“最大最小”原则作为其评价指标，并依据“电梯运行周期与运行总时间之比等于电梯在一个周期内运送的乘客数与乘客总数之比”的“比例”原则,对常见的运行模式描述。4.1.1 常见电梯运行方案的描述假设每层楼工作人员的人数（即电梯需要向每层楼运送乘客的人数）均为100电梯最多能运送20人，假设该办公楼总共10层。假设每层楼之间电梯的平均运行时间是3秒，最底层(地上一层)平均停留时间是20秒，其他各层若停留，则平均停留时间为10秒。1. 分层次法该方案允许电梯可以在任意层停靠,随机运行,两台电梯平均运行周期均为164秒，共运送乘客220人,运送所有乘客共900人,所用时间为T , 并依据“电梯运行周期与运行总时间之比等于电梯在一个周期内运送的乘客数与乘客总数之比”的“比例”原则得: 可解得： (1）2. 单双层法奇偶层运行方案该方案要求两台电梯中一台停靠奇数层,另一台停靠第1层和偶数层。因为一共有10层楼，所以停靠奇数层的电梯的运行周期为114秒, 共运送乘客20人,运送所有乘客共400人,完成运送至奇数层的乘客所用的时间，并依据“电梯运行周期与运行总时间之比等于电梯在一个周期内运送的乘客数与乘客总数之比”的“比例”原则：而停靠偶数层的电梯的运行周期为124秒, 共运送乘客20人,运送所有乘客共500人,完成运送至偶数层的乘客所用的时间,并依据“电梯运行周期与运行总时间之比等于电梯在一个周期内运送的乘客数与乘客总数之比”的“比例”原则: (2）某部电梯直达某高层以上分段运行方案该方案将以6层为界分为上下两段,一台电梯运行第1层至第6层,该电梯平均运行周期均为100秒，共运送乘客20人,运送所有乘客共500人,所用时间为，并依据“电梯运行周期与运行总时间之比等于电梯在一个周期内运送的乘客数与乘客总数之比”的“比例”原则: 另一台则运行第1层,第7层至第10层,该电梯平均运行周期均为114秒，共运送乘客20人,运送所有乘客共400人,所用时间为，并依据“电梯运行周期与运行总时间之比等于电梯在一个周期内运送的乘客数与乘客总数之比”的“比例”原则: (3)4. 某部电梯直达某高层以上分层次法与分段相结合的方案该方案同样将以6层为界分为上下两段,第一台运行第1层,第6层至第10层,该电梯平均运行周期均为124秒；共运送乘客20人,而另一台电梯则可停靠所有楼层, 该电梯平均运行周期均为158秒，共运送乘客20人,在平均情况下可设乘客在各层选择每一台电梯的机率相等,则第一台电梯运送共有乘客人,另一台运送所有乘客共人,第一台电梯完成运送所有乘客所用时间,并依据“电梯运行周期与运行总时间之比等于电梯在一个周期内运送的乘客数与乘客总数之比”的“比例”原则: 停靠所有楼层的电梯完成运送乘客所用的时间,并依据“电梯运行周期与运行总时间之比等于电梯在一个周期内运送的乘客数与乘客总数之比”的“比例”原则: (4)5.逐层运输法两台电梯运送完一层运送另一层。故时间：（5）4.1.2 常见电梯运行方案的比较比较（1）、（2）、（3）、（4）、（5）式。我们容易得到:综上考虑电梯的运行效率可得: 逐层运输方案分段运行方案奇偶层运行方案分层次与分段相结合分层次运行方案的方案。不过考虑到逐层运输不符合实际。因此我们得出结论: 分段运行方案是最及时的将所有等待的乘客快速运至目的地,尽快地疏散等候区的乘客的最优调度方案。4.2 实际问题的求解由4.1.2，在上下班高峰期间，我们采用分段运行方案。 为了减少电梯因停靠次数过多，反复加速减速过程而造成电梯运行周期过长浪费的时间，我们采取对电梯和楼层分区控制的方法，将整栋大楼分为6个电梯服务区，并设第个区域服务的楼层数为，分配的电梯数为1，根据已知的数据，得出电梯往返一次所需的时间，是关于的函数，然后通过建立动态规划模型得出运送完所有楼层人员所需时间最短的一种分区方法，即得到了优化的电梯调运模型。4.2.2 电梯往返一次所需时间由于本题考虑的是电梯上高峰时期的动态规划，因此可以认为电梯每次都能达到满载，并且假设电梯在其所服务的每一个楼层均有停靠。对于第个区域的电梯，其运行过程可分为三部分，第一部分：在第一层的停留时间，第二部分：在服务区域的各层的停留时间为，第三部分：电梯升降过程所用时间为。则电梯往返一次的运行总时间为； 下面来求解； 当时，即对第一个区域，记该区域所分配楼层的最高层为，分配的电梯数为1,则：第一部分所需时间为:第二部分所需时间为:第三部分所需时间为:则电梯往返一次所需时间为： 当2i6时，即对第二至六个服务区，区域所分配楼层的最高层为，各区域分配一部电梯，则：第一阶段运行时间为:第二阶段运行时间为:第三阶段运行时间为:则电梯往返一次所需时间为：4.2.3所有人运送完毕所需总时间由于上梯人员多，电梯量相对不足，为使在规定时段内电梯能尽可能地把各层楼的人流快速送到，我们只需满足当把所有人员运送完毕时，所需时间最短。根据以上公式及数据可以得到各服务区人员全部运送完毕所需时间TM。对服务区i，所有人员运送完毕所需时间为：其中表示服务区所服务楼层人员总和，由、及原始数据得出，“”表示对小数采取加一法保留整数，如“”, 又因为最后一次运送时电梯从最高层向下运行的时间不需考虑，故减去；4.2.4动态规划模型的建立得到电梯的往返时间后，我们就可以来确定电梯的调运方案。确定了楼层分为6个区域后，只需从下往上再确定每个服务区的分区点，在确定分区点时，一旦当前一个服务区确定以后，其后续服务区的服务范围只受当前服务区范围决定，而不受当前服务区之前服务区的影响。模型一： 以各电梯运完所负责楼层人员所需时间的和最小为目标建模从楼梯口开始，从下到上把各个服务区的服务区域作为动态规划的各个阶段，以各个区域的服务区域的最高楼层作为各阶段的状态，本题中，当把30层楼分为6个区域时，各个阶段所处的状态集合分别为：；为使运送完毕所有人员所需时间最短，我们可以考虑对各服务区运送完毕所有人员所需时间求和，取和最小时的分区方案为最优调控方案。这样就可近似为动态规划中的求最短路及其距离的问题，如图所示： 考虑到所属的集合包含的元素太多(均含16个，而且大多是无用的)，可能会对模型的求解造成困难，因此，我们对模型进行简化处理，减少所属集合的元素。 因为各个电梯只为特定的楼层服务，各楼层的员工便只能乘特定的电梯，因此，便有了这样的一个限制条件，那就是：各电梯完成运送所用时间不应相差太大； 下面，便以此为标准来简化模型，具体步骤是：1) 主观的选出一种可行解；2) 求其平均时间；3) 以此平均时间为基准，简化模型且时各电梯运行时间不宜与其相差太大； 步骤1：电梯共服务的楼层为22-1=21层，因此令每个电梯服务34层，且令在较低层服务的电梯，负责的楼层多点，于是得到以下可行解； 服务区i123456服务楼层2-56-910-1314-1617-1920-22所需时间309646206300583546865393总时间29930平均时间4988.3 步骤2：见上表； 步骤3：以(平均值2000)为范围来简化模型，若在范围外则排除； 设表示时的值；表示,时的值； 排除；接受； 接受；接受； 排除；亦排除；因此； 排除； 接受；接受；排除；用的最小值可求S2的最小值，用的最大值可求的最大值，同理，用的最小值可求的最小值，用的最大值可求的最大值；依此类推，可求出，的范围；最终求得：；于是，问题转化为求如下图所示的最短路问题，图中各段长度(即时间)可用matlab求解，源程序见附录，然后可用lingo求最短路，源程序见附录；求得的结果为：； 用表格来表示结果服务区i123456服务楼层2-56-910-1314-1617-1920-22所需时间309646206300583546865393总时间29930平均时间4988.3巧合的是，求得的的结果正是我们第一部中给出的可行解； 模型二： 以使的最大值最小为目标建模 为方便求解，我们依然要对模型进行简化，简化方法与模型一的简化方法相似，且我们要在模型一的简化结果上进一步简化 模型一的简化结果： ；下面进一步缩小的范围，在上述简化的基础上，以( 平均值+1500）为最大值来缩小范围，同时，采用从上往下推导的方法来简化；首先确定 再确定 排除；所以 亦排除所以 再确定 排除，且排除；依依此法最终求得 ： ；接下来进一步简化： 因 故， 不同时出现； 因 故， 不同时出现； 因 故， 不同时出现； 因 故， 不同时出现； 因 故， 不同时出现； 因 故， 不同时出现； 因 故， 不同时出现；可将上述结果以如下图形表示：因此得到了下表所列的9种方案： 方案26913161922方案351013161922方案461013161922方案571013161922方案671113161922方案771114161922方案871114171922方案9711 14172022 对应的时间为：方案13096462063005835468653936300方案24585330863005835468653936300方案33096617349665835468653936173方案44585464749665835468653935835方案56478319749665835468653936478方案66478537031005835468653936478方案76478537052093725468653936478方案86478537052095646290653936478方案96478537052095406486334236478最大值中的最小值为5835，因此最优方案为方案四。将方案四以表格形式表示：服务区i123456服务楼层2-67-1011-1314-1617-1920-22所需时间458546474966583546865393总时间30112平均时间5018.74.3 对问题的回答：对问题一的回答： 我们选择各个电梯运送完乘客所用时间的和(即的和)为一个指标，同时选用各个电梯运送完乘客所用时间的最大值(即的最大值)为另一个指标。对问题二的回答： 在以上建模过程中，本文分别以上述两个指标为目标建立了两个模型，在模型一中，本文的解为各电梯所用时间的和最少的解，在模型二中，本文给出的解为各电梯所用时间的最大值最小的解，两个解并不一样，对于第一个解，虽然总和最小，但最大值为6300，而对第二个解，其最大值仅为5835，且第一个解最小值为3096，最大最小值相差3204，而第二个解的各个值相对比较平均。对问题三的回答： 考虑到实际情况，则要考虑地下停车场，当选定上述模型中的一个后，可令用时最小的电梯同时负责负二楼，令用时次少的负责负一层，当然，这还要结合开车的人数，具体分析。五、 模型的评价1. 模型的不足：（1）在描述分层次方案中，我们假定电梯在一次运行中部一定每层都会停，因此在结果会造成一定的误差；（2）电梯在每次运行中不一定是满载，计算数据可能对实际情况偏小；2.模型优点：（1）对电梯常见的运行模式做了具体分析，对其他建筑高楼电梯的运行模式设计具有一定的指导意义；（2）在问题二中，运用计算机对电梯运行情况进行matlab仿真，得出分区控制可以缩短电梯运行周期，逻辑严谨。建立的动态规划最短路模型，逐阶段全面分析，能够得出最有效的电梯调运方案。3.模型的改进由于条件限制，在进行电梯运行情况仿真时，我们仅对电梯停靠次数为5 次和6次的情况作了具体分析，可能不够完善。在动态规划模型求解过程中，但是由于各服务区状态集元素较多，用此方法计算量偏大，有待进一步探索找出一种更为简便的方法。六、参考文献1） 附录%将楼从下至上分为六段，s1为第一段的最高层数，函数fu1用来求一号电梯运完%第一段各楼层的员工所用的时间；function t1=fu1(s1)m=length(s1);P=0,208,177,222,130,181,191,236,236,139,272,272,272,270,300,264,200,200,200,200,207,207;P1=zeros(1,m);for j=1:mfor k=1:s1(j) P1(j)=P1(j)+P(k);endendT1=20+2*(s1-1)*3+(s1-1)*10;t1=ceil(P1/20).*T1-(s1-1).*3;end%函数fu2是用来求第i号电梯运完第i段各楼层员工所用的时间；s2表示第i段的最高层数，s1表示第i-1段的%最高层数function t2=fu2(s1,s2)m=length(s2);P=0,208,177,222,130,181,191,236,236,139,272,272,272,270,300,264,200,200,200,200,207,207;P2=zeros(1,m);for j=1:mfor k=s1+1:s2(j) P2(j)=P2(j)+P(k);endendT2=20+2*(s2-1)*3+(s2-s1)*10;t2=ceil(P2/20).*T2-(s2-1).*3;end !用lingo来求最短路;sets:cities/X,A5,A6,A7