Elevator Algorithms

http://www.lisazhang.ca/2009/12/elevator-algorithms.html

by signa11 • 15 years ago

144 71 15 years ago

jvdh• 15 years ago

This is a really simple analysis of elevator algorithms, mostly based on anecdotal evidence. If you really want to go down the rabbit hole of these algorithms, there's a whole lot of scientific papers written about them.

http://scholar.google.com/scholar?q=elevator+algorithm&h...

shasta• 15 years ago

Just to point out the obvious problems of having the elevator door start open: 1) you now have a common case where the door starts to close as someone is just about to walk in, startling and/or annoying them, and 2) not only does closing the door first increase the time to get to any other floor, but the elevator doesn't even know whether the door close will be successful (it could be held or otherwise obstructed) -- leading to even more delays on another floor.

chrislomax• 15 years ago

I would imagine that this is geared towards situations where the elevator is always going up. I would say that this is also affected by the business / time of day.

I would say that around 5pm you have more people going down than up so this algorithm falls flat on it's face.

I don't think you could write 1 algorithm and it works for everyone. You could generalise it to apartment buildings but I think there would be a pattern of more people going down at the beginning of the day than at the end of the day too.

nmridul• 15 years ago

I don't know whether an elevator algorithm is as simple as what is mentioned in the article.

The algorithm needs to take into consideration the type of lift (lifts in an housing complex vs commercial building) and time of the day. During morning hours, the lifts in an housing complex might more frequently travel towards the ground floor while the one in a business complex would be travelling up.

Also, there could be buildings where the top floors might have more tenants than bottom ones or the reverse.

There is a scope for self learning algorithm that can adjust its idle position depending on past behaviours.

But elevator algo becomes more complicated when two persons press the switch at same time for the lift. One is at 2nd floor and wants to go up, the other at 4th and wants to go down and lift is at 3rd floor :-)

TheCapn• 15 years ago

Then what is the problem with treating elevators in the same way that traffic lights are treated in many cities: adjust for the time of day.

Using my workplace as the anecdote the elevators get massive usage at 8:00AM as people arrive at work, the majority of calls are from 1st & 2nd floors (you can enter the building on both floors at 8:00, noon and 5:00). After that there is the 9:30-10:30 coffee rush with elevators going up and down. The noon rush, afternoon coffee and evening rush.

Those are the peak points of the day with simple scenarios for when people are most commonly going up down so it wouldn't be difficult to implement scenarios where the algorithm changes at a time.

jandy• 15 years ago

Am I crazy thinking it'd be a good idea to have an elevator which analyses its own usage patterns and adjusts its behaviour accordingly?

eternalban• 15 years ago

http://tierneylab.blogs.nytimes.com/2007/12/20/smart-elevato...

obtu2• 15 years ago

The only optimisation this one has (that the article tells us about) is that passengers choose their floor, but not the elevator to get there.

obtu2• 15 years ago

Not at all. Here's a similar idea, a thermostat with two inputs: too hot and too cold, plus some machine learning tuned for circadian rhythms: https://news.ycombinator.com/item?id=3153227

JonnieCache• 15 years ago

No, because as soon as we found out about this we'd all be going around trying to train strange behaviour into elevators.

Then they'd all end up sulking in the basement...

pedoh• 15 years ago

At the beginning of the day, assume most people are going up from the ground floor. At lunch time, you've got a balance of people going down to the ground floor to get lunch and people going up from the ground floor post-lunch. At the end of the day, most of the people are going down to the ground floor to leave at the end of the day. And at all times you've got deliveries that initiate from the ground floor.

Have your bank of elevators start with a simple "best guess" algorithm, and then learn how to improve that algorithm. If the last employee of the building is ready to leave at 11pm, there's no reason the elevator shouldn't be at that floor waiting after a learning period.

peter_l_downs3• 15 years ago

Very interesting. A friend and I were interested in elevator algorithms last year, and ended up writing an elevator "simulator" in Java. I'll post the code somewhere if anyone's interested, but like chrislomax and TheCapn say is correct: depending on the time of day, the optimal algorithm changes.

The interesting thing about "elevator" algorithms is that they're really very similar to the algorithms used to schedule reads and writes on a hard drive. Reading in some data is similar to picking up a person, and writing data can be thought of as dropping the person off somewhere. Regular (i.e., not solid state) hard drives have large cylinders of addresses. This is sort of like a rolled up building.

I don't have the output in front of me, but I think that both LOOK [1] and SCAN [2] algorithms performed very well. It's cool to note that the SCAN algorithm is referred to as the "Elevator algorithm" by Wikipedia. Clearly we're not the first to go down this rabbit hole.

[1] http://en.wikipedia.org/wiki/LOOK_algorithm [2] http://en.wikipedia.org/wiki/Elevator_algorithm

karambahh• 15 years ago

I'm definitely interested in playing with your simulator!

dodo53• 15 years ago

Also there are choices on what to optimise for. Our elevators are triggered by swiping your company card, which then tells the elevator which floor you're going to. You're then assigned one of 16 elevators. Elevators frequently wait for a couple of minutes for more people to arrive. So instead of which floor(s) should I now go to, there's also how long should I wait to go there. I suspect the algorithm might be optimized to some degree for minimizing number of journeys (to save energy or whatever) instead of/as well as average/maximum wait time per person.

dinedal2• 15 years ago

I use the "Build me a system that controls elevators" as an interview task. It's saddening how many I've interviewed that can't even get me a naive case of all destination floors get shoved on a FIFO queue. If we even get to the discussion on optimizing I've usually already decided to recommend the candidate for hiring.

webspiderus• 15 years ago

it's interesting because I just got the elevator question for the first time a month or two ago and was still scratching my head trying to figure out where the decision point on that question is. i ended up spending about half the interview talking about different ways to optimize for minimal waiting time, but now it seems like that may have just been banter after we'd covered the FIFO queue.

dinedal2• 15 years ago

I try to guide my candidates to produce a functional solution before premature optimization. Obviously once a candidate proves they can come up with at least the simplest case, it's good to get an idea how how they'd optimize it, but since it turns out only 1 out of every 10 candidates actually get that far, the fact that we're having that conversation is enough to push them above the competition.

jes5199• 15 years ago

This. I used to use it, too. We would start with trivial cases (one elevator, two stories), and gradually add more floors and elevator shafts. We never, ever got to the interesting algorithms. It took a surprisingly long for people to describe anything remotely like a working, naive algorithm.

(of course, the most simple algorithm doesn't even use a queue! It just moves the elevator up until it hits the top, and down until it hits the bottom, opening the doors wherever there's a call request)

edw519• 15 years ago

Hmmm, algorithms to control elevator behavior.

How about algorithms to punish inefficient human behavior on elevators:

a. If people are on the elevator, it stops on a floor for a button that has been pressed, and no one gets off (as measured by weight), this means that someone must have pressed a button by accident. Switch from soft muzac to loud Rich Ashley music until the next stop.

b. If someone enters an elevator (as measured by weight) and within 3 seconds 2 buttons are pressed within 1 second of each other by the same finger (as determined by biometrics), that means some dumbass couldn't even press the correct button. Shock them on the second button press.

c. If the elevator is planning to discharge passengers (see a.), and people get on before people get off (as measured by weight), dump hot liquid on the rude entering passengers (those closest to the door).

d. Photograph anyone who summons the elevator by pressing the up or down button on their floor. If the elevator stops and no one gets on (as measured by weight), post their picture on elevatordouchebags.com.

e. If anyone farts on an elevator (as determined by sensors), identify them with a spotlight so that the sufferers don't have to guess who made them suffer.

f. If anyone gets on the elevator without a cart or baby carriage (as determined by sensors) and presses 1 floor down, go up 1 floor instead. When the door opens, flash a message, "Use the stairs next time!"

g. If too many people get on (as measured by weight), open door slightly and shake violently, knocking people out until the weight is under the limit.

Any other ideas?

peter_l_downs3• 15 years ago

Why punish inefficient behavior? All of these seem slightly... inhumane ( :) I suspect that is the point). Really, though, what if the elevator were sped up if people started acting more efficiently (as determined by your multitude of sensors).

Instead of Jandy's suggestion:

>Am I crazy thinking it'd be a good idea to have an elevator which analyses its own usage patterns and adjusts its behaviour accordingly?

why not make the people adjust to the elevator's ideal behaviour?

EDIT: quote formatting

xibernetik• 15 years ago

A good design works with human nature, not against it. If you want people to adjust to the elevator's ideal behavior, you have to subtly guide them to the right direction -- which is possible, but the way you asked it sounds along the lines of telling a whole office to start following arbitrary elevator efficiency rules.

That aside, I think Jandy was referring to a different scenario than what you're envisioning. If you have a skyscraper, and a trendy new bar opens on the 36th floor when the 36th floor use to be occupied by an office, but the elevator was programmed to rest at the 36th floor only at 9AM, lunch hours, and 5PM, telling the bar they have to make their clientele come and leave at those hours for "efficiency" will not go over well. Instead, having an elevator that notices no one's calling from the 36th floor before 8PM anymore doesn't sound like a bad idea.

Tichy• 15 years ago

Clearly what is needed is an iElevator app for iPhone that teaches people how to make the most of their elevators.

ghc• 15 years ago

> Rich Ashley music

FYI it's Rick Astley, not Rich Ashley.

jsaxton862• 15 years ago

There seems to be a lot of interest in minimizing the amount of time users need to wait to get onto the elevator, but this is not the only variable you can optimize. Elevators use a lot of power, and a lot of elevators (especially low traffic ones) are programmed to minimize the amount of power used. For example, the author's suggestion that elevators travel to the ground floor after every trip is highly inefficient and expensive.

alexchamberlain• 15 years ago

I don't know alot about Physics, Engineering or Elevators, but I do know that there is some magical force at work in the world that once made an Apple fall on someone's head. Could we not utilise this force for the better and, perhaps even, recoup some energy?

zwp• 15 years ago

Security mindset edw?

(a), (c) I press all buttons as I exit elevator.

(b) gummi bear attack or similar.

(d) Arrive carrying large cumbersome object "Heh, can you call the elevator for me?" (then run away)

(f) is easily reversible: should send people as far away as possible from their intended destination instead.

(g) throw dumbells into passing elevators.

zandor• 15 years ago

Oh I have some. But I'd rather venture into traffic light algorithms at crossings. Quite simple and effective really:

If anyone presses the button more then once they'll get the same lights as the traffic. So green for the cars, green for them.

eykanal2• 15 years ago

I just started working at a 31-story corporate office with sixteen elevators (A-H for 1-15, I-O for 15-31), and the elevators here incorporate a genius move... outside the elevator are little panels with numbers, and you choose the floor you want before you get on the elevator comes. The panel tells you which elevator you should get on. This way, the system can optimize ahead of time where the different elevators should stop. Since I've been here, I've never waited more than 15 seconds for an elevator.

joezydeco2• 15 years ago

Those work nicely in office buildings where people know the routine. When you put one in a hotel, you'll usually see someone paid to stand around and show guests how to call the elevator.

Cushman• 15 years ago

Is that just a customer comfort thing, or has nobody managed to invent a sign that people will read yet?

dsulli• 15 years ago

That's a good idea. Having that, plus an 'expected wait time' would be really useful. When I push the button, if it tells me I'll need to wait for 4 minutes and 23 seconds for the next elevator, I can use that time more effectively ... maybe go grab a coffee and come back, or perhaps even take the stairs instead.

I don't think owners of office buildings realize how painful it is to have slow elevators. We moved our office out of a 30 story building with 4 elevators, because the unbearable wait to get in and out of the building during peak times.

Lazlo_Nibble• 15 years ago

I saw this implemented at (I think) Times Square Tower a few years back. It had you enter your floor at a podium in the main lobby on the way to the elevators, and it worked beautifully. 49 floors and not once did I have to wait more than ten or 15 seconds for an elevator.

Then they retrofitted a similar system back at my corp HQ. It had you enter your floor on a screen on the wall right in the middle of the elevator lobby and it was (and is) kind of a pain in the ass...because when there's a crush of people waiting for the elevators, you can't get to the screen to enter your floor. When it was just the "up" and "down" buttons in the same location, the odds were pretty good that someone in the crush had already pushed the button you need, but...

seles2• 15 years ago

An old game called Sim Tower was pretty cool in that your success as a huge tower builder was directly linked to how well you could optimize elevators. There was a maximum number of elevators that you are allowed to construct and once your building gets large, if you don't optimize, people will get fed up with the waits and abandon your tower.

The game allows you to setup different patterns for different times of the day. It allows you to set wait floors, set which floors it will stop at, and even set patterns like skip to the top and drop off on way down. This last trick avoids the problem of needing to stop on the same floor on both your way up and way down, which would occur with normal elevators if say the elevator was taking two people up, one to floor 17, one to floor 20, and someone wanted to get on at 17 to go down.

In all the game was really fun (although construction was repetitive), and does make you think about elevator optimization for the rest of your life, I played it as a kid, and I am always thinking about how badly elevators are optimized!

wdewind• 15 years ago

Protip: Only build offices, no condos. I got to 5 stars without once optimizing the elevators.

seles2• 15 years ago

There is a rating higher than 5 stars, called TOWER. It has been a while but if I recall it is very difficult to reach that with offices, because they have a large amount of traffic compared to other ways of getting population, making it to hard to not overload your elevators even with optimization.

What I did was sort of a hack, but worked, in the basement levels express elevators and escalators can go to any floor, so I made tons of them, and made tons of shops, all shops (they had highest population density). Virtually all of my tower was underground.

Dav3xor• 15 years ago

http://www.reddit.com/r/IAmA/comments/b1bpp/i_program_elevat...

afterburner• 15 years ago

"What I don't understand is why so many buildings do not have these optimizations built into their elevators."

I suspect the author has observed more residential towers than corporate towers? Otherwise I would imagine he would find that these practices are usually followed. Except for the door remaining open one, I never see that... maybe a fire code thing?

maeon3• 15 years ago

Machine learning is the best algorithm for this because the floors most used change based on day of week, time of day, day of month, day of year and buttons pressed. The elevator should be at the floor where there is most likely to be a person that hour.

bdrocco• 15 years ago

Didn't anyone here play Sim Tower? Obviously you want the send all your elevators to the ground floor for the morning rush hour and distribute them evenly among your floors for the later part of the day. Perhaps leave a couple extra ones at the ground floor 24/7 for mid-day visitors. :-P

bediger• 15 years ago

What are the engineering standards around this? Like inter-request arrival time distribution, the elevator passenger's floor destination distribution, etc etc?

Also, what about escalators? What standard arrival distributions do designers work with?

noduerme• 15 years ago

It's bizarre to have just read this and then seen the news from New York a few minutes later. http://www.nydailynews.com/new-york/elevator-accident-kills-...

What the hell kind of behavior is that?

MaxGabriel• 15 years ago

Presuming this is using the North American floor conventions (which I presume to be the case based on University of Waterloo being in Canada, which according to wikipedia is likely to use the same naming conventions as America[1]), wouldn't it be better to optimize example 3 by having the second elevator on the seventh floor? This means floors 8-12 and 6-2 are only five floors away. If you station the second elevator on floor 6, then floor 12 is six spots away, and floor 2 four spots away.

Its definitely much more complex than that (e.g. the ground floor elevator could take people down from floors 2 & 3 or something, depends on time of day, etc.), but if the author's intention was to station one elevator at ground level and another in the middle, floor 7 is the better choice.

[1] http://en.wikipedia.org/wiki/Storey#North_American_scheme

mrbgty• 15 years ago

Elevators should be able to see with a camera a percentage of the floor that is visible from the ceiling. Using this percentage (in addition to or just by weight), the elevator should be able to determine whether the elevator is full.

When the elevator is full, it should not stop for people who have pressed buttons not inside the elevator.

aninteger• 15 years ago

There was a guy on /r/iama that programs elevators for a living. He writes a lot of C :)

http://www.reddit.com/r/IAmA/comments/b1bpp/i_program_elevat...

fleitz• 15 years ago

It's probably best to use a E*N entry LRU cache for elevator requests. In the morning it's going to be predominantly ground floor to upper floors, a complete mix during lunch, and in the afternoon upper to lower, by using the E floors that have most entries in the LRU cache you'll be able to fairly efficiently move the elevators to the correct floors most of the time, and also account for any discrepancies in office hours.

(E = the number of elevators, N probably should be the number of floors, no idea what would make a good N)

I'm sure that if you snap shotted the LRU cache every few minutes you could build a pretty good predictive index for the patterns through out the week and time of day.

What might be interesting would be wifi/cell signal detectors that could pick up a cell when it enters the hallway and start moving the elevator already.

jisaacstone• 15 years ago

Related: Double-deck Elevators - http://en.wikipedia.org/wiki/Double-deck_elevator - At what point do these become a worthwhile investment?

jdpnd• 15 years ago

Couldn't a smart elevator system know (approximately) how many people are on each floor and thus make smart decisions based on that information (excluding the fact that a few energetic people may have taken the stairs to move one or two floors).

tomkit• 15 years ago

Why is this suddenly a trending topic? Elevator algorithms have are an old topic that have been studied in the 80's 90's in the database community in relation to doing efficient reading/writing for hard disk heads. The tradeoffs of each algorithm are already well known.

cwp• 15 years ago

I've been thinking about elevator algorithms lately too. My building applies the principle of least privilege to the elevator - residents are issued fobs which give them access to the floor where they live, plus any common areas. The problem is that waving the fob in front of the sensor pad before pressing the button for your floor takes a bit of time, and in that time, it's possible that someone else, somewhere in the building, will press the button to call the elevator. When that happens, the elevator may change it's direction. A race condition!

For example, you're on the 10th floor and want to go to the first floor. You press the down button. The elevator arrives, with it's "going down" arrow lit. You get on, and as you fumble with your fob, someone on the 18th floor presses the down button. The elevator now has a call on the 18th floor, and no destinations yet, because you haven't pressed the "1" button. Now you have a choice: press "1" and ride the elevator up to 18, knowing that it'll (eventually) go down to 1, or get off the elevator press "down" in the hope that another elevator will arrive before this one gets back. Of course, it's very likely that you don't notice the "going up" arrow, because you're fumbling with your fob.

I'm finding this happens surprisingly often, and I think it's a bug.

wnight2• 15 years ago

And amusingly, those fob systems increase the chance of a break-in to your apartment. In a building of 200-400 suites it'd be tedious to try found/stolen keys in every door.

But in a system such as you describe you get on the elevator, wave the fob at the sensor, and press all the buttons. It'll only take you to the specific floor your stolen key will work on - narrowing the search time down to mere minutes.

nerfhammer• 15 years ago

Why don't more elevators have these optimizations? On older buildings at least, I imagine it's because the landlord just doesn't care.

I walked by dozens and dozens of emergency vehicles this morning because of this horrible thing: http://cityroom.blogs.nytimes.com/2011/12/14/three-hurt-in-m...

My last office was in an older building like that and had a set of elevators that were chronically behaving erratically, so that kind of freaked me out more than it would otherwise.

johngalt• 15 years ago

Makes me wonder if there's a different solution to the elevator problem entirely. Expand the scope to "moving people along a vertical axis efficiently". What would a safe continuous elevator look like? Or could the solution for going up be different than the solution going down?

shabble• 15 years ago

There's the Paternoster[1], which is essentially what you're talking about, but as it probably fairly obvious, they're pretty difficult to make both safe and efficient.

I'm reminded of the 'Moving Platform'[2] idea proposed for high-speed trains fairly recently though, and I wonder if there's anything there that could be reused.

What would a packet-switched elevator shaft look like? (Lots of small cars, which divert to individual 'station' queues for each floor, and latch onto a continuous moving belt at fixed intervals - shades of ATM)

[1] https://en.wikipedia.org/wiki/Paternoster

[2] http://www.designweek.co.uk/home/blog/moving-platforms/30277...

jhrobert• 15 years ago

On a different perspective, if you may, ...

We don't walk enough, that's a known fact.

Elevators are bad for your health. Take a walk.

However Delevators are good because most accidents happen when you go downward.

Hence, Elevators going up should be for really older people only (unless you're in a hurry or carrying something heavy or already in good shape...).

Fight for Delevators!

ekianjo• 15 years ago

Well, I agree we do not walk enough, but when you live in large buildings with more than 15 floors you cannot expect people to take the stairs up and down from top to bottom. Elevators are enablers of high people density in cities.

waterlesscloud• 15 years ago

I recently went to the office in Los Angeles that issues permits for filming. It's located inside a studio lot, so you sign in up front, have your ID scanned, get a printed badge to wear and walk to another building that has the permit office.

In that building, you go to the security desk and tell them where you're going. They call the elevator for you. You get on the elevator. It has no buttons inside. The desk sends you up to the permit office.

When you leave the permit office, you press a button next to the elevator and it shows up and takes you to the lobby. There are no other options for you.

Studios got paranoid about security post 9/11. Which I guess makes some sense.

But why the film permit office is inside one of them, I'll never know.

presto8• 15 years ago

I've often wondered how well an adaptive learning system using cameras at each floor would work. The cameras would record how many people are waiting for the elevator and tweak the algorithms accordingly. Historical data could be collected based on time of day, day of week, etc. Could be combined with the building's existing security cameras for cost savings.

skadamat• 15 years ago

I LITERALLY had the same interest about a month ago. I live in a college apt with 8 floors and one elevator, and it's a pain sometimes. My inner hacker definitely wanted to sit down and crank out ways to better create an elevator algorithm

jpren• 15 years ago

As several others have suggested, the elevator should behave differently at different times throughout day.

A smart elevator algorithm would adapt to the arrival behavior of people in a building through some clever stochastic simulation and modeling. For example, a simple model that could work quite well is to optimize for (read: minimize) the average time any passenger would wait for an elevator to arrive. But to do this, we need to model how frequently people request an elevator on each floor over the course of the day.

Modeling elevator requests - We can assume that the number of people who request the elevator on each floor is a Poisson process with a mean of n. On a representative day (i.e. for an office building, choose a weekday), we can observe the number of people who arrive at the elevator each hour. This data would drop in as the n in our Poisson arrival processes.

Computing optimal solutions - Using a statistical library, we can start generating simulated arrival data and apply integer optimization algorithms to determine which floor the elevator should rest on when there are no elevator requests, for each hour of the day.

MarkMc• 15 years ago

Reminds me of the following parable:

The tenants of a large well-to-do apartment block kept complaining that the elevators were always too slow, and they hated waiting in the lobby for the next available elevator. The apartment manager spent some time investigating the cost of installing faster elevator motors before he came up with a much cheaper solution: He installed large mirrors in the elevator lobby; the complaints stopped.

Elevator Algorithms

Related Stories