All elevator algorithms solve the same type of optimization problem: given that a building has n floors and m elevators, how could we most efficiently move people up/down the floors? I'm sure you already know of the simple algorithm that every elevator implements, but one can definitely improve on this. Here's one improvement someone tried to make.
Example #1:This is an intuitive solution. Since there are n floors where people could call the elevator, why not minimize the wait time by making the elevator go back to floor n/2 when it is idle? The problem with this argument is that it assumes that an elevator is equally likely to be called from any of the n floors, which is not true. In most cases, people who use the elevator would use it to either go down to ground floor from the floor they're at, or up from ground floor to the floor they should be in. This means that approximately half the time, elevator request would occur at the ground floor. A better design is the following:
This building has one elevator, and 8 floors. The elevator was made to move back to floor 4 when it is idle.
Example #2:This speeds things up a lot. Not only could you avoid waiting for the elevator to get to the ground floor, you don't even have to press the button and wait for the door to open! I thought that this was a great idea! (An acquaintance pointed out, though, that unsuspecting people might mistakenly think that the elevator is broken. Well then...)
There are no more than 10 floors (I believe it was less), and about 6 elevators. When an elevator is idle, it moves to the ground floor, and opens its door.
The algorithm used in example #2 focuses a lot more on people going up as compared to people going down. I think this makes sense. Going up stairs takes a lot more effort than going down stairs, so people are more likely to use the elevator to go up. However in a building with more floors, more people would want to use the elevator to go down, so having all the elevators in ground floor is not going to help. Here's a solution that seems to work well:
Example #3:This makes a lot of sense. The first elevator takes care of the case where people want to go up from floor 1. The second elevator takes care of the case where people would want to go down, and since the elevator is at floor 6, the wait time is reduced.
This building has two elevators and ~12 floors. It is programmed to ensure that at least one elevator is on the ground floor at any given time. The other elevator is often seen on floor 6, but I'm not sure if there's a pattern here.
For small n and m, I really can't think of a better solution than the one used in example #3. For larger n and m, though, it becomes more complicated:
Example #4:It would be quite disastrous if the elevators aren't organized this way. Imagine working on the top floor and having to wait for the elevator to stop at every floor in between! This elevator is designed to go super fast from the first to the 22nd floor, making things even more efficient.
This building has about 38 floors, and at least 12 elevators. The elevators are divided into two groups: the first group goes to floors up to 22. The second elevator skips all the floors until floor 22, so it stops at floors 22-38 (and the ground floor).
All of these examples are real. What I don't understand is why so many buildings do not have these optimizations built into their elevators. Implementing these changes cost almost nothing, but can save a lot of peoples' time in the long run.
End of Entry
If there were 12 elevators, I'd design one of them to make random free falls unpredictably. That would keep people awake in the mornings, AND would get people to the ground floor much faster.
ReplyDeleteIt would also reduce overall coffee consumption, and consequently promote fair trade labour laws in western Brazil.
freefalls! yay for adrenaline junkies =P
ReplyDeleteI experienced example 2+4 at work during the summer. lucky ppl on floor 9 >.>
I thought most buildings DO have these implemented? maybe I just havent gone into enough buildings w/ elevators or observed that much hehehe seems pretty commonsensical though
@Boggled: Tall office buildings usually implement #4, for obvious reasons, but I really haven't seen #2 and #3 implemented in many buildings. Usually when the last person gets off the elevator, it stays there until it is called again. Maybe the buildings you've been in are different.
ReplyDeleteI suppose it also depends on the time of day. Morning would prolly be elevators all landing at the bottom, lunch would be even split, and afterwork would be just all over the place except for the bottom (on call). hehehe.
ReplyDeletenot a highrise kinda gal XD
The elevator problem is one based on partial information and optimisations built on prediction. Its a lot of unknowns and its far more complicated than anyone would care to think about.
ReplyDeleteBut think about the other problems as well:
1) When a button is pressed you don't know how many people are waiting
2) When the button is pressed you often don't know the direction people are going
3) Then there is power saving. You want to turn lifts off when they aren't in use and moving less floors should also save power.
4) How do we define minimum time? Is it the time for a lift to arrive, total journey time after the button is pressed.
5) Does optimising for minimum time journey system result in capacity issues?
....
An algorithm that remembered days and patterns might be able to better predict the comings and goings and different times (the ground floor rush at 9am and the floors leaving at 5pm). But its not sufficient to solve all problems. You need a very sophisticated algorithm to solve it, but the moment something odd happened it would be worse than a very simple strategy. People can predict the behaviour of simple strategies and its less likely to go wrong.
This has always been a problem I've been interested in. I think to provide the fastest possible service an elevator system needs to know about the people in its building.
ReplyDeleteFor example in an office building there will be multiple companies who many have a number of different start and finish times. So by monitoring these trends an elevator can predict peak times of usage. Whilst this does make the problem more difficult. It would make a very interestring problem to solve!
What if elevators could detect how much weight they were carrying, and had an approximate sense of how much weight was distributed to each floor at different times of day?
ReplyDeletereply to a 2 years old comment, yes, but that is some lateral thinking there FTW!
ReplyDeleteI'm pretty sure that was some vertical thinking, not lateral.
ReplyDeleteI'd use a statistical approach, if the elevator logs frequency use of each floor (over time) then it can statistically go to the floor(s) that are likely to have people at any given time. The system would get more accurate over time :)
ReplyDeleteSorry, late to the party, you just got mentioned on Reddit.
ReplyDeleteMy building, the new World Trade Center 7 building in NYC completely changes the model to remove some unknowns that paulrkeeble mentioned.
The number buttons are in the lobby. People type in the floor they want to go to, and the controller algorithm plans which elevators go to which floors. Interesting implementation with both advantages and disadvantages.
This fixes a problem of what the customer asks for instead of what the customer needs.
ReplyDeleteWhat the customer needs is downshifting and exercise, therefore the elevators should not be as fast as possible so people would have the luxury of waiting Those who could not afford the time can walk the stairs.
Example #5:~10 floors, 2 elevators. 1 for the odd floors, 1 for the even floors and both elevators stay in the ground floor when idle.
ReplyDeleteActually, there has been done some awesome research on Reinforcement Learning (reward-based learning) on elevators by Crites and Barto (the same Barto who wrote THE reinforcement learning book). For example, see http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.5519
ReplyDeleteHi Lisa, what you're discussing are called elevator group dispatch systems and where the elevators sit when they're idle is referred to as 'parking'. Almost all of the digital dispatch systems in use today (since the 90s) have a parking feature. Unfortunately many older buildings are still using old electrical relay systems to control the elevator (think software written with wires and switches), so there's no easy way to re-program them without an expensive overhaul (which most building owners avoid if they can).
ReplyDeleteThe idea of holding the lobby door open is generally called 'lobby open' and to make it work you usually need a big lighted 'THIS CAR UP' sign above the elevator so people know to get in.Sadly, clever parking assignments only help when the building is idle. Most of the time that you're frustrated while waiting for an elevator is when all the cars are active. Optimizing for high-traffic is really where the research goes into, and at the end of the day traffic flow is largely dominated by capacity (too few/slow elevators => long wait time).As a side note: Elevator algorithms are trivial for 1 elevator, but as soon as you have n > 1 the traffic optimization algorithms get much more interesting. People hold doors, elevators stop working or are pulled out of service, door limits stop signaling, people punch new destination floors while the elevator is in flight, etc.
Otis patented some of the basic algorithms back in the 70's, all expired now, but do a uspto search for Otis and 'Dispatch' and you'll find a trove of good info.
Also, some buildings (very modern ones) have a bank of elevators (>4) and you key in the floor you want to go to. A number appears as the door opens for the one you should take, which does have any floor options inside of it. thus the problem is optimized before you get in, rather then after.
ReplyDeleteI whipped up an elevator simulator in python that works on the idea of sending cars back to floor 1, but when a call is made finding the elevator that, by servicing the request, would be the least busy:
ReplyDeletehttps://gist.github.com/5eadf9eae5b35c368826
Very interesting , I agree going down to ground floor and kept is door open is one of the great optimization you can do.
ReplyDeleteYeah, also what if someone drops off at the 10th floor do we go all the way down and wait for the next passenger? What if the next passenger was on the 20th floor.... Just not sure about the power savings or cost
ReplyDeleteImagine the poor guy on the underpopulated floor getting screwed every day...!
ReplyDeleteThis is quite funny, because I went into the exact same process of thinking some time ago.
ReplyDeleteActually, I even entered the process as I manually send the elevator back to ground floor each time I take it :D.
Very interesting analyses here and in the comments... but I have to confess that I never take elevators, because where I live, I get where I need to go so much faster without them, and unless I have to go more than four floors up, I am never tempted to use an elevator.
ReplyDeleteThere is a 5th example, and it is quite efficient, though forces people to un-learn the old system.
ReplyDeleteThere are 38 floors and 12 elevators. When someone wants to go from the ground floor up, they call an elevator and indicate the floor they want to go to. Elevators do not allow input of floors from the ground floor, only the floor pre-selected, you are given a number and go to that elevator.
When going up/down the system will optimize for people calling the elevators somewhere mid-building.
From there we can experiment with things like: Do we always want to have one elevator on stand-by in a good location to service down requests, unless up requests are overwhelming, we can make the decision later too. What about dedicated elevators? What if you know someone is going to floor 22-8, but on floor 29 someone wants to go up. That means we know to service the up goer, then re-rout the elevator. What if someone is going to 28, but at 27 someone wants to go up, here's the interesting thing, we can guess that floors 27-29 due to data we have a-priori are the same office, so we tell the elevator to service 27, then 28 hoping the 27 goer wants to go to 28 (as indicated by past experience/company knowledge). However if we know people at 27 always go to floor 32, it may be better for everyone to send a free floating elevator to 27, and have the up goer just go directly to 32 (let's say elevator is currently at floor 7, and a free elevator is at floor 20).
By dedicating all elevators to optimization and gaining some knowledge into what floor people want to go to we can avoid having to split up elevators into groups and instead just optimize on individual ones.
With only one elevator, the ground-floor door open is the best solution, combined with always go in one direction because last thing you want is the elevator going up, someone stopping it, getting in, then the elevator continues to go up a lot. The person could have just waited outside and not caused the people already going up a delay.
Not to mention time of day - blocks of flats in the morning people mostly want to go down, with the opposite in offices - then reversed later.
ReplyDeleteJust as an aside at Amazon the buttons for the elevator are outside. There's one common panel and everyone waiting pushes the floor that they have to go to. And then it tells you which one of the elevators to wait for.
ReplyDeleteIt allows for far more optimization. Although I've never quantitatively measured the waiting time between this kind of system and other types of elevators.
http://en.wikipedia.org/wiki/Elevator#External_controls
I work in a building with 42 floors and 4 banks for 6 elevators.
ReplyDeleteThey banks serve a block of 10-15 floors each, with a transfer floor at 15, 25,
35. I think this is quite common.
One big problem is when a lift is full and it keep stopping at
every floor, this is very annoying and is a total waste of time. Problem is the
weight isn't an easy value to use, as people carry bags, etc. We came up with
an idea for having a camera look at available floor space (using some kind of
UV paint). The only risk is people opening umbrellas etc ;)
I think the only real way to improve them is to have them learn
based previous data. Over time this would allow them to perform at an optimum
regardless if it’s a weekend or a holiday or on a day when everyone is leaving
early.
I got off the elevator at my office yesterday and was thinking about this very same thing. Was going to build a demonstration/simulator page for it.
ReplyDeleteEvery time I ride the elevator in my building, I tell myself that I have to find the time to build an elevator simulation program - just for fun.
ReplyDeleteToo many times I've been in the lobby, and watched an elevator pass right by G on the way up. Naturally, I'm convinced I could do it better :P
It grows more and more complex in my head every time I notice another factor. Multiple parking levels, peak hours (meal times, people going to work, dog hours), people calling for elevators but changing their minds (forgot something), all looking for that perfect optimization.
I'm really drawn to this sort of puzzle.
Thanks for the article.
SimTower would be perfect for you to play with. You can experiment with all your best options.
ReplyDeletehttp://en.wikipedia.org/wiki/SimTower
I am so glad I'm not the only person who thinks about this stuff. I use to think I was a little bit crazy.
ReplyDeleteWhat I would like to see is accurate data on elevator usage and requests by floor for buildings. I think that these could be optimized further based on that data.
Great article!
Brad Powers
bpowers.org
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
ReplyDeleteUnfortunately, that's only for customers going "down". Customers going up, especially from the lobby should be given high priority because they need to become productive or add value as quickly as possible. I've sweated getting somewhere on time because of stupid elevator designs that don't optimise for lobby traffic.
ReplyDeleteFor those who would be paying for the install/improvement, it would probably boil down to the question, "Why?" In other words, what's the ROI?
ReplyDeleteI have also heard of some buildings that have double-decker elevators that service two floors at the same time. The way they are done is that odd floors can only go to odd floors, and even floors to even. And occasionally they have a transition floor that will get you from one to the other.
ReplyDeletehttp://en.wikipedia.org/wiki/Double-deck_elevator
Can these algorithms be used to get a higher score in Elevator Action?
ReplyDeleteDoes the UP, UP, DOWN, DOWN, cheat codes be used against elevator algorithms?
ReplyDeleteI worked in a building where the traditional up/down panel is replaced with a numpad such that you have to enter which floor you wish to go. Great idea but the implementation was so bad. The wait time was longer than traditional lifts.
ReplyDeleteThis would considerably increase the length of time it takes to go between adjacent floors. Imagine having to go from floor 9 to floor 10 and having to switch elevators on the first floor.
ReplyDeleteI've worked in a building where all elevators automatically returned to the first floor. Worked great in the morning, but _very_ annoying during lunch and after work when everyone is headed home.
ReplyDeleteAdjacent floors isn't a big deal -- you just take the stairs. But if you wanted to go from floor 5 to 10, then it gets more annoying.
ReplyDeleteYeah, but isn't it really the same thing? Take the elevator from 5 to 11 and then take the stairs down one floor. Then, when going back to 5, walk down one floor to nine and go to 5. I'm assuming all floors will have a stairwell. Handicap access will be more inconvenient though.
ReplyDeleteAnd why can't traffic engineers design stop lights such that traveling on a major road is not interrupted every other intersection for two minutes while no cars on side roads wait for no pedestrians to cross before the ten second interval in a five minute cycle leaves them standing in the road?
ReplyDeleteYou sound like you know what you're talking about. I'm looking at elevator dispatching algorithms as a topic for a presentation for a Theory of Algorithms class. Could you point me toward some good sources?
ReplyDeleteHas anyone thought about machine learning algorithms? Since one can imagine that if it is a office building, in the morning, people want to go up, in the afternoon, people want to go down; while in an apartment building, it is the opposite. An elevator can learn the pattern of requests of each days and determine where to stop if idle at that hour. Just a thought.
ReplyDeleteI like traffic lights
ReplyDelete