4 ms·

Interesting video. I've often wondered what the most optimal elevator algorithm is. Imagine a scenario where a single person calls an elevator to go down, and

by cedws 3y ago

Interesting video. I've often wondered what the most optimal elevator algorithm is. Imagine a scenario where a single person calls an elevator to go down, and just as they get in, a group of five people on the floor above also call the elevator to go down. We all know that the elevator would go straight down and then come back up for the people who called the elevator too late. The elevator could actually save time by letting the person on the lower floor board, going one floor up, and letting the group board before going back down. The algorithm could factor in the number of people waiting on each floor, the time taken to travel between floors, and how many people are already on the elevator into account to optimise its route. With multiple elevator shafts there's even more things to think about. Could one shaft serve a lower set of floors while another shaft serves a higher set of floors to minimise 'wasted' time travelling up and down? Could the algorithm take into account the time of day and the ingress/egress of people from the building? Is there a specific floor that's 'hot' and could be prioritised? I guess the two numbers to optimise for are wait time and travel time and there will be some tradeoffs. edit: One more thought. Time taken to travel between floors is probably not even close to linear. The elevator has more time to accelerate for greater elevation changes.

koolba 3y ago
> Could one shaft serve a lower set of floors while another shaft serves a higher set of floors to minimise 'wasted' time travelling up and down? “Shafted” is how the guy already in the elevator would describe the elevator going up to get the group when he wants to go down.
- cedws 3y ago
  :) maybe. The guy already in the elevator would surely benefit from this one day too.
- jrs235 3y ago
  What would be worse than that is being on a low floor needing to go to a high floor or vice versa and someone getting on and pressing all the floors inside the elevator so it has to stop at each and every floor.
robertlagrant 3y ago
If I remember the story correctly, the creator of Sim Tower[0] wondered the same, and discovered that the algorithms governing that were closely-guarded secrets. So he developed Sim Tower. [0] https://en.wikipedia.org/wiki/SimTower https://en.wikipedia.org/wiki/SimTower
- jvanderbot 3y ago
  So, somewhat related. Is there a way to play Sim Tower nowadays? I regret that I never got that last star, and think about it once or twice a year.
  - duck 3y ago
    There is a pretty cool PICO-8 remake: https://www.lexaloffle.com/bbs/?tid=46087 https://www.lexaloffle.com/bbs/?tid=46087
  - brirec 3y ago
    Try https://infinitemac.org/ https://infinitemac.org/ Pick a System Software/Mac OS version (you probably want something like 7.5), then choose the SimTower disc from the CD-ROMs drawer at the bottom of the screen.
    - 4gotunameagain 3y ago
      This has blown my mind, thank you. ...but: The emulator encountered an error: Could not load disk chunk /CD-ROM/aHR0cHM6Ly9hcmNoaXZlLm9yZy9kb3dubG9hZC9TaW1Ub3dlck1hY09TL1NJTVRPV0VSLmJpbiNNT0RFMS8yMzUy/172097536-172228608.chunk#1313: HTTP status 500: ()
- adhesive_wombat 3y ago
  > algorithms governing that were closely-guarded secrets Do many lifts have fancy algorithms in practice? I don't think I've ever had one go backwards to pick up a nearby floor, for example. I suppose optimising where the lift loiters while empty is something I wouldn't really notice happening.
- 3y ago
aaron695 3y ago
[dead]
V__ 3y ago
Have you played Elevator Saga? You could try it and them compare the stats. [1] https://play.elevatorsaga.com/ https://play.elevatorsaga.com/
flir 3y ago
You may enjoy this. I lose a couple of days to it every time I remember it: https://play.elevatorsaga.com/ https://play.elevatorsaga.com/
- cedws 3y ago
  This is amazing, thanks. If Zachtronics released a game like this I'd never be seen again.
zdragnar 3y ago
What are you optimizing for? Median? Mean? 99th percentile? Also, people will try to "beat" the algorithm, especially if they have to wait the same amount of time on a barely trafficked floor as people on the busy "hot" floor... kindof like how cars will zip back and forth in mild traffic jams trying to find the "faster" lane. It's probably better to just have a simpler, predictable system.
brazzy 3y ago
> Could one shaft serve a lower set of floors while another shaft serves a higher set of floors to minimise 'wasted' time travelling up and down? That's actually completely standard for very tall buildings, and of course the shafts that e.g. serve only the higher floors don't go all the way down, because the space used by elevators becomes an even bigger problem than the travel time as buildings get taller. Another option to increase capacity is to have double-decker elevator cars that serve different floors.
- juggertao 3y ago
  There were discussions to put multiple cars in the same shaft. Obviously there are some complications.
myself248 3y ago
The trouble is that the call button doesn't indicate how many people want to go in a given direction, just that there's more than zero with such a desire. If you could get people to input perfect information about where they wanted to go (ideally on the way to the elevator lobby, before having arrived there), much greater optimization would be possible.
- cedws 3y ago
  I was thinking about the problem more from a theoretical standpoint, but you could fit an elevator system with a 'people counter' on each floor.
- mcmoor 3y ago
  Interestingly my building already require that information before using elevator. I wonder how efficient this building's lift actually becomes.
- juggertao 3y ago
  Most modern buildings (2008+) don't have up/down buttons anymore, instead they require each person to input the exact floor they want to go to on a keypad. It's called "destination dispatch".
  - bombcar 3y ago
    This is true on the main landing, but often all the floors above just have simple up/down buttons and you select a floor once inside.
- mywacaday 3y ago
  AI with a camera could give close to perfect information on how many boarded/left on each floor. Maybe it could even identify VIPs like medical personell and give them priority. Of course someone will eventually try to put a subscription model on it.
mlcrypto 3y ago
I've seen elevators exhibit queue starvation behaviors when everybody in the hotel is trying to leave for the same event on time
Jun8 3y ago
You may find my HN comment from two years ago, the resulting discussion and the parent story interesting: https://news.ycombinator.com/item?id=27487993 https://news.ycombinator.com/item?id=27487993
kaashif 3y ago
Concentrated harm and distributed benefit is a recipe to have a few vociferous complainers and many silent beneficiaries. People who believe they've suffered a grave injustice will be much louder. The best algorithm and least complaint-inducing algorithm are distinct.
- deleted 3y ago
  [deleted]
- duped 3y ago
  > Concentrated harm and distributed benefit is a recipe to have a few vociferous complainers and many silent beneficiaries A fascinating example of this with queuing humans is the Disney Fastpass system (1). I think the real design goal to avoid "complainers" is to try and optimize the wait time for your resource to avoid a bimodal distribution and try and spread it out for the average rider, rather than make wait times worse for the majority of people but better for the people who game the system. (1) https://www.youtube.com/watch?v=9yjZpBq1XBE https://www.youtube.com/watch?v=9yjZpBq1XBE, yes this is an 1:45 long video on the history and a simulation of Disney parks, but its worth the payoff.
- cedws 3y ago
  The "harm" in this case is potentially a few seconds added to an elevator ride. I think there is another psychological effect to consider. Once you've boarded an elevator, you're no longer really 'waiting'. Even if an elevator takes you on a longer trip than necessary it might not be as annoying as a longer elevator wait. And ultimately, elevators are not ran by democracy. If the algorithm benefits thousands of employees in an office then any complainers will probably be told to shove it by the office staff. Nobody likes being stopped at a red traffic light but we all understand they're a necessary evil so we don't crash and kill ourselves.
  - grudg3 3y ago
    Unless the C-levels complain, then the algorithm will be changed to make them happy.
  - 3y ago
deleted 3y ago
[deleted]
Ekaros 3y ago
> With multiple elevator shafts there's even more things to think about. Could one shaft serve a lower set of floors while another shaft serves a higher set of floors to minimise 'wasted' time travelling up and down Yes. This is done, that is they start from bottom floors and then just don't stop at lower floors. Thus not needing to accelerate or deaccelerate. One more fun trick is double decker cars. That is one deck of elevator only stops at even or odd floors. This being easiest way to double capacity.

by cedws 3y ago

koolba 3y ago

> Could one shaft serve a lower set of floors while another shaft serves a higher set of floors to minimise 'wasted' time travelling up and down? “Shafted” is how the guy already in the elevator would describe the elevator going up to get the group when he wants to go down.

cedws 3y ago
:) maybe. The guy already in the elevator would surely benefit from this one day too.
jrs235 3y ago
What would be worse than that is being on a low floor needing to go to a high floor or vice versa and someone getting on and pressing all the floors inside the elevator so it has to stop at each and every floor.

robertlagrant 3y ago

If I remember the story correctly, the creator of Sim Tower[0] wondered the same, and discovered that the algorithms governing that were closely-guarded secrets. So he developed Sim Tower. [0] https://en.wikipedia.org/wiki/SimTower https://en.wikipedia.org/wiki/SimTower

jvanderbot 3y ago
So, somewhat related. Is there a way to play Sim Tower nowadays? I regret that I never got that last star, and think about it once or twice a year.
- duck 3y ago
  There is a pretty cool PICO-8 remake: https://www.lexaloffle.com/bbs/?tid=46087 https://www.lexaloffle.com/bbs/?tid=46087
- brirec 3y ago
  Try https://infinitemac.org/ https://infinitemac.org/ Pick a System Software/Mac OS version (you probably want something like 7.5), then choose the SimTower disc from the CD-ROMs drawer at the bottom of the screen.
  - 4gotunameagain 3y ago
    This has blown my mind, thank you. ...but: The emulator encountered an error: Could not load disk chunk /CD-ROM/aHR0cHM6Ly9hcmNoaXZlLm9yZy9kb3dubG9hZC9TaW1Ub3dlck1hY09TL1NJTVRPV0VSLmJpbiNNT0RFMS8yMzUy/172097536-172228608.chunk#1313: HTTP status 500: ()
adhesive_wombat 3y ago
> algorithms governing that were closely-guarded secrets Do many lifts have fancy algorithms in practice? I don't think I've ever had one go backwards to pick up a nearby floor, for example. I suppose optimising where the lift loiters while empty is something I wouldn't really notice happening.
3y ago

aaron695 3y ago

[dead]

V__ 3y ago

Have you played Elevator Saga? You could try it and them compare the stats. [1] https://play.elevatorsaga.com/ https://play.elevatorsaga.com/

flir 3y ago

You may enjoy this. I lose a couple of days to it every time I remember it: https://play.elevatorsaga.com/ https://play.elevatorsaga.com/

cedws 3y ago
This is amazing, thanks. If Zachtronics released a game like this I'd never be seen again.

zdragnar 3y ago

What are you optimizing for? Median? Mean? 99th percentile? Also, people will try to "beat" the algorithm, especially if they have to wait the same amount of time on a barely trafficked floor as people on the busy "hot" floor... kindof like how cars will zip back and forth in mild traffic jams trying to find the "faster" lane. It's probably better to just have a simpler, predictable system.

brazzy 3y ago

> Could one shaft serve a lower set of floors while another shaft serves a higher set of floors to minimise 'wasted' time travelling up and down? That's actually completely standard for very tall buildings, and of course the shafts that e.g. serve only the higher floors don't go all the way down, because the space used by elevators becomes an even bigger problem than the travel time as buildings get taller. Another option to increase capacity is to have double-decker elevator cars that serve different floors.

juggertao 3y ago
There were discussions to put multiple cars in the same shaft. Obviously there are some complications.

myself248 3y ago

The trouble is that the call button doesn't indicate how many people want to go in a given direction, just that there's more than zero with such a desire. If you could get people to input perfect information about where they wanted to go (ideally on the way to the elevator lobby, before having arrived there), much greater optimization would be possible.

cedws 3y ago
I was thinking about the problem more from a theoretical standpoint, but you could fit an elevator system with a 'people counter' on each floor.
mcmoor 3y ago
Interestingly my building already require that information before using elevator. I wonder how efficient this building's lift actually becomes.
juggertao 3y ago
Most modern buildings (2008+) don't have up/down buttons anymore, instead they require each person to input the exact floor they want to go to on a keypad. It's called "destination dispatch".
- bombcar 3y ago
  This is true on the main landing, but often all the floors above just have simple up/down buttons and you select a floor once inside.
mywacaday 3y ago
AI with a camera could give close to perfect information on how many boarded/left on each floor. Maybe it could even identify VIPs like medical personell and give them priority. Of course someone will eventually try to put a subscription model on it.

mlcrypto 3y ago

I've seen elevators exhibit queue starvation behaviors when everybody in the hotel is trying to leave for the same event on time

Jun8 3y ago

You may find my HN comment from two years ago, the resulting discussion and the parent story interesting: https://news.ycombinator.com/item?id=27487993 https://news.ycombinator.com/item?id=27487993

kaashif 3y ago

Concentrated harm and distributed benefit is a recipe to have a few vociferous complainers and many silent beneficiaries. People who believe they've suffered a grave injustice will be much louder. The best algorithm and least complaint-inducing algorithm are distinct.

deleted 3y ago
[deleted]
duped 3y ago
> Concentrated harm and distributed benefit is a recipe to have a few vociferous complainers and many silent beneficiaries A fascinating example of this with queuing humans is the Disney Fastpass system (1). I think the real design goal to avoid "complainers" is to try and optimize the wait time for your resource to avoid a bimodal distribution and try and spread it out for the average rider, rather than make wait times worse for the majority of people but better for the people who game the system. (1) https://www.youtube.com/watch?v=9yjZpBq1XBE https://www.youtube.com/watch?v=9yjZpBq1XBE, yes this is an 1:45 long video on the history and a simulation of Disney parks, but its worth the payoff.
cedws 3y ago
The "harm" in this case is potentially a few seconds added to an elevator ride. I think there is another psychological effect to consider. Once you've boarded an elevator, you're no longer really 'waiting'. Even if an elevator takes you on a longer trip than necessary it might not be as annoying as a longer elevator wait. And ultimately, elevators are not ran by democracy. If the algorithm benefits thousands of employees in an office then any complainers will probably be told to shove it by the office staff. Nobody likes being stopped at a red traffic light but we all understand they're a necessary evil so we don't crash and kill ourselves.
- grudg3 3y ago
  Unless the C-levels complain, then the algorithm will be changed to make them happy.
- 3y ago

deleted 3y ago

[deleted]

Ekaros 3y ago

> With multiple elevator shafts there's even more things to think about. Could one shaft serve a lower set of floors while another shaft serves a higher set of floors to minimise 'wasted' time travelling up and down Yes. This is done, that is they start from bottom floors and then just don't stop at lower floors. Thus not needing to accelerate or deaccelerate. One more fun trick is double decker cars. That is one deck of elevator only stops at even or odd floors. This being easiest way to double capacity.