KONE Polaris Hybrid

Allocations with genetic algorithms of its destination-control system are covered

by Marja-Liisa Siikonen, Janne Sorsa and Tuomas Susi

In the early 1970s, Dr. G.D. Closs showed that with early destination call information, the assignment of calls to elevators could be made more efficiently.^[1] Technology at that time was not ready for the real application of this discovery. Today, many major elevator manufacturers have a destination-control product with destination operation panels (DOPs) at every floor. Most manufacturers, however, do not have a hybrid system in which the same group control allocates both destination calls and normal landing calls.

The advantage of the destination-control system (DCS) is that with the additional information of passenger destination floors, the group control can gather people with either the same origin or destination in the same car. This decreases the number of elevator stops, the elevators travel faster throughout the building, and the handling capacity (HC) of the group is increased, especially if DOPs are placed on floors with heavy traffic. In KONE’s Polaris Hybrid DCS™, DOPs are typically placed on entrance floors, transfer and restaurant floors, and other floors with heavy traffic, which brings about the same service-level improvement as if DOPs were placed at every floor.

The Polaris Hybrid uses a load-weighing device and photocell signals in the door opening to count the number of passengers entering and exiting the elevators throughout the day in 15-min. periods. The group control compiles statistics of the passenger traffic on each floor in both the up and down direction. Based on the statistics, it forecasts the daily traffic for each 15-min. period (Figure 1). Optimization of the group control is set according to the traffic situation. For instance, during light and normal mixed-traffic situations, passenger waiting times are optimized, while during heavy traffic, passenger journey times and HC are optimized. If DOPs are placed at the entrance floors in office buildings, passenger waiting times become shorter, especially during traffic peaks (Figure 2). In the morning and after the lunch hour, there are periods of heavy incoming traffic, which DCS handles more efficiently than the conventional two-button system.

Call Allocation with Genetic Algorithm

In a conventional two-button system, the most effective way to serve existing calls is to allocate them continuously, e.g., at least twice per second. An active landing call is reallocated to the best elevator as long as the chosen elevator starts to decelerate to the floor. Then the call is fixed to that elevator and not reallocated. One way to find the best call allocation would be to test alternative ways for elevators to serve the existing landing calls, referred to here as “elevator routes.” The challenge in continuous allocation is that the number of alternative routes increases exponentially to the power of existing landing calls. For L elevators and N active landing calls, the number of elevator routes is L^N. For example, if there were 20 active landing calls in an eight-car group, the number of alternative elevator routes would be 8²⁰ ≈ 10¹⁷, which cannot be calculated in real time.

In the DCS, destination calls are fixed immediately when the call is registered. Then, the number of alternative elevator routes is just the number of elevators, which makes the computation time short. With the Polaris Hybrid, both destination calls and normal up and down calls are allocated by the same algorithm. In this case, destination calls are fixed immediately, while landing calls are reallocated continuously, as in the conventional control system. Therefore, the computational challenge is quite the same as in conventional control.

The Polaris Hybrid DCS uses a heuristic optimization method called “Genetic Algorithm” (GA) to quickly find efficient elevator routes without calculating all the alternatives.^[3] The algorithm borrows its principle from evolutionary biology. A solution proposal defining the serving elevator of the active calls is encoded in a “chromosome.” In this application, a chromosome of the genetic algorithm is described by a string of integers. The value of a particular “gene” represents an elevator, or a deck of a double-deck elevator^[4] suggested to serve a particular landing call.

An example of a duplex elevator group is shown in Figure 3. The elevators are marked “E1” and “E2.” The triangles on the right side of the elevator shafts represent active landing calls. The green color depicts the up direction, and red depicts the down direction. The yellow circle in the shaft represents the car call given inside elevator E1. The green circles represent destination calls of up-going passengers, and the numbers inside the circles denote their destination floors. Two randomly selected chromosomes are shown on the right, with genes connected to the calls of both types.

The genetic algorithm starts with a random set (or “population”) of M chromosomes. A chromosome defines the serving elevator for each call. Then, the routes of the elevators are constructed, and the estimated time of arrival at each stop on the route is calculated from the elevator dynamics. Finally, the “fitness” value of the chromosome is calculated. These values define the order in which the chromosomes are preferred, with respect to the optimization objective, such as call time, waiting time, journey time or energy consumption. A number of the best chromosomes (K, for instance) with the shortest passenger waiting times are selected from the population of M chromosomes. K will be used as “parents” when creating a new generation of M chromosomes using “crossing over” or “mutation.” After some generations, the best chromosomes remain unchanged in sequential generations, and the algorithm converges to the best solution among those generated. Since the genetic algorithm is a heuristic method, the solution is not necessarily the global optimum, but it is at least near optimal. The solution can be found quickly in real time.

Maximum Up-Peak HC

Sorsa, et al. studied the most efficient way to increase HC in up-peak.^[5] Two types of zoning were applied: elevators were forced to serve adjacent floors in contiguous zones, or there was no such restriction (Figure 4). The destination stops were optimized by balancing, i.e., by minimizing the variance of the zones with respect to relative HC (HC%) and round-trip time (RTT). Passenger arrival rate was selected so all the cars could depart from the lobby with 80% of the rated load.

The handling capacity and RTTs of the example cases in Figure 4 are compared in Table 1. The used optimization objective has a remarkable effect on the optimal choice of destination floors. The number of stops, S, is the same in all test cases, but the highest reversal floor, H, varies. The shortest RTT and maximum HC are reached with contiguous zoning and by balancing HC%. With this solution, in theory, the total HC of the elevator group more than doubles compared to that in conventional control.

Summary

The KONE group controls measure and learns the passenger traffic in a building. The traffic pattern is used in selecting the optimization objective during each 15-min. interval every day. With the Polaris Hybrid, normal two-button calls and destination calls are allocated by the same genetic algorithm. This makes it possible to place both DOPs and normal up and down calls, even on the same floor, and to optimize the service of all calls at the same time.

The Polaris Hybrid increases HC, especially for incoming traffic from the lobby. The amount by which the handling capacity can be increased in a purely up-peak situation depends on the DCS control algorithm, as well as the number of elevators in the group. The results of a simulation study show the HC% of an eight-car group in a 20-floor building can even be doubled with an efficient DCS algorithm that utilizes the information of the passenger destinations.

With DCS, up- and down-peak traffic is mirrored, in which only the origin and destination calls switch places. That is why HCs of both up- and down-peaks are nearly equal, with the same passenger arrival rate. Conventional control systems use continuous call allocation, which is efficient in down-peak, since there is only one destination call to the lobby. However, DCS has more exact information on the number of waiting passengers. As a result, the service level is about the same with conventional and DCS controls in down-peak situations.

The Polaris Hybrid increases the HC of floors with DOPs. In modernization cases where the building has too few elevators, DOPs can be installed in the lobby or turnstiles. With this arrangement, traffic handling can be improved as much as if DOPs were placed on every floor, since the main traffic peaks usually come from the lobby. In new buildings, this DCS can lead to smaller or fewer elevators, or additional served floors in a building compared to the two-button system with collective control.

References
[1] Closs, G.D. “The Computer Control of Passenger Traffic in Large Lift Systems.” Ph.D. thesis, the Victoria University of Manchester, 1970.
[2] Siikonen, M.-L., Kaakinen, M. “TMS9000 Group Control – Using Artificial Intelligence to Improve Passenger Service Quality.” Elevatori, 1994. Vol. 23, No. 3-4, pp. 25-36.
[3] Tyni, T., Ylinen, J. “Evolutionary Bi-Objective Optimisation in the Elevator Car Routing Problem.” EJOR, 168, 2006, pp. 960-977.
[4] Sorsa, J., Siikonen, M.-L. “Double-Deck Destination Control System.” Proceedings of Elevcon 2006: Elevator Technology 16, IAEE, 2006, pp. 318-327.
[5] Sorsa, J., Hakonen, H., Siikonen, M.-L. “Elevator Selection with Destination Control System.” ELEVATOR WORLD, January 2006, pp. 148-155.