Month: August 2014

Elevator Optimization

Attending a conference recently, I stayed on the 6th floor of a hotel that had 8 floors.  2 elevators scuttled visitors to their destinations, although 1 was closed for renovation.  Despite the elevator travelling at a good speed, I noticed some long waits for the elevator to arrive.  I also noticed an inefficient operating plan: when the elevator deposited me on my 6th floor, it would stop and wait there until called again.  As a mathematician and efficiency expert is bound to do, this got me thinking: surely it would be more efficient for the idle elevator to move nearer to floors that it was more likely to be called from.  Exactly half the elevator calls must originate from the lobby, so shouldn't the elevator's resting state be much closer to the ground floor so as to minimize waiting times?  As Professor Farnsworth said, "I'm afraid we're going to have to use ... math!"

 

 A Stochastic Model of Elevators

Assume the structure in question (hotel, skyscraper, etc.)  has 1 ground floor (or "lobby") and m additional floors.  For simplicity, assume an equal amount of traffic visits each of the m floors.  Therefore, exactly half the elevator calls will originate in the lobby, and the remaining calls will be spread uniformly across the m floors. Furthermore, for simplicity assume the elevator travels at unit speed (one floor per time unit). Under the elevator operation method described in the introduction, which I shall call the "lazy model", when idle the elevator will stay where it is. Let us first consider the case of a single elevator:  If we let X denote which floor the elevator is on, where X takes values in {1,..m+1}, the pdf of X (equivalently, where the elevator is called from) is given by

f(x) = \begin{cases} \frac{1}{2}, & \text{ for } x=1; \\\frac{1}{2m}, & \text{ for } 2 \leq x \leq m+1 \end{cases}

If a guest at floor x calls the elevator, and the elevator is currently at floor y, the guest must wait |x-y| time units.  Therefore a guest at floor x waits, in expectation,

W_x=\sum_{y=1}^{m+1} |x-y| f(y) = \sum_{y=1}^{x-1}(x-y)f(y) + \sum_{y=x+1}^{m+1}(y-x)f(y)

For the lobby (x = 1), this simplifies to

W_1=\sum_{y=2}^{m+1}(y-x)\frac{1}{2m}=\frac{1}{2m} \sum_{a=1}^m a = \frac{m+1}{4}

And for other x,

W_x=(x-1)\frac{1}{2}+\sum_{y=2}^{x-1}(x-y)\frac{1}{2m}+\sum_{y=x+1}^{m+1}(y-x)\frac{1}{2m}

=(x-1)\frac{1}{2}+\sum_{a=1}^{x-2}a+\sum_{a=1}^{m+1-x}a

=\frac{2x^2-6x+\color{red}{m^2+m+4}}{\color{red}{4m}}

Don't worry, this expression is not as complicated as it looks, and for a constant building size, all the red terms are a constant.  Note that the wait time is quadratic in x.  To examine the expected average wait time of a guest, we calculate

E[W]=\sum_{x=1}^{m+1}W_xf(x)=\frac{1}{2}W_1+\frac{1}{2m}\sum_{x=2}^{m+1}W_x

=\frac{1}{3}m+\frac{1}{4}-\frac{1}{12m}

So the expected average wait time from calling an elevator until its arrival is linearly increasing in m.  If m=5 the average wait is 1.9 time units; if m=10 the average wait is 3.575 time units; and if m=50 the average wait is 16.915 time units.  But can we do better?

 

Minimizing wait time

An optimal solution is for the elevator to relocate itself to the expected spot it will be called from.  This expected call is

E[f(x)]=\frac{1}{2} + \frac{1}{2m}\sum_{i=2}^{m+1}i = \frac{5}{4} + \frac{m}{4}

Note that at this spot, the elevator is not in general at an integer floor!  That is, the elevator may stop halfway between floors.  This will slightly complicate the analysis.  We shall denote the wait under these conditions at floor x by W_x^{'}.  Let \bar{x}=\sup\{x:x\leq\frac{5}{4}+\frac{m}{4},x \in Z\} denote the highest floor at or below the elevator.  Then

W_x^{'}=\begin{cases} \frac{5}{4}+\frac{m}{4}-x, & \text{ for } x\leq\bar{x}; \\x-\frac{5}{4}-\frac{m}{4}, & \text{ for } x > \bar{x} \end{cases}

Compared to the previous case, wait time is only linear in x.  Calculating the expected average wait time of a guest:

E[W^{'}]=\sum_{x=1}^{m+1}W_x^{'}f(x)=\frac{1}{2}W_1^{'}+\frac{1}{2m}\sum_{x=2}^{\bar{x}}W_x^{'}+\sum_{x=\bar{x}+1}^{m+1}W_x^{'}

=\frac{1}{2}(\frac{1}{4}+\frac{m}{4})+\frac{1}{2m}\sum_{x=2}^{\bar{x}}(\frac{5}{4}+\frac{m}{4}-x)+\frac{1}{2m}\sum_{x=\bar{x}+1}^{m+1}(x-\frac{5}{4}-\frac{m}{4})

If m=5 the average wait is 1.6 time units; if m=10 the average wait is 3 time units; and if m=50 the average wait is 14.25 time units.  This represents a 16% improvement in expected wait time over the naive approach.  This may not seem like a lot, but is a significant savings for no extra cost by simply reprogramming the elevators!  Next time, I will examine the case of multiple elevators.