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.
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.
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.
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 :-)
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.
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
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.
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.
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.
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.
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.
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.
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)
I hardly think the optimization function is obvious.
1. Are you optimizing for total travel time including waiting, or is reducing wait times more important?
2. Are you going for mean or median?
3. If you're going for mean or median, is there a chance the max travel time is very high? Maybe you want to bound the maximum travel time?
4. Is it more important to make going up fast than it is to make going down fast? It seems like first impressions of a building might be more important to some.
5. Should the algorithm change as the traffic patterns change? 9am surely looks different than 5pm.
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.
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?
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.
> A good design works with human nature, not against it.
Although I agree, I was responding to the possibility of an elevator punishing behavior it didn't "like". Both what edw519 and I suggested would lead to "a whole office [...] following arbitrary elevator efficiency rules." It was intended to be a very tongue-in-cheek comment. I completely agree with both you and Jandy: a good elevator design would adjust itself to normal usage patterns and maximize efficiency within those constraints.
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.
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?
The are, with the effect (and I'm guessing intent) that an electrical/motor failure won't lead to the elevator plunging 20 stories and killing all occupants.
Software engineering could (and should) learn a few things from mechanical engineering. People have been saying that for decades, but it bears repeating...
Crash driven design. Design your software such that it can recover from a crash to a known state and continue. Make life so much simpler. Shutdown is just a matter of power off. Startup always does a recovery before starting.
There's a separate emergency brake system to prevent the elevator from falling, because you also need to be safe if the cables holding the elevator up break (this is actually the technology that lead to the first elevators). The counterweight is probably primarily just to reduce power/energy requirements.
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.
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.
People see an open elevator door, they get in the elevator. They don't stop to read the instructions because they are not expecting the elevator to come with instructions and also because they know the elevator doors are not going to remain open forever.
These people are already getting on wrong elevators. The example given has banks of elevators for different floors, marked by sign and by buttons for the specific floors covered. If they don't pay attention they'll get a short tour.
If this was a deadly choice, between an elevator and a trash compactor, it might make sense to over-sign it. As is, it's a trivial and obvious mistake, especially if each bank has a sign saying 'Floors 1-x are reached via the other elevator bank' for someone to read on their round-trip.
Part of the reason users are so clueless is because we go too far in padding their environment. People don't slice off fingers because the sharp end of the knife wasn't properly labelled - they exercise caution.
There is no up/down button, just a keypad with numbers on them. People are accustomed to looking for the up button and, upon not finding one, immediately get into a confused state.
If you need lengthy instructions to show someone how to use your UI, you should reconsider your UI.
At the risk of completely derailing the discussion, sometimes the UI simply just needs to be learned. People who are unfamiliar with elevators would have no idea how to use one.. there's no instructions anywhere, just a panel with numbers. If you aren't familiar with those bathroom faucets that turn on when you put your hands under them, you'll spend a few minutes just staring at it looking for a knob. Eventually, it catches on.
You are right that there's an initial curve, though, and I don't know how to deal with that other than just through the painful experience you described.
Of the top of my head: start off with big up/down buttons. Then show a list of floors. Some people won't notice the second press required, but it's a start. I was confused by those things the first time too.
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.
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...
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!
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.
"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?
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.
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
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?
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.
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.
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.
75 comments
[ 2.6 ms ] story [ 134 ms ] threadhttp://scholar.google.com/scholar?q=elevator+algorithm&h...
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.
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 :-)
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.
Then they'd all end up sulking in the basement...
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.
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
(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)
1. Are you optimizing for total travel time including waiting, or is reducing wait times more important?
2. Are you going for mean or median?
3. If you're going for mean or median, is there a chance the max travel time is very high? Maybe you want to bound the maximum travel time?
4. Is it more important to make going up fast than it is to make going down fast? It seems like first impressions of a building might be more important to some.
5. Should the algorithm change as the traffic patterns change? 9am surely looks different than 5pm.
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?
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
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.
Although I agree, I was responding to the possibility of an elevator punishing behavior it didn't "like". Both what edw519 and I suggested would lead to "a whole office [...] following arbitrary elevator efficiency rules." It was intended to be a very tongue-in-cheek comment. I completely agree with both you and Jandy: a good elevator design would adjust itself to normal usage patterns and maximize efficiency within those constraints.
FYI it's Rick Astley, not Rich Ashley.
Software engineering could (and should) learn a few things from mechanical engineering. People have been saying that for decades, but it bears repeating...
(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.
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.
If this was a deadly choice, between an elevator and a trash compactor, it might make sense to over-sign it. As is, it's a trivial and obvious mistake, especially if each bank has a sign saying 'Floors 1-x are reached via the other elevator bank' for someone to read on their round-trip.
Part of the reason users are so clueless is because we go too far in padding their environment. People don't slice off fingers because the sharp end of the knife wasn't properly labelled - they exercise caution.
If you need lengthy instructions to show someone how to use your UI, you should reconsider your UI.
http://www.jnd.org/dn.mss/are_the_new_elevators_bad_design.h...
You are right that there's an initial curve, though, and I don't know how to deal with that other than just through the painful experience you described.
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.
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...
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!
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.
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?
Also, what about escalators? What standard arrival distributions do designers work with?
What the hell kind of behavior is that?
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
When the elevator is full, it should not stop for people who have pressed buttons not inside the elevator.
http://www.reddit.com/r/IAmA/comments/b1bpp/i_program_elevat...
(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.