第三章 电梯调度的优化方案
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