[数学]电梯的调度问题m遗传算法A.doc

电梯调度问题电梯调度问题题目 商业中心某写字楼有二十二层地上建筑楼层和两层地下停车场，6部电梯，每部电梯最大载重是20个正常成人的体重总和工作里每天早晚高峰时期均是非常拥挤的，而且等待电梯的时间明显增加请你针对早晚高峰期的电梯调度问题建立数学模型，以期获得合理的优化方案1） 请给出若干合理的模型评价指标2） 暂不考虑该写字楼的地下部分，每层楼层的平均办公人数经过调查已知见表1.假设每楼层之间电梯的平均运行时间是3秒，最底层（地上一层）平均停留时间是20秒，其他各层若停留，则平均停留时间为10秒，电梯在各层的相应的停留时间内乘梯人员能够完成出入电梯请你针对这样的简化情况建立数学模型（列明你的假设），给出一个尽量最优的电梯调度方案，并利用所提评价指标进行比较3） 将你在第2问中所建立的数学模型进一步实际化，以期能尽量适用于实际情况，用于解决现实的电梯调度问题表1楼层人数楼层人数楼层人数1无9236172002208101391820031771127219200422212272202005180132722120161811427022207719115300823616261例文：摘要为了评价一个电梯群系统的运作效率，及运载能力，在第一问中，我们用层次分析发，从效益、成本两大方面给出了六个分立的小指标，一同构成电梯群运载效率的指标体系。

对第二问，本文根据题目情况的特殊性，定义忙期作为目标函数，对该电梯调度问题建立非线性规划模型，最后用遗传算法对模型求解第三问中，本文将模型回归实际，分析假设对模型结果的影响，给出改进方案对于问题一，本文用评价方法中的层次分析法对电梯群系统的运作效率及运载能力进行分析经分析，本文最终确定平均候梯时间、最长候梯时间、平均行程时间、平均运营人数（服务强度）、平均服务时间及停站次数这六个指标作为电梯调度的指标体系在这些评价指标的基础上，本文细化评价过程，给出完整的评价方案：首先，采用极差变换法对评价指标做无量纲化处理然后，采用综合评价法对模型进行评价在这个过程中，本文采用受人主观影响较小的夹角余弦法来确定权重系数对于第二问，本文建立非线性优化模型借鉴排队论的思想，本文定义忙期，构造了针对本题中特定情形的简单数学表达式，作为目标函数利用matlab软件，采用遗传算法对模型求解多次运行可得到多个结果，然后用第一问中的评价模型进行评价，最终选出较优方案最得到如下方案：第一个电梯可停层数为：1,2,3,4,5,6,7,10,14,15,16,19,20,22第二个电梯可停层数：1,4,5,7,10,13,16,18,19,20,21第三个电梯可停层数：1,2,3,4,6,8,10,11,12,15,16,20,22第四个电梯可停层数：1,2,3,4,7,10,11,17,18,19,21,22第五个电梯可停层数：1,2,4,7,8,9,17,18,19,20,21第六个电梯可停层数：1,4,5,6,7,8,9,11,13,18,19,20此方案平均忙期为：15.3分钟。

对于第三问，本文是从每分钟到达人群数的分布角度改进模型的第二问中假设在忙期，每分到达人数服从均匀分布，而在实际中，我们可以首先对此进行调查统计，跟据统计数据可以拟合出更符合实际分布函数，可以改进结果关键字：电梯调度；层次分析；极差法；夹角余弦一、 问题重述随着社会经济的持续发展，高层建筑的数量不断增加，其建设高度更令人瞩目，电梯也开始为高层建筑的垂直交通提供保障然而建筑高度的提升使电梯交通系统需求变得越来越复杂，有效的电梯垂直交通系统面临许多挑战其中，人们在要求减少电梯设备占用建筑物的核心空间的同时，要求电梯交通系统的服务数量和质量有大幅度提高特别在工作日里每天早晚上下班高峰期，电梯是非常拥挤的如何对现有资源合理利用，缓解电梯的运输压力，缩短人们的等待时间，是高层建筑垂直交通系统所必须解决的问题由此便产生了电梯的调度问题我们将针对对早晚高峰期的人流情况，对电梯调度问题建立数学模型，以期获得合理的优化方案本文考虑解决以下问题：1. 给出若干合理的模型评价指标2. 针对该特定写字楼的简化情况给出一个合理的调度方案3. 在第二问的基础上，将数学模型进一步实际化，以期能够尽量适用于实际情况，用于解决现实的电梯调度问题。

二、 问题分析(一) 问题一的分析为了实现电梯群系统的优化调度，本文分别从效益和成本两个方向出发，考虑该数学模型的评价指标效益即电梯的运输强度，成本即电梯运行的耗能量，其中耗能量可用平均行程来反映效益也可从多方面考虑：从服务质量的角度说，人们总是希望候梯时间与乘梯时间的总和越短越好；从服务数量的角度说，总是希望电梯交通系统具有最经济的电梯配置，同时能够提供较高的运送处理能力在寻找指标时，需要指标既有代表性，能反映系统的工作情况，又有易衡量性，容易通过调查统计来获得即使我们在评价模型时可以较为容易的得到评价指标数据便于人们得到评价结果因此，本文通过层次分析发，提出了多个评价指标，包括：平均候梯时间、最长候梯时间、平均行程时间、平均运营人数（服务强度）、平均服务时间及停站次数上述个指标的单位不尽相同，为统一评价指标的属性，本文采用极差法对各指标进行无量纲化处理指标权重的合理确定是综合评价结果是否可信的一个核心问题为减少主观影响，本文采用客观赋权值法——变异系数发得到权重系数最终建立了综合评价模型，对电梯调度模型进行评价二) 问题二的分析本题中，已给出每层楼间电梯的平均运行时间，电梯在各层的平均停留时间，各层办公人数，电梯的最大容量。

为了提高电梯的使用率，我们通过电梯的分组管理——每组的电梯只可在特定的楼层停留，不同组的可停层数不同来达到对电梯运行的时间的优化具体对每种方案，我们要确定如下三组数据：1. 分为几组；2. 每组有多少个电梯；3. 每组分别可达的楼层本问题非一般的线性优化模型，因此本题选用遗传算法求解第一问提供了多个评价指标，若综合考虑这些指标，则问题归结为一个多目标规划问题，情况就会较为复杂由于其中许多指标在该特定情况（针对早晚上下班高峰期的电梯运行情况）下的影响甚微，于是可以得到简化的规划模型如：服务时间每个人从进入电梯开始至到达目的楼层所需时间的可变行小从概率角度说，当乘电梯的人较多时，每一时刻电梯内人的目的楼层会基本覆盖所有电梯可达楼层，即可视为：电梯会在每个可达楼层停留所以，优化模型中可以不考虑此项指标平均行程时间针对早晚高峰期，人流方向是相当固定的例如：在上班高峰期，几乎所有人都是从一层进入，分别到达个各楼层，而中途只下不上因此个各电梯的运行路程都是从一层到达该电梯能到达的最高层再下来，如此做往复运动在特定的电梯分组方案中，该项指标的可变性也不大本文通过对各种可能影响因素的细致分析，分析各个指标的可能表达情况及影响因素，考虑考虑增大电梯单位时间的运载量，减少人们的等待时间是大家更为关注的问题，直接的想法为：从每个等待个体角度出发，以等待时间为目标函数。

但这种方法表达式复杂，不易在遗传算法里实现因此我们变换思路，从电梯角度出发，以电梯最大运载能力为目标，针对本题——当人流蜂拥而至时，我们选取将所有人全部运到目的楼层电梯组所需的总时间为目标函数，并作为适应值函数，在遗传算法中作为选择算子进行计算三) 对问题三的分析在问题二中的模型中用了一些假设使得模型与实际有写偏差本文的视角不同也会对模型的对实际情况的拟合度有影响在第三问中，我们将根据第二问的运行结果，结合实际，改进模型三、 模型假设1. 假设人们均在特点时间段达到，并在该时间中，每时刻到达人数服从均匀分布；2. 假设每层楼之间电梯的平均运行时间是3秒，最底层(地上一层)平均停留时间是20秒，其他各层若停留，则平均停留时间为10秒，电梯在各层的相应的停留时间内乘梯人员能够完成出入电梯；3. 假设各层人员都乘坐电梯，并对电梯无偏见；4. 假设人们都在忙期到达，忙期内到达人数服从均匀分布；5. 假设每个电梯在运行时都满载四、 定义与符号说明Т等待时间N停站次数（第一项评价指标）平均服务时间（第二项评价指标）R平均运营人数（第三项评价指标）Тr平均运行时间（第四项评价指标）Тm最长等待时间（第五项评价指标）Т平均等待时间（第六项评价指标）表示第i种方案关于第j项评价因素的指标值 =是第i个方案关于这六项评价指标的指标值向量为n个决策方案的集合第个指标的综合评价得分k第k个电梯l第l层第l层办公人数第k个电梯完成总目标的运行次数第k个电梯在l层的停留情况为第k个电梯的运行模式为这六个电梯组的运行模式，及电梯组的调度情况W电梯群的忙期的长短电梯的平均忙期第k个电梯单次运行时在楼层停留时间第k个电梯单次运行时在楼层间行进时间表示第k个电梯在忙期运行次数:第k个电梯单次运行时间五、 模型的建立与求解(一) 问题一 电梯调度的评价模型1) 用层次分析法[1]寻找评价指标。

对模型进行评价首先要找出合理的评价指标因此我们采用层次分析法，对模型全面分析，寻找评价指标对此，我们分别从效益、成本两个方面出发，建立了如下层次图，如图一：图中，从左至又，分别表示第j项评价因素，其中j=1,2,3,4,5,6表示第i种方案关于第j项评价因素的指标值 =是底i个方案关于这六项评价指标的指标值向量为n个决策方案的集合2) 运用极差变换法[2]建立无量纲的效益型矩阵B变换公式为：3) 计算评价指标的权重运用夹角余弦法[3]由矩阵B来确定各指标的权重夹角余弦法的基本概念：由无量纲的效益矩阵，则可得到各方案与理想最佳和最劣的相对偏差矩阵为：式中，，，再计算U，V对应列向量的夹角余弦得到初始权重，归一化后得到客观性权向量运用夹角余弦法建立客观性权重向量首先由指标矩阵A得到各方案与理想最佳和最劣方案的相对偏差矩阵R与矩阵T，然后求出R与T两矩阵对应列向量的夹角余弦，并最为初始权重，归一化后得到客观性权向量.4) 计算综合评价值由矩阵B可得到第个指标的综合评价得分，且值越大越好用matlab编程，对给定的评价矩阵可以直接计算出结果程序见附录：(二) 问题二 电梯调度的优化模型1. 建立优化模型。

通过分析，本文首先对电梯调度方案进行量化，即要表达出电梯分组情况和每组电梯可停留楼层的情况因此我们用六个向量分别表示各个电梯可停留楼层的情况，具体如下：我们用0-1变量表示第k个电梯在l层停留情况为第k个电梯的运行模式；为这六个电梯组的运行模式，及电梯组的调度情况；在早晚人流高峰期时，常常会造成人流拥堵，即会在某个连续的时间段内，等待接受服务的人数大于电梯所能提供服务的最大人数，这就使部分人不能及时接受到服务，引用排队论里的说法就是队长超过了一定的限额在这段时间内，电梯每次都应是最高效率工作，对上班高峰期来说，就是每次会在第一层满载后再上楼，对下班高峰期来说，就是电梯下到第一层是满载情况本文定义此段时间为忙期因此本文选取忙期的长短作为衡量电梯运行的效率的指标，以此来作为目标函数，对电梯群的调度情况进行优化电梯群的调度情况用一个矩阵来表示，即。