掘金 后端 ( ) • 2024-06-18 08:18
优化电梯调度5：Java多线程与目的地调度算法的融合
多线程 电梯 目的地 算法

概述：

目前所住的房子总楼层34层，且有4个电梯。故此，这边根据基于目的地调度算法进行最后版本的实现，真正解决现实遇到问题。基于前几篇文章描述电梯算法调度，其并不能真正满足现实生活中所遇到情况，故此这边将引入强大的算法-目的地调度算法进行实现。

在这篇文章中，将探讨如何使用Java编程语言实现一个基于目的地调度算法的电梯调度系统，并讨论其优化策略。

引言

目的地调度算法（Destination Dispatch Algorithm）是一种高级电梯调度实现技术，根据输入的目的地楼层信息来优化电梯的分配和运行路线。跟传统的电梯系统相比，目的地调度算法能够提高电梯的运行效率，进一步减少乘客的等待和运行时间，从而提升整体的能源效率。

输入收集

在电梯大厅或通过智能设备，乘客在进入电梯前输入或选择他们的目的地楼层。这些信息被发送到电梯调度中心。

电梯分配

调度系统接收到目的地信息后，使用一系列算法来决定哪部电梯最适合响应该请求。分配算法可能考虑以下因素：

  • 当前电梯位置：距离请求楼层最近的电梯可能会被优先考虑。
  • 电梯运行方向：运行方向与请求方向一致的电梯更适合响应，以减少中途停靠。
  • 电梯负载情况：避免将请求分配给已经满载或接近满载的电梯。
  • 电梯运行状态：考虑电梯是否在运行中，以及是否已经有排队的目的地请求。
  • 等待时间：预估乘客的等待时间，优先分配能够最快到达的电梯。

电梯运行优化

在电梯开始运行后，调度系统会继续优化电梯的运行路线。这可能包括：

  • 合并行程：如果多名乘客选择了相同或相近的楼层，电梯会合并这些请求以减少停靠次数。
  • 顺路处理：电梯在前往较远目的地的途中，会尽可能地顺路服务其他楼层的请求。
  • 动态调整：电梯运行过程中，调度系统会根据新的请求信息动态调整电梯的行程。

用户反馈

乘客在电梯内部也会看到他们的目的地楼层已被注册，以及预计的到达时间。

系统学习和适应

现代的目的地调度系统通常包含学习和适应功能，它们能够分析乘客使用模式，并调整调度策略以适应建筑物的特定需求，如高峰时段的乘客流量。

优势

目的地调度算法的优势在于：

  • 效率提升：减少了电梯的停靠次数，提高了运行效率。
  • 节能：通过优化路线，减少了不必要的电梯移动，节约了能源。
  • 乘客体验：减少了乘客的等待时间和乘坐时间，提升了整体体验。
  • 减少等待时间：系统通过优化电梯运行计划，减少了乘客的平均等待时间。

实现挑战

实现目的地调度算法的挑战包括：

  • 算法复杂性：需要开发复杂的算法来实时处理多个变量和优化决策。
  • 用户习惯：用户可能需要时间适应这种新的电梯操作方式。
  • 系统成本：升级到目的地调度系统可能涉及显著的硬件和软件成本。
  • 故障时影响大：系统故障可能导致整个电梯群停止服务，影响更加广泛。

目的地调度算法是电梯技术领域中的一项重要创新，它通过智能化的调度策略，显著提升了电梯系统的效率和用户满意度。随着技术的不断进步，这种系统将变得更加普及和高效。

电梯调度系统的设计

在此次的设计中，电梯调度系统由两个主要的类组成：Elevator 和 ElevatorScheduler。Elevator 类代表单个电梯，负责处理移动和开关门等基本操作；而 ElevatorScheduler 类则负责管理整个电梯群，并根据乘客的请求来分配最合适的电梯。

Elevator 类的实现

import lombok.SneakyThrows;

import java.util.*;
import java.util.concurrent.locks.ReentrantLock;

/**
 * @Author derek_smart
 * @Date 2024/6/7 11:41
 * @Description 电梯类
 */
class Elevator implements Runnable {
    // 新增属性，表示电梯是否正在移动以及移动方向
    private boolean isMoving;
    int currentFloor; // 当前楼层
    boolean movingUp; // 是否向上移动
    TreeSet<Integer> destinations; // 目的地楼层集合
    private String name;// 电梯的名称，用于区分不同的电梯。
    private ReentrantLock lock = new ReentrantLock(); // 用于并发控制的锁
    /**
     * 初始化电梯，设置起始楼层和电梯编号。
     * @param startingFloor
     * @param i
     */
    public Elevator(int startingFloor,int i) {
        this.currentFloor = startingFloor;
        this.movingUp = true; // 默认向上移动
        this.destinations = new TreeSet<>();
        name ="电梯：" +(i+1)+"号 ";
    }

    // 更新移动状态的方法
    public void setMoving(boolean isMoving) {
        lock.lock();
        try {
            this.isMoving = isMoving;
        } finally {
            lock.unlock();
        }
    }
    // 添加目的地楼层
    public void addDestination(int floor) {
        destinations.add(floor);
    }

    // 新增方法，获取电梯状态
    public boolean isMoving() {
        return isMoving;
    }

    public boolean isMovingUp() {
        return movingUp;
    }

    public int getCurrentFloor() {
        return currentFloor;
    }

    // 处理所有请求
    public void serveRequests() throws InterruptedException {
        while (!destinations.isEmpty()) {
            setMoving(true);

            // 根据移动方向获取下一个目的地楼层
            Integer nextFloor = movingUp ? destinations.ceiling(currentFloor) : destinations.floor(currentFloor);

            // 如果没有更多的楼层可以服务，改变方向
            if (nextFloor == null) {
                movingUp = !movingUp;
                continue;
            }
            // 模拟移动到下一个楼层的时间延迟
            Thread.sleep(calculateDelay(nextFloor));
            // 移动到下一个楼层
            moveToFloor(nextFloor);
            openDoors();
            // 移除已服务的楼层
            destinations.remove(nextFloor);
            // 模拟开门和关门的时间延迟
            Thread.sleep(1000);
            closeDoors();
        }

    }
    // 计算电梯移动到下一楼层的时间延迟
    private long calculateDelay(int nextFloor) {
        // 假设电梯每层之间移动需要1秒钟
        return Math.abs(nextFloor - currentFloor) * 1000L;
    }
    // 移动到指定楼层
    private void moveToFloor(int floor) {
        System.out.println(name+"Elevator is moving from " + currentFloor + " to " + floor);
        currentFloor = floor;
    }

    // 开门
    private void openDoors() {
        System.out.println(name+"Elevator doors are opening at floor " + currentFloor);
    }

    // 关门
    private void closeDoors() {
        System.out.println(name+"Elevator doors are closing");
    }

    @SneakyThrows
    @Override
    public void run() {
        serveRequests();
    }

}

1717577154032.png

Elevator 类封装了电梯的基本属性和行为。每个电梯都有自己的当前楼层、移动方向和目的地集合。电梯可以接收新的目的地请求，并根据这些请求来移动。电梯的移动策略是尽可能地直接到达目的地楼层，减少中途的停靠。此外，为了模拟电梯的运行时间和开关门延迟，在类中引入了时间延迟逻辑，并实现了 Runnable 接口以支持多线程操作。

ElevatorScheduler 类的核心算法

/**
 * @Author derek_smart
 * @Date 2024/6/7 13:41
 * @Description 调度系统类
 */
class ElevatorScheduler {
    List<Elevator> elevators; // 电梯列表
    private ReentrantLock schedulerLock = new ReentrantLock(); // 用于并发控制的锁
    public ElevatorScheduler(int numberOfElevators) {
        elevators = new ArrayList<>();
        for (int i = 0; i < numberOfElevators; i++) {
            Random random = new Random();
            elevators.add(new Elevator(random.nextInt(33),i)); // 假设所有电梯都从底楼开始
        }
    }

    // 分配最合适的电梯给乘客
    public void dispatchElevator(int destinationFloor) {
        schedulerLock.lock();
        try {
            Elevator bestElevator = findBestElevator(destinationFloor);
            if (bestElevator != null) {
                bestElevator.addDestination(destinationFloor);
            } else {
                System.out.println("所有电梯都忙碌，请稍候再试。");
                // 这里可以添加逻辑来处理这种情况，例如添加到等待队列
            }
        } finally {
            schedulerLock.unlock();
        }
    }

    // 每部电梯计算一个得分，得分越低表示电梯越适合响应这个请求
    private Elevator findBestElevator(int destinationFloor) {
        Elevator bestElevator = null;
        int bestScore = Integer.MAX_VALUE;

        for (Elevator elevator : elevators) {
            int score = calculateElevatorScore(elevator, destinationFloor);
            if (score < bestScore) {
                bestScore = score;
                bestElevator = elevator;
            }
        }
        return bestElevator;
    }

    /**
     * 考虑了电梯是否正在移动以及电梯的移动方向。如果电梯的移动方向与请求方向相反，
     * 我们给这部电梯增加一个较大的分数作为惩罚，因为它需要改变方向才能响应请求，这会导致更长的等待时间。
     * @param elevator
     * @param destinationFloor
     * @return
     */
    private int calculateElevatorScore(Elevator elevator, int destinationFloor) {
        int score = 0;
        int distance = Math.abs(elevator.getCurrentFloor() - destinationFloor);

        if (elevator.isMoving()) {
            if ((elevator.isMovingUp() && destinationFloor < elevator.getCurrentFloor()) ||
                    (!elevator.isMovingUp() && destinationFloor > elevator.getCurrentFloor())) {
                // 如果电梯与请求方向相反，增加分数惩罚
                score += 1000; // 你可以根据实际情况调整这个惩罚值
            }
            // 电梯正在移动，增加额外的距离分数
            score += distance;
        } else {
            // 电梯静止，只考虑距离分数
            score += distance;
        }

        // 如果需要，可以在这里添加更多逻辑，如电梯负载、预估等待时间等
        return score;
    }

1717577258217.png

流程图：

flowchart TB  
    A[开始] --> B[接收目的地请求]  
    B --> C{是否有空闲电梯}  
    C -->|是| D[选择最佳电梯]  
    C -->|否| E[检查等待中的请求]  
    D --> F[分配请求到电梯]  
    E -->|有等待请求| G[重新评估电梯分配]  
    E -->|无等待请求| H[将请求加入等待队列]  
    F --> I[电梯添加目的地并更新状态]  
    G --> D  
    H --> J[当电梯变为空闲时重新评估]  
    I --> K{完成所有请求?}  
    K -->|是| L[更新电梯状态为静止]  
    K -->|否| I  
    L --> M[结束]  
    J --> C

流程图中：

  • 开始：流程的起点。
  • 接收目的地请求：ElevatorScheduler接收到一个新的楼层请求。
  • 是否有空闲电梯：检查是否有电梯当前没有在服务请求。
  • 选择最佳电梯：根据一定的算法（如距离、方向、负载等）选择最佳电梯。
  • 检查等待中的请求：如果没有空闲电梯，检查是否有等待中的请求。
  • 分配请求到电梯：将请求分配给选择的电梯。
  • 重新评估电梯分配：对等待中的请求根据当前电梯状态重新评估和分配。
  • 将请求加入等待队列：如果没有电梯可用，将请求加入等待队列。
  • 电梯添加目的地并更新状态：电梯将请求的目的地添加到它的服务列表中，并更新其状态为“移动”。
  • 当电梯变为空闲时重新评估：当电梯完成当前请求后，检查等待队列并重新评估。
  • 完成所有请求?：检查电梯是否已完成所有分配的请求。
  • 更新电梯状态为静止：如果电梯完成了所有请求，更新其状态为“静止”。
  • 结束：流程的终点。

时序图：

sequenceDiagram
    participant User as 乘客
    participant ES as ElevatorScheduler
    participant E as Elevator
    participant Sys as 系统

    User->>ES: 请求电梯至楼层 N
    alt 找到合适电梯
        ES->>E: 评估电梯状态
        E-->>ES: 返回状态信息
        ES->>E: 分配目的地楼层 N
        E->>E: 添加楼层 N 至目的地列表
        E->>Sys: 开始移动至楼层 N
        E->>E: 到达楼层 N
        E->>Sys: 开门
        Sys->>User: 通知乘客电梯到达
        User->>E: 进入电梯
        E->>Sys: 关门
        E->>E: 继续服务其他请求
    else 所有电梯忙碌
        ES->>Sys: 将请求加入等待队列
        Sys->>User: 通知乘客等待
    end

时序图中：

  • 乘客 发出请求，希望电梯到达特定的楼层 N。
  • ElevatorScheduler (ES) 接收到请求，并开始评估哪部电梯最适合响应这个请求。
  • 如果找到合适的 Elevator (E)，ElevatorScheduler 将请求的楼层 N 分配给它，电梯将楼层 N 添加到它的目的地列表，并开始移动。
  • 当电梯到达楼层 N，它会开门，乘客收到通知并进入电梯，然后电梯关门继续服务其他请求。
  • 如果所有电梯都忙碌，ElevatorScheduler 将请求加入等待队列，乘客被通知等待。

ElevatorScheduler 类是电梯调度系统的大脑。它通过一个简单的得分系统来选择最合适的电梯来响应乘客的请求。得分系统考虑了电梯的当前状态、与请求楼层的距离以及电梯的移动方向。如果电梯的移动方向与请求方向相反，系统会给电梯一个较高的得分作为惩罚，因为这会增加乘客的等待时间并且处理所有电梯都忙碌的情况。

DestinationDispatchElevatorSystem 测试类：

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

/**
 * @Author derek_smart
 * @Date 2024/6/7 13:41
 * @Description 调度系统测试
 */
public class DestinationDispatchElevatorSystem {
    public static void main(String[] args) throws InterruptedException {
        ElevatorScheduler scheduler = new ElevatorScheduler(4); // 假设有4部电梯
        // 使用ExecutorService来管理电梯线程
        ExecutorService executor = Executors.newFixedThreadPool(4);
        // 模拟乘客请求
        scheduler.dispatchElevator(5);
        scheduler.dispatchElevator(11);
        scheduler.dispatchElevator(7);
        scheduler.dispatchElevator(3);
        scheduler.dispatchElevator(1);
        scheduler.dispatchElevator(17);
        scheduler.dispatchElevator(9);
        scheduler.dispatchElevator(8);
        scheduler.dispatchElevator(20);
        scheduler.dispatchElevator(25);
        scheduler.dispatchElevator(33);
        scheduler.dispatchElevator(1);
        // 让每部电梯服务它们的请求
        // 启动电梯线程
        for (Elevator elevator : scheduler.elevators) {
            executor.submit(elevator);
        }

        // 关闭ExecutorService
        executor.shutdown();
        executor.awaitTermination(Long.MAX_VALUE, TimeUnit.NANOSECONDS);

    }
}

测试结果：

企业微信截图_17175774954914.png

代码的主要逻辑包括以下几个步骤：

  1. 创建 ElevatorScheduler 对象，并初始化一定数量的 Elevator 对象。
  2. 处理乘客的楼层请求，通过 dispatchElevator 方法分配最合适的电梯。
  3. findBestElevator 方法会为每部电梯计算一个得分，并选择得分最低（最合适）的电梯。
  4. 选定的电梯通过 addDestination 方法添加新的目的地楼层。
  5. 每部电梯通过 serveRequests 方法依次移动到它们的目的地楼层并开关门。

系统的优化策略

在电梯调度系统的实现中，可以采取多种优化策略来提高其性能。例如，可以考虑电梯的实时负载，优先分配载客量较少的电梯；或者可以预测乘客的到达时间，优先分配能够最快到达请求楼层的电梯。此外，还可以通过模拟和数据分析来不断调整得分系统的参数，以达到最佳的调度效果。

结论

通过结合Java多线程技术和目的地调度算法，构建一个高效、响应迅速的电梯调度系统。虽然存在一些设计和实现的挑战，但通过仔细的规划和优化，这些挑战可以被克服。随着技术的发展，期待在未来看到更加智能化、自动化的电梯调度解决方案。

基于目的地调度算法的电梯调度系统是现代建筑中智能电梯系统设计的一个重要方向。通过智能算法的应用，可以显著提高电梯的运行效率，改善乘客的使用体验。随着技术的进步，期待在未来看到更加智能化、高效化的电梯调度解决方案。

最后关于早上等电梯所思所想和所写目前就这些，未来有新的想法将进一步优化实现。
相关内容
Java 核心知识总结 多线程
深入Java多线程：基础篇，你必须掌握！| 多线程篇(一)
Java多线程详细教程
多线程环境下还敢用System.out.println？坑！
轻松入门Java多线程：提升应用性能的秘诀
Java多线程编程入门：从零基础到最佳实践
在可以用协程的情况下是不是多线程已经完全没有意义了
使用ReentrantLock和Semaphore实现单任务执行多线程唤醒
玩转Java并发集合：高效处理多线程并发访问！
探索Java多线程并发工具类：优化多线程应用的开发体验！