Elevator Data Structures and Algorithms

I lived in NYC for six years. I probably spent 1 minute/day on and waiting for elevators during that time. Spending at least 1.5 days of your life with elevators, one can't help to think about what they are doing.

Hard disk-seeking algorithms influenced many elevator algorithms (or maybe the other way around?). One way to think about it: hard disks need to read ("pick up") and write ("drop off") requests at different locations on the disk ("floors").

Here are some elevator algorithms, starting with the most naive and working towards better implementations.

Last in, first-out (LIFO, stack). Serve those with the shortest request first. Some people never get off the elevator.

First in, first-out (FIFO, queue). Serve those who have been on the elevator the longest. People ride the elevator up and down, potentially passing up their floor many times.

Priority queue (attendant service). Serve riders based on priority. High priority means direct travel to your floor.

The "Elevator algorithm" (SCAN). Permit travel only in the same direction until empty, only picking up or dropping off individuals heading in the same direction. When idle, stay on the last floor served or the ground floor.

Bigger elevators (vertical scaling, batching). More riders on the elevator, but more floors to serve.

More elevators (horizontal scaling, parallelization). Faster, but physical (and economic) limits to how many elevators one can have.

Double-decker elevators, split floor (sharding). Two elevators on top of each other, one is serving odd floors, the other even. Can increase load per shaft and decrease travel time (n/2 floors to serve per elevator now).

Destination dispatch (load balancing). Dynamically assign riders to idle elevators or batch riders going to the same floor.

Heuristics-based. Sometimes, there's peak "up" traffic or "down" traffic, e.g., right before shifts start and end.

When designing elevator algorithms, there's a human aspect to it. For example, will riders know how to use the dynamic dispatch panel? Will they accidentally press a button for the wrong floor? How many other people are they comfortable with in the same car?