概述：
写作原由：
今天早上上班时候，等电梯等了快十分钟，故此猜想这个电梯运行的算法到底是啥，当年面试工作时候，给出笔试题也是有这个电梯算法的，故此需要坐下来慢慢想想。
随着高层建筑的增多，电梯作为连接各层的重要交通工具，其调度系统的效率直接影响到人们的日常生活和工作效率。一个优秀的电梯调度算法不仅能够减少乘客的等待时间，还能提高电梯系统的整体运行效率。本文将探讨如何通过实现一个基于优先级队列的电梯调度算法来优化电梯服务。
简单轮询算法（Round Robin）
在电梯系统中意味着电梯会按照固定的顺序访问每一层，不论该层是否有乘客请求。以下是一个用Java实现的简单轮询电梯调度算法的示例：
java
复制代码
public class RoundRobinElevator { private int currentFloor; // 当前电梯所在楼层 private final int topFloor; // 电梯系统的最高楼层 private final int bottomFloor; // 电梯系统的最底楼层 private boolean movingUp; // 电梯移动方向，true为向上，false为向下 public RoundRobinElevator(int bottomFloor, int topFloor) { this.bottomFloor = bottomFloor; this.topFloor = topFloor; this.currentFloor = bottomFloor; // 假设电梯初始在最底层 this.movingUp = true; // 初始向上移动 } // 电梯开始运行 public void startElevator() { while (true) { // 电梯持续运行 visitFloor(currentFloor); if (movingUp) { if (currentFloor < topFloor) { currentFloor++; } else { movingUp = false; // 到达顶层，改变方向 } } else { if (currentFloor > bottomFloor) { currentFloor--; } else { movingUp = true; // 到达底层，改变方向 } } // 模拟电梯在楼层间移动的时间 try { Thread.sleep(1000); } catch(InterruptedException e) { e.printStackTrace(); } } } // 电梯访问楼层 private void visitFloor(int floor) { System.out.println("电梯到达楼层: " + floor); // 在这里可以添加开门、关门的逻辑 // 以及乘客进出电梯的逻辑 } public static void main(String[] args) { RoundRobinElevator elevator = new RoundRobinElevator(1, 10); elevator.startElevator(); } }
电梯从最底层开始，逐层向上移动，直到顶层，然后改变方向向下移动，直到底层，如此循环。每到一层，就调用visitFloor方法模拟电梯到达该层的行为。这种实现是是最简单暴力的实现。
响应轮询
java
复制代码
import java.util.concurrent.ConcurrentLinkedQueue; import java.util.concurrent.atomic.AtomicBoolean; /** * @Author derek_smart * @Date 2024/6/5 9:01 * @Description * <p> 响应轮询 */ public class RealWorldElevator implements Runnable { //表示电梯当前所在的楼层 private int currentFloor; // 电梯可以到达的最高楼层。 private final int topFloor; // 一个 `AtomicBoolean` 实例，用于控制电梯运行的状态。由于它是原子操作，可以确保线程安全 private final AtomicBoolean running = new AtomicBoolean(true); // 一个线程安全的 `ConcurrentLinkedQueue` 队列，用于存储电梯的呼叫请求。 private final ConcurrentLinkedQueue<Integer> requests = new ConcurrentLinkedQueue<>(); public RealWorldElevator(int currentFloor, int topFloor) { this.currentFloor = currentFloor; this.topFloor = topFloor; } /** * 允许外部调用电梯到指定楼层。如果楼层在电梯服务范围内，请求会被添加到请求队列中 * @param floor */ public void callElevator(int floor) { if (floor >= 0 && floor <= topFloor) { requests.add(floor); } } /** * 允许外部停止电梯运行。它将 `running` 标志设置为 `false`， * 使得电梯在完成当前操作后停止运行。 */ public void stopElevator() { running.set(false); } @Override public void run() { while (running.get()) { //只要 `running` 为 `true`， // 电梯就会处理请求队列中的下一个请求。 if (!requests.isEmpty()) { Integer nextFloor = requests.poll(); moveToFloor(nextFloor); } // Sleep for a short time to simulate waiting for the next request try { Thread.sleep(500); } catch (InterruptedException e) { Thread.currentThread().interrupt(); } } } /** * 控制电梯移动到目标楼层的方法。它会逐层移动电梯，直到到达目标楼层，并在每层停留一段时间模拟乘客进出。 * @param destinationFloor */ private void moveToFloor(int destinationFloor) { while (currentFloor != destinationFloor && running.get()) { if (currentFloor < destinationFloor) { // Move up currentFloor++; } else { // Move down currentFloor--; } // Simulate the time it takes to move between floors try { Thread.sleep(1000); } catch (InterruptedException e) { Thread.currentThread().interrupt(); } System.out.println("Elevator is at floor: " + currentFloor); } // Simulate stopping at the floor if (running.get()) { openDoors(); // Simulate time for passengers to enter/exit try { Thread.sleep(3000); } catch (InterruptedException e) { Thread.currentThread().interrupt(); } closeDoors(); } } /** * 模拟电梯在楼层开门 */ private void openDoors() { System.out.println("Opening doors at floor: " + currentFloor); } /** * 模拟电梯在楼层关门。 */ private void closeDoors() { System.out.println("Closing doors at floor: " + currentFloor); } public static void main(String[] args) throws InterruptedException { RealWorldElevator elevator = new RealWorldElevator(0, 10); Thread elevatorThread = new Thread(elevator); elevatorThread.start(); // Simulate some calls to the elevator elevator.callElevator(3); elevator.callElevator(7); elevator.callElevator(5); // Allow the elevator to process the calls Thread.sleep(20000); // Stop the elevator elevator.stopElevator(); elevatorThread.join(); } }
创建了一个RealWorldElevator类，它实现了Runnable接口，使得电梯可以在自己的线程中运行。 电梯接受楼层的请求并将它们添加到一个线程安全的队列中。 当运行标志running为true时，电梯会处理队列中的请求，移动到相应的楼层，并模拟开关门以及乘客进出的时间。
使用了AtomicBoolean来控制电梯的运行状态，并提供了一个stopElevator方法来优雅地停止电梯。 电梯在移动到目标楼层时会检查running的状态，以确保在电梯被停止时能够立即响应。此外，通过捕获InterruptedException来正确处理线程中断。
优先级轮询：
在传统的电梯调度系统中，电梯可能会按照简单的先来先服务（FCFS）原则或是固定的轮询方式响应乘客的请求，这些方法在乘客流量较低时表现尚可，但在高峰时段或特殊情况下，可能无法高效地处理乘客的需求。为了解决这一问题，提出了一种高级电梯调度算法，该算法采用优先级队列来管理请求，根据请求的紧急程度和乘客的目的楼层智能地调度电梯。
java
复制代码
import java.util.PriorityQueue; import java.util.Comparator; import java.util.concurrent.atomic.AtomicBoolean; /** * @Author derek_smart * @Date 2024/6/5 9:41 * @Description * <p> 带优先级轮询 */ public class AdvancedElevator implements Runnable { private int currentFloor; private final int topFloor; private final AtomicBoolean running = new AtomicBoolean(true); private final PriorityQueue<ElevatorRequest> requestQueue; public AdvancedElevator(int currentFloor, int topFloor) { this.currentFloor = currentFloor; this.topFloor = topFloor; // Define the comparator for the priority queue based on priority and distance Comparator<ElevatorRequest> requestComparator = Comparator .comparingInt(ElevatorRequest::getPriority) .thenComparingInt(req -> Math.abs(req.getFloor() - currentFloor)); this.requestQueue = new PriorityQueue<>(requestComparator); } public void callElevator(int floor, int priority) { if (floor >= 0 && floor <= topFloor) { requestQueue.add(new ElevatorRequest(floor, priority)); } } public void stopElevator() { running.set(false); } @Override public void run() { while (running.get()) { ElevatorRequest nextRequest = requestQueue.poll(); if (nextRequest != null) { moveToFloor(nextRequest.getFloor()); } // Sleep for a short time to simulate waiting for the next request try { Thread.sleep(500); } catch (InterruptedException e) { Thread.currentThread().interrupt(); } } } // Existing methods: moveToFloor, openDoors, closeDoors private static class ElevatorRequest { private final int floor; private final int priority; public ElevatorRequest(int floor, int priority) { this.floor = floor; this.priority = priority; } public int getFloor() { return floor; } public int getPriority() { return priority; } } /** * 控制电梯移动到目标楼层的方法。它会逐层移动电梯，直到到达目标楼层，并在每层停留一段时间模拟乘客进出。 * @param destinationFloor */ private void moveToFloor(int destinationFloor) { while (currentFloor != destinationFloor && running.get()) { if (currentFloor < destinationFloor) { // Move up currentFloor++; } else { // Move down currentFloor--; } // Simulate the time it takes to move between floors try { Thread.sleep(1000); } catch (InterruptedException e) { Thread.currentThread().interrupt(); } System.out.println("Elevator is at floor: " + currentFloor); } // Simulate stopping at the floor if (running.get()) { openDoors(); // Simulate time for passengers to enter/exit try { Thread.sleep(3000); } catch (InterruptedException e) { Thread.currentThread().interrupt(); } closeDoors(); } } /** * 模拟电梯在楼层开门 */ private void openDoors() { System.out.println("Opening doors at floor: " + currentFloor); } /** * 模拟电梯在楼层关门。 */ private void closeDoors() { System.out.println("Closing doors at floor: " + currentFloor); } public static void main(String[] args) throws InterruptedException { AdvancedElevator elevator = new AdvancedElevator(0, 10); Thread elevatorThread = new Thread(elevator); elevatorThread.start(); // Simulate some calls to the elevator elevator.callElevator(3,3); elevator.callElevator(7,1); elevator.callElevator(5,10); // Allow the elevator to process the calls Thread.sleep(20000); // Stop the elevator elevator.stopElevator(); elevatorThread.join(); } }
首先定义了一个 ElevatorRequest 类来表示电梯的请求，它包含请求的楼层和一个优先级属性。优先级可以根据不同的标准来设定，例如乘客的特殊需求、请求发出的时间，或者是基于预测模型的高峰时段流量。接着，使用一个优先级队列 requestQueue 来存储和排序这些请求。队列中的请求会根据优先级以及与电梯当前楼层的距离进行排序，确保电梯总是首先响应最紧迫的请求。
电梯的运行逻辑被封装在 run 方法中，它会循环检查优先级队列，取出并处理最高优先级的请求。通过调用 moveToFloor 方法，电梯会移动到请求的楼层，并执行开门和关门操作。这个过程模拟了电梯响应请求并搭载乘客的行为。为了优雅地停止电梯，引入了一个原子布尔标志 running，它可以安全地控制电梯的启动和停止。
此外，为了应对高峰时段的乘客流量，可以进一步扩展此算法，结合历史数据和流量预测模型来动态调整请求的优先级。例如，在上班高峰时段，可以提高通往办公室楼层的请求优先级，而在下班高峰时段，则优先响应通往地面层的请求。
总结：
总结来说，通过实施基于优先级队列的电梯调度算法，可以显著提高电梯系统的响应速度和乘客满意度，特别是在高峰时段和紧急情况下。这种智能化的调度方法为现代建筑中的电梯运输提供了一种高效、可靠的解决方案。
