What you will learn
- How to separate one elevator’s movement from choosing which elevator answers a call.
- The LOOK (elevator) algorithm for ordering stops.
- A cost function for dispatching hall calls across several cars.
- A simple tick-based simulation you can test.
Requirements
- A building with N floors and M elevators.
- Hall calls: someone on floor F presses UP or DOWN.
- Car calls: a passenger inside elevator E presses floor F.
- Each elevator serves stops efficiently without starving anyone.
- Assign each hall call to the best elevator.
Usually out of scope: weight limits, door timing, maintenance mode, fire mode. These are good “how would you extend it” answers (maintenance and fire mode fit the State pattern).
Classes
Dispatcher "1" --> "many" Elevator
Elevator: id, floor, direction (UP/DOWN/IDLE), stops: set[int]
Elevator: add_stop(floor), step(), cost(floor, direction)
Dispatcher: hall_call(floor, dir), car_call(id, floor), tick()
The key split: Elevator knows how to move through its own stops; Dispatcher decides which elevator gets a new hall call. Dispatch policy is a natural strategy to swap later.
The LOOK algorithm
Serving stops in arrival order makes the car zig-zag. The classic approach, borrowed from disk scheduling, is SCAN: keep moving in one direction, stopping at requested floors, and reverse only at the end. LOOK is the practical version: reverse as soon as there are no more stops ahead, instead of travelling to the top or bottom floor.
Properties:
- No starvation: every stop is reached within at most two sweeps.
- Few direction changes, which is what passengers feel as efficiency.
Dispatching
When a hall call arrives, compute a cost for each elevator and pick the cheapest:
- Idle: cost = distance.
- Moving towards the floor in the requested direction: cost = distance (it’s on the way).
- Otherwise: distance plus a penalty for its pending stops, because it must finish its run first.
Real systems tune this with travel and door times, load and energy, but the structure stays the same.
The code
"""Elevator system low-level design: requests, dispatching and the SCAN (LOOK) algorithm."""
from dataclasses import dataclass, field
from enum import Enum
class Direction(Enum):
UP = 1
DOWN = -1
IDLE = 0
@dataclass
class Elevator:
id: int
floor: int = 0
direction: Direction = Direction.IDLE
stops: set = field(default_factory=set)
def add_stop(self, floor: int):
if floor != self.floor:
self.stops.add(floor)
if self.direction is Direction.IDLE and self.stops:
self.direction = Direction.UP if floor > self.floor else Direction.DOWN
def step(self) -> int | None:
"""Move one floor (LOOK: keep going while stops remain ahead, then reverse)."""
if not self.stops:
self.direction = Direction.IDLE
return None
ahead = [s for s in self.stops if (s - self.floor) * self.direction.value > 0]
if not ahead: # nothing further this way: turn around
self.direction = Direction.DOWN if self.direction is Direction.UP else Direction.UP
self.floor += self.direction.value
if self.floor in self.stops:
self.stops.remove(self.floor)
return self.floor # doors open here
return None
def cost(self, floor: int, direction: Direction) -> int:
"""Rough distance-based cost to serve a hall call; lower is better."""
distance = abs(self.floor - floor)
if self.direction is Direction.IDLE:
return distance
heading_towards = (floor - self.floor) * self.direction.value >= 0
if heading_towards and direction is self.direction:
return distance # on the way
return distance + 2 * len(self.stops) + 10 # would need to finish its run first
class Dispatcher:
def __init__(self, elevators: list[Elevator]):
self.elevators = elevators
def hall_call(self, floor: int, direction: Direction) -> Elevator:
best = min(self.elevators, key=lambda e: (e.cost(floor, direction), e.id))
best.add_stop(floor)
return best
def car_call(self, elevator_id: int, floor: int):
self.elevators[elevator_id].add_stop(floor)
def tick(self) -> list[str]:
events = []
for e in self.elevators:
opened = e.step()
if opened is not None:
events.append(f"E{e.id} opens at {opened}")
return events
if __name__ == "__main__":
d = Dispatcher([Elevator(0, floor=0), Elevator(1, floor=8)])
print("call at 2 UP ->", f"E{d.hall_call(2, Direction.UP).id}")
print("call at 9 DOWN ->", f"E{d.hall_call(9, Direction.DOWN).id}")
d.car_call(0, 6)
for t in range(1, 8):
for ev in d.tick():
print(f"t={t}: {ev}")
if t == 2:
d.car_call(0, 4) # passenger who boarded at 2 presses 4
print("positions:", [(f"E{e.id}", e.floor, e.direction.name) for e in d.elevators])
Output:
call at 2 UP -> E0
call at 9 DOWN -> E1
t=1: E1 opens at 9
t=2: E0 opens at 2
t=4: E0 opens at 4
t=6: E0 opens at 6
positions: [('E0', 6, 'IDLE'), ('E1', 9, 'IDLE')]
What happened: E0 on floor 0 is closest to the call at 2, and E1 on floor 8 is closest to 9. E0 also had a car call for 6. After the passenger boarded at 2, they pressed 4; because 4 lies ahead in E0’s direction, LOOK stops there before 6 instead of going to 6 first.
Design notes
- Tick-based simulation makes behaviour deterministic and testable. In a real controller each elevator runs its own loop driven by sensors; the logic is the same.
- Thread safety: hall calls arrive from many buttons at once. Protect each elevator’s
stopswith a lock, or feed all events through one queue processed by a single controller thread (simpler and common). - Direction-aware stops: a production design keeps separate up and down stop sets so a car going up doesn’t stop for someone who wants to go down. Mention it as an improvement.
Key takeaways
- Separate per-car movement (LOOK) from fleet-level dispatching (cost function).
- LOOK reverses only when no stops remain ahead: few direction changes, no starvation.
- A tick-based model makes elevator logic deterministic and easy to test.
- Use a single event queue or per-car locks for concurrent button presses.
Exercises
- Split
stopsinto up-stops and down-stops so hall calls are served only in the requested direction. - Add a
MAINTENANCEstate that ignores new calls and finishes current stops. - Change the dispatcher to a nearest-car strategy and compare total ticks for a set of 20 random calls.
Quiz
- Why not just serve stops in the order they were requested?
- How does LOOK differ from SCAN?
- Why does the cost function add a penalty when the elevator is moving away?
Show answers
- First-come order causes zig-zagging and long travel times; sweeping in one direction is far more efficient.
- SCAN goes to the end of the building before reversing; LOOK reverses as soon as no stops remain ahead.
- That elevator has to finish its current run before it can come back, so the real wait is longer than the raw distance.