# A Survey of Algorithms and Systems for Evacuating People in Confined Spaces
## 3 Evacuation Wayfinding Algorithms
### On-Line Evacuation Wayfinding Algorithms
#### 3.2.3 Queueing Model-Based Algorithms  
Owing to the stochastic, highly transient and nonlinear nature of an evacuation process, queueing models have been proven as a useful tool to capture and analyse the dynamics of evacuees [116]. Normally, by treating significant locations such as doorways or staircases as \"servers\", queueing model-based approaches [117], which generalise the Markovian models of computer systems [118], transfer building graphs to a queueing network or a number of isolated \"queues\" to estimate congestion and evacuation delays. For instance, the process of pedestrians traversing a corridor or stairwell was analysed as a state-dependent process in [86]; a \(M/G/C/C\) state-dependent queue model was utilised to estimate the congestion delays at corridors or stairwells and the overall evacuation time of an evacuation process; the pedestrian flows were classified into three categories: uni-directional flow, bi-directional flow and multi-directional flow; the relationship between the crowd density and the mean walking velocity of evacuees in the three categories of pedestrian flows were derived from [119]; the capacity of a corridor or stairwell was calculated based on [120], which indicated that the evacuee flow would cease to move when the population density reached five evacuees per square meter; the state-dependent service rate of the three categories of pedestrian flows can be calculated in terms of the mean walking speed and the corridor capacity; finally, the time cost for an evacuee flow to traverse a corridor or a stairwell can be computed by the mean value analysis (MVA) algorithm introduced in [121]. To ensure no corridors would be blocked during an evacuation process in a built environment, the work in [87] considered the evacuation planning problem as a service and capacity allocation (SCA) problem and searched for the smallest capacity of each corridor via modelling the building as a \(M/G/c/c\) queueing network; the \(M/G/c/c\) queueing network was employed to calculate the average queue length at each corridor with the following steps: (1) the average walking speed \(V_{n}\) of \(n\) evacuees in a corridor was calculated by the equations derived from the congestion model proposed in [122]; (2) the state-dependent service rate \(f(n)\) with \(n\) evacuees in a corridor could be computed by \(f(n)=\frac{V_{n}}{V_{1}}\), where \(V_{1}\) is the average speed of a lone evacuee; (3) term \(p_{n}\), which is the probability of \(n\) evacuees in a corridor, could be calculated by the equations derived from [123]; (4) the average queue length of a corridor could then be computed by \(L=\sum_{n=1}^{c}np_{n}\); to analyse the smallest capacity of each individual corridor, the generalised expansion method [124; 125] was used to expand the \(M/G/c/c\) queueing network into an equivalent Jackson network via adding an artificial holding node in front of each finite queue to register the blocked evacuees due to capacity limitation; After decomposing the queueing network, a local search algorithm inspired by [126] was used to search for the smallest feasible capacity of each queue. Similarly, the studies in [89; 127] utilised a \(M/G/c/c\) queue model to simulate the dynamics and predict the overall evacuation time of an egress process without hazard; rooms, corridors and stairways were modelled as queues in which the service rate depended on the evacuee density; doors, exits and gateways were imitated as queues in which the service rate depended on not only the evacuee density, but also the faster-is-slower effect [36] and the crowd impatience [128]; to validate the effectiveness of the queue system, a discrete-event simulation model was implemented via the SimEvents toolbox in the MATLAB/Simulink environment, and experimental results showed that the egress time of evacuees in simulations highly matched with the prediction of the proposed queueing model.