使用 Python 实现电梯调度的核心算法【100010451】

> # ♻️ 资源 > **大小：** 1.33MB > **文档链接：**[**https://www.yuque.com/sxbn/ks/100010451**](https://www.yuque.com/sxbn/ks/100010451) > **➡️ 资源下载：**[**https://download.csdn.net/download/s1t16/87390787**](https://download.csdn.net/download/s1t16/87390787) > **注：更多内容可关注微信公众号【神仙别闹】，如当前文章或代码侵犯了您的权益，请私信作者删除！** >  # 工程概论 - 电梯调度模拟 ## 软件设计思路 ### 问题建模及基本假设 查阅18层大楼的层高和电梯速度，再结合便于软件开发的目的，不妨设电梯的速度为 0.5层/秒，且为匀速运动，没有加减速过程。 考虑到实际电梯容量和便于图形化的原因，不妨设电梯容量为12人。 考虑到进出电梯的人越多，电梯停留时间越长，不妨设为每秒钟电梯可以出一人或者进一人。 考虑到出现人群的分布不是均匀的，尤其在 1楼 有非常大的吞吐量，所以设置人群生成规则如下: - 25%的人群 : 1楼出发,到达 random(0,20) - 25%的人群 : random(0,20)出发,到达1楼 - 50%的人群 : random(0,20)出发 到达 random(0,20) 设人群的人数为 random(1,5) ### 技术选型 首先，在所有同学都已经有 C 和 Java 学习经验的基础上，最关键的技术瓶颈在于GUI层。经过交流，团队中只有一名同学掌握有 GUI 开发的经验，技术栈是 .NET 的 C# + WPF。 但是会 C# 的只有一人，如果承担了所有的开发工作就会导致效率低下，所以要将程序解耦为算法层和GUI层。后来算法同学决定使用 Python。因为程序的数据规模非常低，使用 Python 不会造成性能瓶颈，而且可以降低语言层面的复杂度。 算法层和GUI层之间的通信，一开始使用了命令行调用、标准输入输出的方式。算法层和GUI层定义了一致的数据结构，并且使用 JSON 进行数据传递。 但这种方式需要使用者也拥有 Python 环境，且该方式在非GUI开发者的电脑上出现异常，难以调试。所以决定转用 HTTP 协议，使用 Flask 对算法进行服务端的封装，再使用 Docker 部署在服务器上，对外提供API。这样使用者的电脑只需要 .NET Framework 环境就可以运行程序。此外，以后还可以使用 Web 端 / QT / Android / IOS 等不同前端技术及平台开发运行在不同操作系统上的前端程序。 ### 核心算法简介 该电梯调度算法主要基于 LOOK 调度算法。该算法按照楼层顺序依次服务请求，它让电梯在最底层和最顶层之间连续往返运行，在运行过程中响应处在于电梯运行方向相同的各楼层上的请求，当 LOOK 算法发现电梯所移动的方向上不再有请求时立即改变运行方向，从而实现对电梯的有效调度。 此外由于电梯1只停在单数层,电梯2只停在双数层,只有电梯3可以停在任意层。这个约束条件看似引入了新的复杂度，其实恰恰让三个电梯失去了联系，大大降低了复杂度。显然，只存在唯一一种调度分配情况，就是单数层到单数层的人由电梯1负责，双数层到双数层的人由电梯2负责，剩下由电梯3负责。3个电梯之间互不干扰，实现非常简便。在后续实践中，也验证了此调度分配情况可以基本完成负载均衡分配，效率高。 ### 基本数据类型定义 **person**：搭乘电梯的乘客。其属性包括：come_time（出现的时间）、from_floor（起始楼层）to_floor（目标楼层）、current_floor（当前楼层）、in_which_elevator（所在电梯,可取0，1，2，3，分别指不在电梯中、在第一个电梯中、在第二个电梯中、在第三个电梯中）、is_out（是否完成电梯乘坐） **elevator**：电梯。其属性包括：current_floor（当前楼层）、move_direction（运行方向） **floor**：楼层。其属性包括：floor_up_people = []（上行人群）、self.floor_down_people = []（下行人群）、up_button（上升按钮）、down_button（下降按钮） ### 算法伪代码 //已知第t秒时的状态,进行调度,给出t+1时的状态 时间循环（每循环一轮为一秒） //处理person到达事件 遍历person数组，如果p.come_time==t（该乘客首次出现） 将该乘客分配给对应的楼层 更新对应楼层电梯按钮 更新楼层people数组（分为上行人群和下行人群） //处理电梯 //对每个电梯，根据电梯的move_direction分类处理（move_direction取0，1，2，分别代表电梯静止、上行、下行） //（这一秒结束）代表continue，不再执行循环体剩下的部分 如果电梯静止 遍历所有楼层，检测楼层电梯按钮 如果楼上有人按电梯 电梯设置为上行（这一秒结束） 如果楼下有人按电梯 电梯设置为下行（这一秒结束） 如果本层楼有人 如果此人上行 电梯设置为上行（这一秒结束） 如果此人下行 电梯设置为下行（这一秒结束） 如果电梯上行 如果电梯没有对齐某一楼层（如在3.5层） 电梯向上运行半层 更新乘客状态（这一秒结束） 如果电梯对齐了某一楼层 如果电梯中有乘客抵达目标楼层 更新该乘客的状态（这一秒结束） 如果电梯人数已满 电梯向上运行半层 更新乘客状态（这一秒结束） 如果楼层有人要进电梯 更新人的状态 更新楼层的状态 如果楼层上行person数组为空 楼层上行按钮置False （这一秒结束） 如果电梯内人数不为零 向上半层，并且更新乘客状态（这一秒结束） 如果电梯内人数为零 如果电梯以上的楼层还有人 向上半层，并且更新乘客状态（这一秒结束） 如果电梯以上的楼层没有人 电梯状态改为静止（这一秒结束） //下行同理 //其余两个电梯同理 ## 软件功能 不管你是在北上广还是在港澳台，甚至三四线城市，凡是有规模的地区，高楼比比皆是。不管是写字楼，还是大型商城，让你最头痛的就是乘电梯，尤其是在赶时间的时候。 每天早上，那些差5分钟就迟到的人，在等电梯时，一般会做两件事： - 第一，在心里骂电梯慢 - 第二，在心里暗算着电梯调度如何优化 前者可能是写字楼里上班族惯有的精神类疾病，但后者肯定是程序员的职业病。为了上班~~不扣工资~~不迟到，我们决定通过调整电梯调度算法来实现对电梯运行载客的优化，以达到节约时间的目的。 本程序基于我们的电梯调度算法，计划使用三个电梯同时模拟各层楼随机出现人前往不同楼层来验证本算法的可靠性。并且为了使运行结果明显，本程序还增添了可视化界面，使测试人能够清晰明了的观察本程序的运行情况。 ## 运行结果 通过分析最终采用3个电梯，1号电梯只停奇数楼层和1楼，2号电梯只停偶数电梯和1楼，三号电梯所有楼层都停。经过多次测试，每次测试时长均超过10分钟，程序运行稳定，能够满足预想的最优化调度电梯，尽可能的缩短人员的等待时间，来实现效率最大化。 in.json 运行顺利，没有故障，对实际的电梯调度具有参考意义。 ## 结构框图 ![结构框图.png](https://cdn.nlark.com/yuque/0/2024/png/2469055/1711592583643-987427f5-e6fb-44ea-96cd-447ecec523ea.png#averageHue=%23424242&clientId=u17bd17ed-42dc-4&from=paste&height=757&id=u415d2178&originHeight=946&