Everyday Algorithms: Elevator Allocation

Share on Facebook12Tweet about this on Twitter30Share on Google+3Share on Reddit39Share on StumbleUpon4,096

Every day in cities such as Chicago, New York, Tokyo, Singapore, Hong Kong and more, millions of people attempt to leave their buildings via elevator. However, very rarely do we consider how elevators are allocated to provide service, especially during rush hour(s), when most of the building will attempt to exit in a matter of an hour or so.

skyline

There is at least one patent on an algorithm on the subject (Elevator call allocation system based upon passenger waiting time), research (Elevator Traffic Simulation), and has appeared on Quora as well. I have even been asked how I would allocate elevators on an interview before (which I wrote about previously):

There are ten floors, each with the same number of people living on each floor. There are three elevators and no stairs. How would you allocate the elevators for optimal(ish) performance, minimizing waiting time for each floor?

I enjoyed this interview question, I thought it was both challenging and you could take it as far as you desired, but also straight forward enough that you could “get started” and produce some sort of solution. Rather than trying to rack my brain for a month trying to model a real world scenario, in this article I will attempt to solve a simplified model of allocating elevators, similar to the interview question above.

Problem Description

elevators

Creating an algorithm applicable for the real world allocation of elevators is fairly difficult (and is apparently patented). Therefore, I will be trying to solve something similar to my interview question, with a few minor changes:

Design an algorithm to minimize the total waiting time of all individuals waiting in a building, while also taking into consideration load per elevator. Given there are equal number of people on each floor, with a uniform appearance of individuals to use the elevator at each floor. Assuming there are several hours a day which are “rush hour times,” the algorithm should provide the most “fair” way to distribute the elevators to the various floors.

That was a mouthful, but if we break it down, the problem consists of the following:

  • Arbitrary number of floors
  • Arbitrary number of elevators
  • Given rush hour times
  • We must distribute elevators based on some function of load and time

There are also some unsaid variables/constants we should take into consideration:

  • Number of individuals per floor: 100 persons
  • Time for the elevator to transition one floor (without stopping): 5 seconds
  • Waiting time per floor: 20 seconds

I added numbers to the variables above, and although “time for the elevator to transition one floor” is likely not linear (that is to say, it takes time to accelerate from a stopped position), we will assume so in this case. Making these assumptions may “over simplify” the problem, however I believe this article will suffice for an interview or as an excellent launching point to a more in-depth contemplation/discussion.

Notice that I did not take into consideration the capacity of the elevators, in this case I am going to make a big assumption. My assumption will be (throughout this solution) that each elevator has a limitless capacity. Obviously, this cannot be true, however once we have a solution in hand I feel it will be simpler to add a statement such as:

If elevator is full, return to lower level
After dropping off guests, return to previous floor

Perhaps, I will write another article and post it on this blog or I will distribute via my mailing list, in either case, I hope someone will try to solve it themselves!

Elevator Allocation Algorithm

This is probably not the best solution,
though it does seem to work out well.

If you find a better solution, please share!

Screen Shot 2014-07-14 at 8.14.21 PMAs the image above suggests, I decided to designate a specific elevator to a particular floor, I’ll call this zone elevator allocation. The idea being, we can attempt to average the wait time of each floor as well as the load of each elevator.

My particular solution was based off a few observations I made on the time it takes for each elevator to make a circuit (go through all the floors in its loop, i.e. 0 -> 1 -> 2 -> 0). All we need to know is the following to calculate the time for an elevator to complete a circuit:

  1. Time to pass a floor times maximum floor in the circuit times two (up and down), in this case: (5 seconds * <maxFloor> * 2)
  2. Number of stops between ground level (0) to the maximum floor in the circuit times the waiting time at each stop, in this case: (20 seconds * <floorsServiced>)

That’s all it takes to calculate time, all together:

elevatorsCircuitTime=(5*<maxFloor>*2)+(20*<floorsServiced>)

To then calculate the average number of people we carry per circuit we use the following equation:

avgElevatorLoad=<elevatorsCircuitTime>*<floorsServiced>*<peoplePerFloor>/<rushHour>

The variables rushHour equate to the time it takes to complete one rush hours, floorsServiced are the number of floors the elevator stops at, peoplePerFloor are the number of individuals on a given floor, and we already calculate elevatorsCircuitTime. We can then use the time and the average load capacity to complete our algorithm.

My solution to this problem requires two arrays:

  1. Representing the building: The array is filled with the number of people per floor. Each slot in the array representing a floor. An example would be [ 100, 100, 100] would be a four story building with only the top three floors being people who need elevators.
  2. Representing the elevators: Each slot in the array represents the “maximum” floor which that elevator will reach on its circuit (I also input ‘0’ in the first slot in the array for simplicity). For example, [ 0, 2, 3 ] represents an two elevators, elevator one (in slot one) carries passengers from floor 2 and 1 to 0. Elevator two (in slot two) carries passengers from only floor 3 to 0.

My solution begins with array 1 (representing the building) being empty, then every time I “add a floor” to the array I assign an elevator to the floor. The assignments can change, as you will see, but it does follow a similar pattern. The elevator circuit with the lowest circuit is assigned the new floor, unless the capacity is becoming an issue. I added a little function:

elevatorCircuitTime + ((elevatorCircuitTime / 100) * elevatorsAvgLoad)

Because elevatorCircuitTime is an integer, unless the circuit time exceeds 100 seconds (which is a long time for being in an elevator), then the elevatorsAvgLoad beings being factored into the equation. The problem description was rather vague, and as such my solution does have some vagueness regarding the equation above. As such, the function I used to assign a floor to an elevator is rather arbitrary, but it was effective at load managing (though there is likely a more optimal function).

The implementation of the function to add a floor is below:

Notice, every time a “elevatorNumber,” is chosen every elevator above the “elevatorNumber” the elevator array is then bumped up one:

for i in range(elevatorNumber, len(e)):

e[i] += 1

This is because the maximum floor in each circuit above the chosen elevator is still being increased by one, we only want to add one additional elevator to the chosen elevators circuit. The additional function eleLoop(e, i) simply determines the time and average number of people being carried on the circuit.

Once we have the function to add floors, I created a function to loop through and create the floors. Note, in this case all the floors are assumed to be uniform, if this problem was to be expanded upon variable number of people per floor would be fairly easy to take into account.

That’s pretty much it for the allocation portion of the algorithm. It is relatively straight forward and has a fair amount of room for possible improvements, which I leave to you!

Implementation | Python Code

If we piece all of the various portions of the algorithm together, sprinkle in a few extra functions to print out the data and build a little simulator we get a pretty cool little program (which you can fork/view on my github).

Variables:

  • 10 Floors
  • 3 Elevators
  • 1 Rush Hour
  • 5 seconds to pass a floor
  • 20 seconds to stop at a floor
  • 100 people per floor

Output:

[0, 4, 7, 9]

Elevator #1, time for loop 140 seconds, carrying an average of 19.44 people per carry
Elevator #2, time for loop 150 seconds, carrying an average of 16.67 people per carry
Elevator #3, time for loop 150 seconds, carrying an average of 12.50 people per carry

Total Time: 65 minutes

Average number of people per floor as the elevators iterate:

Screen Shot 2014-07-14 at 9.36.02 PM

As you can see my algorithm provides a good, if not the best solution (in this case) and although there is always room to improve (and I challenge you to do so) it is a good start.

Calculating Runtime

The runtime and space required for this algorithm are a little difficult to calculate, but not overly so. The runtime of this algorithm is based off three factors:

k: longest circuits, number of people
n: starting number of people in on the longest circuits serviced floor (that’s a tung twister)
m: total number of floors

  • Run Time: O(m * (n/k))

‘n / k’, because that determines the maximum number of iterations the elevators make on the circuit(s) and ‘m’ because we have to iterate over each floor ever iteration of the elevators. In this case we neglect the “setup” which is filling the “building” array, representing the number of people on each floor, since it is not the dominant term for the run time (m*(n/k) + m).

The maximum space required is very straight forward:

e: number of elevators
f: number of floors

  • Memory Required: O(e + f)

If we brought it all together:

k: longest circuits, number of people
n: starting number of people in on the longest circuits serviced floor
m: total number of floors
e: number of elevators
f: number of floors

  • Run Time: O(m * (n / k))
  • Memory Required O(e + f)

Closing Remarks

I recognize this is not the optimal solution, however it does get the job done. I challenge you to comment, fork from github and improve my code, or write your own solution in your article. I think it is an interesting problem and is similar to resource allocation inside your computer, I wrote a basic introduction to process scheduling as well, if you are interested. I also would love to see a different (hopefully better) solution, so if you come up with one don’t forget to write!

I do plan on writing another article diving more in-depth into this problem and proving a better real world applicable algorithm, however I do not have a date set yet (could be days, weeks, or months). I hope you enjoyed the article and would love to hear your thoughts, so don’t hesitate to comment or email me, thank you!

Related Articles
Recommended Reading

Share on Facebook12Tweet about this on Twitter30Share on Google+3Share on Reddit39Share on StumbleUpon4,096

 Subscribe

If you enjoyed this article subscribe via email, it's free!

Plus exclusive email only content and problem solutions.

View Archived Emails (no surprises, no spam!)

3 comments on “Everyday Algorithms: Elevator Allocation

  1. You should work on this algorithm from the 41st floor of the Marriott Marquis in New York, where the elevator wait times are incredible.

    A couple of time factors to add:
    – Abandoned floor overhead (some people get tired of waiting or hop onto another car heading for the same floor – it happens A LOT when the elevators get busy)
    – Longer wait times per floor as ridership increases. When a car is over 50% full it takes 2-3x times longer to unload.
    – Transit time per floor should have a base value (5 secs?) covering 4 floors of transit (two for acceleration and two for deceleration) and a secondary and much shorter value (2 secs?) for floors transited while at full speed.

  2. There’s a supermarket near me where the elevators are just infuriating. I’m pretty sure nobody thought of anything like this, or if they did, it was eventually messed up by multiple repairs. You’ll press the call button and wait there forever, and at some point both friggin’ elevators show up at the same time. Or only the one will run the entire day. And it’s only a four-story building! There are stairs and escalators, but the way the layout is, you have to walk all over the place to finally get up/down to the level you want. I’d have an easier time scaling the walls.

  3. The Bloomberg building in New York has 3 banks of elevators that use this kind of “zone allocation”.

    Bank 1 goes straight from Ground to 6, the main lobby for the building.

    Bank 2 are the “mid-rise” elevators. If you’re going up, they start on 6 and stop at 15, 17, and 20. Going down, they stop at 20, 17, 15, Ground, and the basement. You cannot take these elevators up from Ground.

    Bank 3 are the “high-rise” elevators. Going up, they start on 6 and stop at 23, 26, and 29. Going down, they stop at 29, 26, 23, Ground, and the basement. You cannot take these elevators up from Ground.

    This system works pretty well in practice. You can usually catch an elevator within 2 minutes, and even during rush hours it’s uncommon to have to wait for more than 1 or 2 elevators. The only irritating part is if you want to go from a mid-rise floor (6 – 20) to a high-rise floor (21 – 29) – then you’ve got to take the mid-rise down to 6 and the high-rise back up to your destination floor!

Leave a Reply

Your email address will not be published.


− two = 5

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">