- Elevator operation is not simply responding to calls; it is a dispatch optimization problem that considers the number of cars, passenger flow, load, and direction of travel together
- For a single car, SCAN changes direction at the top floor, while LOOK turns back at the highest floor with an actual request, which is closer to how people generally expect elevators to operate
- RSR (Relative System Response) for multiple cars scores factors such as estimated arrival time and load, and re-optimizes dispatch every 5 seconds, allowing passengers of a delayed car to be reassigned to another car
- If cars are constantly full, passenger flow is high enough that the elevator stops at every floor, and there are few cars, simple LOOK may be better than complex RSR
- Destination Dispatch, where passengers enter the destination floor in advance, provides more information but makes it hard to change the assigned car; except in some cases such as super-tall buildings or groups with 8+ cars, wait times are generally longer than with traditional up/down buttons
Where does a single car change direction?
- SCAN, patented in 1961, starts from the lobby, goes up to the top floor, then changes direction and comes down, picking up and dropping off passengers along the route
- LOOK does not necessarily go all the way to the top floor; it runs only up to the highest requested floor and then turns back
- The elevator operating pattern people generally know and expect is closer to LOOK
Basic dispatch for multiple cars
- If there are multiple elevators, the system must coordinate which car handles which call
- In a basic system, a central scheduler assigns stop floors for each car and assigns a new call to the nearest car
- But dispatch based only on simple distance cannot adequately reflect situations such as the nearest car being full
How to evaluate wait time
- The most intuitive evaluation metric for elevator algorithms is wait time, from a call until the car arrives
- A simple approach is to measure the percentage of cars that arrive within 30 seconds or 90 seconds
- For a more rigorous evaluation, collect wait times from thousands of trips and examine the distribution and histogram
- If p90 is 2 minutes, it means 90% of passengers waited 2 minutes or less
- If p50 is 1 minute, the car arrived within 1 minute for half of the calls
- Passengers tend to remember unusually long p90 cases more strongly than the average wait time
Passenger flow changes by time of day
- In large office buildings in the morning, most movement is from the lobby up to higher floors
- In the evening, the flow from upper floors downwards dominates due to people leaving work
- At lunchtime, upward and downward traffic is mixed, and during the rest of the day there is a lot of floor-to-floor movement
- Wait-time distributions vary greatly by time of day and traffic pattern, and statistics are especially poor during the morning commute period
How RSR chooses a car
- Otis’s RSR (Relative System Response) scores how suitable each car is for picking up passengers; lower scores mean better suitability
- The pickup score is calculated by combining multiple factors
- Estimated arrival time to the call floor
- Load penalty based on the number of passengers on board
- Anti-clustering penalty applied when another car is already heading to the same floor in the same direction
- Direction-match bonus
- Idle-car bonus for a car within two floors of the call floor
- Low-load bonus
- Anti-bunching suppresses additional assignment if another car is already heading to the same floor in the same direction
- RSR re-optimizes the entire dispatch every 5 seconds
- If car A is delayed, passengers originally scheduled to be picked up by A can be reassigned to car B
- This continuous re-optimization is the key to smoothing passenger flow
Performance differences between LOOK and RSR
- Using a wait-time analysis tool, you can compare the percentage of arrivals within 30 and 90 seconds for LOOK and RSR
- As passenger flow increases, LOOK starts to outperform RSR
- If cars are always full and stop at every floor, the effect of RSR’s additional rules decreases
- In smaller buildings with fewer elevators per car group, LOOK also tends to be better than RSR, so a simpler approach may be more suitable
- In addition to wait time, travel time after boarding until the destination floor can also be measured
- LOOK and RSR show different characteristics on this metric too, but a specific comparison is not covered
Why destination dispatch is disadvantaged despite having more information
- Destination dispatch is a method where a passenger first enters their destination floor at a kiosk on each floor, and the system assigns the elevator to board
- The optimization system can know each passenger’s destination before the car arrives, but wait time is generally longer than with traditional up/down buttons
- There are exceptions where the kiosk method is advantageous, such as very tall buildings with 8 or more elevators per car group
- The core cause of the performance drop is the rigidity of dispatch
- In the traditional method, car routes and passenger assignments can be re-optimized every 5 seconds
- In destination dispatch, passengers must board the car initially assigned to them
- Even if operating conditions change 30 seconds after the call, the assigned car cannot be flexibly changed
- The loss from losing reassignment flexibility is greater than the benefit of additional destination information
Simulation controls and scope
- In the full simulation, you can adjust the number of floors, number of cars, and passenger flow per minute, and check the percentage of arrivals within 30 and 90 seconds
- Real elevator algorithms have many more considerations, and the scope covered here is only part of the overall area
- The call-button input is delivered, but the elevator calculates multiple operating conditions together, so it may not arrive immediately
1 टिप्पणियां
Hacker News की राय
पिछली आधी सदी में लगभग आधे समय तक एलिवेटर सिर्फ relay control से, बिना कंप्यूटर के, चलाए जाते थे, और ऐसे algorithms भी wired logic circuits में implement किए जाते थे
circuit diagrams जैसी दिलचस्प details Otis के पुराने patents में देखी जा सकती हैं
हाई स्कूल की computer science class में मैंने निजी project के तौर पर कई elevator algorithm simulations implement किए थे
rotating hard disk, vertical की बजाय spindle के चारों ओर लिपटे बहुत लंबे elevator जैसी होती है, और SCAN वास्तव में disk scheduling algorithm है: https://en.wikipedia.org/wiki/Elevator_algorithm
सोच रहा हूँ कि destination floor को random set करने की वजह से ही यह नतीजा आया कि destination dispatch कुल मिलाकर खराब है
असली इमारतों में ज़्यादातर लोग ground floor से नहीं बल्कि ground floor की ओर जाते हैं, और ground floor पर एक ही मंज़िल पर काम करने वाले लोग lunch time में साथ निकलते हैं और फिर उसी मंज़िल पर साथ लौटते हैं. destination dispatch ऐसे patterns में फ़ायदे में रहता है क्योंकि यह एक ही destination वाले बड़े groups को साथ बिठा सकता है
कुछ होटलों के kiosk systems breakfast rush के समय के हिसाब से user interface भी बदलते हैं
lunch पर जाने या लौटने वालों का clustering effect भी वास्तव में होता है, और यह सुबह या शाम से ज़्यादा दोपहर में दिखता है
ऐसे लेख भी हैं जिनमें कहा गया है कि offices या hotels ने इस तरीके पर switch करने के बाद waiting time काफ़ी घटा
हाल ही में जिस नई इमारत में गया था, वहाँ भी यही तरीका इस्तेमाल हो रहा था. कॉलेज के दिनों में electrical engineering पढ़ने वाले मेरे roommate ने call buttons, motor, और position sensing के लिए काले squares वाले transparent disc को breadboard से जोड़कर elevator circuit बनाया था; शायद वह कोई simple algorithm था
अगर आप elevator scheduling पहली बार देख रहे हैं, तो यह game recommend करूँगा: https://play.elevatorsaga.com/
iOS·Android के लिए elevator control और automation game Sky Lobby बनाते समय मैंने इस समस्या पर बहुत सोचा था
मैंने LOOK जैसा algorithm चुना, जो player की अपेक्षित movement के सबसे क़रीब था, लेकिन जब choice अस्पष्ट हो तो लंबे समय से इंतज़ार कर रही मंज़िल को प्राथमिकता देकर game में महत्वपूर्ण p90 बेहतर किया. लेकिन जब double-deck elevators, shafts के बीच transfer floors, और express shafts जुड़ जाते हैं, तब कौन सा algorithm optimal या सबसे intuitive है, यह कहीं ज़्यादा अस्पष्ट हो जाता है. चूँकि यह real system नहीं बल्कि game था, इसलिए मैंने बस काफ़ी अच्छा heuristic ढूँढा, और जब players को वह पसंद न आए तो उन्हें schedule को manually override करने दिया; इससे ज़्यादातर लोग संतुष्ट थे
जब भी elevator का इंतज़ार करता हूँ, सोचता हूँ कि ऐसा algorithm बनाना कितना सिरदर्द होगा जो passenger pickup और destination arrival तक के waiting time को कम करे
कभी-कभी तो लगता है कि इसे implement करने वाले लोग जानबूझकर हमें ज़्यादा इंतज़ार कराने वाले शैतानी sadist होंगे
किसी बड़े conference के अगले दिन सुबह सभी लोग नीचे जाना चाहते थे, लेकिन पूरी तरह भरा हुआ elevator हर मंज़िल पर रुक रहा था. अगर 10-person elevator पहले ही 10 मंज़िलों के call passengers उठा चुका है, तो उसे हर मंज़िल पर “अरे, जगह नहीं है, अगला ले लेंगे” दोहराने के बजाय सीधे ground floor जाना चाहिए और 5 मिनट बचाने चाहिए. खासकर अगर दूसरी मंज़िल पर चलने-फिरने में कठिनाई वाले किसी व्यक्ति को flight पकड़नी हो, तो यह गंभीर समस्या है
सभी elevators की position और movement देखें तो scheduling हैरान करने वाली हद तक घनी होती है. lobby में इंतज़ार अंतहीन लगता है, लेकिन dispatch के नज़रिये से activity लगातार चलती रहती है, और building usage time में elevators लगभग कभी idle नहीं होते. सिर्फ status panel देखते रहना भी दिलचस्प है. और अगर elevator technician कहे “सुबह जल्दी मिलते हैं”, तो उसका मतलब अक्सर 4 बजे के आसपास होता है, क्योंकि वे लोगों के काम पर आने से पहले काम ख़त्म करना चाहते हैं
elevators महंगे होते हैं और building owners आवेग में आकर ज़रूरत से ज़्यादा निवेश नहीं करते, इसलिए आमतौर पर उतने ही, या कभी-कभी उससे भी कम, minimum elevators लगाए जाते हैं जितने अपेक्षित demand को संभाल सकें
4 elevators के ऊपर हर एक के scheduled stop floors दिखते हैं, और इंतज़ार करते समय भी elevator और floor assignment बदलकर आवाज़ से बताया जाता है. यह शायद optimal dispatch के लिए बनाया गया feature है
elevators में सबसे बड़ी समस्या algorithm से ज़्यादा वे लोग हैं जो destination direction के हिसाब से up/down call buttons दबाने की अवधारणा नहीं समझते
“ज़्यादा जल्दी आएगा” सोचकर अगर दोनों buttons दबाएँ, तो आधे मामलों में पहले उल्टी दिशा में जाना पड़ता है, और पहले से बैठे लोगों के लिए अनावश्यक stops भी जुड़ जाते हैं
शायद यह fake loading indicator की psychology जैसा है. arrival time जाने बिना इंतज़ार करना उबाऊ और घुटनभरा लगता है, लेकिन अगर उल्टी दिशा में जा रहे elevator में भी चढ़ जाएँ तो लगता है कि कुछ प्रगति हो रही है. आख़िरकार, भले ज़्यादा समय लगे, पर कुछ होता हुआ महसूस होना कम परेशान करता है
दूसरी ओर, अगर up demand कम हो, तो पहले ऊपर जाकर फिर पूरा चक्कर लगाकर नीचे आना इस उम्मीद में इंतज़ार करने से ज़्यादा तार्किक रणनीति हो सकती है कि कभी जगह मिलेगी
ऐसे में up और down दोनों buttons दबाना बेवक़ूफ़ी नहीं बल्कि तार्किक है
algorithm की performance से अलग, लोगों की waiting time perception की psychology भी अहम है
कुछ किए बिना इंतज़ार करना बहुत चिढ़ पैदा करता है, लेकिन उसी समय में कुछ करते रहने पर प्रगति महसूस होती है और असंतोष कम होता है. airports में भी ऐसा उदाहरण है कि passengers को gate से सीधे baggage belt तक भेजकर पहले bag के आने तक इंतज़ार कराने के बजाय, जानबूझकर लंबा और घुमावदार रास्ता बनाया गया; कुल समय वही रहा, फिर भी लोग ज़्यादा संतुष्ट थे
कई elevator algorithms में कुल wear and tear तथा maintenance cost पर अक्सर चर्चा नहीं होती
movement बढ़ने से hydraulic oil जल्दी बदलना पड़ सकता है और parts भी जल्दी ख़राब हो सकते हैं. efficient algorithms समय या दूसरे elevators की position के हिसाब से पहले से repositioning भी करते हैं; जैसे एक नीचे आ रहा हो तो दूसरे को ऊपर भेज देना. demand-signal आधारित algorithms ऐसी movement कम करते हैं. waiting time बढ़े तो भी maintenance घटाने वाला संतुलन महत्वपूर्ण है, और cost उठाने वाले building owners शायद passengers के waiting time को उतना महत्व न दें