Object Oriented Design: Elevator System

Design an elevator system for a multi-story building that coordinates multiple elevators and efficiently processes user requests.

Functional Requirements

1. Support multiple elevators, all serving the same set of floors.

2. Allow users to request an elevator from any floor lobby using the up / down buttons, or select a destination floor from inside the elevator.

3. Assign the most optimal elevator to each incoming request based on factors like distance from the request floor and current direction of travel.

Primary Use Cases

An elevator system primarily serves two key functions: enabling users to call an elevator from any floor lobby and allowing passengers inside the elevator to select their destination floor.

Let’s walk through the workflow of each use case to better understand how the system processes requests.

Use Case 1: Request Elevator From Floor Lobby

1. A user presses the Up or Down button from a floor lobby.

2. The system evaluates each incoming request by analyzing factors such as the requested floor and desired direction of travel, and then selects the most suitable elevator to handle the request.

3. Once an appropriate elevator is selected, the requested floor is added to its list of pending stops. The elevator then adjusts its route accordingly to accommodate the request and serve the user as efficiently as possible.

Use Case 2: Select Floor Inside Elevator

1. A user selects a destination floor by pressing the floor button on the control panel inside an elevator.

2. The elevator adds the floor to its list of upcoming stops, and continues visiting floors in an optimized order.

3. Once all requests have been completed, the elevator transitions to an idle state and waits for new requests.

Object Model Design

To design a scalable and maintainable elevator system, it is essential to first identify the core entities involved and define their responsibilities. These entities represent the key components of the system and form the foundation of the overall architecture.

The primary entities in the system include:

ElevatorSystem

Serves as the central controller, managing all elevators in the system. It is responsible for processing incoming requests and assigning the most suitable elevator to ensure minimal wait time.

Elevator

Represents an individual elevator in the system, responsible for maintaining its current floor, state (idle or moving), direction of movement (up or down), and the set of floors it needs to service (no need to add duplicates floors in pending requests).

It encapsulates its own movement logic, handling how requests are processed and executed through its internal behavior.

Low-Level Design

Let's discuss the low-level design and complexities for each functionality. This will help us build a system that is efficient, scalable, and optimized for real-world usage.

ElevatorSystem

The ElevatorSystem class offers two primary methods for handling requests from users: requestElevator(int currentFloor, Direction direction) and selectFloor(Elevator elevator, int desinationFloor).

We could design this differently. Maintain a queue of pending requests on the controller and have elevators pull from it. In our design, we'll choose to immediately dispatch lobby calls to an elevator when they arrive so the controller only needs the list of elevators and doesn't maintain a queue of unassigned requests. It picks an elevator right away and tells that elevator to add the request to its queue. This keeps the controller stateless beyond just holding the elevators.

enum Direction {
    UP,
    DOWN
}

class ElevatorSystem {

    private final List<Elevator> elevators;

    public ElevatorSystem(int numElevators) {
        elevator = new ArrayList<>();
        for(int i = 0; i < numElevators; i++) {
            elevators.add(new elevator());

            Thread t = new Thread(e);
            t.start(); // starts continuous movement loop 
        }
    }

    // Handles a request for an elevator from a specific floor and direction
    public void requestElevator(int currentFloor, Direction direction) {
        Elevator selectedElevator = selectElevator(currentFloor, direction);
        if (selectedElevator != null) {
            selectedElevator.addRequest(currentFloor);
        }  
    }

    // Handles a floor selection request from inside an elevator
    public void selectFloor(Elevator elevator, int desinationFloor) {
        elevator.addRequest(destinationFloor);
    }

    // Helper Method: 
    private Elevator selectElevator(int floor, Direction direction) {
        // 1. First-Come-First-Serve Strategy
        // 2. Shortest-Seek-Time-First Strategy
    }

}

breaks single responsibility principle. Can mopdify the strategy of how

The dipatch logic relies on the Strategy Pattern, which enables the system to dynamically select and swap between different algorithms for optimizing elevator allocation.

class ElevatorSystem {

    .
    .
    .

    private final ElevatorDispatcher elevatorDispatcher;

    public ElevatorSystem(...,  DispatchingStrategy strategy) {

        .
        .
        . 

        this.elevatorDispatcher = new ElevatorDispatcher(strategy);
    }

    // Handles a request for an elevator from a specific floor and direction
    public void requestElevator(int currentFloor, Direction direction) {
        elevatorDispatcher.dispatchElevator(currentFloor, direction, elevators);
    }

    .
    .
    .

}

ElevatorDispatcher

The ElevatorDispatcher class is responsible for assigning and directing Elevators to handle lobby requests using a specified DispatchingStrategy.

public class ElevatorDispatcher {

    private final ElevatorDispatchStrategy strategy;

    public ElevatorDispatcher(ElevatorDispatchStrategy strategy) {
        this.strategy = strategy;
    }

    // 
    public void dispatchElevator(int floor, Direction direction, List<Elevator> elevators) {
        Elevator selectedElevator = strategy.selectElevator(currentFloor, direction, elevators);
        if (selectedElevator != null) {
            selectedElevator.addFloorRequest(currentFloor);
        } 
    }
}

DispatchingStrategy

The ElevatorDispatchStrategy defines the specific rules for selecting an elevator when a loggy button is pressed.

interface ElevatorDispatchStrategy {
    Elevator selectElevator(int floor, Direction direction, List<Elevator> elevators)
}

By abstracting the selection logic, the system is adaptable to various strategies, allowing flexibility in optimizing the dispatch process. Common dispatching strategies include:

Nearest Elevator Dispatch Strategy

Select the elevator closest to the requested floor, regardless of its state or the direction it's heading.

public class NearestElevatorDispatchStrategy implements DispatchingStrategy {
    // selects the elevator that is closest to the requested floor
    @Override
    public Elevator selectElevator(int floor, Direction direction, List<Elevator> elevators) {
        Elevator bestElevator = null;
        int shortestDistance = Integer.MAX_VALUE;

        for(Elevator elevator: elevators) {
            // Calculate distance between elevator and the requested floor
            int distance = Math.abs(elevator.getCurrentFloor() - floor);

            // Select elevator if it's closer than the current best
            if(distance < shortestDistance) {
                bestElevator = elevator;
                shortestDistance = distance;
        }

        return best;
    }
}

This strategy works well when the system is simple, traffic is low, and most elevators are idle, since choosing the closest elevator minimizes immediate pickup time.

However, it breaks down in more realistic scenarios where elevator direction and movement patterns matter. For example, a request is made from floor 5 to go up, while Elevator A is at floor 2 moving upward and Elevator B is at floor 6 moving downward toward floor 1. The nearest dispatch algorithm selects Elevator B because it is closest in terms of distance.

This leads to inefficient behavior: Elevator B moves down to floor 5, picks up the passenger, and then continues downward due to its current direction, forcing the passenger to travel in the wrong direction first before the elevator eventually reverses and goes up. In contrast, Elevator A, although farther away, is already moving upward and would naturally pick up the passenger on its way, resulting in a faster and more efficient journey.

Idle Elevator Dispatch Strategy

Prioritizes elevators that are currently not serving any requests and are free to respond immediately.

It is generally better than the Nearest Elevator Dispatch strategy because it avoids assigning requests to elevators that are already busy or moving in the wrong direction, leading to more predictable and often faster service.

enum State {
    IDLE,
    MOVING
}

class IdleElevatorDispatchStrategy implements ElevatorDispatchStrategy {

    // selects the elevator that is IDLE and closest to the requested floor
    @Override
    public Elevator selectElevator(int floor, Direction direction, List<Elevator> elevators) {
        Elevator bestElevator = null;
        int shortestDistance = Integer.MAX_VALUE;

        for(Elevator elevator: elevators) {
            if (elevator.getCurrentState() == State.IDLE) {
                // Calculate distance between elevator and the requested floor
                int distance = Math.abs(elevator.getCurrentFloor() - floor);

                // Select elevator if it's closer than the current best
                if(distance < shortestDistance) {
                    bestElevator = elevator;
                    shortestDistance = distance;
                }
            }
        }

        return best; // can be null
    }
    
}

This strategy is good when there are free elevators available, as they have no pending requests or directional commitments and can respond immediately to new calls.

However, there could be scenarios where:

1. A moving elevator may already be heading toward the requested floor and could pick up the passenger naturally. By prioritizing an idle elevator instead, the system may send a father or less optimal elevator. This behavior can increase overall wait times and degrade the system's efficiency.

2. No elevators are idle.

Direction-Aware Dispatch Strategy

Assigns elevator requests only to those elevators that are already moving in the same direction and will naturally pass the requested floor along their current path.

public class DirectionAwareDispatchStrategy implements ElevatorDispatchStrategy {
    // Selects the elevator that is closest to the requested floor and moving in the same direction
    @Override
    public Elevator selectElevator(int floor, Direction direction, List<Elevator> elevators) {
        Elevator bestElevator = null;
        int shortestDistance = Integer.MAX_VALUE;

        for(Elevator elevator: elevators) {
            // skip if elevator is moving in the opposite direction     
            if (elevator.getCurrentDirection() != direction) {
                continue;
            }
            
            // skip if elevator has already crossed the requested floor
            if( (direction == Direction.UP && elevator.getCurrentFloor > floor) ||
                (direction == Direction.DOWN && elevator.getCurrentFloor < floor) ) {
                    continue;
            }
            
            // Calculate distance between elevator and the requested floor
            int distance = Math.abs(elevator.getCurrentFloor() - floor);

            // Select elevator if it's closer than the current best
            if(distance < shortestDistance) {
                bestElevator = elevator;
                shortestDistance = distance;
            }
        }

        return bestElevator; // can be null;
    }
}

While this strategy improves efficiency, it also introduces a key limitation. In some situations, no elevator satisfies both conditions.

For example, all elevators might be moving in the opposite direction or may have already passed the requested floor. In such cases, the strategy cannot make a valid assignment on its own and must rely on fallback approaches like idle or nearest elevator selection.

Composite (Priority-Based) Dispatch Strategy

Evaluates each strategy sequentially (direction-aware, idle-first, and nearest) and selects the first one that can successfully assign an elevator to the request.

class PriorityDispatchStrategy implements ElevatorDispatchStrategy {

    private List<ElevatorDispatchStrategy> strategies;

    public PriorityDispatchStrategy(List<ElevatorDispatchStrategy> strategies) {
        this.strategies = strategies;
    }

    @Override
    public Elevator selectElevator(int floor, Direction direction, List<Elevator> elevators) {

        for(ElevatorDispatchStrategy strategy: strategies) {
            Elevator result = strategy.selectElevator(floor, direction, elevators);

            if(result != null) {
                return result;
            }
        }

        throw new RuntimeException("No elevator available");
    }
}

This strategy ensures efficient handling of diverse scenarios while gracefully falling back to simpler strategies when stricter ones cannot produce the results.

Elevator

Each elevator operates independently without awareness of other elevators in the system, and therefore runs on its own thread, continously serving incoming requests.

In a multithreaded environment, a thread-safe structure like ConcurrentSkipListSet should be used to prevent concurrency issues when the dispatcher adds requests and the elevator processes them simultaneously.

class Elevator implements Runnable {
    private int currentFloor;
    private Direction currentDirection;
    private ElevatorState currentState;

    // Sorted, thread-safe, no duplicates
    private final ConcurrentSkipListSet<Integer> requests = new ConcurrentSkipListSet<>();

    public Elevator(int startFloor) {
        this.currentFloor = startFloor;
        this.currentDirection = Direction.UP;
        this.currentState = ElevatorState.IDLE;
    }


    public void addRequest(int floor) {
        requests.add(floor);
    }

    @Override
    public void run() {
        while(true) {
            try {
                serve();
                Thread.sleep(1000); // simulate time between floors
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
    }

    public void serve() {
        // Strategy 1: First Come, First Serve (FCFS)
        // Strategy 2: Continue Until Clear, Then Reverse (SCAN)
    }

}

breaks single responsibility principle. Can mopdify the strategy of how

The movement logic relies on the Strategy Pattern, which enables the system to dynamically select and swap between different algorithms for optimizing elevator movement.

class Elevator implements Runnable {
    
    .
    .
    .

    private ElevatorMovementStrategy movementStrategy;

    public Elevator(int startFloor, ElevatorMovementStrategy strategy) {
        .
        .
        .
        this.movementStrategy = strategy;
    }

    .
    .
    .

    public void serve() {
        movementStrategy.move(this);
    }

}

ElevatorMovementStrategy

The ElevatorMovementStrategy defines the rules for how an elevator processes and serves its pending requests.

interface ElevatorMovementStrategy {
    void move(Elevator elevator);
}

By abstracting the movement logic, the system is adaptable to various strategies, allowing flexibility in optimizing the movement process. Common movement strategies include:

First Come, First Serve Strategy

class FIFOMovementStrategy implements ElevatorMovementStrategy {

    @Override
    public void move(Elevator elevator) {

        if (elevator.requests.isEmpty()) {
            elevator.currentState = Direction.IDLE;
            return;
        }

        // Peek at the oldest request (don't remove yet)
        int targetFloor = elevator.requests.peek();

        // Move towards it
        if (elevator.currentFloor < targetFloor) {
            elevator.currentFloor++;
            elevator.currentDirection = Direction.UP;
        } else if (elevator.currentFloor > targetFloor) {
            elevator.currentFloor--;
            elevator.currentDirection = Direction.DOWN;
        }

        // Remove request when we arrive
        if (elevator.currentFloor == targetFloor) {
            elevator.requests.poll();
        }

    }

}
    

While the dispatching strategy considers the direction of elevators when assigning external requests, the First Come First Serve movement strategy inside the elevator does not take direction into account when serving its own queue.

As a result, even if an optimal elevator is selected initially, the elevator may still behave inefficiently by processing requests in arrival order rather than following a directional flow. This can lead to unnecessary direction changes and increased travel time.

Continue Until Clear, Then Reverse (SCAN)

The SCAN (Elevator Algorithm) improves upon FIFO by ensuring that the elevator continues moving in its current direction, servicing all requests along the way, before reversing direction. This minimizes unnecessary back-and-forth movement and improves overall efficiency.

class ScanMovementStrategy implements ElevatorMovementStrategy {

    @Override
    public void move(Elevator elevator) {

        if (elevator.requests.isEmpty()) {
            elevator.currentState = ElevatorState.IDLE;
            return;
        }

        elevator.currentState = ElevatorState.MOVING;

        Integer nextFloor;

        if (elevator.currentDirection == Direction.UP) {
            nextFloor = elevator.requests.ceiling(elevator.currentFloor);
        } else {
            nextFloor = elevator.requests.floor(elevator.currentFloor);
        }

        // If no request in current direction → reverse
        if (nextFloor == null) {
            elevator.currentDirection = (elevator.currentDirection == Direction.UP)
                    ? Direction.DOWN
                    : Direction.UP;
            return;
        }

        // Move one step toward next floor
        if (elevator.currentFloor < nextFloor) {
            elevator.currentFloor++;
        } else if (elevator.currentFloor > nextFloor) {
            elevator.currentFloor--;
        }

        // Remove request when reached
        if (elevator.currentFloor == nextFloor) {
            elevator.requests.remove(nextFloor);
        }
    }
}

The SCAN strategy ensures that requests are grouped based on direction, reducing zig-zag movement and improving throughput. By continuing in one direction until all requests are served and then reversing, it provides a more predictable and efficient servicing pattern compared to FIFO.

Final UML Diagram