Management Science and Operational Research Blog

Combinatorial Optimisation is an intriguing field. The problems can be formulated rather easily, but finding an optimal solution reveals to be really hard in many occasions. This makes them the prefect toys for mathematicians and computer scientists. A particularity of such problems is that they are especially difficult to solve if the number of variables gets big or the formulations includes a lot of stochastic elements. In these cases it might be impossible to find an optimal solution at all. Last week I encountered a neat application of Combinatorial Optimisation which has a limited complexity and generates real benefits. It was on my way to a job interview, in São Paulo’s Rochavera Building ¹.

There you don’t hit an up- or down-button when taking an elevator. Instead, you encounter a couple of panels in the elevator hall. So in order to take an elevator you have to type your destination floor into one of these panels, which returns immediately the number of the elevator you should take. Such a system has obviously been implemented in order to optimize the passenger flow, and I think this is quite a clever implementation of Combinatorial Optimisation for the following reasons.

• The full formulation of the problem is simple and well defined. There are not much stochastic elements and the total number of variables is limited. So there is no necessity to oversimplify the model formulation, leading to an solution which might be optimal only in theory.
• Local optimisations return suboptimal results. This can be easily seen when using an classical elevator system where each elevator is optimised by its own. For this particular application, even lay people recognize the potential for improvements.
• The fact that the passenger must type the destination floor-and not just inform if she wants to go up or down-brings a real benefit. Each time I am in an elevator which stops at every floor I realise the value of such information.

But there are also some questions in regard to the control software:

• What is the right objective function for such a problem? The minimisation of waiting times for the passengers or the minimisation of travelling times to the destination floors?
• Since a group of persons might have the same destination and therefore type the floor number only once, how do you model the capacity limit of an elevator?

Anyhow, I might sound a bit geeky, but the elevator did me put in the right mood for my interview.

1. Rochaverá Corporate Towers – www.rochavera.com.br [↩]