# 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
Rather than simulating all the building components as \(M/G/c/c\) queues, the research in [129] modelled doorways that can pass one person at a time as \(M/M/1\) queues; on the other hand, corridors or stairs were modelled as \(M/G/\infty\) queues, in which the infinite number of servers implied that no congestion occurred in corridors or stairs. Rather than using traditional closed network models that suffer from high computational costs, the study in [90] proposed a computationally-efficient open network model with product form to predict the congestion level at each point of interest (PoI) and the overall evacuation time with respect to average arrival and departure rates at each observation point; by assuming Poisson arrivals of evacuees at each originating location, uni-directional corridors that allowed at most one evacuee to pass at a time and exponentially traversal delays at each corridor, a \(M/M/1\) queue model was established to mimic each corridor; hence, the average delay at a corridor could be calculated by \(\frac{1}{\mu-\lambda}\), where \(\frac{1}{\mu}\) represents the average traversal time of a corridor and \(\lambda\) represents the average arrival rate of evacuees at a corridor; the average traversal time of a path can be calculated by summing the average delay of each corridor on it. Rather than considering each significant location (such as a doorway or staircase) as an independent \"queue\" and then using either the limiting probabilities for the number of customers in an M/G/C/C state-dependent queueing model [130] or steady-state solutions [90] to analyse the number of evacuees at the location, the work in [91] treated all the significant locations in the designated area as a \"queueing network\" by considering the interaction effects of various evacuees among linked \"queues\"; in this study, to predict the time cost \(T\) for an evacuee to traverse a path, a G-network model [131] was employed to compute the utilisation rate of each node and edge periodically under the combined impact of a specific routing scheme and panic behaviours; [PERSON]'s formula was then used to calculate the average delay of each node and edge; finally, \(T\) can be calculated by summing the average latency of each node and edge on it. The research in [92] proposed an urban-scale evacuation wayfinding system to guide vehicles to safe zones in the aftermath of a disaster in a latency- and energy-efficient manner; a G-network model [132] was utilised to analyse and capture the dynamics of vehicles under the joint influence of interactions among individual vehicles and the re-routing decisions from the navigation system; by using this G-network model, the average number of vehicles and the average traversal time at each intersection or road segment could be calculated; hence, the total average delay experienced by a vehicle and the total fuel consumption in the network could be described by a goal function; finally, a gradient descent algorithm was utilised to reduce the time and fuel cost (minimise the goal function) by optimising the probabilistic choices of linked road segments at each intersection.