Elevator dispatch algorithm choice

Question

We have a single elevator servicing an 8 level residential building. What might be the optimal elevator positioning algorithm to optimize user experience (primarily, wait time)?

I was thinking along these lines:

1. Most calls are likely to come from the Ground Level. So after servicing every call elevator heads back to ground level.

2. Option #1 might impose excessively high penalties on people summoning from, say, 7th level. So might returning to wait on, say, the 4th level minimising average response times?

3. Just wait wherever it last went to! (This is the current default)

Wondering what people think? (I've seen elevator scheduling articles but most tackle the multiple elevators servicing a commercial building test case)

Of course, in a more complex situation it is also likely that usage on some floors might be higher than the rest. An algorithm that "learns" this might be even smarter, but I've no clue how it might exploit this.

PS. A single elevator servicing a 8 level building is odd. Would probably be a code violation now. But has been grandfathered in as this is an older building.

PPS. If optimizing energy usage was a criterion would Algorithm #3 be the natural best? Or could one do better?

Answer 1

Any problem like this involves a matrix of priorities that you need to decide on before you can have a solution. For example, do you care more about people waiting on the ground floor than any of the other floors? Do you care about energy consumption? Is there a particular floor that is more important than others?

Once you've decided on these, you can build a simple discrete model (in something like Arena) and test your various algorithms.

I had a problem very much like this one at university to model and solve, where we allocated equal value to people waiting regardless of what floor it was on; assumed the same distribution of use on each floor (other than the first floor, with first being what americans would call second floor); and we included the energy consumption and wear and tear costs on the elevator as factors.

Then you need to remember that an elevator has more than one stationary state: Doors open waiting, and doors closed waiting. If an elevator is waiting with it's doors closed, it can respond much faster than if it has to first close its doors.

Our end result was that if the elevator stopped on any floor less than half way between the top and the ground floor, it was best for it to wait there (with doors closed) until the next call. If it stopped at anywhere in the top half of the floors, it should move down to the middle floor and wait there with doors closed.

As it turns out, this is also the algorithm used by a building that I lived in which had 9 floors.

Answer 2

People use the elevator to move between ground (0) floor and one of the higher floors. There are two directions, upward and downward. In situation when all the people have to use elevator, upward and downward category stats would distribute normally, so about 50% of calls should be from the floor level.

People are more up to use stairs in the following situations:

• when they want to go down, especially when it means 1-3 floors
• when they want to go up 1-2 floors

The reason has economical background - both waiting and using stairs is an alternative cost for them. The cost of going up increases, let's say, linearily depending on the number of floors to travel. If this cost is quite low, some of them choose to invest the power of their muscles (relatively low requirement for this when there are just a few floors to go) instead of spending time for waiting.

While giving numbers here is a little bit difficult, this will definitely shift the tendency of calling elevator to the calls from the ground level. Let's just assume that 60% of calls are coming now from the ground floor.

In this case, placing the elevator on the ground floor when idle seems to be the best solution. Should you have two elevators in your building, you could consider pulling one down to ground floor when idle, and sending the other to one of the middle floors. 4th is not reasonable here, because some people from lower floors will use the stairs and the need for an elevator increases with the number of the floor. So, I think the second one should wait at maybe 6th floor when idle.

Anyway, I think it would be good to collect usage stats to tweak the algorithm if necessary or to treat it as a proof or concept.

Answer 3

You might factor in heuristics like

• more people will be exiting than entering in the morning
• more people will be entering than exiting in the evening

Of course observed patterns (i.e. learning) would have more weight than heuristic guesses like the ones I've made above. You do some meaningful optimization without a learning algorithm simply by recording events over a period of time and then analyzing them yourself possibly with the aid of simple visualization software, then adjusting the behavior of the dispatch algorithm. With this technique in effect you are the learning algorithm. It would be even more effective you wrote a simulator with which you could plug in various dispatch algorithms and play them over the data that was collected and see which dispatch algorithm gives the desired characteristics.