多路电梯调度算法(二)

输入：乘客请求事件，所有电梯状态 输出：电梯命令 其中， 电梯状态电梯状态电梯命令电梯命令乘客请求事件乘客请求事件 最高层数添加电梯停时响应事件X 楼上行请求 剩余负载取消电梯停时响应事件X 楼下行请求 运行方向（上、下、静止） E 电梯内有乘客请求去 Y 楼 能否到达 X 楼开往 X 楼 开往（静止时：上、下）设置开往方向（上、下） 算法思想算法思想 一、统计每层楼的“剩余负载”变化情况 如果 0、1 层“剩余负载”的平均增量大于其它楼层，则是下班 如果 0、1 层“剩余负载”的平均增量小于其它楼层，则是上班 二、流程： a. 电梯按环形路线运行，向上至顶，再向下至底，再向上至顶，。 b. 电梯停时，按 a 从近向远扫描，如果在某一站，有必要停的话（参考 c,d），就开往那一站。 c. 如果有乘客请求在 E 电梯的 X 层停，则标志 E 电梯需要在 X 层停。 d. 如果有乘客请求上/下行， 下班时，标志一个电梯需要在那停。 上班时，标志所有电梯都需在那停。 e. 如果 c、d 发生，执行 b 算法很简单，但模式识别思想很赞。 算法很粗糙，可以有很多优化。比如， 上班时，环形路线并不是最佳的，我们已经证明内线、外线的模式更佳。即是说，适当的时候可以拒绝去 高层的请求。 下班时，如何选择电梯 来响应乘客上/下行的请求。我们的方案很粗糙： 电梯 ID=楼层*电梯总数/(楼 层高度+1)。 更精细的方案是考虑电梯的“剩余负载”，或者更精细地根据楼层远近绑定电梯和楼层。 但因为时间关系没有实现他们。有兴趣的读者可以尝试。 相关工作相关工作 按钮按钮 为了过滤重复请求，我们引入了“Button”（这更应该在电梯中实现） IButton -Press（ID） -UnPress（ID） -IsPressed（ID） -NotPressed（ID） 每个电梯有个 Button，记录需要停的楼层 四个电梯共享一个 Button，记录上行、下行的情况。 最佳算法最佳算法 在没有新的外部请求的情况下，我们找得到了最佳调度算法 （动态规划法） 目标：让电梯里的人为零 转移：电梯在任何状态下，只有两种选择，上行一层，或下行一层。这两个新的状态是当前状态的子问题。 新状态下，电梯里的人可能减少。 合并：如果当前在同一个楼层，并且电梯递里的乘客一样，则可以合并状态，取离开乘客平均等待时间最 少的那个状态。 可以证明，每一层，只有 N 种状态，于是，总共只有 N*N 种状态。算法有效 但是电梯外部请求是不确定的，所以不存在最佳调度算法。于是，我们转向模式识别。 模式识别模式识别 实际上，电梯的外部请求有两种极端情况， 上班时，大量乘客从一楼和地下一层进电梯 下班时，大量乘客从一楼或地下一层出电梯 这两种情况下最佳调度方式不太可能一样，所以上/下班的信息对调度会有很大帮助 我们可以从 每一层的“剩余负载”变化，即每一层多少重量的人进出， 提取出上/下班信息。 “剩余负载”更新是离散的，而且有毛刺。为了让上/下班信息稳定，我们增加了移动平均滤波器。 移动平均滤器如此有用，以至于我一定要把代码贴出来。 RateMeasurer 如果一楼和地下一层进的人很多，无疑是上班模式； 如果一楼和地下一层出的人很多，无疑是下班模式。 测试框架测试框架 电梯系统还包括 电梯、乘客和楼。这部分工作由 Sen Xiang 完成。简单介绍下 楼是顶层对象，包括一些电梯、一个调度器和一个计时器。 初始化后，计时器开始计时， 乘客： 如果时间和乘客到达时间一致，乘客状态变为等待，并发送上/下行请求。 如果电梯停在乘客所在楼层，并且开往方向与乘客的去向一致，则乘客进入电梯，乘客状态变为正在电梯 中，并发送目的