Where Should I Stand When Waiting For Elevators

2017-11-12

Introduction

Elevator scheduling does not depend on where people stand. You pushed the button on one side, then "ding! ", a flashing green light on the other end means you will have to walk. People would just stand in random positions hoping elevators will hit their guesses. However randomness is not our best friend, and here I am proposing a scientific way to decide where you should stand while waiting for elevators.

If you do not like theories, you may skip the rest and go to the code (to be added) now.

If you do not like codes as well, that is all I have for you and you may now click wherever the little cross is to close this tab. Thank you.

The Math

Suppose we have $K$ elevators, lined up on one side, in the lobby in total. Let $X$ be a random variable of categorical distribution with $K$ classes numbered from 1 to $K$, with a probability vector $\mathbf{p}$, $$X|\mathbf{p}\sim \text{Categorical}(\mathbf{p})$$ $\mathbf{p}$ records prior information with $$\mathbf{p}|\alpha \sim \text{Dirichlet}(\alpha )$$ $\alpha$ is the vector of hyperparameters. Suppose we have a flat Dirichlet distribution to begin with, that is, ${\alpha }_0=\mathbf{1}$. Suppose we have a historical record of arrival count for all $K$ elevators. Let it be $\mathbf{c}$, we would update the prior distribution using $$\mathbf{p}|\alpha \sim \text{Dirichlet}({\alpha }_0+\mathbf{c})$$ Then the probability of elevator $i$ arrives for you is expected to be $$\mathbb{E}(p_i|\mathbf{c},\alpha )=\frac{c_i+{\alpha }_i}{\sum _m{c}_m+\sum _n{\alpha }_n}=\frac{c_i+1}{N+K}$$ where $N$ is total number of historical arrivals. Suppose $x\in [0,1]$ is a representation of where you should stand. For example, $x=0$ can mean you should stand at the very left of the lobby and $x=1/2$ would then mean you should stand right in the middle of the lobby, and so on. And the elevators are spaced equally in the lobby. We want to minize the expected walking distance from where you are standing to the arriving elevator, by solving following optimization problem, $$\underset{x}{min}\sum _{i=0}^{K-1}|x-\frac{i}{K-1}|\cdot \frac{c_i+1}{N+K}$$ $$\text{s.t.}0\le x\le 1$$ Of course this will blow up if there is only one elevator and you want to know where you should f***ing stand. To solve, let $$y_i=|x-\frac{i}{K-1}|$$ The equivalent LP will be, $$\underset{x}{min}{y}_i\cdot \frac{c_i+1}{N+K}$$ $$\text{s.t.}x-\frac{i}{K-1}\le y_i,\text{for }i=0\cdots K-1$$ $$-x+\frac{i}{K-1}\le y_i,\text{for }i=0\cdots K-1$$ $$0\le x\le 1$$ And this can be easily solved, for example, using interior point method.

To Be Added

1. The case where both sides have elevators in the lobby.
2. The case where you are floating in the air in the center of a spherical lobby, and elevators , or better, the teleports, are locating on the surface of the sphere.
3. I used expectations, but we have much more in the posterior. Optimization can be done instead with probabilistic variables directly.

© The Responsible Adult 2017 - 2025