Richard D Peters
Peters Research Ltd and the University of Northampton, UK

This paper was presented at ELEVCON PARIS 2014, The International Congress on Vertical Transportation Technologies and first published in the IAEE book “Elevator Technology 9”, edited by A Lustig.  It is reproduced with permission from The International Assocication of Elevator Engineers.  This web version © Peters Research Ltd 2014.

Key Words: Dispatching, simulation, control, artificial intelligence

Abstract. Dispatching is the part of the elevator control which chooses which elevator serves which call.  Although dispatching can be performed with relatively simple rules there are opportunities to improve performance by applying more intelligent algorithms.  This paper reviews the fundamentals of dispatching, explaining a range of different approaches including fuzzy logic, neural networks and genetic algorithms.  Important issues missed by some designers of artificial intelligence dispatchers are highlighted.  Suggestions are given for elevator consultants who have to mediate enhanced performance claims from competing suppliers.

1.    Introduction

This paper primarily addresses collective control where there are up and down landing call buttons on each floor and car call buttons in the car.  At the top and bottom landing there is a single button as the passenger can only travel in one direction.  Down collective, single push button and destination control are discussed elsewhere (CIBSE, 2010) (Barney, 2003) (Smith & Peters, 2002).

Figure 1. Collective control

The decision of which elevator should be allocated to answer a landing call is made by the dispatcher.  Dispatching was originally a skilled human job, but over the years became automated using relatively simple rules based on experience and common sense.   Figure 2 illustrates a simple dispatching decision.  There is a down landing call at level 4.  Car B is travelling in the right direction and is the closest car; but has a stop for a car call at level 6.  Car A is further away, but could go straight to the call. Should Car A or Car B be “allocated” to the call?

Figure 2. Deciding which elevator to allocate to a call

Although dispatching can be performed with simple rules, when more elevators and more landing calls are considered, the number of different ways the system could answer the calls grows exponentially.  In Figure 3, there are five landing calls and four elevators; which is the best way to allocate the landing calls to the elevators?  Because of this complexity, in modern group control systems, dispatching is sometimes performed with powerful microprocessors applying artificial intelligence.

Figure 3. In a busy building there are many alternative allocation options to consider

2.    Collective operation

First consider how a single elevator answers the calls allocated to it.  Most modern elevators answer calls collectively as illustrated in Figure 4.  All landing calls, and the resulting car calls in one direction are served; then the car reverses and serves calls in the opposite direction.

Figure 4. Collective operation (passenger destinations shown above heads)

Collective operation is not necessarily the most efficient way to service the passengers.  For example if in Figure 4 step (iv) both passengers had loaded, the stop at step (vi) could have been avoided. However, a passenger would be taken in the “wrong direction” first.  This is generally considered unacceptable (Barney, 2003).

3.    Basic group collective dispatching algorithms

3.1    Nearest car

One of the simplest group collective algorithms is based on allocating the closest car that can stop in time for the landing call.  This is illustrated in Figure 5 where cars A, B and C are 15 m, 10 m, and 5 m away in distance from the 7 down landing call respectively.  Car C is allocated as this is the nearest car, and there is time for it to slow down to stop.

Figure 5. Group collective algorithm based on allocating the nearest car

3.2    Estimated time of arrival

The estimated time of arrival (ETA) algorithm is very similar, except that the decision is made based on time rather than distance.  Consider the scenario in Figure 6.  Cars B and C are 10 seconds and 5 seconds away from the 7 down landing call respectively.  Car A would be 15 seconds away from the landing call if it travelled there directly.  However, it has to stop at level 8 for a car call and a time allowance is made for the stop, in this instance 10 seconds.  Car C has the lowest ETA and so receives the allocation.

Figure 6. Allocation with ETA algorithm

3.3    Giving priority to coincident calls

Some systems give priority to coincident calls; if the car is already stopping for a car call, then there is potentially some benefit in serving the landing and car call with a single car stop.  In Figure 7 car B has a car call on the same floor as the landing call, so it receives a bonus of 10 seconds which is deducted from the ETA.  The result is an adjusted ETA of 0 seconds, which is now better than car A.  So, car B receives the allocation.

Figure 7. ETA allocation with coincident call bonus for car B

Giving priority to co-incident calls does not always improve quality of service; some passengers will wait longer.  However there is a reduction in the number of stops made by the elevators which increases handling capacity; if the system is busy this is a good strategy.

4.    Application of Artificial Intelligence

Artificial intelligence (AI) is a specialist subject which focuses on developing machines and software which exhibit the sort of intelligence you might expect of human beings.  AI is complex, and cannot be addressed fully without extensive study.  In this section the purpose is to introduce some of the most basic concepts and demonstrate how they may be applied to elevators.

4.1    Fuzzy logic

To understand the basics of fuzzy logic, first consider a sports advisor program trying to asses a person’s potential as a basketball player.  Simple “crisp” logic makes decisions as illustrated in Figure 8; the person has to meet two independent, fixed criteria in order to be recommended basketball as a sport.

Figure 8.  Sports advisor program using crisp logic

A fuzzy logic approach could assess the degree and the importance of each skill, creating a combined score for the person’s potential as a basketball player.  In Figure 9 we establish a rating for the person’s height and running ability.  The importance of each skill is given a rating and then an overall score is established.  If the score exceeds a threshold amount, then the recommendation to play basketball is made.

Figure 9. Sports advisor program using fuzzy logic

To apply this approach to elevators, consider Figure 10.  Car A is furthest away from the 7 down landing call and almost empty.  Car B is close and almost empty.  Car C is very close but almost full.  So, combining those two considerations (and possibly others), car B is allocated the call.

Figure 10. Example application of fuzzy logic to dispatching

4.2    Neural networks

Artificial neural networks are computer based models of the brain.  They are designed to learn and are good at pattern recognition.  Consider the child Anna learning to read as in Figure 11 .  She is shown the letter ‘a’ in many different fonts.  Each time she is shown the letter ‘a’, she is told, “this is an ‘a’”.  After this she is trained.  Now we present her with the letter ‘a’ in a font she has not seen before.  Because she has learnt the shape or pattern of an ‘a’, she is able to recognise it and tells us “it’s an ‘a’”.

Figure 11. Anna learning to read

Likewise it is possible to train a neural network to recognise patterns of landing and car calls, teaching the network what the “correct” allocation is.  The “correct” allocation may be determined by simulation or some other means.  Then when a new scenario is presented to the network, it will make allocations applying the trained network.  The difficulty with this approach is that it takes a complex network and a lot of training to reach the point where good allocations are made.

Another way to apply a neural network is to consider a single element of the dispatching problem.  In an ETA dispatcher, we have to estimate how long it will be until a car reaches a landing call.  We could do this using formulae for the travel time, making an allowance for the delay associated with each stop between the car’s current position and the landing call.  This would provide a good estimate, but may not account for a crowded car which will take longer to load and unload, or the possibility of additional calls being added before we reach the landing call in question.  There are many factors which might affect the actual ETA.  Using a neural network we can learn the significance of these automatically.  An example of this approach given by Powell (Powell, et al., 2000) is illustrated in Figure 12.

During training the network’s inputs, i1 to in are presented with the cars’ distance to the call, the number of calls before the call, and any other inputs which could have some significance.  The weights w1 to wn start the training with an arbitrary value.  For each set of inputs, we then compare the actual ETA with the sum of i1w1 + i2w2 + i3w3 ….. + inwn and then adjust the weights according to a set of rules.  As the network is trained the ETA estimate improves.

This simple neural network is called a linear perceptron; it has a single neuron as opposed to the human brain which has about 85 billion.  A linear perceptron is limited by the fact that it can only calculate ETA in terms of a linear equation.  A more accurate estimate would need a multi-layer network with more neurons.

Figure 12. Using a linear perceptron to calculate ETA

4.3    Genetic algorithms

A genetic algorithm mimics the process of natural selection to search for solutions where it is impractical to consider every possible alternative.  Figure 13 represents a system with four elevators and five landing calls; for this discussion the floor and direction of the landing calls is not important.  There are many different ways we could allocate the landing calls to the elevators.  With four elevators and five calls, there are four to the power of five, 1024 possible options.  Of course many of these options will represent a poor choice, but we do not necessarily have time to check every option.  So the genetic algorithm relies on the process of natural selection to search for good solutions.

In Figure 13 each allocation, for example Landing Call 1 to Elevator 2, corresponds to a gene.  Each set of allocations corresponds to a chromosome, for example Landing Call 1 to Elevator 2, Landing Call 2 to Elevator 1, Landing Call 3 to Elevator 3, Landing Call 4 to Elevator 4, and Landing Call 5 to Elevator 2.  For clarity abbreviate this to:

LC1- E2, LC2 – E1, LC3 – E3, LC4 – E4, LC5 – E2.

Figure 13. Allocations represented as genes in a chromosone

To begin the dispatching process, select some random chromosomes, for example:
E1 – LC1, E4 – LC2, E2 – LC3, E3 – LC4, E4 – LC5
E3 – LC2, E4 – LC1, E1 – LC3, E2 – LC5, E2 – LC4
E2 – LC5, E1 – LC2, E4 – LC1, E1 – LC4, E3 – LC3
E2 – LC4, E3 – LC3, E1 – LC5, E4 – LC1, E1 – LC2

Each of these can be tested with a simulation performed by the dispatcher.  The best performing chromosomes are kept, in this case:

E3 – LC2, E4 – LC1, E1 – LC3, E2 – LC5, E2 – LC4
E2 – LC4, E3 – LC3, E1 – LC5, E4 – LC1, E1 – LC2

The next generation of chromosomes are evolved by natural techniques.  For example, two chromosomes can be compared with the next generation sharing the common genes and the choice between different genes being selected randomly, see Figure 14.

Figure 14. Evolving the next generation by choosing common genes and a random selection process for others

Another technique may be to take a well performing chromosome and mutate one of the genes, see Figure 15.

Figure 15. Evolving the next generation by mutating one of the genes

The new generation is tested and compared with the previous generation.  The best chromosomes are kept, and the process is repeated until the time allowed for the dispatching process comes to an end.

5.    Other considerations

Elevator dispatching is a popular academic challenge and the subject of many research papers from specialists in artificial intelligence.   The allocation process described in sections 3 and 4 is considered in detail, but this alone is not enough to ensure efficient dispatching.  This section deals with other considerations sometimes forgotten.

5.1    Parking calls

Parking calls are used to move an elevator without an allocated landing call to a floor in anticipation of future demand.  The most common example of the requirement for parking calls is seen during up-peak traffic.

In morning up-peak traffic there is often a stream of people arriving at the ground floor.  In a conventional system there is never more than one up landing call at the ground floor, so only one car is sent.  When that car is loading with the doors open no new landing calls can be inserted at ground.  So, there may be a queue of several car loads of people at the same time as their being one or more idle elevator at upper floors waiting for an allocation.

A common solution is to insert parking calls during periods of known up-peak traffic.  These calls bring the idle cars to the ground or other busy floor, ready to respond to the new landing call once the previous elevator has departed.  If the arrival rate of passengers is greater than the loading rate of a single car, then it is necessary to load more than one car at a time.

Parking calls are often used at other times of the day, particularly in high rise buildings where leaving all the idle elevators close in proximity to each other will extend the waiting time of people registering a call at a distant floor.

5.2    Increasing handling capacity to avoid saturation

Where passenger demand exceeds the handling capacity that can be delivered by the selected method of dispatching, the elevator group saturates, and the optimisation goals are often self-defeating.  In this case, different dispatching strategies and optimisation goals are needed.

Barney shows that a conventional system has greater handling capacity at down peak than in up-peak (Barney, 2003).  To achieve this increase in handling capacity the building is divided up into sectors; an elevator is sent to the top of each sector in turn.  This reduces the number of stops per elevator round trip and so increases handling capacity.

Likewise in an evacuation scenario where it is safe to use the elevators, or at the end of a major event with large numbers of people, the dispatcher optimisation goals need to be different.  The dispatcher should consider increasing handling capacity as an optimisation goal as well as or instead of response and waiting times.

5.3    Future demand

The dispatching problem is normally solved based on current calls in the system.  While these calls are being served other calls will be entered that will change the optimum solution.  Most systems will re-allocate calls to account for this.

Accounting for future demand earlier in initial allocation will improve performance, but brings additional complexity to the dispatching problem.

Simple rules, like giving priority to coincident stops (see section 3.3) give some benefit.  More sophisticated techniques can be used to estimate the number of people behind the call, through extrapolation seeking to minimise passenger based quality of service measures, e.g. waiting time and time to destination, rather than system based measures such as landing call response time (Smith & Peters, 2002).

A generalised solution would consider alterative futures based on learnt traffic patterns, and assess the probability of these futures before making allocations.  This would address the problem of self-defeating optimisation algorithms and allow for parking calls to be created automatically based solely on learnt traffic.

5.4    Load bypass

Elevator groups applying collective control should include a load bypass function in order to avoid stopping for landing calls when the elevator is full. Load weighing needs to be properly calibrated.  Alternative load detection such as volumetric detection can be more effective in buildings such as hospitals where the space taken by passengers is not proportional to mass, for example because equipment and beds are being transported.  Learning can be used to assess when the elevator is too full to accept additional passengers.

5.5    Doors

Door control is not generally thought of as part of the dispatching algorithm.  However information available to the dispatcher about traffic demand can be used to make intelligent decisions relating to door operation. In some cases these savings will be greater than can be achieved through intelligent dispatching.

5.6    Bunching

In some instances elevators bunch, as do other transportation systems, e.g. buses.  This is a natural phenomenon which can be allowed for, although solutions need to be applied with caution as what works in one scenario may compromise performance in another situation.

5.7    The real world

Dispatchers are normally designed using simulation programs where people do what they are told, elevators perform ideally, and communication between the elevator controller and the dispatcher is perfect.  The real world is very different.  Without on-site observation and detailed monitoring allowing the designer to examine past events, it is unlikely that the simulated performance will be achieved.

In the real world passengers will sometimes press both up and down buttons at the same time.  They will quit waiting for an elevator travelling down and get into an up elevator.  They will obstruct doors.  Irrespective of training, people will try and beat the system.  The best approach is to design systems which deter and mitigate the effects of misuse.

6.    Mediating performance claims

Elevator consultants have the difficult problem of mediating enhanced performance claims from competing suppliers offering intelligent dispatchers.  This is a challenging task as simulations provided by suppliers are normally based on different assumptions, even when inputs are nominally the same.  Furthermore, reality does not always correspond with simulation, or even logging statistics.  Comments from clients that “the statistics are good but the reality is different” are not uncommon.

The epilogue of CIBSE Guide D section 4 (CIBSE, 2010) states that the “CIBSE Lifts Group is also pleased to participate in peer review of enhanced performance claims”.  To validate performance claims requires open access to monitoring data and statistics from existing jobs.  Without that validation, relying on enhanced performance claims puts clients at risk, in which case the consultant is better to rely on generic models.

Where the consultant is confident that simulated performance can be delivered, test simulations should consider different traffic biases (incoming, outgoing and interfloor traffic) and entrance/special floor arrangements representative of those expected in the building.  Simulation should be performed across a range of traffic intensities including driving the system into saturation to assess performance in this case.

7.    Conclusions

This paper has considered conventional collective control where there are up and down landing call buttons are each floor and car call buttons in the car.  Some of the content is applicable to other forms of control.

The dispatching problem for conventional control can be solved simply and effectively with basic rules.  There are many strategies which can be taken to improve basic dispatching, all of which have merits.  Sometimes clever dispatching is let down because some aspects of the dispatching problem have been missed.

It is relatively easy to demonstrate dispatcher improvements in simulation.  However, without validation of actual installations, relying on enhanced performance claims puts clients at risk.

REFERENCES

1. Barney, G., 2003. Elevator Traffic Handbook. London: Spoon Press.
2. CIBSE, 2010. CIBSE Guide D:2010 Transportation Systems in Buildings. London: The Chartered Institution of Building Services Engineers.
3. Powell, B., Sirag, D. & Whitehall, B., 2000. Artificial Neural Networks in Elevator Dispatching. Berlin, The Internation Association of Elevator Engineers.
4. Smith, R. & Peters, R., 2002. ETD Algorithm with Destination Control and Booster Options. Milan, The International Association of Elevator Engineers.