Elevator Algorithm

Problem:   Describe an algorithm that you could use if programming an elevator. 

Solution:  No custom elevator knowledge is assumed here.  Let’s start by drawing a picture to allow us to make sure that we understand the problem.

Pic 1 is a simple picture of an elevator and some floors it can stop on.

Let’s start by talking about the characteristics of the problem, which we will have to optimize:

•        There are a certain number of floors on which the elevator can stop
•        It takes a certain amount of time for the elevator doors to open and close
•        It takes time for the elevator to accelerate, stop and has a max speed
•        People can signal the elevator and indicate whether they are going up or down
•        The elevator has a maximum capacity

Now, lets’ talk about some of the basic elements of an algorithm for an elevator:

•        Elevators should minimize waiting times for people who are signaling the elevator
•        Once an elevator starts going up and someone indicates a higher floor on it, the evator should not go down
•        Same as 2, but for down
•        Elevators should minimize transit times for people in the elevator

Well, already, this is looking much more complicated.  We have multiple characteristics and rules.  Let’s now put this together, and start talking about what we know about elevators:

•       When someone is in the elevator, it is going up or down. 
•       It will go up and stop at every floor where either: 1) someone in the elevator has selected, or 2) someone outside the elevator has pressed the up button
•       It will go down and stop at every floor where: 1) someone in the elevator has selected, or 2) someone outside the elevator has pressed the button
•      It will always stop at the bottom floor when going down if someone has pressed the up button
•      It will always stop at the top floor when going up if someone has pressed the down button

These are the basics.  Now, let’s try an example.  Assume that someone walks into a building and presses the up button on the bottom floor – what happens?

Well, assuming no one is in the elevator, it will come down from the floor it is on.  So, the person will have to wait while the elevator comes down. 

This example highlights another issue.  Where does the elevator wait when it is not in use?

One first thought would be to wait in the middle.  This would seem to optimize between people going up and people going down.  We can probably assume too that there are relatively few trips between floors – though even this may not be true if for example a company has offices on more than one floor.

But, let’s keep it simple.  But, think about someone coming in to go up.  When do people do this?  And, when do people go down primarily?

This would depend a little on the type of building.  In an office building, people will often come in in the morning and leave in the evening.  In an apartment building, it would be the opposite. 

One optimization could be to move the elevator closer to where people are expected at different times of day.  This could reduce wait times dramatically.

We have most of what we need to write out an algorithm.  Let’s do it now:

First, let’s bring in all the rules that are expected:

1    When someone is in the elevator, it is going up or down. 

a.       It will go up and stop at every floor where either: 1) someone in the elevator has selected, or 2) someone outside the elevator has pressed the up button

b.      It will go down and stop at every floor where: 1) someone in the elevator has selected, or 2) someone outside the elevator has pressed the button

2    It will always stop at the bottom floor when going down if someone has pressed the up button

3    It will always stop at the top floor when going up if someone has pressed the down button

And, let’s add, assuming we have an office building:

•      The elevator will wait at the bottom floor when not in use between 7am-10am. 
•      The elevator will wait at the top floor when not in use between 3pm – 7pm.
•      At other times, the elevator will wait in the middle floor

Well, we have a good algorithm here. 

Most important in this problem, is to 1) not ignore the obvious such as the rules of how an elevator works and what it is trying to optimize, and 2) always seek to ‘stretch’ your answer.  In this case, we stretched with an optimization problem.

/* Please let me know if you find bugs or have alternate solutions.  Thx, Noah */