Fulfilling the Potential of DD DCS

The double-deck destination-control system (DD DCS) combines two well-known approaches to boost morning up-peak traffic in office buildings and save building core space.

This article describes the technical principles of elevator dispatching, on which Rick Barker’s article “Harmonized Elevator Dispatching and Passenger Interfaces” (ELEVATOR WORLD, November 2018) is based. Editor

Double-deck elevators with DCSes are used in tall buildings to reduce core space occupied by elevators. However, DCS lunch traffic performance still limits potential space savings, which is largely due to the immediate assignment of passenger calls to elevators and decks. This article introduces two optimization methods for an elevator group control system to solve this challenge. First, uncertain near-future passenger arrivals are modeled by scenarios, which then define the optimal elevator routes robustly. Second, the re-optimization of call assignments gives maximum flexibility for the control to react to new passenger arrivals.

Introduction

The DD DCS combines two well-known approaches to boost morning up-peak traffic in office buildings and save building core space.^[6] A double-deck elevator consists of two attached elevator cars. This doubles car capacity per elevator shaft. In addition, the dual lobby enforces the even/odd split, where passengers are distributed to the lower and upper decks based on their destination floors.^[5] In a DCS, passengers give their destination floors using numeric keypads in the lobbies. Based on the additional information, the DCS can gather passengers traveling to the same destinations in the same elevators, which reduces elevator stops and increases up-peak handling capacity.^[13] On the other hand, both the double-deck elevators and DCS do not yet perform optimally during mixed lunch traffic.^{[15 & 16]}

For the DD DCS, lunch traffic is challenging for several reasons:

1. Traffic: Lunch traffic does not provide as many opportunities to group passengers into the elevators as up-peak traffic does, since typically less than half of the traffic is incoming. Interfloor traffic between the upper floors breaks the even/odd split, which is an efficient strategy for incoming and outgoing traffic.
2. Signalization instant: The current de facto standard DCS assigns an elevator to each call and signals it immediately after a call has been registered. This assignment cannot be changed later. At the time the call is finally served, the assignment may no longer be optimal due to changes in system state.
3. Passenger behavior: The DCS assumes that each passenger gives exactly one call. Passengers, however, often travel in socially connected groups to the same destinations.[11] Typically, only one passenger in a group gives the call, while the others tailgate into the elevator. Individual passengers have also been observed to register several calls in rapid succession in the hope of getting an elevator faster or with more space.

Traffic conditions cannot be altered. However, the bilevel optimization model (in the following section) maximizes the efficiency of elevator routes independent of the overall objective, which minimizes, e.g., passenger waiting times. The signalization instantly determines the assignment policy under which the elevator group control system (EGCS) operates. The current DD DCS is based on immediate assignment policy (IA), to which both the serving elevator and deck are immediately fixed. To reduce the risk of current assignments becoming suboptimal in the near future, the EGCS can optimize elevator routes in a robust manner by predicting new passenger arrivals and estimating the number of passengers of a call (“Predicting Passenger Arrivals With Risk Scenarios” section).

An alternative way of reducing the effects of future system states is to postpone the instant when the serving elevator or deck is finally fixed. The DD DCS allows the delayed deck assignment policy (DDA): the serving elevator is still immediately signaled, as is customary, but the EGCS can reoptimize the serving deck until the last moment. The delayed elevator assignment policy (DEA) allows reoptimization of both the serving elevator and deck. The DEA has also been considered for single-deck elevators.^[9] In the “Genetic Algorithm for Real-Time Optimization” section, a real-time genetic algorithm is introduced to solve the bilevel model under DDA and DEA, while the advantages of these techniques are demonstrated by simulations in the “Simulation Results” section.

Bilevel Model of Double-Deck Elevator Dispatching

The main task of the EGCS is to dispatch an elevator to serve each passenger call. Mathematical methods to make the dispatching decision have been researched widely, especially for conventional control.^[4] One approach is to frequently solve a snapshot optimization problem, called the “elevator dispatching problem” (EDP).[20] The solution to the EDP defines the route of each elevator belonging to elevator group E to serve the set of passenger calls V. The elevators are dispatched to the first calls of their routes. In the DCS, passenger calls pair a landing and car call. Therefore, set V can be further divided into landing and car calls, formally denoted by S and T.

The double-deck elevator dispatching problem (DD-EDP) assigns an elevator and a deck to each passenger call and determines their serving order.^[18] This problem can be formulated as a single-level optimization model, where all decisions are simultaneously considered globally. In a bilevel optimization model, the elevator assignments are decided by an upper-level problem, while the deck assignments and the ordering are decided by separate lower-level problems for each elevator.

The single-level model has a disadvantage in that it may produce inefficient elevator routes when minimizing passenger waiting times. An example of such a situation is shown in Figure 1 (left), where a passenger inside the lower deck is traveling toward F3, and another is waiting for transportation from F3 to F7. The numbers beside the arcs show the combined stop and flight times between the corresponding start and end floors of the flight, as well as the elevator arrival time on the end floor (in parentheses). In this example, the problem is to decide whether the lower or upper deck picks up the waiting passenger on F3. Clearly, the upper-deck solution shown in the middle minimizes waiting times, since it takes only 4.8 s for the upper deck to reach F3, compared to the 6.8 s it takes the lower deck. However, the upper-deck solution contains a stop, during which the lower deck

This observation leads to the decomposition of the single-level model to two levels, where the upper level optimizes passenger service quality, and the set of lower-level problems optimizes the route of each elevator separately. The bilevel model considers two assignment variables. In the upper-level problem, passenger calls i V are assigned to elevators e  E by binary decision variables x_e,i. In the lower-level problem of elevator e, calls i V_e are assigned to deck d {1,2} by binary decision variables y_e,d,I, V_e ={i      V|x_e,i = 1}. In addition, the lower-level problem determines the order in which the calls are visited using binary arc variables z_e,d,i,j, where call i V_e precedes call j V_e if z_e,d,i,j = 1. The key variable for objective functions is elevator/deck arrival time to a call floor, t_e,d,i, which defines passenger waiting and journey times, as well as the total elevator route time. Each call is associated with call time y_i elapsed since its registration and demand Di, as well as the number of passengers, which is positive for landing calls and negative for car calls.

The bilevel optimization model follows (see your author’s 2017 article, “Optimization Models and Numerical Algorithms for an Elevator Group Control System,”^[18] for details):

subject to

where  is the set of optimal elevator routes, , that minimizes the route time for each elevator e with the given assignments . The objective function (Eq. 1) minimizes the total passenger waiting time. It is straightforward to modify it to minimize passenger journey times by changing the innermost summations to consider car calls T_e instead of landing calls S_e. Demand D_i typically corresponds to one passenger. The demand might also be a larger number, which is either an input or an estimated passenger group size. Eq. 2 ensures each call is assigned to exactly one elevator.

The lower-level problem in Eq. 3 defines the route of an elevator as the sequence of locations to be visited. Elevator/deck arrival times are accumulated along the route by flight times between floors and stop times. The lower-level objective is to minimize route time, which corresponds to the arrival time for the last stop. In addition, the model keeps track of the number of passengers inside each deck. As a result, a feasible solution satisfies the capacity constraint. Furthermore, the basic rules of elevator operation are followed.^[3]

Predicting Passenger Arrivals With Risk Scenarios

The DCS, under the IA, requires two kinds of predictions about passengers: the number of passengers and new arrivals. Individual passenger arrivals can be modeled as a Poisson process with rate  persons per 5 min.^[1] Modern elevators can accurately count boarding and alighting passengers and learn the arrival rates on each floor for the 15-min periods of a day.^[14] Passenger batch arrivals can be modeled as a compound Poisson process, where they arrive at lobbies in batches or bursts of demand.^[11] Batch sizes cannot be directly observed from the passenger counts but can be estimated for each one-directional elevator trip.^[12] If batch sizes follow a geometric distribution with the mean batch size of β, the process is known as a geometric Poisson or Pólya-Aeppli process with  ⁄β arriving batches per 5 min.^[10]

The robust DD-EDP considers multiple scenarios with different passenger demands.[19] A scenario s is defined by risk levels  , which are used to predict demand  and arrival time of a new passenger on floor k. The demand is drawn from the inverse distribution function of discrete random variables for probability

where F denotes the cumulative distribution function for n events.

The demand on call floor k consists of the initial demand at the time of registering the call and the demand increasing with time,

where G and GP stand for the geometric and the geometric Poisson distribution, respectively. The parameter of the geometric distribution is 1/β, while the geometric Poisson distribution is parameterized by the expected number of batch arrivals within time  (i.e., the time since the call was registered plus the remaining time until elevator arrival). The prediction can also be applied for the ordinary Poisson process with individual arrivals. Then, the initial demand  equals one, and  reduces to the Poisson distribution with β = 1.

On floors without calls, a new passenger arrival may occur, at most, in time  with probability  , where  denotes the time since the previous call was recorded on floor k. Since batch interarrival times follow an exponential distribution with parameter , time  can easily be solved from the distribution function.

As an example, these prediction methods are tested on one single-deck elevator under the down-peak condition with the mean batch size of one-and-a-half persons.[19] Approximately 60,000 scenarios are generated by combining three risk levels for each floor. In each scenario, passengers are predicted with both the Poisson and the geometric Poisson process in an instance of the EDP. Figure 2 shows the distribution of the total demand carried along the elevator route across all scenarios. The figure also has two constant lines, which correspond to the demand without predictions and the realized demand in a simulation.

Clearly, the solution to the snapshot EDP has a risk of becoming suboptimal, since the realized passenger demand is much higher than assumed without predictions. The estimation with the geometric Poisson process results in wider distributions than the Poisson estimates. This guarantees the robustness of the solution. Furthermore, the realized values remain within the range only when assuming the geometric Poisson process. This indicates a batch arrival process should be used in passenger prediction.

Genetic Algorithm for Real-Time Optimization

A genetic algorithm is an optimization method that mimics naturally occurring evolution.^[7] The algorithm manipulates the population of chromosomes over generations by genetic operators such as crossover and mutation. A chromosome defines a candidate solution to an optimization problem at hand, where each gene of a chromosome determines the value of one decision variable. The fitness of a chromosome corresponds to the objective function of the optimization problem, which is usually minimized.

A genetic algorithm has already been applied to single-deck elevator dispatching and the real-time optimization of an EGCS, which was later extended to double-deck elevators.^{[15, 17 & 20]} The algorithm sets up a gene for each passenger call. The possible values of a gene are the range of elevator car indices, which uniquely map all elevator/deck combinations to an index. Thus, a chromosome assigns both an elevator and a deck to a passenger call, which makes it a single-level model.

The bilevel DD-EDP problem only assigns an elevator to a passenger call on the upper level. The genetic algorithm is slightly modified to solve the bilevel model: a gene value represents an elevator index. Thus, a chromosome corresponds to a solution to the upper-level problem. Figure 3 describes the principle through an example, where deck A1 has a passenger traveling to F3, and three passengers on floors F4, F5 and F6 are waiting to be picked up and transported to the main lobby. The task is to assign an elevator and a deck to these three passenger calls. The outgoing passengers can be served by both decks and transported to the lower or the upper lobby level according to the optimal solution. From the upper lobby, the passengers can use the escalator to travel to the ground-floor exit. The chromosome shown on the left side of the figure assigns the call on F4 to elevator A, and the calls on F5 and F6 to elevator B. The optimal deck assignments and elevator routes for this upper-level assignment are shown on the right side of the figure. Thus, the optimal solution takes advantage of coincident calls on F3 and F4 (simultaneous delivery and pickup), as well as on F5 and F6 (two simultaneous pickups).

The earlier single-level model allows poor deck assignments in the search space of the genetic algorithm. For example, deck A1 could serve floor F4; deck B1, floor F6; and deck B2, floor F5, which would maximize noncoincident stops, as well as passenger waiting and journey times. Poor candidate solutions are eventually discarded by the genetic algorithm, but they first need to be evaluated. This, on the other hand, wastes scarce computational resources of an EGCS. The bilevel model discards such irrelevant deck assignments from the highest level of optimization, which eases the search of the global optimum.

Naturally, the bilevel model also needs to consider these poor deck assignments, but they are delegated to the less-complex lower-level problems, do not disturb the high-level optimization and can be handled by efficient heuristics.^[18]

The assignment policy determines the moment when the serving elevator and/or deck of a passenger call must finally be fixed. In other words, a passenger call can be reassigned to another elevator and/or deck until fixed; e.g., at the deceleration point. This, on the other hand, is in direct relationship with the size of the search space in the genetic algorithm: the search space grows exponentially with respect to the number of newly registered calls and the number of calls waiting for pickup  (Table 1). Usually,   is small (either one or two), but may be large.

The most remarkable observation of the table is that the bilevel model has the same size of search space for both the IA and DDA. This means that the DDA does not increase the (high-level) computational complexity from the IA with the bilevel model. In the earlier single-level model, the search space grows exponentially with respect to , which increases the required computational effort of the DDA beyond the practical limit of an EGCS. The high-level complexity of the bilevel model does not depend on the number of decks, which makes this approach efficient also for multideck elevators and other multicar systems.

As an example, consider a large-scale instance in which 32 passenger calls are waiting for pickup. A group of five double-deck elevators serves all floors. One call is newly registered, while 31 are waiting for pickup. Thus, when applying the bilevel model to this problem, the number of feasible solutions equals five for the IA and DDA but 5³² > 10²² for the DEA. Even if the evaluation of one solution took 1 µs, the evaluation of all feasible solutions would take 108 years in the case of the DEA. The genetic algorithm, however, evaluates only about 3,000 candidate solutions before converging to the likely optimum in less than 100 ms, which is fast enough for real-time optimization.^[18] The fast convergence of the genetic algorithm is demonstrated in Figure 4, which shows the evolution of population fitness throughout the generations. In the initial population, the minimum (best), maximum and average fitness values are all high. However, they drop sharply within approximately 15 generations to such a level that large improvements are not found anymore. The best solution is found during the 24th generation, while the algorithm continues to search for better solutions until the 64th generation.

Simulation Results

A case study of an office building with 18 upper floors and two entrance floors is conducted to demonstrate the effect of the assignment policies on passenger service quality. Each floor has a population of 100. Floor-to-floor distances are equal at 4.15 m. A double-deck elevator group with five identical elevators with a rated speed of 4 m/s, an acceleration of 1 m/s² and a jerk of 1.6 m/ s3 serves all floors of the building. The end floors are only served by one deck: the bottom floor by the lower deck and the top floor by the upper deck. Each deck has capacity for 17 passengers.

Door opening and closing times are 1.4 and 3.1 s, respectively, while no door preopening is used. In addition, there is a start delay of 0.7 s and door closing delay of 0.9 s; i.e., the delay after passenger clearance before door closing. Lunch traffic consisting of 40% incoming, 40% outgoing and 20% interfloor traffic is simulated using the KONE Building Traffic Simulator (BTS™).^[21] In these simulations, the objective function of the DD-EDP minimizes the journey times of incoming passengers and the waiting times of other passengers. A series of simulations is run with increasing passenger demands from 4% to 15% of the population per 5 min.^[8] Each passenger demand is simulated for 120 min, after which the simulation is reset for the next demand. The first 15 and last 5 min are discarded from the results. Average passenger waiting and transit time, as well as time to destination, are shown for each arrival rate in Figures 5-7.^[2] In this study, the results of the immediate assignment (IA) represent the first double-deck destination control.^[17]

The delayed assignment policies significantly improve passenger service quality, as can be expected. Average waiting times with the DDA are up to 5 s shorter than with the IA. On average, the improvement is about 10% but up to 15% under the most intense passenger demand. The DEA, on the other hand, shows a dramatic reduction of up to 15 s, or 30%, in average waiting time.

The delayed assignment policies also reduce passenger transit times. Somewhat surprisingly, the shortest transit times are observed with the DDA, as the averages are up to 5 s or 5-7% shorter than with the IA. In this respect, the DEA does not improve on the IA, except for the low passenger demands. The good performance of the DDA can be attributed to the reduced number of stops, since the origins and destinations of interfloor passengers can be better optimized among the other stops of elevator routes. On the other hand, the DEA seems to weigh waiting times more when it has the chance to reassign elevators optimally.

The improvements by delayed assignment policies in times to destinations combine the observations about waiting and transit times. With the DDA, average transit times are up to 8 s, or 7-8%, shorter than with the IA, which is the result of reductions in both waiting and transit times. The improvement provided by the DEA in average time to destination can be attributed to the improvement in average waiting time. The reduction is up to 15 s but varies between 10% and 15% for different passenger demands. As a result, the DDA and the DEA are rather close to each other (within 5 s), with respect to average time to destination.

However, the DEA clearly provides the best service quality. The significance of the above results is clear if they are contrasted with elevator planning. Typically, passenger demand of 11% or 12% of the population per 5 min is assumed as the required handling capacity for lunch traffic. For such a high demand, passenger waiting time is usually the determining design parameter for the DD DCS. Typically, an average of less than 40 s is required. As shown in Figure 5, the average waiting time with the IA is slightly greater than 40 s with 11% and 12% demand.

With these demands, the DDA pushes the average waiting time to a satisfactory level, while the DEA can provide good service quality. Thus, the proposed

elevator group should be rejected with the IA but is acceptable for the DDA and DEA. Another approach is to look for the maximum passenger demand that the elevator group can handle satisfactorily.

Based on Figure 5, the DEA can handle at least 15% (and, probably, 16%) of the population per 5 min. This indicates the DEA can handle at least 30% more population than the IA or DDA.

Conclusion

This paper introduced advanced mathematical models and algorithms for an elevator group control system, which ultimately aims to solve the lunch traffic challenge and fulfill the potential of the DD DCS. The described methods enable higher occupancies in buildings, reasonable passenger service quality in the case an elevator is out of service or further reductions in the number of elevators.

References

[1] Alexandris, N.A. “Statistical Models in Lift Systems,” Ph.D. thesis, The Victoria University of Manchester, Institute of Science and Technology (1977).
University of Manchester, Institute of Science and Technology.
[2] Barney, G. “Towards Agreed Traffic Design Definitions,” ELEVATOR WORLD, Vol. 53 (2), p. 108 (2005).
[3] Closs, G. The Computer Control of Passenger Traffic in Large Lift Systems, Ph.D. thesis, The Victoria University of Manchester, Institute of Science and Technology (1970).
[4] Fernández, J. and Cortés, P. “A Survey of Elevator Group Control Systems for Vertical Transportation: A Look at Recent Literature. IEEE Control Systems, Vol. 35 (4), p. 38-55 (2015).
[5] Fortune, J. “Modern Double-Deck Elevator Applications and Theory,” EW, Vol. 44 (8), p. 63-68 (1996).
[6] Fortune, J. “Predestination Hall Call Selection for Double-Deck Lifts (3-D Encoding).” EW, Vol. 53 (8), p. 126-133 (2005).
[7] Goldberg, D.E. Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Boston (1989).
[8] Hakonen, H. and Siikonen, M-L. “Elevator Traffic Simulation Procedure,” EW, Vol. 57 (9), p. 180-190 (2009).
[9] Hiller, B., Klug, T. and Tuchscherer, A. “An Exact Reoptimization Algorithm for the Scheduling of Elevator Groups,” Flexible Services and Manufacturing Journal, Vol. 26 (4), p. 585-608 (2014).
[10] Johnson, N., Kemp, A. and Kotz, S. Univariate Discrete Distributions, 3rd Edition, John Wiley & Sons Inc, Hoboken, New Jersey (2005).
[11] Kuusinen, J-M., Sorsa, J., Siikonen, M-L. and Ehtamo, H. “A Study on the Arrival Process of Lift Passengers in a Multi- Storey Office Building,” Building Services Engineering Research and Technology, Vol. 33 (4), p. 437-449 (2012).
[12] Kuusinen, J-M., Sorsa, J. and Siikonen, M-L. “The Elevator Trip Origin-Destination Matrix Estimation Problem,” Transportation Science, Vol. 49 (3),
p.559-576 (2015).
[13] Schröder, J. “Advanced Dispatching — Destination Hall calls + Instant Car-to-Call assignment: ‘M-10,’” EW, Vol. 38 (3), p.
40-46 (1990).
[14] Siikonen, M-L. Planning and Control Models for Elevators in High-Rise Buildings, Ph.D. thesis, Helsinki University of Technology, Systems Analysis Laboratory (1997).
[15] Sorsa, J., Siikonen, M-L. and Ehtamo, H. “Optimal Control of Double-Deck Elevator Group Using Genetic Algorithm,” International Transactions in Operational Research, Vol.10 (2), p. 103-114 (2003).
[16] Sorsa, J., Hakonen, H. and Siikonen, M-L. “Elevator Selection With Destination Control System,” EW, Vol. 54 (1), p. 148-155 (2006).
[17] Sorsa, J. and Siikonen, M-L. “Double-Deck Destination Control System,” Elevatori, Vol. 37 (5), p. 42-56 (2008).
[18] Sorsa, J. Optimization Models and Numerical Algorithms for an Elevator Group Control System, Ph.D. thesis, Aalto University School of Science, Systems Analysis Laboratory (2017).
[19] Sorsa, J., Ehtamo, H., Kuusinen, J-M., Ruokokoski, M. and Siikonen, M-L. “Modeling Uncertain Passenger Arrivals in the Elevator Dispatching Problem With Destination Control,” Optimization Letters, Vol. 12 (1), p. 171-185 (2018).
[20] Tyni, T. and Ylinen, J. “Genetic Algorithms in Elevator Car Routing Problem,” Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001),
L. Spector, et al. (Ed.), Morgan Kaufman Publishers, San Francisco, p. 1413-1422 (2001).
[21] Siikonen, M-L., Susi, T. and Hakonen, H. “Passenger Traffic Flow Simulation in Tall Buildings,” EW, Vol. 49, (8), p. 117-123 (2001).