Java离散事件仿真：摩天大楼电梯调度算法与状态机实践

简介《ElevatorSimulation摩天大楼电梯类型及算法仿真》是一份面向Java学习者与电梯调度算法入门者的项目源码包围绕摩天大楼场景梳理单向、双向、观光、高速及消防电梯等类型并以先来先服务、最近楼层优先、最少行程时间、预调度和群控等策略为线索帮助读者理解电梯、呼叫、客流生成、调度器与建筑环境之间的协作关系。资源包共75个文件以25个Java源文件为核心配合13个XML配置及若干偏好、数据、日志和说明文件压缩包约70KB体量轻便便于在本地导入IDE后阅读、运行和二次修改。目前已有403人学习适合用于课程设计、毕业设计原型或Java面向对象与调度算法练习读者可从中获得较完整的项目结构、类职责划分和模拟实验思路并据此比较不同调度策略在等待时间与运行效率上的表现。1. 摩天大楼电梯仿真为什么“最快到达”反而让平均等待更糟摩天大楼电梯仿真的反直觉结论是把“最近的一台轿厢”派给新请求短时看很快整栋楼的均值却常常更差。Java 写的调度算法如果只按距离排序会把同向长走廊切碎制造频繁反转和空驶。这个机制值得搞懂因为它把电梯类型、请求队列、状态机和统计指标串成一个可验证的黑匣子你改一行排序规则等待时间尾部、能耗代理和吞吐会一起变化。搞清底层才知道仿真不是动画而是调度策略的实验台。2. 电梯类型与状态机从单轿厢到目的楼层调度怎么建模摩天大楼电梯仿真先要回答一个建模问题你到底在仿“一部电梯”还是在仿“一组电梯如何分配乘客”。单轿厢的状态机只关心楼层、方向、门和负载群控系统还要维护厅外请求队列、分区规则、目的楼层分配表。Java 工程如果把这些概念混在一个类里后面换调度算法就会牵一发动全身。我一般会先把“物理轿厢”和“调度决策”拆开轿厢只接受“去某层接人/放人”的指令调度器只决定谁去接哪个请求。这样 SCAN、LOOK、目的楼层调度才能在同一套事件循环里替换。2.1 摩天大楼里常见的电梯类型与适用边界摩天大楼里的电梯不是按“载重”随便分类而是按服务模式和停站策略分类。乘客电梯最常见按厅外上下呼梯分配轿厢货梯通常独立井道停站少但开关门和装卸时间更长消防电梯在仿真里一般作为独立服务通道不参与普通群控评分双层轿厢把奇偶层绑定减少停站次数但要求楼层客流成对出现目的楼层电梯让乘客在厅外先选目标层系统直接分配轿厢并给出停站序列。不同类型对应不同的状态机约束不能只改一个“容量”参数就假装切换了类型。乘客电梯的核心是“厅外请求 轿厢内选层”两套队列。厅外请求带方向因为同一个人向上和向下的服务成本不同轿厢内选层不带方向只表示必须停靠。货梯更接近“按任务批次运输”调度时通常把装卸时间作为大常量避免频繁开关门。目的楼层调度把厅外请求从“上下方向”升级为“目标楼层”分配时就能提前拼车减少中间停站。分区调度则把楼层切成低区、高区、穿梭区用换乘把长行程截短。每种类型都有适用边界目的楼层适合客流集中、楼层高的塔楼分区适合超高层但会增加换乘等待。提示仿真里切换电梯类型时先改请求对象和停站规则再改调度器。只改调度器而不改请求生命周期指标会失真。2.2 轿厢状态机的四元组与请求生命周期我习惯把轿厢状态压成四元组当前位置、运行方向、门状态、负载与任务集合。位置是离散楼层方向是 UP/DOWN/IDLE门状态至少包含 CLOSED/OPENING/OPEN/CLOSING任务集合分“已分配但未接”和“已上车待送”。请求生命周期则是厅外生成 → 进入等待队列 → 被调度器分配给某台轿厢 → 轿厢到达并开门 → 乘客上车或放弃 → 轿厢内选层 → 到达目标层下客 → 请求完成。这个生命周期里最容易出错的是“已分配但未接”阶段请求既不能重复分配给第二台轿厢也不能在轿厢满员时被静默丢弃。状态机的推进不能靠“每一帧改一点”而要靠事件到达楼层事件、开门完成事件、上客完成事件、关门完成事件。每次事件只做合法转移例如 CLOSED 只能到 OPENINGOPEN 才能上客。方向也不是随时可反转LOOK 算法要求轿厢在当前方向没有更远请求时才反向否则会出现“抖动”——刚向上走一层又向下等待时间尾部被拉长。把方向反转写成显式条件比在调度器里散落 if 更容易排查。2.3 用 Java 枚举和不可变请求对象固化状态下面这段 Java 代码把方向、门状态和厅外请求固化成枚举与不可变对象。不可变请求的好处是调度器可以安全地把它放进多个候选集合做比较而不会被某个算法中途改掉方向或时间戳。轿厢状态保持可变但约定只在事件循环线程里改避免为了仿真引入不必要的锁。enum Direction { UP, DOWN, IDLE } enum DoorState { CLOSED, OPENING, OPEN, CLOSING } final class HallCall { final long id; // 请求唯一标识用于去重和统计 final int floor; // 厅外呼叫楼层 final Direction dir; // 乘客意图方向目的楼层调度可改为 targetFloor final long createdAt; // 仿真时钟毫秒用于等待时间统计 HallCall(long id, int floor, Direction dir, long createdAt) { this.id id; this.floor floor; this.dir dir; this.createdAt createdAt; } } final class CarState { int currentFloor 1; Direction direction Direction.IDLE; DoorState door DoorState.CLOSED; int load 0; // 当前载客数 final int capacity 21; // 仿真参数按电梯类型调整 final SetLong assigned new HashSet(); // 已分配未完成的厅外请求 final SetInteger carCalls new HashSet(); // 轿厢内选层 }HallCall.id是后续做重复分配检测的主键createdAt不要用系统时间必须用仿真时钟否则加速仿真时统计会漂移。CarState.capacity是策略参数不是物理常量货梯和乘客电梯要用不同值。assigned保存的是“已分配但未完成”的厅外请求完成或乘客放弃后才能移除。carCalls只存目标楼层不存方向因为轿厢内选层不区分上下。把这些字段定清楚后面实现 LOOK 的候选集过滤时就不会把“反向请求”误塞进同向队列。3. 调度算法SCAN、LOOK与群控分区到底在优化什么电梯调度算法的分歧不在“谁先来”而在“顺路服务能省多少停站”。FCFS 公平但轿厢容易来回跑SSTF 最近优先短时好看却会让远端请求饿死SCAN 像磁盘臂一样扫到端点再反向LOOK 则扫到最远请求就反向减少空驶。摩天大楼群控还要处理多台轿厢的分区与目的楼层分配。Java 实现里算法差异最终落在一个候选集排序和过滤规则上同向且在前方的请求优先反向请求要么等反向要么交给其他轿厢。3.1 从FCFS到LOOK扫描方向与顺路服务FCFS 按请求到达时间排队实现最简单但轿厢会在楼层之间来回跳。假设轿厢在 30 层向上先来了 5 层向下请求又来了 35 层向上请求FCFS 可能先向下跑把 35 层乘客的等待拉长。SSTF 按距离排序短时等待低但持续有近层请求时远端请求会被无限推迟形成饥饿。SCAN 要求轿厢沿当前方向走到端点再反向优点是方向稳定缺点是端点空驶。LOOK 是 SCAN 的实用变体当前方向没有更远请求就反向不强行走到端点。在仿真里LOOK 的关键不是“排序”而是“候选集过滤”。当轿厢向上时只把楼层大于等于当前位置且方向为 UP 的厅外请求放进候选集反向请求暂时不参与除非轿厢内没有任务且当前方向空闲。这个过滤条件把“顺路”写成了可验证的不变量。很多实现翻车是因为把反向请求也按距离排序结果轿厢刚过 20 层就接了一个 18 层向下请求方向反转同向乘客全被拖慢。3.2 目的楼层调度与分区调度把等待转嫁给换乘目的楼层调度把厅外“上下呼梯”改成“目标楼层”分配时就知道乘客要去哪可以提前拼车。它的收益来自减少停站同一台轿厢接到的乘客目标层接近停靠序列更短。代价是厅外等待可能变长因为系统要把乘客凑到同一台轿厢。仿真时必须统计“厅外等待”和“到达目的层总时间”两个指标只看前者会误判。目的楼层调度适合高层塔楼的高峰客流不适合目的层极度分散的场景。分区调度把楼层切给不同轿厢组低区、高区、穿梭区分开服务。它的收益是缩短单台轿厢的行程代价是跨区乘客要换乘。仿真里要显式建模换乘乘客到达换乘层后重新生成请求等待时间要累加。分区边界不能拍脑袋常见做法是按客流热力切或者让高层快梯只停少数层。群控系统还要防止“分区空转”低区轿厢闲着高区排队很长但请求不能跨区分配。这个约束要在调度器里写死否则指标会虚高。3.3 用Java优先队列实现方向感知的候选集下面这段 Java 代码用优先队列实现 LOOK 的候选集排序。distanceInDirection不是简单绝对值同向且在前方的请求距离小反向请求返回一个很大的哨兵值保证它们不会插队。队列里只放过滤后的请求排序规则再按距离和到达时间打破平局。ComparatorHallCall lookOrder(CarState car) { return (a, b) - { int da distanceInDirection(car, a); int db distanceInDirection(car, b); if (da ! db) return Integer.compare(da, db); return Long.compare(a.createdAt, b.createdAt); // 同距离先到先服务 }; } int distanceInDirection(CarState car, HallCall call) { if (car.direction Direction.UP) { if (call.dir ! Direction.UP || call.floor car.currentFloor) { return Integer.MAX_VALUE / 2; // 反向或已过楼层不插队 } return call.floor - car.currentFloor; } if (car.direction Direction.DOWN) { if (call.dir ! Direction.DOWN || call.floor car.currentFloor) { return Integer.MAX_VALUE / 2; } return car.currentFloor - call.floor; } return Math.abs(call.floor - car.currentFloor); // 空闲时按距离 } PriorityQueueHallCall candidates new PriorityQueue(lookOrder(car)); for (HallCall call : hallQueue) { if (distanceInDirection(car, call) Integer.MAX_VALUE / 2) { candidates.offer(call); } }lookOrder的比较器依赖car的当前方向所以每次方向变化后要重建队列或重新过滤不能长期缓存。distanceInDirection里的哨兵值Integer.MAX_VALUE / 2是为了避免加法溢出同时让反向请求排在最后如果你直接返回Integer.MAX_VALUE距离比较可能溢出。createdAt作为第二排序键保证同距离请求不会因为堆的不稳定顺序而随机漂移。候选集只放过滤后的同向请求candidates.poll()取出的就是下一个最顺路的停靠点。这个实现不处理容量满员时要在上客事件里拒绝并保留请求否则会出现“幽灵上客”。4. 仿真时钟与事件驱动为什么不能用sleep驱动电梯电梯仿真最常见的错误是用Thread.sleep让轿厢“一层一层走”。这样做看似直观实际上把仿真时间和真实时间绑死跑一天客流要等一天随机种子也无法复现事件顺序。离散事件仿真的做法是维护一个按时间排序的事件队列仿真时钟直接跳到下一个事件时间中间没有事件的时间段不消耗计算。电梯的到达、开门、上客、关门、下一层到达都是事件调度器只在事件之间做决策。Java 实现里事件队列通常是一个PriorityQueueEvent时间单位用毫秒随机到达用指数分布生成。4.1 离散事件仿真与仿真时钟推进离散事件仿真有两个核心变量当前仿真时间now和事件队列。每次从队列取出最早事件把now设为该事件时间然后执行事件处理。事件处理可能产生新事件比如“到达 10 层”会产生“开门开始”“开门完成”会产生“上客开始”。时钟推进不是固定的可能从 0 直接跳到 1200 毫秒再跳到 3500 毫秒。这样跑一小时客流只需要计算事件数量不需要等待真实时间。电梯仿真里事件类型至少包括请求到达、轿厢到达楼层、开门完成、上客完成、关门完成、下客完成。事件队列的排序必须稳定可复现。两个事件时间相同怎么办常见做法是给事件加一个单调递增的序列号时间相同按序列号排序。否则PriorityQueue在时间相等时顺序不确定同一随机种子跑两次指标会漂移。仿真时钟也不要混用System.currentTimeMillis()所有时间都从 0 开始统计指标用now - createdAt。如果要做实时动画可以在事件循环外做展示层插值但调度和统计必须走仿真时钟。4.2 Java事件循环和请求生成器下面这段 Java 代码给出事件循环和指数分布请求生成器的骨架。Event的time是仿真毫秒seq是同一时间的稳定排序键。请求生成器用固定种子保证同一份配置可以复现同一串客流。enum EventType { REQUEST_ARRIVAL, ARRIVE_FLOOR, DOOR_OPENED, BOARDED, DOOR_CLOSED, ALIGHTED } final class Event implements ComparableEvent { final long time; // 仿真时钟毫秒 final long seq; // 同一时间的稳定顺序 final EventType type; final long requestId; // 关联请求非请求事件可为 -1 final int carId; Event(long time, long seq, EventType type, long requestId, int carId) { this.time time; this.seq seq; this.type type; this.requestId requestId; this.carId carId; } public int compareTo(Event o) { int t Long.compare(time, o.time); return t ! 0 ? t : Long.compare(seq, o.seq); } } PriorityQueueEvent queue new PriorityQueue(); long now 0; long seq 0; Random rnd new Random(42L); double lambda 0.8; // 每秒到达率按楼层和时段调整 long nextArrival now (long)(-Math.log(1 - rnd.nextDouble()) / lambda * 1000); queue.add(new Event(nextArrival, seq, EventType.REQUEST_ARRIVAL, -1, -1)); while (!queue.isEmpty()) { Event e queue.poll(); now e.time; switch (e.type) { case REQUEST_ARRIVAL - { // 生成厅外请求再排下一次到达 } case ARRIVE_FLOOR - { // 到达楼层后触发开门事件 } case DOOR_OPENED - { // 上客/下客容量检查 } default - { } } }lambda是每秒平均到达请求数按楼层热力和时段调整指数分布的公式-ln(1-u)/lambda生成下一次到达间隔乘 1000 转成毫秒。seq保证同一毫秒的多个事件按产生顺序处理避免堆顺序不确定。requestId把事件和请求关联起来统计等待时间时可以直接从请求对象取createdAt。事件循环里不要做耗时计算调度决策要轻量否则仿真加速比会下降。ARRIVE_FLOOR只负责触发开门开门完成后再判断上下客这样容量和门状态不会互相踩。4.3 统计指标平均等待、长等待尾部、能耗代理仿真只报平均等待时间是不够的。电梯体验的痛点常在尾部95 分位等待、最大等待、超过阈值的请求比例。平均等待降了但尾部变长乘客感知可能更差。能耗代理也要统计常见做法是累计运行楼层数、开门次数、空驶楼层数不需要真实功率模型。吞吐用单位时间完成请求数表示和等待指标一起看避免调度器靠“少服务”刷低等待。目的楼层调度还要统计换乘等待和总到达时间否则会把等待转移当成优化。指标采集要绑定请求生命周期请求生成时记录createdAt上车时记录boardedAt到达目标层记录completedAt。厅外等待是boardedAt - createdAt总时间是completedAt - createdAt。如果请求被取消或超时要单独计数不能从分母里悄悄删掉。多轿厢仿真还要按轿厢统计空驶率否则某台轿厢被调度器冷落也看不出来。指标输出建议按场景分组上行高峰、下行高峰、交错客流、夜间低峰每组跑多个随机种子看均值和方差。5. 避坑与排查电梯仿真里最容易翻车的五件事电梯仿真的 bug 往往不报错只是指标悄悄变好或变坏。请求重复分配会让等待时间虚低方向抖动会让尾部变长容量被忽略会让吞吐虚高随机种子不固定会让对比实验失去意义死锁会让仿真提前停摆。下面五条是我在类似工程里踩过的坑每条按现象、原因、解决写方便对照排查。5.1 请求重复分配与“幽灵轿厢”现象同一厅外请求被两台轿厢同时接走统计里等待时间很短但乘客人数对不上或者某台轿厢到达后没人上车。原因通常是调度器每次扫描hallQueue都重新分配没有检查请求是否已经在某台轿厢的assigned集合里或者分配后没有从待分配队列移除只改了标志位。另一种情况是轿厢满员时把请求退回队列但旧轿厢的assigned没清理后续又分配一次。解决给每个HallCall一个唯一id维护全局assignedIndex分配时用putIfAbsent语义失败就跳过。请求完成、乘客放弃、超时才允许释放。写一个断言任意时刻sum(car.assigned.size()) hallQueue.size() totalActiveRequests。这个不变量能提前暴露“幽灵轿厢”。如果要做目的楼层调度还要检查同一乘客不能被拆成两个目标层请求。5.2 方向反转抖动与饥饿现象轿厢在相邻楼层之间反复反向平均等待没怎么降95 分位等待明显变长或者低楼层请求不断插队高楼层请求等了很久。原因常见于用绝对距离排序而没有方向过滤或者空闲时用“最近请求”导致远端饥饿。方向抖动还会让开门次数暴增能耗代理变差。解决LOOK 的候选集必须按当前方向过滤反向请求只在没有同向任务且轿厢空闲时参与。给每个请求加等待年龄超过阈值时提升优先级或允许跨方向救援但救援要记录日志避免变成隐性 SSTF。跑对照实验时单独看“方向反转次数”和“最长等待”这两个指标比平均值更敏感。5.3 容量与开关门时间被忽略现象仿真吞吐高得离谱轿厢载客数超过容量或者开门瞬间完成上下客等待时间被低估。原因通常是上客事件没有检查load capacity或者把开门、上客、关门压成一个瞬时事件。摩天大楼里开关门和乘客进出占用的时间不可忽略尤其货梯和高峰客流。解决把开门、上客、关门拆成独立事件上客按容量逐个或按批次处理满员时保留请求并记录“满载跳过”。开关门时间做成参数按电梯类型配置。统计里增加“满载跳过次数”和“开门次数”如果吞吐异常高先查这两个。5.4 随机种子与指标不可复现现象同一套调度算法跑两次平均等待差很多无法判断是算法改动还是随机波动。原因通常是请求生成用了未固定种子的Random或者事件队列在时间相同时顺序不稳定或者统计里混入了系统时间。多线程仿真还会让事件处理顺序漂移。解决固定随机种子事件加seq稳定排序所有时间用仿真时钟。对比实验至少跑 10 个种子报告均值和置信区间。调度器本身尽量单线程展示层可以另开线程。如果必须并发把随机数生成和事件队列放在单线程事件循环里工作线程只做纯计算。5.5 死锁满员轿厢与目的楼层队列互等现象仿真时间不再推进事件队列为空但还有未完成请求或者所有轿厢都满员停在某层厅外队列一直不减少。原因可能是目的楼层调度把所有乘客分配给同一台轿厢轿厢满员后无法上客而其他轿厢没有被分配也可能是换乘层请求互相等待形成环。解决加“无事件可推进”检测如果事件队列为空且活跃请求数大于 0输出当前轿厢状态和等待队列判定死锁。目的楼层分配要限制单轿厢的待接请求数超过阈值强制分给下一台。换乘场景要保证换乘层有独立服务能力。调试时打印每个请求的状态和所属轿厢死锁往往一眼能看出来。6. 设计取舍为什么没有“万能调度算法”以及怎么验证你的仿真电梯调度没有全局最优只有场景取舍。FCFS 公平但吞吐差SSTF 短时快但尾部长LOOK 方向稳定但端点可能空驶目的楼层减少停站但把等待转移到厅外分区缩短行程但增加换乘。下面这张表是我做方案对比时会填的矩阵指标不是绝对值而是同一客流下的相对变化。策略平均等待长等待尾部能耗代理实现复杂度适用场景FCFS较高较稳定较高低教学、基线对照SSTF短时低容易恶化高低低客流、单梯LOOK中等较好中等中常规群控基线目的楼层厅外可能高总时间较好较低高高层塔楼高峰分区区内低换乘层高低高超高层、分区明确验证时不要只跑随机客流。先构造极端场景全上行、全下行、上下交错、单层爆满、所有请求集中在远端、轿厢容量为 1、开关门时间为 0 和很大两档。极端场景能暴露方向抖动、饥饿和死锁。再做对照实验同一随机种子下只改一个参数记录均值、95 分位、最大等待、满载跳过次数和运行楼层数。如果平均等待降了但尾部涨了要判断目标场景更在意哪个。仿真结果要能复现配置文件、种子、调度器版本一起存档。从那以后我每次加新调度器都先把请求分配不变量写成断言再跑一遍极端场景才敢看均值曲线。希望帮到你。本文还有配套的精品资源点击获取