Jonathan Landy – Optimal Elevator Placement
jslandy's notes on math, data, etc.
We ask at which floors we should place a set of idle elevators in a building so<br>as to minimize the expected wait time of the next caller. If there is just one<br>elevator, we show that it should be placed at the "median of the demand<br>distribution" — i.e., it should sit at the floor at which half the demand lies<br>above that floor and half below. When there are multiple elevators available,<br>they should be placed at floors such that they each individually sit at the<br>demand medians of their respective "domains". We can use gradient descent to<br>find the solution, but the system is not always convex and so there may<br>sometimes be local minima.
Problem setup – expected wait time
Consider a building with some elevators that customers use to move between<br>floors. We'll assume that demand arrives randomly with distribution
\begin{equation}<br>p(i) = \text{probability next elevator request appears on floor } i \tag{1}\label{1}<br>\end{equation}
If there are \(N\) floors total, then the full set of probabilities can be<br>written as
\begin{equation}<br>\vec{p} \equiv (p_1, p_2, \ldots, p_N) \tag{2}\label{2}<br>\end{equation}
with the \(\{p_i\}\) summing to \(1\). If an idle elevator sits at floor \(j\) and is<br>called to floor \(i\), we posit the rider will have to wait a time
\begin{equation}<br>\text{wait time}(i, j) \equiv |i - j|. \tag{3}\label{3}<br>\end{equation}
for the elevator to arrive. Here, we are choosing some convenient units so<br>that the time to move one floor is exactly one unit of time. The form<br>(\ref{3}) simply says that it takes twice as long for an elevator to get to a<br>location twice as far away.
Question: Where should we place our available idle elevators so as to<br>minimize the expected wait time for the next caller?
Single elevator
If there is just one elevator available, the wait time is minimized if we place<br>it at the median of (\ref{2}). Proof:
If the idle elevator sits at \(j\), the average wait time is
\begin{equation}<br>E(\text{wait time}) = \sum_{i=1}^{N} p(i) |i - j| \tag{4}\label{4}<br>\end{equation}
Differentiating the above wrt \(j\) and setting the result to zero we get
\begin{equation}<br>\partial_j \, E(\text{wait time}) = \sum_{i:\, i \leq j} p(i) - \sum_{i:\, i > j} p(i) = 0\tag{5}\label{5}<br>\end{equation}
The minimum will occur at that point \(j\) where half the weight is below \(j\) and<br>half above — the median of the distribution.
Example 1: simple steady state
Suppose the riders primarily use the elevator to go up from the ground floor to<br>a single upper floor, and then on exit return back to the first floor. In this<br>case, half of all rides start at the ground floor, and the others start on one<br>of the remaining floors \((2, 3, \ldots, N)\). Since exactly half the demand is<br>at floor 1, the median of (\ref{2}) is between floors 1 and 2. We can place<br>the elevator at either location (i.e., floor 1 or 2) to minimize the expected<br>wait time.
Example 2: simple, but up and down demand varies throughout day
Now instead suppose that early in the day more people enter the building, while<br>at the end more people leave. In this case, (\ref{2}) will have more than half<br>its weight at floor 1 at the start of the day. During these periods we should<br>definitely hold the elevator at floor 1. Later in the day, the distribution<br>will shift to having less than half its weight at floor 1 and its median will<br>be on some upper floor.
In a simple case, suppose all people enter at the start of the day and leave at<br>the end of the day. If the upper floors are evenly populated, we then want to<br>hold the elevator in the middle of floors \((2, 3, \ldots, N)\) in the evening —<br>i.e., at floor \(1 + \frac{N}{2}\).
Multiple elevators
To understand the optimal placement of multiple elevators, we'll next pursue a<br>gradient descent type solution. To that end, consider the change in expected<br>wait time when the \(i\)-th elevator moves up a bit to \(x_i \to x_i + \Delta<br>x_i\). As shown in Figure 1, when this occurs the points that this elevator is<br>responsible for have their wait times change. To first order, the effect is
\begin{equation}<br>\Delta E(\text{wait time}) = \Delta x_i \left[ \int_{\frac{x_{i-1}+x_i}{2}}^{x_i} p(x) \, dx - \int_{x_i}^{\frac{x_i+x_{i+1}}{2}} p(x) \, dx \right] \tag{6}\label{6}<br>\end{equation}
That is, the points above ("in front") of \(x_i\) (and served by this elevator)<br>have their wait times reduced by \(\Delta x_i\), while those behind it have their<br>wait times increased by \(\Delta x_i\).
Rearranging (\ref{6}) gives
\begin{equation}<br>\frac{\partial E(\text{wait time})}{\partial x_i} = \int_{\frac{x_{i-1}+x_i}{2}}^{x_i} p(x) \, dx - \int_{x_i}^{\frac{x_i+x_{i+1}}{2}} p(x) \, dx, \tag{7}\label{7}<br>\end{equation}
analogous to (\ref{5}) above. The result (\ref{7}) allows us to apply gradient<br>descent to find the minimum: We start at some convenient initial locations for<br>the idle elevators, use (\ref{7}) to calculate the gradient wrt to...