Elevator Algorithm – Finding the Shortest Path for Floor Orders

algorithmspathpath findingsimulation

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?

Best Answer

"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.

Related Topic