# A Survey of Algorithms and Systems for Evacuating People in Confined Spaces
## 3 Evacuation Wayfinding Algorithms
### On-Line Evacuation Wayfinding Algorithms
#### 3.2.1 Network Flow-Based Algorithms  
Network flow-based algorithms consider the evacuation planning problem as a minimum cost network flow problem [105; 106]. Commonly, this type of algorithm first predicts the upper bound of the overall evacuation time and then converts the original building model into a time-expandednetwork by duplicating the original network for each discrete time unit. After that, linear programming or heuristic algorithms are utilised to compute the optimal evacuation plan. This type of approach can achieve the optimal solution, but normally does not take the spreading of the hazard into consideration. For instance, the work in [9] utilised a dynamic network optimisation model to minimise the overall evacuation time and prevent \"bottlenecks\" from occurring in a large building; the building was represented by a graph model composed of nodes and arcs; the capacity of a node was determined by dividing the space area of the node by the typical space occupied by an evacuee; the capacity of an arc, which was defined as the maximum number of evacuees that were allowed to traverse the arc per unit time, was determined by the passageway width; the graph model was expanded into a time-expanded network by duplicating the original graph model over \(T\) time periods, where \(T\) was determined by dividing the approximate evacuation time \(T_{e}\) by the length of a time period (10 s); to reduce the computational complexity and ensure the existence of a feasible solution, the minimum feasible building evacuation time \(T_{e}\) was determined by the proposed bisection search algorithm; the time-expanded network was solved via a large-scale dynamic transshipment algorithm from the GNET program [107]. Since the search complexity of a time-expanded graph grows exponentially with the increase of the time bound \(T\), the studies in [108; 109] developed a polynomial time algorithm to solve the evacuation problem with a fixed number of sources and exits; the evacuation problem was converted to a quickest flow problem, which aimed to send a specific amount of flows from sources to sinks in the shortest time; the building model was represented by a graph with integral transit times and capacities on the edges; the evacuees flows were represented by the temporally-repeated flows proposed in [105] rather than static flows in a time-expanded network; the quickest flow problem with multiple sources and sinks was then transferred to a lexicographic maximum dynamic flow problem and could be solved by using the algorithms presented in [110; 111]. Since linear programming algorithms that utilise time-expanded networks to calculate optimal evacuation plans can suffer from high computational cost, the work in [82; 83] proposed a heuristic-based algorithm called capacity constrained route planner (CCRP) to produce sub-optimal evacuation plans in a time-efficient manner; rather than transforming the original evacuation network into a time-expanded network, CCRP employs [PERSON]'s shortest path algorithm [112] to search only the original evacuation network and calculate the quickest routes for evacuees; CCRP first searches the route with the shortest arrival time from any source node to any destination node in terms of path length, previous reservations and possible waiting time; then it allocates evacuees to this route with respect to the capacity of the route; the CCRP algorithm will iterate the above two steps until all the evacuees reach the exits. These approaches can theoretically solve optimal routes with the shortest time to exits by avoiding congestion. However, to achieve shortest time to exit, evacuees must accurately follow the suggested paths and reach every node on schedule and may even wait a certain time at a node to avoid congestion. This is impractical in a real evacuation process. Moreover, these approaches suffer from high computational complexity because the time-expanded network will contain at least \((N+1)T\) nodes for a graph with \(N\) nodes and an upper bound of evacuation time \(T\).