电梯的模拟算法与优化调度方案

本 科 生 毕 业 设 计 (论 文)

题目：电梯的模拟算法与优化调度方案

The simulation arithmetic and move scheme about

elevator

教学单位 _计算机科学与技术学院 姓 名 __ _ 学 号 ___

年 级 _____ _________ 专 业 _ 信息与计算科学 指导教师 ___ 职 称 _____ _ _

2009 年 5 月 5 日

目录

1

摘要 .................................................................................................................................................. 3 Abstract ............................................................................................................................................. 4 第一章 绪论 ................................................................................................. 错误！未定义书签。

1.1问题的提出 ......................................................................................................................... 4 1.2基本假设 ............................................................................................................................. 6 1.3基本术语和符号说明 ......................................................................................................... 6 1.4问题的分析 ......................................................................................................................... 8 第二章 模型的建立与解答 ........................................................................................................... 13

2.1 电梯问题分析 ................................................................................................................ 13 2.2 电梯运行时间 ................................................................................................................ 14 2.3 电梯系统的模拟算法 ...................................................................................................... 16 第三章 电梯调度的优化方案 ..................................................................................................... 21

3.1 电梯调度问题的分析 ...................................................................................................... 21 3.2 电梯调度的方案 .............................................................................................................. 22 第四章 模型的推广 ..................................................................................................................... 25 第五章 模型的评价 ..................................................................................................................... 25

5.1模型的优点 ....................................................................................................................... 26 5.2模型的不足 ....................................................................................................................... 26 参考文献......................................................................................................................................... 27 致谢 ................................................................................................................................................ 28 附录 ................................................................................................................................................ 28

电梯的模拟算法与优化调度方案

2

摘要

电梯是现代高层建筑中非常普遍的运输工具，如何合理的调控使用现有电

梯，以提高电梯的服务效率，尽量减少人流的乘梯等待时间和乘梯时间等，已经成为电梯管理中的首要任务。

本文首先借助计算机给出电梯模拟系统的算法，目的是向管理者提供一种比较真实的电梯服务情况。其次,通过计算机给出的模拟数据为管理者提供一套更有效的电梯调度方案。

关键词： 效率 算法 方案

3

Abstract

Elevator is a formal transport measure in the model high-rise building.How to regulate the existing elevator reasonably so as to improve the efficiency of elevator service and reduce the waiting time for elevator has become the primary task in the elevator management. The text firstly has presented the elevator simulation arithmetic with the help of the computer, in order to provide managers with an actual elevator service complexion. Besides, through using the simulation data that the computer has given, which offers managers a set of elevator move scheme.

Key words: effect arithmetic scheme

第一章 绪论

1.1问题的提出

1.1.1背景：

4

电梯是现代高层建筑中不可缺少的便捷工具，它的重要性与平面中的汽车相同。据国外资料统计，每天乘电梯的人次已经超过了每天乘坐汽车的人次。随着现代化高楼的发展，对电梯的数量、质量以及如何更好地使用电梯都提出了很高的要求。对于一栋写字楼，在早高峰时间，人们经常抱怨，在电梯回来之前他们在大厅等待的时间太长，另一些人则抱怨他们在电梯中呆的时间太长，还有人申诉，早高峰时间大厅里人太挤。本文将对A First Course in Mathematical Modeling . Third Edition书中模拟电梯系统的算法进行改进，从而模拟电梯系统反应更真实的电梯服务状况并提供一套优化的电梯调度方案。

1.1.2重述：

考察对象是成都某一繁华地区的一座19层写字楼（该写字楼和电梯的参数如表1所示），在早高峰时间，上午7：45到9：10，人们进入一楼大厅并乘电梯到他们所在的楼层，有4部电梯为这座大楼服务，乘客到达大楼的时间间隔在0~30秒内随机地变化，到达后每个乘客选择第一部可乘的电梯（这里我们把这4部电梯从1到4进行编号），当某人进入电梯并选择到达楼层后，电梯在关门前等待15秒，如果另一个人在这15秒内到来，这种等待将重新开始；如果15秒内无人到达，电梯就把全体乘客送上去。

表1 该写字楼的楼层和电梯参数 大 楼 参 数 电 梯 额 大楼层数 门厅高度h 非门厅的楼层高度h 电梯数量 最大速度Vm 最大加速（减）度Am 加速度变化率ɑ 19层 2.6米 2.6米 4部 2米/秒 1.4米/秒2 2米/秒2 5

定 参 数 额定容量 开（关）门时间 乘客转移时间 13人 5秒 3秒

1.2基本假设

由于我主要讨论的是上班高峰时期电梯的使用情况，为了简化问题的研究，故作以下假设：

1．考虑到在上班的高峰期里下行的乘客比较少，所以假设只有上行的乘客而没有下行的乘客，即所有电梯只是往上运送乘客；

2．电梯在运送乘客的中途没有其他乘客要上电梯，在下行时各中间层也不作停靠；

3．由于乘客的到达是随机的，事先并不知道将去哪一个楼层，所以，我们假设到来的乘客是以相同的概率去大楼的每一个楼层； 4. 假设楼层间的运送时间为2秒。

1.3基本术语和符号说明

1.3.1 基本术语

⑴跟踪时间的时钟TIME（以秒计），开始时TIME的值是0秒（上午7：45），当TIME到达5100秒（上午9：10）时模拟结束。

⑵乘客编号，按照乘客到达的次序给乘客编号：到达的第一位乘客为1，第二位乘客为2，依次类推。

⑶电梯j的可乘用时间RETURN[j]，若电梯j当前在1层可以乘用，则这个时间就是当前时间，于是RETURN[j]=TIME。若电梯j在运行中，则它的可乘用时间是它回到1层的时间。乘客按照电梯编号的顺序进入一部可乘电梯：首先是电梯

6

1（如果可乘用），然后是电梯2（如果可乘用），等等。

⑷数组Sj和Fj，为了在电梯运送过程中根踪被选择的楼层和楼层被选择的次数，该算法设置了两个一维数组Sj和Fj，Sj表示乘客所选择的1到19层的任意一层（这里虽然没有乘客选择第一层，为了简单起见也包括在内），Fj表示每一层楼所乘客选择的次数。例如，有一位乘客选择了第8层楼，则将1分别输入到Sj的第8个分量和Fj的第8个分量。如果另一位乘客也选择了第8层楼，则Sj不变，Fj的第8个分量变为2.依次类推。假定电梯j中的乘客选择3层1次、5层3次、7，9，11层各选择1次、14层选择5次、17层选择2次，那么对这部电梯，Sj=（0，0，1，0，1，0，1，0，1，0，1，0，0，1，0，0，1，0，0），Fj=（0，0，1，0，3，0，1，0，1，0，1，0，0，5，0，0，2，0，0）.用这些数组计算电梯j运行时间，于是可确定它返回1层的时间，如前所述，这个返回时间记作RETURN[j].这些数组也用来计算电梯j中每位乘客的运送时间。

⑸运送时间tr，表示电梯从启动到停止过程中，运行距离为r层楼时的运行时间，即电梯从启动到运行r层楼后停靠所需要花费的总时间。

1.3.2 符号说明

； beti:乘客i与i-1到达时间间隔（在0和30秒钟之间变化的一个随机整数）

arrivei:从时钟t=0开始计时，乘客i的到达时间（仅当乘客排队等待电梯时计算）；

； floori:乘客i选择的楼层（2到19之间变化的一个随机整数）

elevatori:乘客i停留在电梯里的时间；

； waiti：乘客i进入电梯之前的等待时间（进当乘客排队等待电梯时计算）

deliveryi：乘客i从到达到运送至目的地楼层的时间，包括等待时间；

Sj：记录电梯j被选择楼层的0、1一维数组，不计楼层被选择的次数； Fj：对于电梯j中正运往目的地楼层的乘客，记录被选择楼层的次数的一维整数数组；

Oj：当前使用电梯j的乘客数；

RETURNj：从时钟t=0开始计时，电梯j返回大厅并可供乘客乘坐的时间；

firstj：电梯j返回大厅后第一位进入的乘客的编号；

queue：当前等待一部电梯变成可乘用电梯排队的总长度；

quecust：排队等待的第一位乘客的编号；

startque：当前的排队开始形成的时钟时间（可能更新）；

stopj：电梯j在整个模拟中停止的次数；

7

eldelj：电梯j用于运送当前这批乘客的总时间； operatej：电梯j在整个模拟中运行的总时间；

tr: 电梯从启动到运行r层楼后停靠所需要花费的总时间；

limit：最后进入一部可乘用电梯（在它开始运送之前）的乘客的编号； max：数组Sj最大非零元素的指标（被选择的最高楼层）；

remain：下一步可乘用电梯起程后还在排队的乘客数；

quetotal：花时间等待的乘客总数；

TIME:从t=0开始当前时钟的时间（秒）；

DELTIME：一位乘客从到来到抵达目的地楼层的平均运送时间，包括等待时间； ELEVTIME：一位乘客呆子电梯里的平均时间；

MAXDEL：一位乘客从到来到抵达目的地的楼层的最长运送时间； MAXELEV：一位乘客呆在电梯里的最长时间； QUELEN:在最长的队中等待的乘客数； QUETIME：等待的乘客呆在队中的平均时间； MAXQUE：等待的乘客呆在队中的最长时间。

1.4问题的分析

随机模拟介绍

在对实际问题的求解过程中，在能够用分析方法（机理分析和测试分析）建立和求解的数学模型中，目的通常或是求最优解，或是寻找变量间的规律，或是分析参数和输入变量对结果的影响，如果这样建立的模型基本上符合实际，那么求出解析解或是数值解，当然也可以对原问题做出回答。但是，对于一些带有随机因素的复杂系统，用分析方法建模常常需要做出许多简化假设，与面临的实际问题可能相关甚远，以至解答根本无法应用。这是模拟几乎成为人们的唯一选择。 模拟是在整体运行过程中对系统的仿真，是非常有效和广泛使用的分析、研究复杂系统的技术。将实际系统简化制成实物模型，进行物理实验，成为物理模拟。而在一定假设条件下，利用数学运算模拟系统运行，可成为数学模拟。现代的数学模拟都是在计算机上进行的，成为计算机模拟。

模拟分为静态模拟和动态模拟。蒙特卡洛随机模型是典型的静态模拟，动态模拟又可分为联系系统模拟和离散事件系统模拟，前者研究系统的状态随时间连

8

续变化的情形，其模型一般是微分方程；后者讨论的是系统状态只在一些离散时间点上，由于事件驱动而变化，其模型一般只能用流程图或网络来表示。 离散事件模拟通常有如下一些步骤：

①了解问题背景，明确模拟目的。模拟常常是要得到系统的某些性能指标，或者进一步要通过性能指标的比较来确定最佳策略。

②建立模拟模型，确定计划，制定流程。要明确系统运行的条件，找出系统各部分间的数学或逻辑关系，如有必要，画出模拟流程图。

③获取一组输入数据，可以是实际的，也可以是按一定的概率分布随机产生的。 ④在计算机上运行一边，得到系统指标的一个样本，同时对流程做一次检验。 ⑤获取多组输入数据，进行多次模拟。用统计方法得到性能指标较好的统计。 ⑥根据模拟目的，或是对不同条件下的性能指标进行比较和选优，或是就模拟的参数、初始条件、模拟过程的长度等对结果的影响进行分析。

在日常生活中经常有很多实例就是排队服务系统的模拟，像生活中经常有排队等候服务的现象：自选商场收款台前顾客排队验货付款；病人在医院按挂号顺序等候就诊；车间发生故障的机器等待修理；机场搭载乘客的飞机等待起飞。研究这些现象时，排队等待服务的对象，如病人、飞机等，通称“顾客”，进行服务的主体，如医生、跑道等，通通成为“服务员”。本例只讨论一个服务员的情形，称单服务系统。 ⑴模拟的目的

对于排队服务系统，顾客常常注意排队的人是否太多，等待的时间是否太长，而服务员则关心他空闲的时间是否太短。于是排队常与排队的长度、等待时间、顾客光临系统的频率及服务员的服务效率有关。如果知道了顾客到达的时间和服务时间的统计规律（大量实际数据或概率分布），怎样通过模拟得到衡量系统性能的数量指标，并与分析模型的结果进行比较，是这次模拟的目的。 ⑵系统的假设与输入

单服务员系统的运行过程十分简单：当一位顾客到达系统时，若服务员空闲则立即进入服务，服务完毕离开系统；若服务员正在工作，待正接受服务的顾客离开后再进行服务。首先做以下基础假设： ① 顾客源是无穷的；

② 排队的长度是没有限制的；

③ 到达系统的顾客按先后顺序一次服务，称“先到先服务”。

两位顾客先后到达系统的时间间隔（时间间隔记作i）是随机变量，其概率分布已根据经验或理论假设确定。我们事先给出假定到达时间i的概率分布如表2：

9

表2 i的概率分布表

到达间隔i/min 概率p

(0,2] 0.4 (2,4] 0.5 >4 0.1

每位顾客的服务时间（实际上是接受服务的时间s）也是随机变量，假定其概率分布如表3：

表3 s的概率分布表

服务时间s/min 概率p

(0,2] 0.5 (2,4] 0.5

根据这两个分布，可以产生任意多个到达间隔i和服务时间s的数据，比如产生了下面一组数据（如果已有大量的实际数据，也可以直接应用，不需要从概率分布产生），如表4。

表4 到达间隔i和服务时间s的数据

k ik sk 1 2 0 2 1 3 3 3 1 4 4 3 5 1 4 6 3 1 7 1 2 8 8 4 9 2 1 10 4 3 ? ? ? 其中ik表示第k位顾客与第k-1位顾客到达的时间间隔，sk是第k位顾客的服务时间。 ⑶系统的状态

在任意时间t，系统的状态可以用排队等候顾客的数目和服务员是否在工作来描述，排队等候顾客的数目称队长，记作L(t)，为非负数据，服务员的状态用S(t)来表示。当服务员工作时，令S(t)=1，服务员空闲时S(t)=0.

引起系统状态L(t)和S(t)改变的行为称为事件。这里只有两个类型事件，分别是顾客到达和顾客离开。即第k位顾客到达的时间为ak,离开时间为bk，它们很容易根据已有的到达间隔ik和服务时间sk按照以下的递推关系得到（设a0=b0=0）。

ak?ak?1?ik, dk=max(ak,dk-1)+ sk,k=1,2,? (4.1)

ak, dk分别是“顾客到达”和“顾客离开”事件的发生时刻，系统状态只

10

在这些时候才有变化。所以在模拟系统的运行过程中可以设置时钟t，让t依事件发生的先后顺序，从一个事件发生的时刻跳到下一个事件发生的时刻，这种模拟称为下一事件的推进法。 ⑷初始条件和终止条件

不妨假设t=0是第一位顾客到达的时刻，此时服务员处于空闲状态。模拟的终止时刻是t(给定值)，或模拟直到第n个(给定值)顾客进入服务的时刻为止，这个时刻记作T(n)。

运行模拟时可以事先产生一批数据ik, sk如表4，再由(4.1)式计算ak, dk。然后让时钟t按ak, dk从小到大的顺序跳动。但更加常见的不是产生一批数据ik,

sk待用，而是在时钟t跳到某一事件时，才产生一个需要的i或s。这里我们采用后一种方法来运行，不过每一次产生那个i或s仍采用表4所给出的数据。

设当前时钟为t，队长L(t)记作WL，服务员状态S(t)记作SS，t以后下一个“顾客到达”事件的发生时刻记作AT，t以后下一个“顾客离开”事件的发生时刻记作DT，在每一个事件发生时，都要设置、记录这4个量的数值。具体运行过程如下：

① 初始时刻(t=0)置WL=0，SS=0，AT=0，DT=999，表示无人排队；服务员空闲；下一个(即第一位)顾客到达时刻为t=0，999表示一个大于T(不妨令T=100)的数。每当服务员空闲时就要令DT=999，比较AT

② AT=0

③ AT=1DT=2，置时钟t=DT=2(第1位顾客离开时刻)。因WT=1，令WT=1-1=0(第2位顾客进入服务)，产生一个服务时间s(=s2=3),置DT=2+3=5，t

表5 单服务员系统模拟运行记录 时钟t 0 0 1 第k位顾客到达/离开 初始时刻 k=1到达 k=2到达 WL 0 0 1 SS 0 1 1 AT DT 0 999 1 4 2 2 11

2 4 5 6 8 9 11 12 13 15 16

k=1离开 k=3到达 k=2离开 k=3离开 k=4到达 k=5到达 k=4离开 k=6到达 k=7到达 k=5离开 k=6离开 0 1 0 0 0 1 0 1 2 1 0 1 1 1 0 1 1 1 1 1 1 1 4 8 8 8 9 12 12 13 21 21 21 5 5 6 999 11 11 15 15 15 16 18 ⑸系统的性能指标

前面提到，人们常用排队长度、等待时间及服务利用率等来衡量一个排队对服务系统的性能，由于它们都随时间改变，所以，一般取在一段时间内的平均值作为指标。常用的3个指标如下：

① 系统的平均队长，记作L,指队长L(t)在[0，T]内的平均值；

② 顾客平均等待时间，记作W，指顾客总的等待时间对[0,T]内进入服务的顾客数n的平均值；

③ 服务利用率，记作U，指服务员工作时间在T中的比例。 知道了状态L(t)和S(t)(0≦t≦T),这3个指标，可由下式计算：

1T L??L?t?dt

T0

W?

U?1TL??Ltdt?T ?0nn1T?S?t?dt

0L 因为状态L(t)和S(t)都是阶梯函数，所以，上面的公式中的积分可化为简单的求和。需要指出的是，由于输入数据的随机性，每次模拟得到的结果是不同的。为了得到所求指标较精确的估计，需进行若干次独立的模拟，得到这些指标一个极大的样本，然后利用统计中母体参数的点估计或区间估计来确定以上各指标。

12

第二章 模型的建立与解答

2.1 电梯问题分析

⑴在上班高峰期，任何一个需要乘坐电梯的乘客，比如乘客甲，他的整个乘坐电梯的过程的具体步骤：

第一步，乘客甲到达门厅并等待电梯到达。 第二步，电梯到达。

第三步，在乘客甲之前的乘客都分别进入电梯。 第四步，乘客甲进入电梯。

第五步，乘客甲进入电梯后等待其后面的所有乘客进入电梯。

第六步，电梯启动并经过中间一些停靠后到达乘客甲所要去的楼层停靠。 第七步，等待在甲之前的乘客下电梯。 第八步，乘客甲下电梯。

第九步，电梯运送完全部乘客后返回门厅。

⑵当另一位乘客到达大楼的门厅时，出现两种可能的情况，一种是这位乘客有可乘坐的电梯，另一种情况是这位乘客没有可乘用的电梯，在没有可乘用的电梯时，这位乘客开始排队等候，一旦有一部电梯变成可乘用的，它就被做上“标记”，并且乘客只能选择这部电梯去目的地楼层，直到它满载（13位乘客），或者超过15秒钟没有另外的乘客到达，乘用后电梯启程运送所有的乘客。即使电梯满载了13位乘客，电梯也要等待15秒钟以便搭乘最后一位乘客，以及留下选择楼层和电梯启程的时间。

⑶考虑到A First Course in Mathematical Modeling . Third Edition 171页中给出的电梯模拟系统的算法是以匀速的状态运行的，缺乏实际性。因为电梯在起动时，先以增大加速度的变加速运行，在匀加速度的加速运行，接着在以减加速度的变加速运行。直至达到平稳的最高电梯运行速度为止（这是我们平时乘坐电梯时会有很明显的感觉）。故本文将对此算法进行改进，下面给求电梯加速和减速

13

而额外花费的时间。

2.2 电梯运行时间

针对乘客不同的到达程度（到达率），会有不同的电梯往返时间，因而有必要先来研究一下它们之间的关系。

下面先来给出电梯运行距离和所需时间之间的关系，也即t[r]的表达式。要求得运行时间t[r]，必须要知道电梯的运行速度曲线。电梯运行速度曲线是由电梯本身的硬件所决定的，在电梯出厂时已被确定，很难在电梯的使用过程中加以改变。通过对网上资料的搜索，我们可以知道：电梯的运行曲线直接影响到乘客使用电梯时的舒适感。按加速度大小，电梯加速度曲线常可分为三角形、梯形和正弦波形三种。正弦波形加速度曲线的实现较为困难，而三角形曲线加速度在起动及制动阶段的转折点处的加速度变化率均大于梯形曲线，在起动和制动时会使人感到较强的振动而感到不舒适，所以电梯系统中很少被采用。而梯形曲线则因容易实现并且有良好的加速度变化率频繁指标，故实际被电梯系统广泛采用。假定我们所讨论的电梯组也是梯形曲线加速度，至于其它类型的速度曲线，此处不加以讨论。

采用梯形加速度曲线的电梯在起动时，先以增大加速度的变加速运行，在匀加速度的加速运行，接着在以减加速度的变加速运行。直至达到平稳的最高电梯运行速度为止（这是我们平时乘坐电梯时会有很明显的感觉）。当电梯需要停靠时，其运行状况刚好与起动时相反。具有梯形加速度的速度曲线、加速度曲线及加速度变化率曲线通常如图5所示：

图5 电梯运行曲线图

14

加加速度（m/s3） 加速度（m/s2） 速度（m/s）

由图5得：在电梯启动阶段，即当时间t满足0≦t≦t1时，加速度逐渐增大，那么在时刻t，速度

v1?t??at22,

其中a表示加速度的变化率(加加速度)； 此后一段时间，即在t1≦t≦t2时，速度

v2?t???at12?a?t1?t2 ；

2当电梯作减加速度加速运行时，即当t2≦t≦t2+ t1时，速度

2v2?t???at12?t2?t22?a??t1?t2??t；

??由于在时刻t= t2+ t1时有最大电梯运行速度为vm，故当t= t1时电梯有最大加速度为am，由此可以求得t1=am/a, t2=vm/am,从电梯启动到停靠，如果经历时间为t，那么，其所运行的高度

t1t2t2?t1h?2???0v1?t?dt??tv2?t?dt??tv3?t?dt???vm??t?2t1?2t2?

12??

于是电梯从启动到停止，当运行距离为r层楼时的运行时间为

15

t?r???h?r??t1?t2??a?t1?t2?2vm??vm .

针对之前给出的大楼的参数，代入上面的表达式，我们可以求得电梯运行距离和运行时间的关系：

t?r??ama?h?rvm?vmam?1.42?2.6r2?21.4?2.12857?1.3r

由上式可以看出，电梯从启动到停止的运行时间t(r)与所运行的楼层数r存在这一种线性关系，并且含有常数项2.12857.该常数项说明，在电梯上行过程中每次停靠时，由于电梯加速和减速而额外花费的时间大约是2.12857秒钟。

2.3 电梯系统的模拟算法

以下是A First Course in Mathematical Modeling . Third Edition 171页电梯模拟系统改进后的算法：

输入 beti和floori。这里beti和floori都是随机的整数，基于前面的分析，我

们给出求beti和floori的matlab程序,如下：

x=fix(30*rand(22)) y=fix(2+17*rand(22))

beti=reshape(x,1,484) floori=reshape(y,1,484)

输出 DELTIME，ELEVTIME，MAXDEL，MAXELEV，QUELEN,QUETIME，MAXQUE，stopj,

以及每部电梯使用时间的百分比。

1) 开始时将以下参数置为零：DELTIME，ELEVTIME，MAXDEL，MAXELEV，

QUELEN,QUETIME，MAXQUE,quetotal,remain

i?1 deliveryi?15

2) 对于第一位乘客，生成到达时间间隔、目的楼层，并初始化运送时间： 3) 初始化时钟及电梯的可乘用时间、停止次数、运送时间。初始化所有乘

客的等待时间。

TIME?beti

对于k?1到4: returnk?TIME, stopk?operatek?0

16

对于k?1到484: waitk?0

若TIME?5100，执行5到32步。

4) 选择第一部可乘用电梯：

若TIME?return1,则j?1,否则 若TIME?return2,则j?2,否则

若TIME?return3,则j?3,否则

若TIME?return4,则j?4,

否则(当前无电梯可乘用)转第19步。

5) 置入第一位占用已标记电梯的乘客的编号，初始化电梯占用及楼层选择

向量：

firstj?i, Oj?0

6) 对于k=1到19: Sj?k??Fj?k??0

7) 置入楼层选择向量，电梯j承运乘客，并增加占用电梯的乘客数：

Sj?floori??1

Fj?floori??Fj?floori??1

Oj?Oj?1

8) 产生下一位乘客并调整时钟：

i?i?1

TIME?TIME?beti

deliveryi?15

9) 将全部可乘用电梯设定为当前时钟： 对于k=1到4：

若TIME?returnk,则returnk?TIME 否则returnk不变。

10) 若beti?15且Oj?13，则对每位在标记电梯j上的乘客增加运送时间： 对于k?firstj到i?1:

deliveryk=deliveryk+beti

并将第7步承运电梯上的当前乘客，且产生下一位乘客。 否则(标记电梯已经离开)： 置limit=i?1且转第11步。

第11步至18步实现标记电梯j上全部乘客的运送： 11) 对于k?firstj到limit,执行第12到16步。 12) 计算乘客k呆在电梯里的时间：

N?floork?1 (一个指标)

17

elevatork=楼层间的运送时间+前面电梯停靠的额外时间(约两秒)+前面

乘客的转移时间+当前乘客的转移时间+前面楼层的开/关门时间+当前楼层的开门时间

?2N?2?Sj?m??3?FJ?m??3?5?Sj?m??5

m?1m?1m?1NNN

13) 计算乘客k的运送时间：

deliveryk=deliveryk+elevatork

14) 对总运送时间求和以得到平均运送时间：

DELTIME=DELTIME+deliveryk

15) 若deliveryk﹥MAXDEL,则MAXDEL=deliveryk

否则MAXDEL不变。 否则MAXELEV不变。

16) 若elevatork﹥MAXELEV,则MAXELEV=elevatork，

17) 计算电梯j的总停止次数、在运行中的时间及返回1楼大厅的时间：

stopj?stopj??Sj?m?

m?119

Max=Sj中最大一个非零分量的指标(即要去的最高楼层) eldelj=运送时间+乘客转移时间+开/关们时间

?2?Max?1??3?Fj?m??5?Sj?m?m?1m?11919

returnj?TIME?eldelj operatej?operatej?eldelj

18) 转第5步。

第19步至32步用于当前无电梯可乘用且已经形成等待排队的情形： 19) 初始化排队：

quecust?i (队中第一位乘客的编号)

startque?TIME (排队开始的时间) queue?1

arrivei?TIME

20) 产生下一位乘客并调整时钟：

i?i?1

18

生成beti和floori

TIME?TIME?beti

arrivei?TIME

queue?queue?1

21) 检验电梯的可乘用：

若TIME?return1,则j?1且转第22步,否则 若TIME?return2,则j?2且转第22步,否则

若TIME?return3,则j?3且转第22步,否则

若TIME?return4,则j?4且转第22步,

否则(仍无电梯可乘用)转第20步。

22) 电梯j可乘用。初始化楼层选择向量并确定排队长度： 对于k?1到19:

Sj?k??Fj?k??0

remain?queue?13

23) 若remain?0，则R?i且Oj?queue。

否则 R?quecust?12且Oj?13。

24) 电梯j承运乘客：

对于k?quecust到R:

Sj?Fk??1且Fj?Fk??Fj?Fk??1

25) 若queue?QUELEN,则QUELEN?queue

否则QUELEN不变。

26) 调整排队乘客总数：

quetotal?quetotal?Oj

QUETIME?QUETIME? 27) 若

m?quecust??TIME?arrive?

mR?TIME?startque??MAXQUE,则MAXQUE?TIME?startque

否则MAXQUE不变。

28) 以占用标记电梯上第一位乘客的编号设置标号：

firstj?quecust

29) 计算标记电梯上每一位乘客的运送和等待时间： 对于k?firstj到R：

deliveryk?15??TIME?arrivek?

waitk?TIME?arrivek

19

30) 若remain?0，则令queue?0且转第8步产生下一位乘客

否则令limit=R且对于k?firstj到limit执行第12到17步。结束后

转第31步。

31) 调整排队乘客总数检验电梯的可乘用： queue?remain quecust?R?1 startque=arriveR?1 32) 转第20步。

第33步至36步计算早高峰电梯模拟的输出值： 33) 输出以下数值：

N?i?queue,所服务的乘客总数 DELTIME?DELTIMEN,平均运送时间 MAXDEL,一位乘客的最长运送时间 34) 输出一位乘客呆在电梯里的平均时间和最长时间：

ELEVTIME??

35) 输出在最长的队中等待的乘客数，等待的乘客呆在队中的平均

时间和最长时间：

QUELEN QUETIME?MAXQUE

limit?m?和 MAXELEV elevatorlimitm?1QUETIME

quetotal36) 输出每一部电梯停止的总次数和每部电梯运行时间的百分比：

operatek 对于k=1到4:显示stopk和5100

停止

注：按照A First Course in Mathematical Modeling书中电梯模拟系统的算法15次独立模拟的结果，得到了一张代表3周的早高峰时间表，见附录表1。

20

第三章 电梯调度的优化方案

3.1 电梯调度问题的分析

高楼中电梯的数量和质量是在建楼初期根据高楼的功能以及预计进出楼的人流大小来设计和确定的，在高楼的使用中很难进行改造。然而在楼的后期使用中，实际交通流量可能会跟预先设计时的估计值有较大的不同，也许会大大超出预先设计的容量。此时，如何合理的调控使用现有电梯，以提高电梯的服务效率，尽量减少人流的乘梯等待时间和乘梯时间等，就成为电梯管理中的首要任务。

在电梯的控制管理中最常见的是电梯不分区使用和分区使用这两种情况。所谓不分区使用是指每一部电梯都可以响应所有楼层的使用要求，可以在大楼的每一层上下客。本文的电梯模拟算法就是采用不分区的方法设计的。

要提高电梯的使用效率，达到优化就要考虑分区的效果。分区调度是电梯群控的常见控制方法。图6表示的就是一个分成三个区的电梯系统，途中灰色区域表示的电梯直达不停靠的楼层，白色表示电梯服务的楼层。分区是根据电梯台数和建筑物层数将电梯划分为几个运行区域，各部电梯仅响应本分区内的使用要求。

21

图6 电梯分区示意图

3.2 电梯调度的方案

根据调查，我们得到以下数据：在7:45到8:00和8:45到9:00这两段时间里，乘客乘坐电梯是最拥挤的状态，这也完全符合实际的情况。 新的概念说明：

时区：把7:45到9:10按一刻钟的时间划分时区，即 7:45到8:00 为1时区 8:00到8:15 为2时区 8:15到8:30 为3时区 8:30到8:45 为4时区 8:45到9:00 为5时区

9:00到9:10 为6时区 在1、5时区(也就是忙时)分区。

当对电梯系统采用分区域进行调度时，我们必须确定合适的分区点。在把大楼分成两个区、每个区两部电梯时，采用穷举的方法可以很快的确定出分区点。而当把大楼分成四个区或更多的区，虽然分区点的确定同样可以采用穷举法的方法来确定，但是当楼层数比较多时，计算量和工作量比较大，对于该写字楼，我们采用动态规划的方法来确定分区点。

使用动态规划必须满足Bellman等人提出的最优化原理，该原理指出：“一个过程的最优策略具有这样的性质：即无论初始状态和初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略。”动态规划求解关

22

键路径并不需要搜索所有路径，只要满足状态的无后效性，就可以只计算各阶段的关键路径，最终计算出全局的最优路径。

对该写字楼使用的4部电梯，我将分4个区来进行更有效的优化调度。如图7所示：

B 1 C 2 D 3 2 开始0 3 3 4 结束19 4 5 16 S0 S1 17 S2 19 S3 S4

图7

按电梯上高峰动态分区的空间特征即区域特征来划分动态规划的阶段，每一个区域为一个阶段。每一个阶段可分配的最低楼层到最高楼层的楼层数是这个动态规划模型的状态。如果将4部电梯分为4个区，设起始楼层为0，用字母A表示，最高楼层为19，用字母E表示。从A到E分为四个阶段，用字母k来表示阶段变量，于是从A到E可分为：A~B，B~C，C~D和D~E四个阶段，即k=1,2,3,4。每一个阶段代表一个分区，令Sk为已经决定的第k(k=1,2,3,4)阶段所取的状态，对于分区而言，第k阶段代表的分区区间为[Sk+1，Sk+1].例如当S1=1,S2=3,S3=5时，则对应的楼层分区为第1层、第2层到第3层、第4层到第5层以及第6层到最高层（第19层）这样的四个分区。 为求得动态规划的最优策略，确定以整个电梯系统的平均逗留时间尽量少作为优化的目标函数，并以图7中的各连线来表示某乘客去该阶段所代表的分区区间所需要的平均逗留时间和乘客目的楼层在该区间内的概率的乘积，例如，从A0到

31?，其中W(3,1)表示分区中最低楼层为第1层且含有B3的连线可取值为W?3，193P?11nr?1rINTW?tp???xl?2Sr?1l?02求出的去该楼层分区的乘客的平3层楼时根据

23

均逗留时间，其他与此相同；B1到A5的连线可取值为状态i到状态j的连线取值为

4W?4，2?。一般地，从19j?iW?j?i,i?1?，此外的m表示整栋楼所具有的楼m层数。于是该动态规划问题就转换成了著名的最短路径问题。我们可以采用Dijkstra算法求得最短路径和对应的分区区间。于是，我们可与给出该写字楼的优化调度方案的动态规划算法：

第一步，画出与图7相似的动态规划图形。

第二步，计算出图形中每条线段的长度。如果线段是从楼层i到楼层j的，那么

j?iW?j?i,i?1?，W?j?i,i?1?表示分区的最低楼层为第i+1该线段长度取值为m3P?11nr?1rINTW?tp???xl?2Sr?1l?02求出的去该楼层，且该分区共有j-i层楼时，根据

层分区的乘客的平均逗留时间。

第三步，求解最短路径问题；这里采用Dijkstra算法，求得最短路径和对应的分区区间。

Dijkstra算法的C语言描述：

Void ShortestPath.DIJ(MGraph G , int v0 , PathMatrix &P, ShortPathTable &D){

∥用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及其带权长度D[v]。

∥若P[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点。 ∥final[v]为TRUE当且仅当v?S，即已经求得从v0到v的最短路径。 For(v=0;v

Final[v]=FALSE;D[v]=G.arcs[v0][v];

For(w=0;w

D[v0]=0;final[v0]=TRUE; ∥初始化，v0顶点属于S集 ∥开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集 For(i=1;i

min=INFINITY; ∥当前所知离v0顶点的最近距离

for(w=0;w

if(!final[w]) ∥w顶点在V-S中 if(D[w]

final[v]=TRUE; ∥离v0顶点最近的v加入S集

24

for(w=0;w

if(!final[w]&&(min+G.arcs[v][w])){ ∥修改D[w]和P[w]，w?V?S D[w]=min+G.arcs[v][w];

P[w]=P[v];P[w][w]=TRUE; ∥ P[w]=P[v]+[w] }∥if }∥for

}∥ShortestPath.DIJ

第四章 模型的推广

①在当地一座有4部电梯的4到12层的居民楼，收集高峰时（如早高峰）乘客到达间隔（可能的话，还有到达楼层）的数据，并且根据数据（构造累积直方图）建立到达间隔和到达楼层的子模型。最后也可以得到附录表1那样的结果。

②对于大型商场，我们可以根据该算法，在多方采集数据的情况下，更好地设计调度方案。比如：我们可以连续二或三天进行调查，在全天的运营调查中，调查每位乘客的目的地楼层；调查节假日的客流情况。

第五章 模型的评价

25

5.1模型的优点

① 本文在建立算法之前考虑到了电梯在运行过程中的速度曲线，进而求出每次因停靠而额外花费的时间，通过模拟电梯算法得到的数据具有一定的真实性。 ② 提出时区的概念，然后通过时区对电梯进行分区设置，从而大大提高了电梯的运行效率。

③ 在电梯的优化调度方案中，利用动态规划算法求解分区点的方法，具有一定的严密性和实用性。

5.2模型的不足

① 在电梯模拟中为了表示的方便仅当下一位乘客到达大厅时才调整时钟TIME，因此TIME不是每秒都在变动的真正时钟。当已经形成排队，下一位乘客到达之前一部电梯在第20步回到大厅是可能的，而直到那位顾客真正到来，可乘用的电梯的承运才开始，于是呆在队中的等待时间会稍微偏大一点。 ② 本文中模拟电梯的算法中忽略了电梯的加速运行速度，并对其做了一个假设（即楼层间的运行时间为2秒），而只考虑了电梯每次停靠所带来的额外时间，

26

参考文献

[1]Frank R.Giordano.Maurice D.Weir,William P.Fox . A First Course in Mathematical Modeling . Third Edition 北京：机械工业出版社 . 2005:171 [2]杨启帆 . 数学建模案例集 . 北京：高等教育出版社 . 2006:152 [3]董臻圃 . 数学建模方法与实践 . 北京：国防工业出版社 . 2006:78

[4]严蔚敏 . 吴伟民 . 数据结构（C语言版）. 北京：清华大学出版社 . 2006:189

27

致谢

特别感谢黄老师在本篇论文中的指导，在此祝愿黄老师身体健康，工作顺利。

附录

表1 连续15天电梯模拟的结果

模拟序号

所服务的乘客平均运送最长运在电梯里送时间 的平均时28

在电梯里的最长时在最长队中的乘客在队中的平均在队中的最长时间

数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 平均值（四舍五入） 328 322 309 331 320 313 328 312 329 314 317 341 318 319 323 322 时间 147 139 146 153 138 147 143 137 153 136 140 147 412 385 404 405 341 377 325 344 396 345 356 386 146 409 149 371 间 89 88 87 89 87 91 88 86 87 88 85 90 80 88 91 间 208 211 201 205 208 211 195 198 208 205 202 211 208 208 218 数 12 18 12 13 15 13 10 12 11 9 10 18 11 13 15 时间 40 43 37 42 48 45 35 46 37 35 38 45 36 33 39 166 176 161 149 178 146 120 163 155 128 129 177 140 135 166 139 352 144 374 88 206 13 40 153 每部电梯停 止的总次数 1 2 67 74 62 72 72 69 59 69 58 65 76 62 61 69 52 62 66 60 63 68 每部电梯运行总 时间的百分比 1 2 84 88 85 85 86 85 86 87 80 83 82 78 82 81 82 86 84 3 56 52 61 68 58 72 70 61 70 57 4 52 61 62 44 58 47 61 43 57 65 3 80 78 80 87 80 82 84 81 82 78 4 75 77 80 73 74 74 82 73 78 83 82 86 83 29

64 83 58 64 76 67 75 63 64 67 64 65 64 63 63 58 70 63 56 53 55 65 54 56 86 87 91 84 86 86 85 82 82 83 81 83 81 78 83 82 87 82 77 77 73 81 76 77

30

本文来源：https://www.bwwdw.com/article/eszo.html