Elevators
This fascinating article unravels the hidden complexities of elevator algorithms, from basic SCAN and LOOK methods to advanced systems like Otis' RSR. It delves into how wait times are optimized, revealing the counter-intuitive finding that 'smarter' systems like Destination Dispatch can often be less efficient due to their rigidity. Hacker News readers appreciate this deep dive into an infrastructural component often taken for granted, especially the blend of technical detail and surprising real-world performance observations.
The Lowdown
Elevators, a ubiquitous part of modern life, hide a surprising depth of algorithmic complexity behind their simple function of moving people vertically. This article peels back the layers, exploring how these systems manage traffic, minimize wait times, and the often counter-intuitive trade-offs involved in their design. It highlights that the 'best' algorithm isn't always the most sophisticated, and human behavior plays a significant role in perceived efficiency.
- Basic Algorithms: The journey begins with simple algorithms like SCAN (travels end-to-end) and LOOK (reverses direction at the highest/lowest request), which form the foundation of single-car dispatch.
- Multi-Car Coordination: With multiple elevators, coordination becomes key. Initial simple approaches assign to the nearest car, but more sophisticated methods are needed.
- Measuring Efficiency: Elevator algorithms are primarily judged by wait times, often focusing on the p90 (90th percentile) to address the psychological impact of long waits.
- Traffic Patterns: Different times of day (morning rush, lunch, evening) present unique traffic demands that challenge algorithms, with morning rushes often having the worst wait statistics.
- Smarter Dispatch (RSR): Otis' Relative System Response (RSR) algorithm scores cars based on various factors (ETA, load, direction, idle proximity) and re-optimizes every 5 seconds, allowing for dynamic re-routing.
- LOOK vs. RSR: Surprisingly, RSR doesn't always win. In high-flow, high-occupancy scenarios, or smaller buildings, the simpler LOOK algorithm can sometimes outperform RSR, suggesting that complexity isn't always superior.
- Destination Dispatch: This system requires passengers to input their destination before the elevator arrives, assigning them a specific car. Counter-intuitively, it often leads to worse wait times than traditional up/down buttons because its rigidity prevents the re-optimization that RSR excels at. The system cannot adapt once a passenger is assigned.
- Interactive Simulation: The article includes a simulation tool to demonstrate these concepts with adjustable parameters.
Ultimately, elevator algorithms are a delicate balance between engineering efficiency and the unpredictable nature of human traffic. The article serves as a powerful reminder that sometimes, simple, flexible solutions are superior to complex, rigid ones, especially when real-world variables are at play.
The Gossip
The Perils of Human Passengers
Many commenters lament how human behavior can undermine even the most optimized elevator algorithms. Issues range from people redundantly pressing both 'up' and 'down' buttons, thereby causing unnecessary stops and confusion, to passengers misunderstanding how Destination Dispatch systems work. The discussion also touches on the psychological aspects of waiting, noting that perceived progress (even if misguided) can improve user experience, and highlights that user experience doesn't always align with engineers' metrics.
Gaming the System: Elevator Simulators and Challenges
The article resonated with many who have encountered elevator scheduling as a computer science problem or a game. Commenters recall past programming assignments, share links to popular elevator simulation games like 'Elevator Saga' and 'SimTower', and discuss their own experiences developing such games. This highlights the enduring appeal of elevator logic as a practical yet complex optimization challenge in recreational and educational contexts.
Beyond Wait Times: Maintenance and Maximization
The discussion extended beyond just passenger wait times to other critical, often unseen, operational considerations. Commenters pointed out the importance of factors like elevator wear and tear, energy consumption, and the capital expenditure (cap-ex) of the equipment itself. They noted that real-world algorithm design must balance these costs against passenger convenience, and that optimizing for throughput might be the primary driver due to the high cost of each elevator car.
Destination Dispatch Debates
The article's counter-intuitive finding that Destination Dispatch often performs worse sparked considerable debate. Some commenters shared anecdotal evidence suggesting that in specific real-world scenarios, like office buildings with predictable 'lunch rush' patterns or hotels, Destination Dispatch can be highly effective by batching passengers. However, others reiterated the article's point that the system's rigidity, preventing re-optimization once an elevator is assigned, is a major drawback, particularly in unpredictable traffic. There was also speculation on whether a smarter algorithm could mitigate these issues or if the problem lies in user education.