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.