9 ms·
Elevator Algorithms
- jvdh 15y agoThis 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&hl=en&btnG=Search&as_sdt=1%2C5&as_sdtp=on http://scholar.google.com/scholar?q=elevator+algorithm&h...
- deleted 15y ago[deleted]
- shasta 15y agoJust 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 15y agoI 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 15y agoI 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 15y agoThen 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 15y agoAm 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 15y agohttp://tierneylab.blogs.nytimes.com/2007/12/20/smart-elevators-dumb-people/ http://tierneylab.blogs.nytimes.com/2007/12/20/smart-elevato...
- obtu 15y agoThe only optimisation this one has (that the article tells us about) is that passengers choose their floor, but not the elevator to get there.
- obtu 15y agoNot 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 https://news.ycombinator.com/item?id=3153227
- JonnieCache 15y agoNo, 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 15y agoAt 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_downs 15y agoVery 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 http://en.wikipedia.org/wiki/LOOK_algorithm [2] http://en.wikipedia.org/wiki/Elevator_algorithm http://en.wikipedia.org/wiki/Elevator_algorithm
- karambahh 15y agoI'm definitely interested in playing with your simulator!
- dodo53 15y agoAlso 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.
- deleted 15y ago[deleted]
- dinedal 15y agoI 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 15y agoit'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.
- dinedal 15y agoI 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 15y agoThis. 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)
- deleted 15y ago[deleted]
- jhugg 15y agoI 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.
- edw519 15y agoHmmm, 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_downs 15y agoWhy 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 15y agoA 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.
- eykanal 15y agoI 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.
- joezydeco 15y agoThose 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 15y agoIs that just a customer comfort thing, or has nobody managed to invent a sign that people will read yet?
- tedunangst 15y agoPeople 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.
- wnight 15y agoThese 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.
- seles 15y agoAn 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 15y agoProtip: Only build offices, no condos. I got to 5 stars without once optimizing the elevators.
- seles 15y agoThere 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 15y agohttp://www.reddit.com/r/IAmA/comments/b1bpp/i_program_elevators_for_a_living_ama/ http://www.reddit.com/r/IAmA/comments/b1bpp/i_program_elevat...
- afterburner 15y 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 15y agoMachine 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 15y agoDidn'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 15y agoWhat 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 15y agoIt'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-1-manhattan-article-1.991368?localLinksEnabled=false http://www.nydailynews.com/new-york/elevator-accident-kills-... What the hell kind of behavior is that?
- MaxGabriel 15y agoPresuming 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 http://en.wikipedia.org/wiki/Storey#North_American_scheme
- mrbgty 15y agoElevators 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 15y agoThere 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_elevators_for_a_living_ama/ http://www.reddit.com/r/IAmA/comments/b1bpp/i_program_elevat...
- fleitz 15y agoIt'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 15y agoRelated: Double-deck Elevators - http://en.wikipedia.org/wiki/Double-deck_elevator http://en.wikipedia.org/wiki/Double-deck_elevator - At what point do these become a worthwhile investment?
- jdpnd 15y agoCouldn'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 15y agoWhy 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 15y agoI'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.
- wnight 15y agoAnd 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 15y agoWhy 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-midtown-elevator-plunge-one-critically/ 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 15y agoMakes 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 15y agoThere'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 https://en.wikipedia.org/wiki/Paternoster [2] http://www.designweek.co.uk/home/blog/moving-platforms/3027767.article http://www.designweek.co.uk/home/blog/moving-platforms/30277...
- jhrobert 15y agoOn 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 15y agoWell, 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 15y agoI 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 15y agoI'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 15y agoI 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 15y agoAs 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 15y agoReminds 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.