Back in highschool, simulating different elevator algorithms was one of the projects I implemented during my CS class. It wasn't for the class — AP CS did not require anything like actual programming — but it was a fun project.
A cool connection is that a spinning-disk hard drive (HDD) is actually kind of like one really long elevator, just wrapped around a spindle instead of perfectly vertical. The SCAN algorithm is actually a disk-scheduling algorithm!
I wonder if this is an artifact of how the author used random destinations. I worked in a building that used Destination Dispatch, and the common travel pattern seemed to be:
- Everyone who is not on the ground floor generally want to go to the ground floor.
- People who are on the ground floor generally travel in large groups to the same destination.
This happens because people who worked on the same floor often leave for lunch at the same time, and return at the same time to the same floor. Destination Dispatch helps in this case because it's batching large groups of people with the same destination.
Yeah, and definitely is not the right story for hotels. His premise of "morning traffic mostly from lobby to floors" is completely false in an hotel where you get it both ways due to people going down for breakfast and going back up and the down once again.
I see hotels with the kiosk model changing the UI depending on breakfast rush hour
Yes, it's definitely more likely for an individual already in an upper floor to return to ground than a stop above or below. The people queuing up in simulations don't seemingly get this right all the time.
Also the group of people going to or returning from lunch is real as well. The grouping factor happens more at the middle of the day and less at the morning or evening. Primarily because of lunch.
Cruise ships that use destination dispatch have been much nicer too. Ships that use the older algorithms are a pain to wait during peak times. Guess plus side you’ll use the stairs more.
Is it because the criteria is wait time not travel time? Destination dispatch would avoid some extra stops on the trip.
I just visited a new building with destination dispatch, so it seems to be still around.
My EE roommate in college had to build an elevator circuit as a final problem. It was on a bread board and had a bunch of call buttons and had a motor and a clear disk with black squares so it could figure out where it was…. I think it was the simple algorithm…
Surely there's a dataset out there with elevator calls for an office building you could test on, instead of the poor random destination case.
Surprisingly, claude failed to find a good one.
Also, part of destination dispatch (I'm guessing based on experience) removes the 'stopping on every floor problem', so the real test would be total time including wait at that point I think.
I wish there were more games like this. It’s such a simple premise but so satisfyingly difficult after each level. And it even has a bit of randomish failure which makes for even more challenge.
If you buy the adorable monochrome console called the "Playdate" https://play.date it comes with a bunch of games included, including a cute elevator game where you help penguins to different floors while controlling the elevators yourself using the crank:
https://play.date/games/flipper-lifter/
Wow, I just came here to comment that I've always wondered if a game where you have to program an elevator scheduler would be any fun. I thought surely no-one's thought to make that before, too! Glad to be proven wrong.
I am amazed how in US closing elevator doors switch to opening if someone touches the door edge. This results in abusive behavior of people intentionally jamming their arms in the path of closing doors, and delaying everyone else inside the stopped elevator.
Hah, I thought a lot about this problem while developing Sky Lobby, a mobile game (iOS / Android) about controlling and automating elevators.
In the game, some of the elevators are automated, and I wanted to choose an algorithm that best aligned with what players would expect an elevator to do. I ended up going with something close to LOOK, which (as the article states) is mostly what people expect. Except in case of ambiguity, I had it prioritise floors that have been waiting longer, to improve the p90, which is important in the game.
But now, add in these challenges:
- double-deck cabs (where attached cabs cover two floors at once)
- transfer floors between shafts
- express shafts
and the best (or at least, most expected) algorithm becomes much less obvious! I'll leave it as an exercise for the reader to figure out the best one.
Luckily I was in charge of a game, not a real elevator system, so I just had to find a heuristic that was good-enough, and could tweak the rules to let players manually override the elevator's plan if they don't like where it's going. This seems to have satisfied most players.
Thanks for sharing this. I was just commenting about the challenge of making a fun elevator sim game. This looks great -- can't wait to play with it this weekend!
Thanks! Would love to hear your thoughts if you get a chance to play it. I'm currently working on adding a few more towers and challenges. After that maybe I'll deep-dive into the "best" automated scheduling algorithm for all this :)
Oh my god, every time I'm waiting for the elevator, I think of how annoying it must be to be someone who's building the algorithm to make sure that you minimize the amount of wait times between picking up people and taking them to their destination. Then I also wonder if the people who apply the logic and program the logic into the elevators are actually evil sadists that are doing it on purpose to make us wait longer enough and suffer a little extra.
> minimize the amount of wait times between picking up people and taking them to their destination
I wish elevators accounted for load.
I've been to a couple of larger conferences where on the Monday morning after, the hotel elevator was just hammered. Everyone wanted to go down, and the elevator would dutifully stop on every single floor no matter how full it was. If you were mobility disabled on the 2nd floor, you were basically fucked if you had a flight to catch.
One would think that, if it's a 10 person elevator and it's already stopped on 10 floors requesting it, that it could save an extra 5 minutes by just going directly to the ground floor, instead of stopping on every floor with the same conversation of "Oof, can't fit in there. I'll get the next one!"
I have done several third-party elevator integrations (software that talks to the elevator controller) for coordinating other equipment with the elevator. One thing that always struck me once I had full visibility into the location and motion of all the elevator cabs is how busily they are scheduled. Waiting in the elevator lobby for a cab seems to take forever, but viewed from the dispatch side, it is a flurry of activity and cabs are rarely idle during any hours the building is normally occupied. It is easy to nerd out just watching the status panel.
Another thing I learned: If an elevator mechanic says: "I'll meet you first thing in the morning." He means something like 4:00AM. They want to get in and out before people start arriving to start their day.
One other thing to add: It isn't the elevator scheduling software being obtuse, that software gets a huge amount of thought. But elevators are expensive, and building owners do not over-spend on a whim. Typically, they have just enough cabs (if that) to handle the expected load.
Not only that but different countries have code regimes that make more elevators especially expensive. See how building codes in the US basically ensure there are only two real manufacturers in the market vs a healthy ecosystem in others: https://youtu.be/Or1_qVdekYM
It's pretty much throughput. The cap-ex of a single cab swamps any other cost, so the only way to reduce total number of cabs is optimizing for throughput.
Modern elevators have regen braking, so they can recover most of the energy spent on going down. Older elevators used braking resistors for that.
(BTW, going _down_ while empty is typically more energy-consuming for the elevators because they are counterweighted)
Edit: that's also why you shouldn't use elevators in a fire. If the brakes in the elevator machine room fail, the cab won't crash down. It will go _up_, possibly dragging you into the fire. Many firefighters died because of that.
The biggest problem I always have with elevators is not the algorithm, it's the people seemingly being unable to grasp the concept of pressing either the up or the down request button, depending on where they want to go. Almost always I find someone will press both, because "then the elevator comes faster". Completely ignoring the fact that they end up going the wrong way first half the time, and adding an unnecessary halt for everyone already in there. How hard can it be to understand?..
My wife always randomly hits the up or down button, then gets upset if I explain why she should only pick the one she really wants. She forgets the next time. I think some people never really understand how elevators work.
See also: the keep open / close doors button. I had one building administrator explain to me we should add a delay of 10 seconds to the "quickly shut door" button because otherwise she kept getting her arm hit by the door. When I asked why we would add a delay to the button that's meant to reduce delays (why not simply wait for the door to close on its own, then?), and whether we should fix the sensor that prevents doors from closing if there's an obstacle instead, she just kept staring blankly at me. I don't think she understood me at all.
Again, some people simply don't grasp how elevators work.
Yeah and you can flail your head around looking for the arrow or you can just ask. Especially on a busy elevator lobby there might be multiple cars opening at the same time so you cant even tell from the ding/ding-ding
Sometimes I think "stupid" questions like these are just a way to break the ice, something that gets used to kindly acknowledge the momentary existence of others in our lives before we continue down our separate paths.
In situations like this the answer usually comes by flipping it and assuming they do understand, and asking why it makes sense now.
It's probably just the old 'fake loader' psychology, to be honest. Waiting without knowing when the elevator will arrive is boring/frustrating, where getting into an elevator that moves, even if the wrong direction, feels like progress.
Things are happening, and even if it takes longer ultimately that's a less frustrating state to be in.
In some places, I see people do that. It’s not stupidity. I learned the logical reason after observations. During busy hours in some busy buildings, there isn’t enough elevator capacity. Therefore, if you want to go down to the ground floor, taking a trip up and then down might be better (a less-bad worst case outcome, or even a better average outcome) than waiting for a non-full downward elevator. In such case, it’s logical to press both up and down.
Elevator algorithm I'm used to always goes up from lobby and always goes down from any other floor. Meaning that it goes all the way to the highest order and picks orders top-down until reaching lobby. Only exception is going to underground parking floors which is relatively rare in my housing complex.
When you're at a lower floor and you're trying to go down, but its a time period where traffic is trying to leave you can end up in a situation where nearly every elevator going down is already full. So you call for down, cab arrives but is already full, it goes, you call again, another comes, its already full, rinse/repeat. Sometimes there's not much up traffic during that time, so it can be a legit strategy to just go ahead and call on the up and ride it all the way instead of waiting and hoping for space coming down.
Although I guess that's not quite what you're talking about.
Aside for the algorithms and how well they work, there is a psychological aspect to how people perceive "wait" times. It turns out just waiting is very annoying. But having people do anything during that same wait period → perceived as progress → not upset.
An example iirc was waiting for luggage at the airport. It takes min of x minutes for the first bags to show. In one version, passengers went directly from the gate to the luggage carousel and waited x mins for the first bag → unhappy. Then the airport decided to add a long, round-about "walk" path from the gate to the luggage area that burned some of those minutes → same total "wait" but happier passengers.
I have destination dispatch at my office, and while I don't like my personal user-experience of it, I can't imagine what would better suit a building when you have so many elevators in the same place i.e. in my case 10+ I think?
What I find annoying though is you clunkily go click a floor then clunkily wait then clunkily walk over to the elevator assigned which may or may not be on the other end of the space. Also another interesting thing I've seen is that it seems in my case the distance from destination selection and elevator assigned seems to reduce at times when the office is emptier so that too seems to def be accounted into the algorithm.
Destination dispatch should be no worse than standard up/down buttons, right (at least in theory)? It provides additional information about the destination, but it should be possible for that information to be interpreted as if it were just an up/down button press, so RSR could still be used. I have a feeling a better algorithm could in fact make destination dispatch slightly better than RSR... or am I missing something?
Of course, user error is also a factor, so this isn't accounting for people not understanding how to use it and making things worse that way.
As the article says, the problem with destination dispatch is that it 'locks in' an elevator. The passenger gets told at call time what elevator to go to, and it can't change that mid flight. RSR has the advantage that the passenger has no idea which elevator will come, and so RSR can change the elevator they will get in real-time as conditions change. This was an insight I had not considered before reading the article.
The way I've seen it work is that there's a touch screen in the elevator lobby. You tap a floor, and then screen will say "Car C" (along with an audible message). The problem is that then the system can't reassign you to a different car after that. You'll typically have a bunch of different people going to a bunch of different floors, and there would be no reliable way to communicate to each individual their new assignment. Each car will also typically display which floors it's going to when it arrives. I suppose that, rather than assigning a car immediately, you could have passengers check cars as they arrive to see if they're going to their desired floor. Then the system could do reassignment, but people would be scrambling to check every car to see if it's the right one for them, and that's assuming that they understood the system. It would be way too chaotic in practice.
Little extra "fun" anecdote: my building has two banks of eight elevators, each servicing 20 or so floors, and has six destination dispatch kiosks: one at each end and the middle of each bank. The kiosks originally had nice metal buttons for each floor and you could easily tap yours as you walked by.
Sometime during Covid, the metal buttons were replaced with glass touch screens – which are totally unreadable on sunny days, because in our stunning glass-ceilinged atrium mezzanine they sit directly in sunbeams[0]. So now you have to walk up to the kiosk, shade it with your body, and squint at the screen to make out where to touch it.
You could give each one a diceware-eff-wordlist-like "ID" when they input where they want to go, perhaps have a "group" and "single" button/column per destination in the menu as well to inform the elevator if it's a group traveling together, and importantly have a fast-food-pickup-counter style dispatch screen up top visible from the waiting "hall", that assigns you a cab with an appropriate notice/heads-up period so you can make your way over to the assigned cab.
Display a set of floors on a big overhead screen (in floor order so they're easy to find), have the "elevator" column blank until the elevator is assigned, and let them watch the column that's going to show them which elevator to use.
But yes, this seems like a case of "unfortunately, people".
I think the problem with simulations like this is that it doesn't include the chaos of innatentive humans.
Forcing functions that dump people into well defined funnels can have such a high net positive effect it more than makes up for theoretical losses.
It's like narrow, hard road bike tires losing performance because of deflection from rough road surfaces and how long it took designers to factor that in to real bikes.
Kind of like airplane boarding. The ideal algorithm would be to make people board from back to front, and from window to aisle. However, people are not disciplined enough to strictly sort themselves, they won't all take the same time to sit, and some people want to board together (family with children for example).
Apparently, the fastest known way to fill up a plane in real-life conditions is to let people board in random order, without pre-assigning a seat.
In these various elevator algorithms, it's not commonly discussed the overall wear and tear on the elevator. More movements would typically translate to faster repair times. Hydraulic fluids needing to be replaced, parts breaking, etc.
Efficient elevator algorithms will often suggest moving an elevator into a preempted positioning strategy, based on time of day or peer elevator positions. The scheduler might move an elevator up to offset one coming down, for example. The demand-signal algorithms at least minimize movement in this way.
I think minimizing maintenance at the cost of increasing wait times is probably an important balance to get right. No doubt, the cost owners for maintenance are not going to perceive the wait time of passengers to be as important.
Someone needs to design an elevator that only breaks down between midnight and 5am. Maybe a different model to accommodate late night crowds returning to large residential buildings.
Slightly OT, but this reminded me of Colson Whitehead's _The Intuitionist_[1], an amazing speculative mystery novel about two dueling schools of elevator inspection philosophies: the Empiricists and the Intuitionists.
> After my lecture, a Maxis employee who shall remain nameless buttonholed me. "You guessed right," she said. "Sim Tower was built around a real elevator simulation program we bought from a Japanese guy."
This is commonly referred to as the "dial-a-ride" problem, which is an optimization problem with a multi-variate cost. Back in college for my senior design project we built a multi-axis closed loop servo system which would emulate a slide guitar. The dial-a-ride problem is identical to optimizing travel for a string of notes/chords.
It's worth noting that for roughly half of the last century, elevators were entirely controlled by relays, with no computers at all; these algorithms would be implemented in hardwired logic. Look at Otis' old patents for some interesting details, including schematics.
Oh wow, this is perfect reading for me. One of my first college career fair questions was "Tell me how you would program an elevator". Forgot what sad attempt at an answer I gave, but I pretty much thought about that algorithm every time I've ever waited for the elevator. Which was pretty much daily when living in NY.
This was fun to read and play with but I'd like to see it with different usage patterns, too.
The simulator seems to have passengers spawning on a random floor and then transiting to a different random floor. But for where I work, the trips are pretty much always from the lobby to a floor, or from a floor to the lobby. Nobody goes inbetween floors except maybe the cleaners.
No mention of an algorithm/sensor for checking capacity of the car. It's a pain when your elevator car shows, it's full, and your request is canceled, meaning you have to press again. Better if the car was full and just moved on.
I can see how that could be challenging when people get off on intermediate floors, making a full car available again, changing status. And, if 3 people are waiting and there is room for 1, should it stop or not? Etc.
My favorite takeaway from this is how simplicity often beats complexity.
I've never really liked Destination Dispatch elevators. Besides struggling to find the car I've been assigned to, sometimes you really have to hustle across the lobby to catch it. Then you also run into visitors that assume it's a normal car and can hit a floor button when the get in, only to realize they've walked into a car without buttons.
>Then you also run into visitors that assume it's a normal car and can hit a floor button when the get in, only to realize they've walked into a car without buttons.
I work in a building with Destination Dispatch elevators so I'm used to them. I have the opposite problem where I'll get into a normal elevator and just stand there without pushing anything.
What makes me more peeved about destination dispatch elevators are people who aren't used to them, and all pile into an elevator without hitting a floor, thinking one input is enough for everyone. Then, a totally full elevator stops at intermediate floors to pick up callers, but there's no room to get in. If everyone put the floor in as they arrive to the elevator lobby, then the elevator would know how many people are in the elevator and won't overfill them.
This is a fun simulation to play with. One variable I appreciate in efficient elevators is how the doors work. Usually they don't let you press the button to open a closing door - effectively delaying an already departing car
I am wondering where these more complex elevator algorithms are deployed, because I never see them.
I was recently at a Radisson hotel in Germany where I was tried to summon an car, but none would appear for a long time. I believe that someone was keeping the doors open on their floor to wait for someone. The fact that all the other elevators were passing by in both directions was actually a bit infuriating as well.
At that moment I really wished for an algorithm that would recognize when an car spent a significant amount of time on one floor and then reassign the other floors to a new elevator.
Our building installed destination dispatch system to their elevators and it seems to help overall. However, it breaks when say a team wants to get lunch together, but only one person presses the elevator button. The elevator thinks that it can keep on accepting new passengers so it stops at floors even though it's already full.
We used to do this as an interview question at my current job. We didn't expect people to solve it necessarily, and we just specified to solve for a single elevator car. We just wanted to see how people would break down the problem.
Even at that relatively reduced level of complexity, it's quite tricky to figure out how to prioritize who gets served when.
One case not covered, I believe I saw at London Heathrow was where 4 cars essentially moved people across only 2 floors. With only 1 centralized button, only 1-point-something car was effectively moving people on average, because people had to wait for the currently filled car to have its doors closed and starting to move, before hitting the button to call the next car to pick them up. Imaging 100-200 people in line and, often, overly eager would-be elevator passengers hitting the button too early. Thus leading to halting the just filled car and doing an additional full open and close doors cycle. Fun stuff!
Most importantly, after entering the elevator. First press the close button and then the floor. That way u, safe the time of pressing a button as the door is already closing.
You have no idea how excited I was to see this article today. I've long been fascinated with elevators and the algorithms that control them. Thank you!
Our elevator (4 cars) displays above each car the planned stops and can change mid-wait the car<>floor allocation and issue sound indication. I’d expect it to be allow optimal allocation.
User experience is not always correlated with metrics targeted by engineers.
I visit a building sometimes with destination dispatch elevators, and with low exposure across multiple years I'm confused every time the elevator I need to take is open behind me.
I once used the paternoster lift in Germany, beats any elevator algorithm efficiency because it's a non-stop "conveyor" with no doors. I still get nightmares about that elevator.
> This counterintuitive result is all thanks to the rebalancing step where every 5 seconds, the system re-optimizes each elevator's path. The kiosk enforces rigidity, you must get in the assigned elevator.
Sounds like destination dispatch would work better if it didn't tell you which elevator to get into until the elevator arrived.
I recently wrote an article about this problem, and detail one reasonable algo for minimizing wait time. (Doesn’t consider concept of cars being full though, interesting addition)
I feel like most cases of wait times are due to elevators "waiting" empty in the wrong floor. They either all wait in the bottom floor, or all wait where they were last left at. Would be better if their waiting floors were distributed throughout the floors so that first response is fast.
The problem is that in the morning the “last stop” for the elevator might be the lobby not a mid floor. And so it would have to move itself back up without any passengers or calls to upper floors. Basically “optimistically” moving itself back up. And I wonder if some (most?) control systems don’t do that because of… well I dunno. Lots of elevators have pretty old or basic control systems in them. Maybe predate caring about energy and many also probably aren’t strictly smart enough to be concerned about wear factors and stuff.
It could also be that you and I simply aren’t privy to what is actually happening “the instant” you are waiting for the elevator.
…which makes me wonder how often the firmware in these get updated. Assuming it’s not just a pile of ancient relays and stuff. And if, when they do get updated, the algorithms get improved. Or if the algorithm is something that gets sold to the building and “upgrading” is an actual purchase.
Anyway, I could get a little LLM buddy to look it all up but where is the fun in that?
I was on a Royal Caribbean ship a couple weeks ago (Utopia, 18 decks, 5,668 passengers). It has 24 main elevators split between front and back, left and right. So a bank of 6 in front of you each time you needed a lift. You press your floor on a touchpad and it assigns you an elevator A through F.
I swear no matter if it was busy or not, it seemed like everyone was assigned to the same one or two elevators. The wait was always so long too, I used the stairs most of the time if just going <6 flights.
Someone besides RCCL needs to study that algorithm.
Possibly to balance the hours on elevator banks. Common in buildings to leave some out of the cycle, since elevator maintenance can be a year out to schedule. Probably much worse out at sea
Disk drive read/write algorithms have a lot in common with elevator algorithms. At least they did in the days of physical heads moving across a platter.
I don't think it was mentioned, but the algorithm would be different based on the behavior of the majority. In some buildings most traffic is either up from lobby or down to lobby, e.g. it's very rare for people to go from floor 5 to floor 6. In some it's the other way around, where majority of moves don't involve lobby.
This is absolute catnip to me. Fantastic job to the author! It really scratches the itch of wanting to understand elevator dispatch algos!
I want something similar for advanced sensor stop lights...
I've long toyed with creating an elevator simulator game, but every time I build a prototype I realize it's not that fun to manually dispatch elevators, and playing with algos only goes so far! Elevator Saga is great for the programming side: https://play.elevatorsaga.com/
My friend lives in a building with one of those super old elevators with the manual double doors and no queuing. It's the sort of elevator that someone probably got paid to operate once upon a time.
Using such a primitive elevator gave me a newfound appreciation for the complexity of modern designs. The queueing algorithms are subtle but clever, and the difference in efficiency is instantly obvious once you've dealt with the alternative.
Parking is a big factor too. Where you put the elevator when it is not being used can mean the difference between the doors opening instantly and worst case scenario.
In a similar vein, there was an interesting discussion [0] a while back about elevator buttons [1] and how timing for door close/open works, along with a bit of the history and regulations that go into them.
If you optimize for initial wait times, someone who is going to a floor not usually visited might effectively get trapped on an elevator which shuttles between more trafficked floors to reduce wait for elevators overall. Maybe this is very unlikely in practice.
Is there a comprehensive overview of a) multi-bank elevator algorithms that are out there, b) the config parameters that the elevator tech/company can set on an elevator system?
For example, some elevators allow adjusting the door closing/opening speeds etc., I'd be curious what other things can be adjusted.
What this doesn't include: not all people are equal. Do you want the CEO of your new office building to have to wait behind a bunch of plebeians? At least one car is going to have to be reserved for the better people.
This does happen. I also once worked on a destination-dispatch elevator system installed in a high-end condo building (high-end, as in concierge and parking valet for residents). Anyway... the resident's key card would of course automatically call a cab to take them to their unit's floor, but also the security system had entries for things like "dog owner" and "allergic to dogs" so that the DD system would never schedule them together for the same cab.
My biggest pet peeve is elevator banks where they don’t make some number of idle elevators automatically come back to the lobby. Half your traffic is over there! Everyone coming in has to wait an extra minute or two because all your elevators were chilling on the 35th floor and above.
My apartment building is replacing the elevators, and someone on staff revealed that the first renovated elevator is intended to pick up only from the lobby (i.e. if you summon an elevator from the 10th floor, one of the others will come). This has caused some grumbling or calling it an "express elevator". In an apartment it really is mostly trips to many floors from the lobby. The only time this maybe would be inconvenient might be in the morning commute, when fewer people are re-entering.
You should observe if it is the same elevator all the time and the building people just don’t understand it. Our building elevators (bank of 2) always seems to try to keep one in the lobby. About 75% of the time you get an elevator right away when you call it from the lobby. But it definitely isn’t the same elevator! Allocating an exclusive single elevator to that function would seem to be strictly worse from many angles. Like if you modeled having an algorithm like “elevator 2 only services calls from the lobby” you’d find it would be very inefficient and not every effective. But I can see having one in the bank always returning to lobby right away making sense.
My guess is whoever hinted at that didn’t fully understand what they were taking about.
So many problems can be cast to arrays to be solved with various linear algebra.
Considering LLMs are "Level 1000+" puzzles in this analogy, I wonder if every problem could be represented by an n-dimensional vector and solvable with algebra.
They at least make great interview questions - Tic-Tac-Toe is commonly given, but is obvious. The board already "looks" like arrays. The less obvious ones, like elevators (or load balancing), are always interesting.
I think a small improvement that could be made is to have the dot representing the person be colored the same as a dot on each floor, which would obviate the destination floor for each individual.
If you like elevator hacking don’t forget the seminal DEF CON talk by Deviant Ollam and Howard Payne: https://youtu.be/oHf1vD5_b5I
I watch it like once a year because it always tickles some part of me. Like all the different modes you can get an elevator into. The most fancy one people might encounter is when moving into or out of a building. The front office can give you a key to give exclusive control over an elevator so your movers aren’t waiting around on elevators. Put it in that mode and it will stop responding to calls from other floors. Only the person with the key can control the elevator. You get on, select the floor, door closes elevator goes, and then just chills there with the door open waiting for you. Annoying for the rest if the building (the building is down an elevator when in that mode) but is amazing for the person using it! But there are way, way more depending on the installation and function.
Fun fact: most elevator shafts are sealed at the top as tight as possible to prevent them from becoming a giant chimney in a fire. It never even occurred to me until I was in a mechanical room wondering “where is the hatch to look down the shaft?” The answer is “there is none, and it’s a feature not a bug.” You want to block all airflow so fire doesn’t chase up the shaft into neighboring floors. Who knew!
Lol, love this post. Every single day when I take the elevators at the office I try and figure out what the algorithm is behind it. Been too lazy to just research it. Now I know!
Over the years, I've witnessed numerous instances of poor elevator behavior:
- Two elevators ascending and descending in near lock step, in a two-elevator building, effectively reduced to one elevator.
- When going in a different direction from the requested one (e.g. called elevator to go up, but actually going down), the doors wastefully close, open and close again. Seen this in many elevators.
- At 3 a.m. you take the elevator to a parkade, like to get something from a car. When you return to the elevator a minute later, it is gone; it spontaneously moved away even though nobody is using it but you.
The question about designing elevators used to be the mainstay of programming job interviews. I had an annoying interview where I was asked, for the umpteens time to design an elevator. I already made up my mind at the time, knowing I'm not going to work for the company, but decided to have a... unexpected approach.
So, for instance, I didn't measure the elevator's efficiency in the wait time. I included (weighted) travel time. I assumed LOOK algorithm was used. And then when I tried to calculate various outcomes for different trips I suddenly realized that elevator's efficiency and fairness seem to go different ways.
Without trying to reproduce my evaluation system, here's my finding in fewer details: if you have two passengers, one going from the ground floor to the top floor and other joining for the shorter ride down in the middle, then the elevator that makes a "detour" is more efficient, but it hardly seems fair that the passenger traveling ground floor to the top should go even a single floor in the opposite direction.
Somehow, until that point, I lived with an illusion that the most efficient solution to a problem must be the most fair to every participant. Discovering this counterexample sent me on the "tour of discovery" of ethics and different philosophers who contributed to it... and while in the end it made me none the wiser, I'm happy to have discovered this field.
As someone who lives in a penthouse, elevator’s frustrations are real struggle especially in rush hours, because the elevator has to travel dedicated to you rather than you piggy backing on one that is already going up or down.
Having gone to many large furry cons(notoriously brutal on the elevators due to how much floor-to-floor traffic there is compared to other usage) I’ve seen these algos basically completely fail to adapt to unusual patterns. I once spent over half an hour on checkout day, in a hotel with 8 banks, to even have a car stop on our floor at all. Can’t really blame the algo for such a unique situation and at the end of the day a saturated system is a saturated system and nothing can be done to make it fast, but it’s always interesting to witness when a system is completely unable to accommodate a demand like that.
(In the example above we gave up and decided it was cardio time, five laps up and down 14 flights to escape with all our luggage.)
I can't say I have. The only 2 times I have been frustrated at an elevator are when I was in one and the door wouldn't shut, and the other was when had someone pressed the emergency stop so I couldn't use it.
At a previous employer we had heteregenous elevators. In one bank, some went to the lower half of floors only while others went to all and the company installed a "smart" elevator system. I kind of became known because I was constantly yelling about this system in the feedback group because I hate "smart" elevators and and (IMHO) they just don't work. What actually works is express elevators and sky lobbies.
This article covers one of the deficiencies this system had: full elevators. For example, you'd want to go down and an elevator would skip your floor because another had already been assigned. That one would show up full and you couldn't go down. Down wasn't so bad because the stairs weren't a bad option but up was terrible. Going up a few floors was fine. Going up 20 was... a bigger issue.
Back in the day we had elevator operators and people in the lobby during the morning rush who would shepherd people into particular elevators. I actually think this system works way better than anything technology has come up with. Even if you nail the implementation (and I've never experienced elevators that have), people don't read and will just get into elevators anyway.
Anyway the article says that generally speaking on smaller banks simple up and down buttons work best. I absolutely agree.
There's a deeper issue here though and that is solutions looking for a problem. Nobody is making money from up and down buttons. They are fromn selling smart elevator solutions. And you see this everywhere in life. It basically devolves into rent-seeking behavior. Salespeople wine and dine a couple of people responsible for making decisions and then make bank on selling something nobody wants or needs as well as the constant maintenance and updates.
I think this comparison is also assuming the distribution of request & requested floor is uniform? When actually near pairs are less likely (I'll just take the stairs) than bottom to top, so even analysing it is more complex than at first glance.
Back in highschool, simulating different elevator algorithms was one of the projects I implemented during my CS class. It wasn't for the class — AP CS did not require anything like actual programming — but it was a fun project.
A cool connection is that a spinning-disk hard drive (HDD) is actually kind of like one really long elevator, just wrapped around a spindle instead of perfectly vertical. The SCAN algorithm is actually a disk-scheduling algorithm!
https://en.wikipedia.org/wiki/Elevator_algorithm
We did this in college as well using microcontrollers and leds or something - i forget the exact details. It was super fun
> Destination Dispatch [...] are in general worse
I wonder if this is an artifact of how the author used random destinations. I worked in a building that used Destination Dispatch, and the common travel pattern seemed to be:
- Everyone who is not on the ground floor generally want to go to the ground floor.
- People who are on the ground floor generally travel in large groups to the same destination.
This happens because people who worked on the same floor often leave for lunch at the same time, and return at the same time to the same floor. Destination Dispatch helps in this case because it's batching large groups of people with the same destination.
Yeah, and definitely is not the right story for hotels. His premise of "morning traffic mostly from lobby to floors" is completely false in an hotel where you get it both ways due to people going down for breakfast and going back up and the down once again.
I see hotels with the kiosk model changing the UI depending on breakfast rush hour
Yes, it's definitely more likely for an individual already in an upper floor to return to ground than a stop above or below. The people queuing up in simulations don't seemingly get this right all the time.
Also the group of people going to or returning from lunch is real as well. The grouping factor happens more at the middle of the day and less at the morning or evening. Primarily because of lunch.
Cruise ships that use destination dispatch have been much nicer too. Ships that use the older algorithms are a pain to wait during peak times. Guess plus side you’ll use the stairs more.
> - People who are on the ground floor generally travel in large groups to the same destination.
I also thought that this is one of the biggest reasons destination dispatch was better.
There are even articles about switching to destination dispatch in office buildings or hotels lead to dramatic reductions in wait time.
Is it because the criteria is wait time not travel time? Destination dispatch would avoid some extra stops on the trip.
I just visited a new building with destination dispatch, so it seems to be still around.
My EE roommate in college had to build an elevator circuit as a final problem. It was on a bread board and had a bunch of call buttons and had a motor and a clear disk with black squares so it could figure out where it was…. I think it was the simple algorithm…
Surely there's a dataset out there with elevator calls for an office building you could test on, instead of the poor random destination case.
Surprisingly, claude failed to find a good one.
Also, part of destination dispatch (I'm guessing based on experience) removes the 'stopping on every floor problem', so the real test would be total time including wait at that point I think.
For folks that have never seen elevator scheduling the game: https://play.elevatorsaga.com/ Enjoy this rabbit hole :D
I wish there were more games like this. It’s such a simple premise but so satisfyingly difficult after each level. And it even has a bit of randomish failure which makes for even more challenge.
If you buy the adorable monochrome console called the "Playdate" https://play.date it comes with a bunch of games included, including a cute elevator game where you help penguins to different floors while controlling the elevators yourself using the crank: https://play.date/games/flipper-lifter/
You will like https://www.zachtronics.com/
at a quick glance, it reminds me of "the farmer was replaced", if you havent seen/heard of that one
https://store.steampowered.com/app/2060160/The_Farmer_Was_Re...
I remember this one, it deserves all sorts of praise
I can also recommend https://store.steampowered.com/app/375820/Human_Resource_Mac...
and its sequel is also worth a mention https://store.steampowered.com/app/792100/7_Billion_Humans/
but imo, unlike farmer, these games reaaaaly lack the ability to make functions/subroutines
manually doing all the goto loops becomes tiring
looks very well made, but I still prefer https://en.wikipedia.org/wiki/Elevator_Action !
This is great, but to me, the definitive elevator scheduling game was SimTower.
Sid Meier's Elevator Manager was such a great game... so much nostalgia.
I always come back to this game whenever I'm at a hotel for a conference waiting for the elevator.
Wow, I just came here to comment that I've always wondered if a game where you have to program an elevator scheduler would be any fun. I thought surely no-one's thought to make that before, too! Glad to be proven wrong.
I am amazed how in US closing elevator doors switch to opening if someone touches the door edge. This results in abusive behavior of people intentionally jamming their arms in the path of closing doors, and delaying everyone else inside the stopped elevator.
That's the case with most elevator doors, worldwide...? If you put your hand in a closing elevator door, it's supposed to open again.
Every time I enter an elevator, I wonder whether it will be the first one I've come across that supports deselect.
Hah, I thought a lot about this problem while developing Sky Lobby, a mobile game (iOS / Android) about controlling and automating elevators.
In the game, some of the elevators are automated, and I wanted to choose an algorithm that best aligned with what players would expect an elevator to do. I ended up going with something close to LOOK, which (as the article states) is mostly what people expect. Except in case of ambiguity, I had it prioritise floors that have been waiting longer, to improve the p90, which is important in the game.
But now, add in these challenges:
- double-deck cabs (where attached cabs cover two floors at once)
- transfer floors between shafts
- express shafts
and the best (or at least, most expected) algorithm becomes much less obvious! I'll leave it as an exercise for the reader to figure out the best one.
Luckily I was in charge of a game, not a real elevator system, so I just had to find a heuristic that was good-enough, and could tweak the rules to let players manually override the elevator's plan if they don't like where it's going. This seems to have satisfied most players.
Thanks for sharing this. I was just commenting about the challenge of making a fun elevator sim game. This looks great -- can't wait to play with it this weekend!
Thanks! Would love to hear your thoughts if you get a chance to play it. I'm currently working on adding a few more towers and challenges. After that maybe I'll deep-dive into the "best" automated scheduling algorithm for all this :)
I currently work in one of the top global incumbent company in the elevator market in R&D software.
I would have never thought there were so many challenges behind a car moving up & down.
This industry is so niche and peculiar.
Elevator trip scheduling is one of the many challenges. Really a great experience so far
Oh my god, every time I'm waiting for the elevator, I think of how annoying it must be to be someone who's building the algorithm to make sure that you minimize the amount of wait times between picking up people and taking them to their destination. Then I also wonder if the people who apply the logic and program the logic into the elevators are actually evil sadists that are doing it on purpose to make us wait longer enough and suffer a little extra.
> minimize the amount of wait times between picking up people and taking them to their destination
I wish elevators accounted for load.
I've been to a couple of larger conferences where on the Monday morning after, the hotel elevator was just hammered. Everyone wanted to go down, and the elevator would dutifully stop on every single floor no matter how full it was. If you were mobility disabled on the 2nd floor, you were basically fucked if you had a flight to catch.
One would think that, if it's a 10 person elevator and it's already stopped on 10 floors requesting it, that it could save an extra 5 minutes by just going directly to the ground floor, instead of stopping on every floor with the same conversation of "Oof, can't fit in there. I'll get the next one!"
The article describes the RSR algo which takes load into account.
In that case, would it pay to call for an elevator going up, and then remain on it until it's being called down?
I have done several third-party elevator integrations (software that talks to the elevator controller) for coordinating other equipment with the elevator. One thing that always struck me once I had full visibility into the location and motion of all the elevator cabs is how busily they are scheduled. Waiting in the elevator lobby for a cab seems to take forever, but viewed from the dispatch side, it is a flurry of activity and cabs are rarely idle during any hours the building is normally occupied. It is easy to nerd out just watching the status panel.
Another thing I learned: If an elevator mechanic says: "I'll meet you first thing in the morning." He means something like 4:00AM. They want to get in and out before people start arriving to start their day.
One other thing to add: It isn't the elevator scheduling software being obtuse, that software gets a huge amount of thought. But elevators are expensive, and building owners do not over-spend on a whim. Typically, they have just enough cabs (if that) to handle the expected load.
Not only that but different countries have code regimes that make more elevators especially expensive. See how building codes in the US basically ensure there are only two real manufacturers in the market vs a healthy ecosystem in others: https://youtu.be/Or1_qVdekYM
They might have other objective functions like wear-and-tear on the elevators, total energy usage, or something
It's pretty much throughput. The cap-ex of a single cab swamps any other cost, so the only way to reduce total number of cabs is optimizing for throughput.
Modern elevators have regen braking, so they can recover most of the energy spent on going down. Older elevators used braking resistors for that.
(BTW, going _down_ while empty is typically more energy-consuming for the elevators because they are counterweighted)
Edit: that's also why you shouldn't use elevators in a fire. If the brakes in the elevator machine room fail, the cab won't crash down. It will go _up_, possibly dragging you into the fire. Many firefighters died because of that.
The biggest problem I always have with elevators is not the algorithm, it's the people seemingly being unable to grasp the concept of pressing either the up or the down request button, depending on where they want to go. Almost always I find someone will press both, because "then the elevator comes faster". Completely ignoring the fact that they end up going the wrong way first half the time, and adding an unnecessary halt for everyone already in there. How hard can it be to understand?..
I don't think I've ever seen someone do that
I haven't ever seen anyone do this in the United States, but I saw it in China and Italy.
I've never seen anyone do this anywhere in the world including Italy.
I've never been to China but wouldn't you learn quickly after getting in an elevator going the wrong way not to do that again?
The only exception I can see if there's way more people than elevators and you just need to get spot at all costs.
My wife always randomly hits the up or down button, then gets upset if I explain why she should only pick the one she really wants. She forgets the next time. I think some people never really understand how elevators work.
See also: the keep open / close doors button. I had one building administrator explain to me we should add a delay of 10 seconds to the "quickly shut door" button because otherwise she kept getting her arm hit by the door. When I asked why we would add a delay to the button that's meant to reduce delays (why not simply wait for the door to close on its own, then?), and whether we should fix the sensor that prevents doors from closing if there's an obstacle instead, she just kept staring blankly at me. I don't think she understood me at all.
Again, some people simply don't grasp how elevators work.
I fear in both cases, its not a lack of understanding of elevators but of common sense...
Because most buildings now they just put one button so people stop clicking both
That has not been my experience, and logically it doesn't really make much sense. If you do so, you are making the problem strictly worse.
What? I’ve never seen that. The elevator needs to know which way you want to go.
i just saw this for the first time today in Romania...
On the ground/lowest floor, there's only one button as there's only one way to go.
And then when the elevator door opens, they ask the people inside: "Are you going up or down?" There's an arrow showing that, for Christ's sake.
Yeah and you can flail your head around looking for the arrow or you can just ask. Especially on a busy elevator lobby there might be multiple cars opening at the same time so you cant even tell from the ding/ding-ding
True but sometimes someone hits a button on the inside by mistake. Or someone was going to get off then decides not to.
Sometimes I think "stupid" questions like these are just a way to break the ice, something that gets used to kindly acknowledge the momentary existence of others in our lives before we continue down our separate paths.
… and the elevator is still going the way it is going, and that way is still indicated by the illuminated arrow.
"Questions are never indiscreet. Answers sometimes are."
"Have you stopped urinating in public?"
In situations like this the answer usually comes by flipping it and assuming they do understand, and asking why it makes sense now.
It's probably just the old 'fake loader' psychology, to be honest. Waiting without knowing when the elevator will arrive is boring/frustrating, where getting into an elevator that moves, even if the wrong direction, feels like progress.
Things are happening, and even if it takes longer ultimately that's a less frustrating state to be in.
In some places, I see people do that. It’s not stupidity. I learned the logical reason after observations. During busy hours in some busy buildings, there isn’t enough elevator capacity. Therefore, if you want to go down to the ground floor, taking a trip up and then down might be better (a less-bad worst case outcome, or even a better average outcome) than waiting for a non-full downward elevator. In such case, it’s logical to press both up and down.
Elevator algorithm I'm used to always goes up from lobby and always goes down from any other floor. Meaning that it goes all the way to the highest order and picks orders top-down until reaching lobby. Only exception is going to underground parking floors which is relatively rare in my housing complex.
When you're at a lower floor and you're trying to go down, but its a time period where traffic is trying to leave you can end up in a situation where nearly every elevator going down is already full. So you call for down, cab arrives but is already full, it goes, you call again, another comes, its already full, rinse/repeat. Sometimes there's not much up traffic during that time, so it can be a legit strategy to just go ahead and call on the up and ride it all the way instead of waiting and hoping for space coming down.
Although I guess that's not quite what you're talking about.
Aside for the algorithms and how well they work, there is a psychological aspect to how people perceive "wait" times. It turns out just waiting is very annoying. But having people do anything during that same wait period → perceived as progress → not upset.
An example iirc was waiting for luggage at the airport. It takes min of x minutes for the first bags to show. In one version, passengers went directly from the gate to the luggage carousel and waited x mins for the first bag → unhappy. Then the airport decided to add a long, round-about "walk" path from the gate to the luggage area that burned some of those minutes → same total "wait" but happier passengers.
I have destination dispatch at my office, and while I don't like my personal user-experience of it, I can't imagine what would better suit a building when you have so many elevators in the same place i.e. in my case 10+ I think?
What I find annoying though is you clunkily go click a floor then clunkily wait then clunkily walk over to the elevator assigned which may or may not be on the other end of the space. Also another interesting thing I've seen is that it seems in my case the distance from destination selection and elevator assigned seems to reduce at times when the office is emptier so that too seems to def be accounted into the algorithm.
Destination dispatch should be no worse than standard up/down buttons, right (at least in theory)? It provides additional information about the destination, but it should be possible for that information to be interpreted as if it were just an up/down button press, so RSR could still be used. I have a feeling a better algorithm could in fact make destination dispatch slightly better than RSR... or am I missing something?
Of course, user error is also a factor, so this isn't accounting for people not understanding how to use it and making things worse that way.
As the article says, the problem with destination dispatch is that it 'locks in' an elevator. The passenger gets told at call time what elevator to go to, and it can't change that mid flight. RSR has the advantage that the passenger has no idea which elevator will come, and so RSR can change the elevator they will get in real-time as conditions change. This was an insight I had not considered before reading the article.
That sounds like two separate things then. Could you not have people select a destination without locking in an elevator?
(I've never encountered destination dispatch myself, so I'm not really sure how it works in practice)
The way I've seen it work is that there's a touch screen in the elevator lobby. You tap a floor, and then screen will say "Car C" (along with an audible message). The problem is that then the system can't reassign you to a different car after that. You'll typically have a bunch of different people going to a bunch of different floors, and there would be no reliable way to communicate to each individual their new assignment. Each car will also typically display which floors it's going to when it arrives. I suppose that, rather than assigning a car immediately, you could have passengers check cars as they arrive to see if they're going to their desired floor. Then the system could do reassignment, but people would be scrambling to check every car to see if it's the right one for them, and that's assuming that they understood the system. It would be way too chaotic in practice.
Little extra "fun" anecdote: my building has two banks of eight elevators, each servicing 20 or so floors, and has six destination dispatch kiosks: one at each end and the middle of each bank. The kiosks originally had nice metal buttons for each floor and you could easily tap yours as you walked by.
Sometime during Covid, the metal buttons were replaced with glass touch screens – which are totally unreadable on sunny days, because in our stunning glass-ceilinged atrium mezzanine they sit directly in sunbeams[0]. So now you have to walk up to the kiosk, shade it with your body, and squint at the screen to make out where to touch it.
[0] http://www.angel.net/~nic/photos/elevators.jpg
You could give each one a diceware-eff-wordlist-like "ID" when they input where they want to go, perhaps have a "group" and "single" button/column per destination in the menu as well to inform the elevator if it's a group traveling together, and importantly have a fast-food-pickup-counter style dispatch screen up top visible from the waiting "hall", that assigns you a cab with an appropriate notice/heads-up period so you can make your way over to the assigned cab.
Display a set of floors on a big overhead screen (in floor order so they're easy to find), have the "elevator" column blank until the elevator is assigned, and let them watch the column that's going to show them which elevator to use.
But yes, this seems like a case of "unfortunately, people".
After visiting a hospital with like 5 floors and 2 elevators people were having a hell of a time with just 'going up ' or down arrows
Thanks for the context. That makes sense.
I think the problem with simulations like this is that it doesn't include the chaos of innatentive humans.
Forcing functions that dump people into well defined funnels can have such a high net positive effect it more than makes up for theoretical losses.
It's like narrow, hard road bike tires losing performance because of deflection from rough road surfaces and how long it took designers to factor that in to real bikes.
Kind of like airplane boarding. The ideal algorithm would be to make people board from back to front, and from window to aisle. However, people are not disciplined enough to strictly sort themselves, they won't all take the same time to sit, and some people want to board together (family with children for example).
Apparently, the fastest known way to fill up a plane in real-life conditions is to let people board in random order, without pre-assigning a seat.
In these various elevator algorithms, it's not commonly discussed the overall wear and tear on the elevator. More movements would typically translate to faster repair times. Hydraulic fluids needing to be replaced, parts breaking, etc.
Efficient elevator algorithms will often suggest moving an elevator into a preempted positioning strategy, based on time of day or peer elevator positions. The scheduler might move an elevator up to offset one coming down, for example. The demand-signal algorithms at least minimize movement in this way.
I think minimizing maintenance at the cost of increasing wait times is probably an important balance to get right. No doubt, the cost owners for maintenance are not going to perceive the wait time of passengers to be as important.
Not to mention maintenance means taking an elevator out of service, meaning average wait times go up during that period.
Someone needs to design an elevator that only breaks down between midnight and 5am. Maybe a different model to accommodate late night crowds returning to large residential buildings.
Slightly OT, but this reminded me of Colson Whitehead's _The Intuitionist_[1], an amazing speculative mystery novel about two dueling schools of elevator inspection philosophies: the Empiricists and the Intuitionists.
1. https://en.wikipedia.org/wiki/The_Intuitionist
Makes me want to play Sim Tower again.
There’s something so satisfying about watching a machine just dutifully work through queued tasks like this.
A fun tidbit about Sim Tower:
> After my lecture, a Maxis employee who shall remain nameless buttonholed me. "You guessed right," she said. "Sim Tower was built around a real elevator simulation program we bought from a Japanese guy."
https://web.archive.org/web/20090916193335/http://www.gamasu...
Would that be Yoot Saito? I remember his name on the box.
If you liked SimTower, Project Highrise is worth taking a look into.
https://store.steampowered.com/app/423580/Project_Highrise/
Project Highrise doesn't have elevator simulation. Elevator is just portal that teleports the sim to proper floor.
I had another game in mind.
https://archive.org/details/elevator_nes
This is commonly referred to as the "dial-a-ride" problem, which is an optimization problem with a multi-variate cost. Back in college for my senior design project we built a multi-axis closed loop servo system which would emulate a slide guitar. The dial-a-ride problem is identical to optimizing travel for a string of notes/chords.
It's worth noting that for roughly half of the last century, elevators were entirely controlled by relays, with no computers at all; these algorithms would be implemented in hardwired logic. Look at Otis' old patents for some interesting details, including schematics.
Oh wow, this is perfect reading for me. One of my first college career fair questions was "Tell me how you would program an elevator". Forgot what sad attempt at an answer I gave, but I pretty much thought about that algorithm every time I've ever waited for the elevator. Which was pretty much daily when living in NY.
This was fun to read and play with but I'd like to see it with different usage patterns, too.
The simulator seems to have passengers spawning on a random floor and then transiting to a different random floor. But for where I work, the trips are pretty much always from the lobby to a floor, or from a floor to the lobby. Nobody goes inbetween floors except maybe the cleaners.
No mention of an algorithm/sensor for checking capacity of the car. It's a pain when your elevator car shows, it's full, and your request is canceled, meaning you have to press again. Better if the car was full and just moved on.
I can see how that could be challenging when people get off on intermediate floors, making a full car available again, changing status. And, if 3 people are waiting and there is room for 1, should it stop or not? Etc.
My favorite takeaway from this is how simplicity often beats complexity.
Load penalty is part of the Otis RSR algorithm, it's in the article.
The elevator rabbit hole:
Deviant Ollam on Elevator Hacking https://youtu.be/ZUvGfuLlZus
I've never really liked Destination Dispatch elevators. Besides struggling to find the car I've been assigned to, sometimes you really have to hustle across the lobby to catch it. Then you also run into visitors that assume it's a normal car and can hit a floor button when the get in, only to realize they've walked into a car without buttons.
>Then you also run into visitors that assume it's a normal car and can hit a floor button when the get in, only to realize they've walked into a car without buttons.
I work in a building with Destination Dispatch elevators so I'm used to them. I have the opposite problem where I'll get into a normal elevator and just stand there without pushing anything.
What makes me more peeved about destination dispatch elevators are people who aren't used to them, and all pile into an elevator without hitting a floor, thinking one input is enough for everyone. Then, a totally full elevator stops at intermediate floors to pick up callers, but there's no room to get in. If everyone put the floor in as they arrive to the elevator lobby, then the elevator would know how many people are in the elevator and won't overfill them.
The elevators I've seen have a "group call" feature slightly hidden in the menu.
That’s awesome! I haven’t really played with them, only silently seethed when the elevator is crowded.
This is a fun simulation to play with. One variable I appreciate in efficient elevators is how the doors work. Usually they don't let you press the button to open a closing door - effectively delaying an already departing car
There are some awesome hacker talks about elevators on YouTube worth checking out
I am wondering where these more complex elevator algorithms are deployed, because I never see them.
I was recently at a Radisson hotel in Germany where I was tried to summon an car, but none would appear for a long time. I believe that someone was keeping the doors open on their floor to wait for someone. The fact that all the other elevators were passing by in both directions was actually a bit infuriating as well.
At that moment I really wished for an algorithm that would recognize when an car spent a significant amount of time on one floor and then reassign the other floors to a new elevator.
Our building installed destination dispatch system to their elevators and it seems to help overall. However, it breaks when say a team wants to get lunch together, but only one person presses the elevator button. The elevator thinks that it can keep on accepting new passengers so it stops at floors even though it's already full.
We used to do this as an interview question at my current job. We didn't expect people to solve it necessarily, and we just specified to solve for a single elevator car. We just wanted to see how people would break down the problem.
Even at that relatively reduced level of complexity, it's quite tricky to figure out how to prioritize who gets served when.
One case not covered, I believe I saw at London Heathrow was where 4 cars essentially moved people across only 2 floors. With only 1 centralized button, only 1-point-something car was effectively moving people on average, because people had to wait for the currently filled car to have its doors closed and starting to move, before hitting the button to call the next car to pick them up. Imaging 100-200 people in line and, often, overly eager would-be elevator passengers hitting the button too early. Thus leading to halting the just filled car and doing an additional full open and close doors cycle. Fun stuff!
Most importantly, after entering the elevator. First press the close button and then the floor. That way u, safe the time of pressing a button as the door is already closing.
You have no idea how excited I was to see this article today. I've long been fascinated with elevators and the algorithms that control them. Thank you!
Our elevator (4 cars) displays above each car the planned stops and can change mid-wait the car<>floor allocation and issue sound indication. I’d expect it to be allow optimal allocation.
User experience is not always correlated with metrics targeted by engineers.
I visit a building sometimes with destination dispatch elevators, and with low exposure across multiple years I'm confused every time the elevator I need to take is open behind me.
I once used the paternoster lift in Germany, beats any elevator algorithm efficiency because it's a non-stop "conveyor" with no doors. I still get nightmares about that elevator.
> This counterintuitive result is all thanks to the rebalancing step where every 5 seconds, the system re-optimizes each elevator's path. The kiosk enforces rigidity, you must get in the assigned elevator.
Sounds like destination dispatch would work better if it didn't tell you which elevator to get into until the elevator arrived.
EDIT: already being discussed in the thread at https://news.ycombinator.com/item?id=49125423
Reminds of something I haven't thought about in a very long time... SimTower
This is like the how it’s made of a website. I could read and click through an endless amount of these kinds of explainers.
I recently wrote an article about this problem, and detail one reasonable algo for minimizing wait time. (Doesn’t consider concept of cars being full though, interesting addition)
https://jslandy.com/elevators/
I feel like most cases of wait times are due to elevators "waiting" empty in the wrong floor. They either all wait in the bottom floor, or all wait where they were last left at. Would be better if their waiting floors were distributed throughout the floors so that first response is fast.
In the middle or end of the day, yes. In the morning, waiting on the bottom floor is the best.
Unless you're a hotel. Then the timing is flipped: Wait in a distributed manner in the morning/mid-day, gather on the floor in the evening.
The problem is that in the morning the “last stop” for the elevator might be the lobby not a mid floor. And so it would have to move itself back up without any passengers or calls to upper floors. Basically “optimistically” moving itself back up. And I wonder if some (most?) control systems don’t do that because of… well I dunno. Lots of elevators have pretty old or basic control systems in them. Maybe predate caring about energy and many also probably aren’t strictly smart enough to be concerned about wear factors and stuff.
It could also be that you and I simply aren’t privy to what is actually happening “the instant” you are waiting for the elevator.
…which makes me wonder how often the firmware in these get updated. Assuming it’s not just a pile of ancient relays and stuff. And if, when they do get updated, the algorithms get improved. Or if the algorithm is something that gets sold to the building and “upgrading” is an actual purchase.
Anyway, I could get a little LLM buddy to look it all up but where is the fun in that?
Most systems to that. Empty-cab strategy is a programming option in the controller. If all cabs are idle (very rare) they are typically spread out.
Yes! I always thought that, when unused, elevators should distribute themselves along the floors, weighted by the floors that use them the most.
I was on a Royal Caribbean ship a couple weeks ago (Utopia, 18 decks, 5,668 passengers). It has 24 main elevators split between front and back, left and right. So a bank of 6 in front of you each time you needed a lift. You press your floor on a touchpad and it assigns you an elevator A through F.
I swear no matter if it was busy or not, it seemed like everyone was assigned to the same one or two elevators. The wait was always so long too, I used the stairs most of the time if just going <6 flights.
Someone besides RCCL needs to study that algorithm.
Possibly to balance the hours on elevator banks. Common in buildings to leave some out of the cycle, since elevator maintenance can be a year out to schedule. Probably much worse out at sea
This type of system is mentioned in the article under the "Destination Dispatch" section.
One of the most frustrating assignments[1] (2011) in my computer science education was trying to build a better mousetrap for elevator control.
[1]: https://clarkmoody.com/Moody_AgentBasedElevatorControl.pdf
Disk drive read/write algorithms have a lot in common with elevator algorithms. At least they did in the days of physical heads moving across a platter.
Ahhh brings back memories of "Elevators from Hell" [1]
Now maybe I can beat that game!
1. https://www.dosgames.com/game/elevators-from-hell/
I don't think it was mentioned, but the algorithm would be different based on the behavior of the majority. In some buildings most traffic is either up from lobby or down to lobby, e.g. it's very rare for people to go from floor 5 to floor 6. In some it's the other way around, where majority of moves don't involve lobby.
This is absolute catnip to me. Fantastic job to the author! It really scratches the itch of wanting to understand elevator dispatch algos!
I want something similar for advanced sensor stop lights...
I've long toyed with creating an elevator simulator game, but every time I build a prototype I realize it's not that fun to manually dispatch elevators, and playing with algos only goes so far! Elevator Saga is great for the programming side: https://play.elevatorsaga.com/
This reminds me of elevator saga (https://play.elevatorsaga.com/) - little programming game where you have to program elevator schedules.
My friend lives in a building with one of those super old elevators with the manual double doors and no queuing. It's the sort of elevator that someone probably got paid to operate once upon a time.
Using such a primitive elevator gave me a newfound appreciation for the complexity of modern designs. The queueing algorithms are subtle but clever, and the difference in efficiency is instantly obvious once you've dealt with the alternative.
Parking is a big factor too. Where you put the elevator when it is not being used can mean the difference between the doors opening instantly and worst case scenario.
In a similar vein, there was an interesting discussion [0] a while back about elevator buttons [1] and how timing for door close/open works, along with a bit of the history and regulations that go into them.
0: https://news.ycombinator.com/item?id=35152341
1: https://computer.rip/2023-03-13-the-door-close-button.html
And there's still no adequate explanation for what "Korean lunch mode" is!
I wonder how a TWIN system with 2 cars per shaft factors in here: https://www.tkelevator.com/us-en/products/elevators/all-elev...
That will need planning and assignment I guess? But at what load figures does it become more efficient?
Anybody knows what algorithm HITACHI is using on their elevators? Their elevators feels most “responsive” in high rises.
It also depends on the person understanding what the elevator button does: https://blog.jgc.org/2010/06/elevator-button-problem.html
If you optimize for initial wait times, someone who is going to a floor not usually visited might effectively get trapped on an elevator which shuttles between more trafficked floors to reduce wait for elevators overall. Maybe this is very unlikely in practice.
Is there a comprehensive overview of a) multi-bank elevator algorithms that are out there, b) the config parameters that the elevator tech/company can set on an elevator system?
For example, some elevators allow adjusting the door closing/opening speeds etc., I'd be curious what other things can be adjusted.
What this doesn't include: not all people are equal. Do you want the CEO of your new office building to have to wait behind a bunch of plebeians? At least one car is going to have to be reserved for the better people.
This does happen. I also once worked on a destination-dispatch elevator system installed in a high-end condo building (high-end, as in concierge and parking valet for residents). Anyway... the resident's key card would of course automatically call a cab to take them to their unit's floor, but also the security system had entries for things like "dog owner" and "allergic to dogs" so that the DD system would never schedule them together for the same cab.
My biggest pet peeve is elevator banks where they don’t make some number of idle elevators automatically come back to the lobby. Half your traffic is over there! Everyone coming in has to wait an extra minute or two because all your elevators were chilling on the 35th floor and above.
My apartment building is replacing the elevators, and someone on staff revealed that the first renovated elevator is intended to pick up only from the lobby (i.e. if you summon an elevator from the 10th floor, one of the others will come). This has caused some grumbling or calling it an "express elevator". In an apartment it really is mostly trips to many floors from the lobby. The only time this maybe would be inconvenient might be in the morning commute, when fewer people are re-entering.
You should observe if it is the same elevator all the time and the building people just don’t understand it. Our building elevators (bank of 2) always seems to try to keep one in the lobby. About 75% of the time you get an elevator right away when you call it from the lobby. But it definitely isn’t the same elevator! Allocating an exclusive single elevator to that function would seem to be strictly worse from many angles. Like if you modeled having an algorithm like “elevator 2 only services calls from the lobby” you’d find it would be very inefficient and not every effective. But I can see having one in the bank always returning to lobby right away making sense.
My guess is whoever hinted at that didn’t fully understand what they were taking about.
Super interesting. I've always wondered how exactly they work.
Our elevator doesnt stop for people who called it after it started on the way up. It only picks up people on the way down
My autism just went KABLAOW when seeing this. I know what I'm doing the next hour.
Level 1: Elevators, load balancing (1D arrays)
Level 2: Traffic lights, graphics (2D arrays)
Level 3: Flight control, simulations (3D arrays)
Level 4: Satellite tracking, virtual worlds (4D arrays)
...
So many problems can be cast to arrays to be solved with various linear algebra.
Considering LLMs are "Level 1000+" puzzles in this analogy, I wonder if every problem could be represented by an n-dimensional vector and solvable with algebra.
They at least make great interview questions - Tic-Tac-Toe is commonly given, but is obvious. The board already "looks" like arrays. The less obvious ones, like elevators (or load balancing), are always interesting.
I think a small improvement that could be made is to have the dot representing the person be colored the same as a dot on each floor, which would obviate the destination floor for each individual.
Yes the visualization is great but overused and could also use a stop button. I would have also liked to see different kinds of plots.
This is beautiful. By the end of it I started to feel like I was calculating complicated chess lines in a middle game.
This is cool, but wondering which tool was used to build those animations?
The animation is really cool, how did you make it?
I absolutely adore this, I am always trying to guess whichever elevator will come in first in large crowded buildings. Thanks for this article.
If you like elevator hacking don’t forget the seminal DEF CON talk by Deviant Ollam and Howard Payne: https://youtu.be/oHf1vD5_b5I
I watch it like once a year because it always tickles some part of me. Like all the different modes you can get an elevator into. The most fancy one people might encounter is when moving into or out of a building. The front office can give you a key to give exclusive control over an elevator so your movers aren’t waiting around on elevators. Put it in that mode and it will stop responding to calls from other floors. Only the person with the key can control the elevator. You get on, select the floor, door closes elevator goes, and then just chills there with the door open waiting for you. Annoying for the rest if the building (the building is down an elevator when in that mode) but is amazing for the person using it! But there are way, way more depending on the installation and function.
Fun fact: most elevator shafts are sealed at the top as tight as possible to prevent them from becoming a giant chimney in a fire. It never even occurred to me until I was in a mechanical room wondering “where is the hatch to look down the shaft?” The answer is “there is none, and it’s a feature not a bug.” You want to block all airflow so fire doesn’t chase up the shaft into neighboring floors. Who knew!
Don't forget the executive elevator algorithm (EEA), which uses a priority interrupt to take passengers directly to the top floor.
Also need to make sure you increase the speed going past floors 4 and 13 to avoid bad luck.
This article gives me war flashbacks about a particularly irritating OO design interview from 5 years ago.
Lol, love this post. Every single day when I take the elevators at the office I try and figure out what the algorithm is behind it. Been too lazy to just research it. Now I know!
Over the years, I've witnessed numerous instances of poor elevator behavior:
- Two elevators ascending and descending in near lock step, in a two-elevator building, effectively reduced to one elevator.
- When going in a different direction from the requested one (e.g. called elevator to go up, but actually going down), the doors wastefully close, open and close again. Seen this in many elevators.
- At 3 a.m. you take the elevator to a parkade, like to get something from a car. When you return to the elevator a minute later, it is gone; it spontaneously moved away even though nobody is using it but you.
I didn't realize that neal.fun had some competition.
The question about designing elevators used to be the mainstay of programming job interviews. I had an annoying interview where I was asked, for the umpteens time to design an elevator. I already made up my mind at the time, knowing I'm not going to work for the company, but decided to have a... unexpected approach.
So, for instance, I didn't measure the elevator's efficiency in the wait time. I included (weighted) travel time. I assumed LOOK algorithm was used. And then when I tried to calculate various outcomes for different trips I suddenly realized that elevator's efficiency and fairness seem to go different ways.
Without trying to reproduce my evaluation system, here's my finding in fewer details: if you have two passengers, one going from the ground floor to the top floor and other joining for the shorter ride down in the middle, then the elevator that makes a "detour" is more efficient, but it hardly seems fair that the passenger traveling ground floor to the top should go even a single floor in the opposite direction.
Somehow, until that point, I lived with an illusion that the most efficient solution to a problem must be the most fair to every participant. Discovering this counterexample sent me on the "tour of discovery" of ethics and different philosophers who contributed to it... and while in the end it made me none the wiser, I'm happy to have discovered this field.
This is super interesting. I've always wondered how the complicated things work!
I've always wondered about elevator algorithms. This is awesome.
As someone who lives in a penthouse, elevator’s frustrations are real struggle especially in rush hours, because the elevator has to travel dedicated to you rather than you piggy backing on one that is already going up or down.
I love elevator simulations.
Maybe I missed it, but the algorithm should also redistribute empty elevators that stop too closely to each other.
Having gone to many large furry cons(notoriously brutal on the elevators due to how much floor-to-floor traffic there is compared to other usage) I’ve seen these algos basically completely fail to adapt to unusual patterns. I once spent over half an hour on checkout day, in a hotel with 8 banks, to even have a car stop on our floor at all. Can’t really blame the algo for such a unique situation and at the end of the day a saturated system is a saturated system and nothing can be done to make it fast, but it’s always interesting to witness when a system is completely unable to accommodate a demand like that.
(In the example above we gave up and decided it was cardio time, five laps up and down 14 flights to escape with all our luggage.)
>All this technology just to underperform the S&P
My takeaway is that the benefit of using a much more complex algorithm is marginal.
> Everyone has shared the frustration of waiting for an elevator that never seems to arrive.
Really? Maybe I'm lucky I never had to deal a lot with elevators.
I can't say I have. The only 2 times I have been frustrated at an elevator are when I was in one and the door wouldn't shut, and the other was when had someone pressed the emergency stop so I couldn't use it.
This is a good article. It reminds me of a story.
At a previous employer we had heteregenous elevators. In one bank, some went to the lower half of floors only while others went to all and the company installed a "smart" elevator system. I kind of became known because I was constantly yelling about this system in the feedback group because I hate "smart" elevators and and (IMHO) they just don't work. What actually works is express elevators and sky lobbies.
This article covers one of the deficiencies this system had: full elevators. For example, you'd want to go down and an elevator would skip your floor because another had already been assigned. That one would show up full and you couldn't go down. Down wasn't so bad because the stairs weren't a bad option but up was terrible. Going up a few floors was fine. Going up 20 was... a bigger issue.
Back in the day we had elevator operators and people in the lobby during the morning rush who would shepherd people into particular elevators. I actually think this system works way better than anything technology has come up with. Even if you nail the implementation (and I've never experienced elevators that have), people don't read and will just get into elevators anyway.
Anyway the article says that generally speaking on smaller banks simple up and down buttons work best. I absolutely agree.
There's a deeper issue here though and that is solutions looking for a problem. Nobody is making money from up and down buttons. They are fromn selling smart elevator solutions. And you see this everywhere in life. It basically devolves into rent-seeking behavior. Salespeople wine and dine a couple of people responsible for making decisions and then make bank on selling something nobody wants or needs as well as the constant maintenance and updates.
> people in the lobby during the morning rush who would shepherd people into particular elevators
That's what the no-button elevators with the kiosk does.
did he factor in the lifting speed?
Enjoyed the read, thanks!
Beyond the content, the font, style, etc made it a pleasant experience for me.
I think this comparison is also assuming the distribution of request & requested floor is uniform? When actually near pairs are less likely (I'll just take the stairs) than bottom to top, so even analysing it is more complex than at first glance.