44
$\begingroup$

Situation

  • My apartment block has ten stories.
  • The first ground level is 1, the highest story is 10.
  • There are two equivalent elevators, spanning all stories.

Current configuration: One elevator always rests at level 1, the other at level 10.

Thoughts

I am pretty sure that this is a bad configuration and I started thinking about a better one. While keeping one elevator always on the first level seems very reasonable, I think the one on the tenth level is very inefficient.

An efficient configuration would be where most people would wait as little as possible to reach their level. One example situation that occurs is that, someone walks 30m in front of me outside the building and takes the first elevator and then I have to wait for the second one to come down from 10 to 1.

Modeling

Let's further assume:

  • People only use the elevator to get from their story to the ground level (1) and from ground level back to their story.
  • The number of elevator users is the same for all levels.
  • The usage over time is uniform.

My Calculation

I did a "numerical calculation" (spreadsheet) and found that if I optimize one elevator $U$ for people going up and one elevator for people going down $D$, then elevator $U$ should always be on floor 1 and elevator $D$ should be on floor 6. I compared all start levels for people wanting to go down from 2-10 and an elevator on level 6 has the minimum number of traversed levels.

So for the story $s \in \{2..10\}$ where the person starts his descent and $r \in \{1..10\}$ the story where the elevator rests we need to find $$min \left(\sum_{s=2}^{10} (s-1)+|s-r|\right)$$

The values over $r$ are: enter image description here

Questions

Taking into account the points in Situation and Modeling:

  1. Is there a better position for elevator $D$ than level 6?
  2. And maybe even something better for $U$ even though it's position on the first floor seems "very optimal"?
$\endgroup$
  • 3
    $\begingroup$ "inefficient" on what sense? You must start defining with precision what is the criteria you want to use here for "efficient". $\endgroup$ – Masacroso Jul 23 '17 at 14:19
  • $\begingroup$ Feel free to correct mathematical wording and terms, since I have little practice with this in English. $\endgroup$ – problemofficer Jul 23 '17 at 14:19
  • 2
    $\begingroup$ There is no reason to reserve one elevator for people going up: If it i sinstead used to fetch someone from anothre floor, it will be available at floor 0 immediately after that task because that is where the task takes it to. $\endgroup$ – Hagen von Eitzen Jul 23 '17 at 20:34
  • 1
    $\begingroup$ Unrelated: play.elevatorsaga.com $\endgroup$ – Carsten S Jul 23 '17 at 21:42
  • 3
    $\begingroup$ Are there stairs? How many flights are people prepared to walk up (probability distribution)? what about down (presumably a larger number)? Does this probability vary not just between trips (for the same person it will depend on load) but on time of day? For that matter do you want to take into account many people going out to work in the morning and coming back in the evening? $\endgroup$ – Chris H Jul 24 '17 at 9:09
45
$\begingroup$

In general, elevator scheduling is a seriously difficult problem (see, e.g., this presentation and its list of references for some idea of its complexity). Your example situation starts to get at why it's hard: in order to know how often this happens, you need to know how quickly the elevator travels, relative to how often people arrive. And once it happens, maybe it would be better to dispatch the 10th-floor elevator, but maybe the 1st-floor elevator will do its thing fairly quickly and you should just wait for it to be done. In order to answer these kinds of questions, you need lots of data about your apartment's specific situation; a theoretical answer based on a few assumptions isn't going to get you anywhere useful.

But the hard part is determining what to do when the elevators are busy. You're asking about which floors you want the elevators to rest on, which is something that only matters when they are not particularly busy. And in that case, along with your assumptions, we can come up with something tractable.

So, in addition to the assumptions you made, I will also assume that:

  • Only one person wants to use the elevator at a time, so the elevators are always on their resting floors when someone wants to use them.
  • Elevators move from floor to floor at constant speed, so a passenger's wait time is proportional to the distance to the closest elevator. (This assumption could be removed and it wouldn't make the problem much more difficult, but it's hard to know what to replace it with.)

Additionally, unless we are in a certain classic mathematician joke, your assumptions imply that a passenger will want to go up or down with equal probability.

This is enough to solve the problem. We take a representative population consisting of one person on each higher floor wanting to go down, and 9 people on the ground floor wanting to go up. Over this population, we minimize the total waiting time; i.e., the total distance to the closest elevator. The following simple python script does this for each possible elevator configuration, and then tells you which one is best:

least_wait_time = float('inf')
passengers = [1 for i in range(0, 9)] + range(2, 11)

def wait_time(passenger, elevator1, elevator2):
    return min(abs(passenger - elevator1), abs(passenger - elevator2))

for high_elevator in range(2, 11):
    for low_elevator in range(1, high_elevator):
        total_wait_time = sum(wait_time(passenger, low_elevator, high_elevator)
            for passenger in passengers)
        print 'Elevator positions: ' + str((low_elevator, high_elevator))
        print 'Total wait time: ' + str(total_wait_time)

        if total_wait_time < least_wait_time:
            best_elevators = (low_elevator, high_elevator)
            least_wait_time = total_wait_time

print ''
print 'Optimal elevator position: ' + str(best_elevators)
print 'Optimal wait time: ' + str(least_wait_time)

It turns out that the optimal thing to do, given all these assumptions, is to put one elevator on floor 1 and the other one on floor 7. This gives a total wait time of 15 (i.e., over the population of 18 people, the nearest elevator will on average start 15/18 floors away).

Why is this different from your result? Because we're not assuming the elevator on floor 1 is used solely to go up. If someone wants to come down from floor 2 or 3, the 1st-floor elevator is already closer to them than the higher-up elevator even when the higher elevator is at floor 6, so it's not useful to keep the higher elevator close to them. So we might as well move the higher elevator up a bit to keep the people on really high floors happy.

$\endgroup$
  • $\begingroup$ @BrevanEllefsen Your upvote is worth 10 reputation points, so... :-). (And of course there are bounties which you can award to an existing answer.) $\endgroup$ – Luc Jul 24 '17 at 6:53
  • $\begingroup$ @Luc sure, but +10 would yield 100 reputation points ;) As far as a bounty goes? While I think this answer probably qualifies for one, I feel the same way about a lot of posts on this site, and so I try to be sparing with my bounties, using them either to reward the best of the best answers or to encourage answers to my own questions (which I avoid doing often since it can reward poor quality answers, so I usually wait a year or so and try editing a few times to ensure nothing else is working!) $\endgroup$ – Brevan Ellefsen Jul 24 '17 at 6:57
  • $\begingroup$ How does this compare to elevators waiting at the floor they last stopped at? $\endgroup$ – Baldrickk Jul 24 '17 at 13:55
  • 1
    $\begingroup$ @Baldrickk: That'd take a more complicated analysis, because it means that the order people show up in becomes relevant. But my guess would be that this does better. The advantage to having elevators wait at the floor they last stopped at is that they're more likely to be in high-traffic areas, but we've already got an elevator in the high-traffic area. And some of the time you're going to end up with two elevators in the lobby, which is (under the low-frequency assumption we've been making) a total waste. $\endgroup$ – Micah Jul 24 '17 at 15:22
  • $\begingroup$ @Micah considering the assumptions you made in your last paragraph, I think the optimal solution would be one elevator at 3 and the other at 8. $\endgroup$ – AMAN Jul 26 '17 at 9:38
8
$\begingroup$

Your model concerns the "low frequency mode" of the elevators: The building is $n\geq1$ stories high, whereby the floors are numbered from $0$ to $n$. The elevators are at rest at floors $r$ and $s$ with $0\leq r<s\leq n$, and are waiting for the next customer. This customer will arrive with probability ${1\over2}$ at floor $0$, and with probability ${1\over2n}$ each at one of the floors $k\in[n]$. The expected waiting time of this customer then is $$E(r,s)={1\over2} r+{1\over2n}\sum_{k=1}^r(r-k)+{1\over2n}\sum_{k=r+1}^{s-1}\min\{k-r,s-k\}+{1\over2n}\sum_{k=s}^n(k-s)\ .$$ In your case $n=9$. Use your spreadsheet power to compute the minimal $E(r,s)$. In any case the lower elevator should not be reserved for customers wanting to go upwards.

$\endgroup$
  • $\begingroup$ Sorry, I have an issue where my brain seems to sometimes skip random sentences, and it apparently skipped that very important bit :o $\endgroup$ – Doktor J Jul 24 '17 at 19:40
0
$\begingroup$

Classroom aspects of mathematical modeling is treated in the joint report called GAIMME developed by SIAM and COMAP (The Consortium for Mathematics and Its applications).

http://www.siam.org/reports/gaimme-for_print.pdf

One extended example in this report has to do with elevator management issues. Look starting at page 148 in the report above.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.