43

I'm trying to simulate an elevator, as always I started very simple by taking only a single order at a time, then added memory to the elevator in the form of queues so that floors are traveled in the order in which they were pressed, which obviously isn't the best approach.

So at the moment I'm using a very simple and "short sighted" logic which is, for the current floor find the floor closest to me and set it as my next destination and loop till no more floors are in the list.

But this doesn't always work, for example the elevator was in the 3rd floor of a 5 floor building and got orders 4,5,2 the shortest path would be 2->4->5 which costs 4 floors but using this logic 4->5->2 which costs 5 has the same chance of being picked, depending on the code.

How do I find the shortest path and make the elevator more efficient?

5
  • 2
    Somewhat related: programmers.stackexchange.com/q/96278/149904
    – manlio
    Commented Sep 22, 2016 at 7:39
  • 11
    I'd like to invite you to my office and figure out the algorithm that the elevators use there. Because I absolutely can't.
    – gnasher729
    Commented Sep 22, 2016 at 14:22
  • 2
    @gnasher729 Oh, I can even though I don't know you, because it's surely the same as in my office: never stop at the floor I'm in, except when already full of people. Am I right?
    – Andres F.
    Commented Sep 22, 2016 at 17:43
  • 2
    Not quite. There are four elevators. You press the button, nothing moves for a very long time. If one moves it stops right before your floor and waits for ages, until it is overtaken by another one which goes past your floor and then comes down. On the way down to the ground it stops at least three times with nobody entering.
    – gnasher729
    Commented Sep 22, 2016 at 19:11
  • 3
    Relevant programming game / challenge: play.elevatorsaga.com
    – dwikle
    Commented Sep 27, 2016 at 18:46

4 Answers 4

Reset to default
43

"Efficiency" is not the most important feature, the most important is to make sure every order is followed, that there is no starvation. If someone presses 100 and people keep pressing 1 and 2 it may be efficient to keep going between those floors, but it'd be nice for 100 to be visited at some point.

I think (from personal observation when I was interested in figuring out) that most of them do:

  1. Start going in the direction of the first button pressed, keep track of which direction we're going
  2. When a floor is reached and that button was pressed, stop and open the doors, mark the buttons for this floor as not pressed anymore.
    • If there are still more floors that we need to visit that are in the same direction, keep going in that direction.
    • If not and there are still floors we need to visit, move in that direction.
    • If not then we're done and will start at 1 when a button is pressed again.

Note that many elevators have buttons "I want to go up" and "I want to go down" next to the doors instead of a single button. The algorithm only needs a small change: in 2, if the only button pressed for that floor is one of the buttons next to the door, only stop and open the doors if we are going in that direction. Possibly keep the button pressed if the doors open because of a button pressed inside the elevator and it is going in the wrong direction.

You never have to figure out an entire path, just in which direction to go next.

10
  • this completely skipped my mind, I was so focused on efficiency and forgot other things are important too. it's still not efficient to go say from 2->100 and back to 1 simply because it was in the same direction but at least it ensures no starvation. and,completely off topic, perhaps this is why it's common to find two elevators with this logic? which makes me wonder if it's more common to find the elevators going in the opposite direction at any given time. anyways, I'm still curious on how to find the shortest entire path, but this does answers my question very neatly, thanks
    – Raed Tabani
    Commented Sep 22, 2016 at 7:47
  • 12
    Note that once you get to a building with 100 floors, you will typically have elevators serving only a specific range of floors (e.g. 0-19, 20-39, …), as well as express elevators that only go long distances (e.g. 0 to 50, 0 to 100, 50 to 100, but no floors in between), so you might have to change elevators to get to your destination. You might also have multiple elevators per shaft that obviously cannot pass each other. Totally off-topic: IIRC, there was a question about the efficiency of those up and down arrow buttons on the User Experience site that made for very fascinating reading.
    – Jörg W Mittag
    Commented Sep 22, 2016 at 8:01
  • thanks, I didn't know that. subdividing seems as a good a strategy if one part breaks down the whole system doesn't and also to distribute the load which is important for mechanical wear and tear. I wondering if these express elevators came to be due to the logical shortcomings of the Knuth's Elevator algorithm.
    – Raed Tabani
    Commented Sep 22, 2016 at 8:19
  • only other thing i'd add is that often they have a 'home' floor that they will return to when not in use, this can be different for different elevators, and possibly even change depending on time of day and expected usage patterns
    – jk.
    Commented Sep 22, 2016 at 15:48
  • I have a tendency to push the up/down button semi randomly regardless of which direction I'm actually travelling in. In my case, I only ever have one destination, so the elevator takes me to that location regardless of whether I chose up or down. I suspect that if I were to push the down button, choose a floor above me, and then choose a floor below me before the elevator starts moving, it would take me to the floor below me rather than the floor that I pushed first. I could be wrong, I'll be sure to test it next time I find myself in an elevator.
    – Ucenna
    Commented Sep 22, 2016 at 17:48
15

The other answer correctly gives the standard elevator algorithm, which is basically "keep going in the same direction as long as possible and make every necessary stop along the way".

There are other elevator algorithms. For example, consider an apartment building where apartments get more expensive as you go up. The owners of the building might choose to modify the elevator algorithm to "go in the same direction as long as possible but only stop on the way down". That way if you have people in the elevator who are in the lobby and are going to 2, 5 and 10, the elevator goes to 10, then 5, then 2, dropping people off in order of how much rent they pay. But of course when the people on 10 leave their apartment, they'll more often have to wait longer to get to the lobby.

If you're looking for an efficient solution then come up with a metric for cost and implement a bunch of different algorithms, and run simulations. Remember to measure not just the average cost, but also metrics like the longest any one request takes to be serviced. Optimizing for low averages can sometimes deoptimize the worst case, which is bad.

1
  • 2
    It seems to be rare (other alogirthms)
    – FindOutIslamNow
    Commented Feb 19, 2018 at 6:23
13

Note that elevators use the same scheduling algorithms as some hard drive controllers. The standard SCAN algorithm is even known as the elevator algorithm. I think in practice the LOOK algorithm is more common, as it is slightly more efficient than SCAN.

2
  • When you speak so certainly, do you have professional experience implementing the code for elevators? Especially newer elevator systems? I am curious if after 9/11 in NYC there has been higher priority on sending passengers down vs. bringing them up.
    – John Zabroski
    Commented Aug 29, 2019 at 17:54
  • Get passengers out, not down. I am often using the elevator in a car park, where the third floor of floors 1 to 6 is the ground level, so to escape, floor 3 would be the best.
    – gnasher729
    Commented Feb 1, 2020 at 16:46
2

This answer is about a more advanced destination control system. In a building with multiple elevators where people indicate which floor they want to go to and the system assigns an elevator to them.

The idea is fairly simple, theoretically you know where everyone and every elevator is going. So you can for each elevator, calculate When your expected arrival time is and how much it will slow down the others. Greedely pick the fastest elevator.

There are limitations to this such as groups pressing the button only once and people pressing the button multiple times.

https://www.peters-research.com/index.php/support/articles-and-papers/38-understanding-the-benefits-and-limitations-of-destination-dispatch

Not the answer you're looking for? Browse other questions tagged or ask your own question.