**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 */

From my friend Steve: Should I assume the floors are in order? The floors numbers in US buildings look like alphabet soup. The newest technology has users punch in their floor number in the lobby and the cabs have no buttons. Also, how many local and express cabs are in the bank, and are we optimizing for dispatch time or trip time? Are there up peak and down peak periods? Do we trigger those periods by car load factor or clock?

ReplyDelete