Rory Smith, ThyssenKrupp Elevator Inc 
Dr Richard Peters, Peters Research Ltd

Key Words: Simulation, dispatching, destination dispatch, boosters

This paper was presented at ELEVCON MILAN 2002, The International Congress on Vertical Transportation Technologies and first published in the IAEE book “Elevator Technology 15”, edited by A. Lustig.  It is reproduced with permission from The International Assocication of Elevator Engineers.  The paper was republished by Elevator World (July 2002), and by Lift Report (2/2003).  This web version © Peters Research Ltd 2009.

Abstract

The ThyssenKrupp ETD (Estimated Time to Destination) traffic control system applies a range of artificial intelligence and optimizing techniques to elevator dispatching.  ETD can operate as a full destination control system, for which passengers register their destination floors at landings.  ETD can also operate with conventional up/down hall call buttons, or with a combination of up/down hall call buttons and “booster” destination call stations on peak floors.  The system has been developed using Elevate™ simulation software to implement and test dispatching strategies.  Examples of improved passenger service and increased handling capacity are demonstrated with simulation.

1.   Introduction

The dispatching algorithms used by ThyssenKrupp Elevator (TKE), North America were based on Estimated Time of Arrival (ETA).  This effective system reduces waiting time by selecting the elevator in a group that can answer a hall call in the lowest amount of time.  TKE, formerly known as Dover Elevator, introduced this system in 1985.  With the acquisition of Dover Elevator by Thyssen in 1999, the merged company’s market position included a stronger presence in mid and high-rise projects.  It was obvious that a more sophisticated dispatching system was needed.

Thyssen Germany had developed a destination-based system that used touch screen terminals for destination entry and to advise passengers of which car to take.  Like all destination-based systems, the input devices were more costly than conventional up/down hall call buttons.  Nonetheless, it was decided to utilize the technology developed in Germany for our next generation system.

Several members of the elevator consulting community were contacted and asked their opinion of existing destination-based systems.  All stated that they liked the systems but did not like the price.  Lerch Bates Associates suggested that a system that utilized destination input devices at the Lobby and conventional buttons at the upper floors might be a cost effective alternative to full destination systems.  This concept has formed the basis for TKE’s new system described in this paper.

In order to fine-tune the destination-based algorithms and demonstrate their effectiveness, a solid, technically-based dispatcher performance simulation system was needed.  Such a system was highlighted at a recent Elevcon meeting.  At the Berlin meeting in 2000, Roger Howkins presented a provocative paper that described the use of elevators for evacuation.  Sadly, this paper was timely when one considers the tragic events of September 11, 2001, in the United States.  In his presentation Mr. Howkins used Elevate simulation software to demonstrate an evacuation algorithm.  This demonstration made the benefit of simulation very clear, particularly simulation developed by an independent entity.

A decision was made to adapt the general Elevate software to include not only the new TKE destination-based algorithms but also existing TKE dispatcher algorithms for benchmark comparison.  Dr. Richard Peters, the developer of the Elevate software, was contracted as an independent entity to provide software support.  After the simulation models were validated for existing TKE dispatchers, it was decided to proceed with the development of the new ETD Destination Dispatch control system.

2.   A brief history

In a destination based control system (also known as call allocation), passengers register their destination floors at landings.  The system then tells the passenger which elevator to use.

Port (1961) introduced the concept of destination dispatch in an Australian patent application.  He reported that up and down hall call buttons were confusing passengers.  By knowing passengers’ destinations, he could reduce passenger error and group together, in the same car, passengers traveling to the same destination.  Barker (1995) reports that the Port system was installed in two buildings in Sydney, Australia.  Barney and Dos Santos (1977) discuss destination control, presenting optimization algorithms and simulation results based on work done by Closs (1970) at the University of Manchester Institute of Science and Technology.  Destination dispatch was not generally available until the introduction of Schindler’s Miconic 10, the operation of which is described by Schröder (1990).  Otis took a different approach to destination control, with a system called Channeling, as described by Powell (1992).  Rather than have passengers register their destinations, Channeling limits the number of floors served by each car during the up peak.  A display screen is provided to communicate to the passengers which floors are currently being served by which elevator.  Channeling “boosts” the up peak performance.   Hikita et al  (2001) present Mitsubishi’s Sigma AI-2200 control system, which can operate with destination call stations at the main lobby floor.  Barney (1992) analyses the different up peak systems.

3.   ThyssenKrupp ETD dispatching concept

3.1   Overview of approach

An ETA (Estimated Time of Arrival) traffic control system’s aim is to minimize the time a passenger waits for an elevator.  When a passenger places a new call, the system calculates which elevator can reach it first.  This is normally the elevator to which the call is allocated.

The ThyssenKrupp ETD (Estimated Time to Destination) traffic control system aims to minimize total passenger journey time, which is the time passengers are waiting for and traveling in the elevators.  ETD takes account of the time it will take for each elevator to serve the new call.  It also takes full account of the impact of the new allocation on all other passengers in the system.

ETD can operate as a full destination control system, for which passengers register their destination floors at landings.  ETD can also operate with conventional up/down hall call buttons, or with a combination of up/down hall call buttons and “booster” destination call stations on peak floors.

3.2   Implementation

First consider ETD operating as a full destination system, in which passengers enter their destination at the landing.  In theory, we know about every passenger currently waiting for an elevator, or traveling in a car.

A new passenger arrives and registers a call.  ETDe is the estimated time to destination, in seconds, of the new passenger if they were to use elevator e.  It is calculated by determining the estimated time of arrival of elevator e at the landing where the new passenger is waiting.  Then continuing to map the trip of the elevator forward in time until the passenger reaches their destination, taking into account all intermediate stops on the elevator’s journey.

The system also calculates the System Degradation Factor of the allocation for every other passenger in the system.  SDFe,k  is the delay that the new passenger will cause to passenger k, in seconds, if the new passenger is allocated to the elevator e.  SDFe,k is calculated by mapping out the journey of passenger k before and after the introduction of the new passenger into the system.  SDFe,k is calculated for all passengers (k=1 to n) currently waiting or traveling.

The Total Cost of the allocation of the new passenger to elevator e is then the system degradation to all the other users of elevator e, plus the estimated time to destination for the new passenger.  This can be written as follows:

The system allocates the new passenger to the elevator with the lowest total cost.

3.3   Example scenario

To understand how the ETD algorithm differs from other algorithms, consider the following scenario: there are three elevators, and a number of calls on the system.  A new down hall call is registered at level 7.  Which elevator should serve the call?

Using ETA

• Car 1 is 15 s from the call.  It has to stop at level 8, which will delay it 10 s on its journey to level 7.  So the ETA of Car 1 is 15 s plus 10 s, which is 25 s.
• Car 2 is 10 s from the call.
• Car 3 is 5 s from the call. 

Based on the above analysis, the ETA algorithm allocates Car 3.

Using Fuzzy Logic, or other intelligent controller
 
     

                                                                                   
There are many variations in implementation, but the deciding logic may be as follows:

• Car 1 is far and almost empty
• Car 2 is close and almost empty
• Car 3 is very close and almost full.

Car 2 is allocated in preference to Car 3 as the more intelligent controller realizes that minimizing ETA is not always the best strategy.  It is worse to delay the almost full car to pick up the new passenger, even though it is the closest.

Using ThyssenKrupp ETD Full Destination
 
           
If Fred is allocated to Car 1, then

• The delay to Anna is 0 s.
• Fred waits 15 s for the elevator to travel to him, plus 10 s to drop off Anna.
• Once picked up, Fred then has to complete his journey, which will take 25 s.
• The Total Cost is 50 s.

If Fred is allocated to Car 2, then

• Simon’s trip is delayed by 10 s while Fred is picked up.
• Fred has to wait 10 s to be picked up.
• Fred then takes 25 s to complete his journey, plus 10 s to drop off Simon.
• The Total Cost is 55 s.

If Fred is allocated to Car 3, then

• A group of 8 people are each delayed 10 s to pick up Fred and 10 s to drop off Fred.
• Fred has to wait 5 s to be picked up.
• Fred takes 25 s to reach his destination once he has been picked up.
• The Total Cost is 190 s.

Fred is allocated to Car 1, as this allocation is the best overall solution.

This example is indicative only of how the different systems may evaluate the same scenario and make a different decision.  For other scenarios, the different systems may or may not make the same allocation.

3.4   Conventional calls with ETD

The ETD algorithm applies a common approach to both conventional up/down hall calls, and destination calls, allowing both to be used in the same system.

For hall calls in the system, we calculate the ETD and the SDF for hall calls and corresponding car calls.  If the system does not know the actual car call that will arise from the hall call, then an inferred or estimated car call is assumed.  Once the hall call is answered, and the car call is known, the system makes any appropriate correction in subsequent calculations.

A destination call normally corresponds to one person, but a hall call may have a group of people behind it.  So, the system estimates the number of people behind each hall call, and gives the call an appropriate weighting.  In this way, each passenger is equally important in the evaluation.  The estimate of number of people behind a hall call is continually updated.  So, as a hall call gets older, it becomes more important.  This inherently avoids “long wait” calls.

4.   Simulation results

Using Elevate a wide range of buildings and traffic scenarios have been modeled.  The following results are for a “benchmark” 18-story building with 50 persons per floors, and six 3000 pound (1360 kg) elevators at 500 ft/min (2.5 m/s).  The results are typical of other simulations.

Key      Average Waiting Time (s)
           Average Transit Time (s)
 
 
  
 
 
Figure 1.1     12% up peak traffic

 
 
 
Figure 1.2      15% up peak traffic

 
 
 
Figure 1.3      12% lunchtime traffic

 
 

Figure 1.4      15% lunchtime traffic

 
 
 
Figure 1.5      7% down peak

 
 
 
Figure 1.6      15% down peak
 
Up peak simulations assume 100% of the traffic is traveling up the building from the main terminal floor.  Lunchtime simulations assume 40% of the traffic is traveling up the building, 40% down and 20% inter-floor.  Down peak simulations assume 100% of the traffic is traveling down the building to the main terminal floor.

Passenger Waiting Time is defined as the actual time a prospective passenger waits after registering a landing call (or entering the waiting queue if a call has already been registered) until the responding elevator doors begin to open.  If the responding elevator doors are already open when a passenger arrives, the waiting time for this passenger is taken as zero.  The Average Waiting Time is the average Passenger Waiting Time for all passengers transported during the simulation.  Passenger Transit Time is the time the responding elevator doors begin to open to the time the doors begin to open again at the passenger’s destination.  If the responding elevator doors are already open when a passenger arrives, the transit time for this passenger commences at the time the passenger arrived.  The Average Transit Time is the average Passenger Transit time for all the passengers transported during the simulation.

5.   Discussion

5.1   Grouping of passengers traveling to common destinations

If a large number of people arrive at an elevator landing during a short time, a destination control input enables the system to group together the people traveling to common destinations.  For example, everyone traveling to levels 3 and 5 may be allocated to car 1, and everyone traveling to levels 4, 6 and 7 may be allocated to car 2.  Because people traveling together are put in the same cars, the elevators make fewer stops.  People have to wait for their allocated elevator to arrive, which is not necessarily the next car to stop at the floor.  So, they may wait longer.  But once they are in the car, the reduced number of stops means they get to their destination floor faster. 

This grouping is inherent within the ETD algorithm; it is not programmed specifically, but is a product of the algorithm to minimize ETD + SDF.

Grouping works particularly well at busy floors, where there are a significant number of people traveling to common destinations.  As shown in Figures 1.1 and 1.2, during up peak traffic, the improvements in journey time arising from grouping are dramatic.  At other times, for example at lunchtime, the grouping is less significant, and the performance improvements achieved with destination input during the up peak are not realized.  However, an advanced dispatcher with or without destination input, such as ETD, will outperform less intelligent systems.  For example, see Figures 1.3 and 1.4.  

BEWARE!  Selecting fewer, lower speed or smaller elevators for a commercial office building based on the enhanced performance of destination control systems or boosters during up peak, is likely to cause problems with performance at other times, particularly during lunch time and evening peaks.  As suggested by Siikonen (2000), if planning a building based on up peak traffic, designs using up peak boosters should use a higher value of up peak handling capacity so that the elevators are able to handle lunch time traffic.  Barney (2002) states that provision of destination information is most effective for heavy traffic situations, particularly up peak.

5.2   Reallocation of calls

When a conventional system allocates a hall call to an elevator, it can change its mind about the allocation, up to the point where the allocated elevator starts slowing down to answer the call.  The benefit of allowing re-allocation is that the best elevator to serve a call may change as new calls are introduced into the system.  There are also nuisance difficulties, for example if the allocated elevator has its doors held open for a long period at a preceding stop.  Except in special circumstances (e.g. car goes out of service), destination control does not allow re-allocation of calls.  Once the passenger has been told which car to use, the system is committed to sending that car, even if 5 seconds later, it is no longer the best car for the call.  Hence, in traffic scenarios where grouping is minimal, a system with destination input offers no meaningful improvements over conventional systems. 

6.   Other ThyssenKrupp ETD features

6.1   Learning

ETD includes algorithms to learn about the traffic in the building where it is installed.  The system learns the traffic flow in terms of people rather than by calls.  We are not only interested in when the next call is likely to be made.  We also want to know how many people will be behind a (conventional up/down, non-destination) call.

To address cultural and social variations, the system also learns both the mass of typical passenger, and the capacity factor (how full passengers fill the car).  The capacity factor is learned by time of day, as passengers may load cars more fully at different times.  For example at the end of the day when people want to go home, there is a tendency for passengers to accept fuller cars.  This helps in decisions, such as whether or not to bypass a call because the elevator is full.

6.2   Call correction

It is human nature to try and “beat” the system, and most conventional systems will cancel calls automatically if misuse is detected.  Abuse with destination calls is also a potential problem.  A passenger at level 7 may repeatedly register a destination call to level 3, assuming (correctly) that if the system registers a queue of people waiting, it may send a car more quickly.  This type of abuse is detected and corrected automatically.  Other corrections include detecting people who place a call, then do not get into the elevator when it arrives.  Conversely, a group of passengers may arrive at a landing with destination call stations, and only register a single destination call.  The additional passengers are detected using load weighing when the call is answered, allowing a correction to be made.

6.3   Timed early car announcement

In some dispatching systems, as soon as a passenger registers a hall call, a light and gong announce which elevator will serve the call.  This is sometimes known as early car announcement.  Once announced, the allocation of the car to the call is normally fixed.

The ETD dispatcher allows re-allocation of calls on floors without destination input.  As already discussed, whenever possible, from the dispatching viewpoint it is beneficial to allow re-allocation of hall calls as the best elevator to serve a call may change as new calls are introduced into the system.  However, early announcement of the arrival of the elevator does have advantages.  The passengers have the assurance that the elevator is about to arrive, and the perception of how long they have waited may be less.  The passengers also have time to move towards the landing doors before the elevator arrives, which speeds up the loading process.

The ETD dispatcher allows the early car announcement time to be specified, allowing enough time for passengers to be ready for the elevator.  In simulation, tests have shown that an early car announcement time of about 10 seconds does not degrade dispatching performance significantly, while providing most of the benefits of early car announcement.

7.   Summary and conclusions

Up peak boosters and full destination systems work primarily because they group together people who are traveling to and from the same destination.  They work particularly well during up peak traffic.  How well up peak boosters and destination systems work for a specific building application will depend on how well the algorithm is implemented, and actual passenger traffic.    The ETD dispatcher has been evaluated with Elevate, and each option has been shown to have distinct advantages depending on the application.

7.1   ETD conventional 

With regular hall call buttons ETD outperforms both Elevate’s benchmark system and earlier ThyssenKrupp algorithms. 

7.2   ETD full destination

Full destination systems are good at grouping peak loads, such as those that occur in commercial office buildings during the morning up peak.  In a modernization where the existing system has insufficient handling capacity, the improvements can be dramatic.  The benefits are more dramatic in up peak than in other traffic conditions. 

Full destination systems can also cope with installations where not all the elevators in a group serve the same floors.  Conventional systems cannot deal with this scenario efficiently. For example, consider an office building where only one car of a group of four elevators serves the basement car park.  Traveling to the car park, the passenger only has a one in four chance of the correct elevator responding to their call.  With a destination system, the system knows the passenger’s destination, so it can allocate the correct elevator.  Another scenario is the high rise building where the building steps back at higher levels, so not all of a bank of elevators can travel to the highest floors.

7.3   ETD with boosters

For this option, destination input is only provided at heavy traffic floors that benefit from grouping.  For example, boosters may be placed at the main terminal and at a cafeteria floor.  At other floors, the use of conventional up and down hall call buttons allows the system to benefit from the opportunity to re-allocate calls.  As there are less destination input devices, the cost is lower, making it the best performance-value option in most applications with peak traffic.

References

1. Barker F (1995)   Is 2000 feet per minute enough?  International Conference on High Technology Buildings, Council on Tall Buildings and Urban Habitat, São Paulo, Brazil
2. Barney G C, dos Santos S M  (1977)  Lift Traffic Analysis Design and Control  1st  edn. (London: Peter Peregrinus)
3. Barney G C (1992)  Up peak revisited    Elevator Technology 4, Proceedings of ELEVCON’92 (The International Association of Elevator Engineers)
4. Barney G C (2002)   Elevator Traffic Handbook: Theory and Practice Draft edn, to be published 2002 Q4 by Spon Press, London.
5. Closs G D (1970) The computer control of passenger traffic in large lift systems, PhD Thesis, Control Systems Centre, University of Manchester Institute of Science & Technology
6. Hikita S et al, The Latest Elevator Group Control System  Elevator Technology 11, Proceedings of ELEVCON 2001 (The International Association of Elevator Engineers) (2001)
7. Port L W (1961)  Elevator System  Commonwealth of Australia Patent Specification, Application Number 1421/61, 14 February 1961
8. Powell B (1992)  Important Issues in Up Peak Traffic Handling    Elevator Technology 4, Proceedings of ELEVCON’92 (The International Association of Elevator Engineers)
9. Schröder J (1990)  Advanced Dispatching Destination Hall Calls + Instant  Car-to-Call Assignments: M10  Elevator World, March 1990, Volume XXXVIII, No 3
10. Siikonen M L (2000)  On Traffic Planning Methodology  Elevator Technology 10, Proceedings of ELEVCON 2000 (The International Association of Elevator Engineers)