Elevators

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

> 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.

For folks that have never seen elevator scheduling the game: https://play.elevatorsaga.com/ Enjoy this rabbit hole :D

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.

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.

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.

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?..

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.

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.

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.

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.

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.

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.

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.

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.

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

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

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.

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.

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.

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.

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.

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.

[flagged]

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.