By Luran Li
Elevators are so prevalent in our daily life that we all have the experience of waiting in a lobby, staring at the digital display as the floor number ticks by, and being excited by the beep signaling we have arrived at our car. Much of our time has been saved by travelling in an elevator, but that could be as much as the time we have spent waiting. I have always wondered, in a building with a group of four or more elevators, how are they scheduled to serve people’s requests, and how efficient this strategy is.
After searching on the Internet and skimming through a handbook of vertical transportation, I have learnt that about two decades ago, most of the elevators would serve the requests following a fixed set of rules that are engineered in logic circuits. In the modern days, however, those circuits are replaced with microprocessors, which can be thought of as mini computers that can run programs to solve complex problems. This has opened up the possibility of adjusting the schedule of elevators dynamically as new passengers arrive, and efficiency may be increased by considering this extra information.
My project involves formulating the scheduling of elevators as an optimisation problem and writing a computer solver using a technique called approximate dynamic programming. A central idea in the formulation is to divide the continuous timeline into discrete states that fully describe the status of the system. Each state comprises the position of each elevator and the requests it is currently serving, as well as the passengers that are still waiting. The goal is to determine the action for each elevator to take in every time block so that the total serving time (travelling plus waiting) of all passengers are minimised.
The solver has generated good schedules using only one fifth of the allocated computing time. The result was compared with the optimal solutions obtained by dynamic programming, which can only solve small (approx. 10 floors), but not large (100 floors) instances of the problem in a feasible amount of time.
For future work, we may develop a more sophisticated model that incorporates people’s happiness in the measurement of the service. For example, a person would be content with waiting for 20 seconds, and therefore that waiting time can be neglected. On the contrary, penalties should be added for people that have waited for more than 5 minutes. With the advent of the computing power, it is reasonable to believe an elevator system can cope with such a complicated model and operate efficiently with effective programming.
Luran Li was one of the recipients of a 2013/14 AMSI Vacation Research Scholarship.