A viral system algorithm to optimize the car dispatching in elevator group control systems of tall buildings

A viral system algorithm to optimize the car dispatching in elevator group control systems of tall buildings Pablo Cortés 1* , Luis Onieva 2 , Jesús Muñuzuri 3 , José Guadix 4 University of Seville, Escuela Técnica Superior de Ingeniería, Ingeniería Organización Camino de los Descubrimientos s/n, Sevilla 41092, Spain Email: 1 [email protected]s.es, (+34954486153); 2 [email protected]; 3 munu[email protected]s.es; 4 guad[email protected]s * Corresponding author Abstract.- Nowadays is very common the presence of tall buildings in the business centres of the main cities of the world. Such buildings require the installation of numerous lifts that are coordinated and managed under a unique control system. Population working in the buildings follows a similar traffic pattern generating situations of traffic congestion. The problem arises when a passenger makes a hall call wishing to travel to another floor of the building. The dispatching of the most suitable car is the optimization problem we are tackling in this paper. We develop a viral system algorithm which is based on a bio-inspired virus infection analogy to deal with it. The viral system algorithm is compared to genetic algorithms, and tabu search approaches that have proven efficiency in the vertical transportation literature. The experiments undertaken in tall buildings from 10 to 24 floors, and several car configurations from 2 to 6 cars, provide valuable results and show how viral system outperforms such soft computing algorithms. Keywords: Elevator; lift; viral system; bio-inspired algorithms; elevator group control system; vertical transportation Acknowledgments The authors acknowledge the financial support provided by the Spanish Plan for Research and Development Technology and Innovation Plan through its Programme Industrial Production and Design, project Ref. DPI2010-15352. A viral system algorithm to optimize the car dispatching in elevator group control systems of tall buildings Abstract.- Nowadays is very common the presence of tall buildings in the business centres of the main cities of the world. Such buildings require the installation of numerous lifts that are coordinated and managed under a unique control system. Population working in the buildings follows a similar traffic pattern generating situations of traffic congestion. The problem arises when a passenger makes a hall call wishing to travel to another floor of the building. The dispatching of the most suitable car is the optimization problem we are tackling in this paper. We develop a viral system algorithm which is based on a bio-inspired virus infection analogy to deal with it. The viral system algorithm is compared to genetic algorithms, and tabu search approaches that have proven efficiency in the vertical transportation literature. The experiments undertaken in tall buildings from 10 to 24 floors, and several car configurations from 2 to 6 cars, provide valuable results and show how viral system outperforms such soft computing algorithms. Keywords: Elevator; lift; viral system; bio-inspired algorithms; elevator group control system; vertical transportation 1. Introduction Transportation is a classic discipline with a long tradition in the industrial engineering research (see for example Xie and Jia, 2012; Yan et al. 2012; Yin and Kim, 2012; Keshavarz and Khorram, 2011; or Muñuzuri et al. 2010 amongst others as recent contributions). A particular case of transportation is vertical transportation which considers the vertical transportation of passengers or freight in a building through its floors. In fact, in the late years, the rapid growth of the building industry and associated technologies has been demanding parallel growth in the field of vertical transportation. The progressive price increase in the urban centres of the larger cities makes the necessary intensive ground exploitation by means of the construction of tall buildings (see figure 1 depicting an image of the Manhattan business centre). To manage with the vertical transportation system of such buildings, the installation of synchronized elevator groups in is a usual practice. Figure 1. A landscape of the upper Manhattan skyscrapers from the Empire State Building The main objective of an optimal elevator group control system (EGCS) is to provide a good quality of service to its passengers (see CIBSE Guide, 2005). The problem tackled by every EGCS is to solve the assignment process of a car of the elevator group to a hall call made by a passenger wanting to travel from a floor to other different floor in the building. When a passenger presses a landing call button of the panel in the hall, he/she expects that a car of the EGCS will arrive in a few seconds. This assignment process must be done analysing the different options and selecting the most suitable car to serve the person having issued the call. This assignment must be done optimizing the waiting times that the passenger will experiment. The most common optimization criterion (Cortés et al., 2006) for quality of service in elevator group controllers is the reduction of the average journey time (AJT) which consists of the waiting time queuing in the hall (average waiting time, AWT) plus the travel time to destination inside the car (average travel time, ATT). The average waiting time (AWT) is the actual time a prospective passenger waits after registering a hall call (or entering the waiting queue if a call has already been registered) until the responding elevator doors begin to open. Following the CIBSE Guide, for car loads less than 50%, AWT can be approximated by (1), while for car loads over 50%, it is approximated by (2) INT.AWT 40 = , for car loads < 50 % (1) INT CC P AWT      −+= 2 77.0 8.1 4.0 , for car loads > 50 % (2) Where INT is the interval (the main floor arrival average time), P is the number of passengers, and CC is the rated car capacity. The average travel time (ATT) is the time the responding elevator doors begin to open to the time the doors begin to open again at the passengers’ destination. Following the CIBSE Guide again, it is calculated as (3). Pt S t)S( S H tATT psv ⋅ + + ++= 2 1 1 2 (3) Where H is the highest reversal floor, S the expected number of stops, t v the single floor transit time (in seconds), t S the stopping time (in seconds), t P the passenger transfer time (in seconds), and L the number of cars within the elevator group. Therefore, the problem that an EGCS must tackle consists of the allocation of a car of the group to a hall call made by a passenger based on a criterion such as the AJT, and it is a NP- Hard problem that presents n k possible combinations for n floors and k lifts, and therefore it is an extreme computational complexity problem. In the recent years, research on EGCS for vertical transportation in buildings is gaining a considerable interest from the scientific community. Although mathematical approaches have been sometimes considered (see Zhang et al., 2010; Mulvaney et al., 2010; or Utgoff and Connell, 2012), advanced approaches including soft computing or artificial intelligence algorithms are prevailing to provide optimal car-call allocation for EGCS in nowadays. In this line, genetic algorithms have been widely used providing good and valuable results since a long time (Fujino et al., 1997; Cortés et al., 2004; Tyni and Ylinen, 2006) and research continues being undertaken in this field (Hirasawa et al., 2008; Bolat et al., 2010). Also, other soft computing techniques such as particle swarm optimization have been also applied (Li et al., 2007), as well as immune systems algorithms (Li et al., 2007). Tabu search has attracted less attention than genetic algorithms, although recently two algorithms based on deterministic and probabilistic approaches have been presented to deal with the problem (Bolat et al., 2011). Lastly, control systems based on fuzzy logic are being enthusiastically tried recently (Jamaludin et al., 2010; Rashid et al., 2011; or Cortés et al., 2012) too. Recently, viral systems which are a novel bio-inspired technique has been introduced in the literature devoted to applied bio-inspired algorithms (Cortés et al., 2008) providing successful applications to the Steiner problem in networks (Cortés et al., 2010), knapsack problem (Suryadi and Kartika, 2011), vehicle routing problem (Pérez-Martínez et al., 2011), or scheduling problems (Cortés et al., 2012). It is interesting to note that an application of the biological virus concept was developed by Kubota et al. (1996) as a genetic operator of a genetic algorithm applied to a self-organizing manufacturing system. Here, we have applied this novel technique to deal with the optimization of the hall call-car allocation system of the EGCS. Following the method, cells are defined as the feasible solutions that are encoded following the Cortés et al. (2004) strategy that has been widely accepted by the vertical transportation scientific community. In addition, we follow the Bolat et al. (2011) methodology to make a quick evaluation of the cell fitness. The remaining of the paper deals with the presentation of the problem and the adaptation of the viral system algorithm to solve the car-call allocation optimization in EGCS, which is shown in section 2. Then in section 3, experimental results are provided for tall buildings from 10 to 24 floors, and several car configurations from 2 to 6 cars. Finally, the main conclusions are drawn in the final section. 2. The viral system approach to optimize the elevator group control system The elevator group control system of a building includes a set of microchips in controllers to determine which car of the group should serve each hall call. When passengers arrive to the hall of the building and press an up or down button the EGCS must assign a car of the group to such call. Passengers arrive to a building following specific traffic patterns. Four main patterns are traditionally catalogued (see CIBSE Guide, 2005 and Benmakhlouf and Khatorfor, 1993 amongst others). Figure 2 shows usual patterns in an office building. Uppeak traffic characterizes a larger than average number of up landing calls; it typically appears when workers arrive to the building in the early morning to start their working day. Downpeak traffic characterizes a larger than average number of down landing calls; it takes place when the workers leave the building to go back home. A lunchpeak traffic pattern takes place in the middle of the day, and it is due to the appearance of up and down peaks; it appears usually for lunching at midday. Finally interfloor traffic corresponds to the rest of the day; this pattern is characterized for a low demand (usually around a 4% of the population) in both directions. Figure 2. Traffic pattern in an office building This section presents an algorithm that assigns the most suitable car to a hall call made by a passenger arriving to the hall of a building. The next subsections show the solution encoding (cell genome in terms of the viral system); the evaluation of the solution (that is, the fitness evaluation of such genome when infected by a virus); and the details of the viral system implementation. 2.1. Cell genome definition The possible solutions for the allocation of a hall call to a car are encoded according to binary array (see Cortés et al., 2004 for a first proposal). So, one array is associated to each car in the elevator group, and is defined by representing the up and down calls at each floor that are assigned to this specific car. So the length of each array is equal to 2×(Number_of_Floors-1). So, the first Number_of_Floors-1 integers correspond to the hall calls in the upward direction from the ground floor to the highest floor. The second Number_of_Floors-1 integers correspond to the hall calls in the downward direction from the highest floor to the ground floor. Figure 3 depicts the solution encoding. The array holds the information referring to the hall calls by means of a binary codification. A bit 0 indicates no hall call at that floor, and a bit 1 indicates an existing hall call at that floor. Figure 3. Solution encoding for a twelve story building corresponding to one car of the group and its associated physical button box 2.2. Evaluation of the cell fitness Each possible car-hall call allocation (cell) is evaluated following the methodology described in Bolat et al. (2011), which has been proved to be an easy-to-implement and fast-to-compute technique. Moving up traffic Moving down traffic uppeak downpeak lunchpeak lunchpeak Time Traffic volume Traffic volume So, given the following parameters: - L 1 : ground floor level - L 2 : highest down hall call level - L 3 : number of down hall calls between L 1 and L 2 . - L 4 : highest up hall call level - L 5 : number of up hall calls between L 1 and L 4 . - L 6 : lowest down hall call level - t: door opening and closing time - t p : passenger transfer time - Hct: Highest car trip time - Lct: lowest car trip time The cell fitness, f, is calculated depending on the type of passengers’ movements. So, a fitness value is firstly calculated for each car, i, in the group taking into account the three different cases of table 1. Each formula relates in which floor the passenger is taken and in which floor the passenger is transferred. So, as a general definition for L, it shows the floors where passengers are get on and off. In case of no hall calls f i = 0. Table 1. Fitness evaluation as function of the traffic pattern in the building Uppeak traffic pattern Downpeak traffic pattern Lunchpeak or interfloor traffic patterns f i = t(L 4 -L 1 ) + t p (L 5 -L 1 ) f i = t(L 2 -L 1 ) + t p (L 3 -L 1 ) f i = t(L 4 -L 1 ) + t(L 2 -L 4 ) + t(L 2 -L 6 ) + t p (L 3 +L 5 -L 1 ) Finally the group fitness evaluation is given by (4), and the final fitness is evaluated for the proposed assignment and given in (5). Parameters k 1 and k 2 are chosen equal to 1.5 and 2 following the recommendations given in Bolat et al. (2011). 1 being the number of cars in the group n i i group f f , n n = = ∑ (4) ( ) 1 2group f k · f k · Hct Lct = + − (5) 2.3. Viral system algorithm A viral system algorithm (VS) is inspired in the virus behaviour. Viruses are intracellular parasites shaped by nucleic acids, such as DNA or RNA, and proteins. The protein generates a capsule, called a capsid, where the nucleic acid is located. The capsid plus the nucleic acid shape the nucleus-capsid, defining the virus. Although there are many different types of viruses developing with different behaviours when infected cells, here we follow the specific case of phages. A phage is any one of a number of viruses that infect bacteria. They do this by injecting genetic material, which they carry enclosed in an outer protein capsid. One of the main characteristics of phages is the replication mechanism which follows a lytic replication process. A lytic replication process follows the next steps: (i) the virus is adhered to the border of the bacterium. After that, the virus penetrates the border being injected inside this one; (ii) the infected cell stops the production of its proteins, beginning to produce the phage proteins, starting to replicate copies of the virus nucleus-capsids; and (iii) after replicating a number of nucleus-capsids, the bacterium border is broken, and new viruses are released, which can infect near cells. As an alternative to lytic replication, some viruses are capable of lodging in cells giving rise to the lysogenic replication. A lysogenic replication follows the next steps: (i) the virus infects the host cell, being lodged in its genome, where a pro-phage (mutation) can arise; (ii) the virus remains hidden inside the cell during a while until it is activated; and (iii) the replication of cells altered, with proteins from the virus, starts. So, lysogenic replication produces the genome alteration of the cell leading to a procedure similar to a mutation process. On the other hand, phages have the property of leading an antigenic response in the infected organism. In these situations an immune response is originated causing the creation of antibodies. So, in such case the infection is stopped for that cell. So in computational terms, VS follows an exploration process that combines lytic replication to search the neighbourhood of the existing solutions together with a mutation process, including some randomness due to the probability of developing antibodies. VS has proved effectiveness for massive and selective infections (Cortés et al., 2008; Cortés et al., 2010). However, here we opted for a selective infection due to its lighter computational load required by a real time problem as the EGCS. Furthermore, here we have developed the evolution of a virus through the organism instead of a population of virus trying to make faster the computation of the algorithm too. Once a selective infection takes place and viruses are liberated inside the organism, the virus selects a cell with a low value of fitness, f(x), in the neighbourhood. This infected cell is stored in the clinical picture (accordingly with viral system notation). The clinical picture includes the encoding of the solution that is being explored (the genome of the cell that is infected, in biological terms) and the number of nucleus-capsids being replicated, NR, (for lytic replications) or the number of hidden generations, IT, (for lysogenic replications). Thus the state of each virus is given by the three-tuple “cell genome-NR-IT”. Every cell infected by a virus develops a lytic or a lysogenic replication according to a probability p lt (for lytic replication) or p lg otherwise, where p lt + p lg = 1. In case of lysogenic replications, the activation of the mutation process takes place after a limit of iterations has been reached (LIT). The value of LIT depends on the cell’s health conditions, so a healthy cell (high value of the objective function being minimised, f(x)) will have a low infection probability, i.e. the value of LIT will be higher. An unhealthy cell, on the contrary, will have a lower value of LIT. See Cortés et al. (2008) for adjusting the value of LIT. In case of lytic replications, a number of virus replications (NR) is calculated for each iteration as a function of a binomial variable, Z, adding its value to the current NR in the clinical picture. Z is calculated using a Binomial distribution given by the maximum level of nucleus-capsids replicated, LNR, and the single probability of one replication, p r . So, Z = Bin (LNR , p r ). LNR represents the limit to break the cell border and to release the lodged viruses. As in the lysogenic cycle, the value of LNR is set depending on the value of the objective function being minimised, f(x). Thus cells with higher f(x) have lower probability of getting infected, and therefore the value of LNR will be higher. See Cortés et al. (2008) for adjusting the value of LNR. However, the virus will not be able to infect those cells that have developed antigens. Given p an (x) the probability of generating antibodies for a cell x, the antibody response is defined by the random variable A(x) as a Bernoulli: A(x) = Ber (p an (x)). If cell x generates antibodies, the cell is not infected, but starts a lysogenic process. Higher values of f(x) imply healthy cells and therefore cells that have a higher probability of developing antigenic responses. On the contrary, cells with low value of f(x) imply unhealthy cells with lower probability of developing antigenic responses. This effect is represented by an hypergeometric function, where the cell with an inverse objective function evaluation, 1/f(x), in ranking position-i, has a probability of generating antibodies, p an (x), that is given by q(1-q) i , with q equal to the probability of generating antibodies for the worst healthy cell. Finally, a residual probability remains, which is added to the worst cell. Figure 4 defines the algorithm evolution for the lytic replication. The initial state is on the lefthand side: the virus process starts with the virus breaking the border and starting the infection of new cells in its neighbourhood. The virus selects the most promising cell, which is the least healthy cell. The Organism process is characterized by the probability of antigenic response in the least healthy cell. Those cells developing antibodies are not infected. Finally, the right hand side of the figure defines the new clinical picture, with new infected cells lodging viruses. The cells generating antibodies follow a new lysogenic replication in order to gain computational efficiency. Figure 4. Viral system lytic replication evolution concept The flowchart of the algorithm is presented in figure 5. Cell genome NR IT Lytic replication virus DNA Bacterium DNA V(x) Virus Lowest healthy cell without antigenic response (infected cell) Lowest healthy cell with antigenic response (non-infected cell) Healthy cell (non-infected cell) Clinical picture Genome of new cell NR IT Option 1 Non-antigenic response Option 2 Antigenic response Lysogenic replication Mutation Figure 5. Viral system flowchart 3. Experimental results The experimentation was carried out using an Intel Pentium M Processor 740 at 1.73 GHz with 2 GB RAM, and algorithms were encoded using software Matlab version 7.0. Tests were carried out for tall buildings from 10 to 24 floors at 3.3 metres of distance. We also considered different car configurations for the EGCS: 2, 3, 4 and 6 cars. Table 2 gives the main specifications of the building and elevators respectively. Total time of a car stopping is given by t s = t open +t close +t p, where t open is the time for opening door, t close is the time for closing door, and t p is the time for passenger transfer. Parameters of the viral system algorithm were calibrated to the following values (table 3) after testing and trying with different combinations. The algorithm was 10,000 times iterated. Define type of replication: p lt : lytic replication / p lg : lysogenic replication Lytic replicationLysogenic replication Infected cell replicates nucleus-capsids NR i ≥ LNR i , for iinfected cell Neighbourhood search: identify lowest healthy cell NO YES Develops antigenic response? YES Store value Best solution? YES NO NO IT i ≥ LIT i , for i infected cell Mutate cell genome encoding NO IT i = IT i + 1, for iinfected cell YES New cell infected by virus New cell infected by virus Store value YES Best solution? NO Update NR parameter for infected cell Initiate: inoculate a virus in a randomly selected cell Yan, S., Wang, S-S., Wu, M-W., 2012. A model with a solution algorithm for the cash transportation vehicle routing and scheduling problem. Computers & Industrial Engineering, 63(2), 464-473. Yin, M., Kim, K.H., 2012. Quantity discount pricing for container transportation services by shipping lines. Computers & Industrial Engineering, 63(1), 313-322. Zhang, Y., Fan, Z-P., Liu, Y., 2010. A method based on stochastic dominance degrees for stochastic multiple criteria decision making. Computers & Industrial Engineering, 58(4), 544- 552.