1. Introduction

1.1 Background

With rapid urbanization and increasing population density, subway systems have become a cornerstone of modern metropolitan transportation networks. In major cities around the world, subways offer high-capacity, high-frequency service that alleviates surface congestion and enables economic and social mobility. As subway systems grow larger and more complex, the risk of emergencies—like fires, power outages, and overcrowding—also increases.

Recent decades have witnessed a rise in subway accidents, drawing attention to the urgent need for reliable evacuation strategies. For instance, the 2014 Moscow Metro derailment caused 24 deaths and over 160 injuries due to delays and confusion in evacuation response (Walker, 2014). Similarly, the 2003 Daegu subway fire in South Korea resulted in 192 fatalities, largely exacerbated by smoke spread and insufficient evacuation coordination (Yoon, 2023). These incidents underscore the critical need to optimize emergency planning for large-scale, confined transit environments.

This study proposes a novel optimization strategy for subway evacuation based on graph-theoretic modeling. We model station layouts as graphs with dynamic edge properties to analyze routing strategies that balance individual efficiency and system-wide flow.

1.2 Related Research

Evacuation modeling in metro environments has garnered extensive attention across multiple disciplines including transportation engineering, operations research, and computational simulation. Numerous efforts have sought to model pedestrian behavior, assess building bottlenecks, and optimize evacuation outcomes under emergency conditions.

Chalmet et al. (1982) proposed one of the earliest applications of network optimization for building evacuation, laying the foundation for graph-based evacuation models. However, such early models largely assumed deterministic travel times and ideal path choices without accounting for pedestrian interaction or density effects. In more recent work, Yang et al. (2022) introduced a stochastic user equilibrium model built upon the social force paradigm, emphasizing the influence of congestion and interaction forces on path selection.

Another recent contribution by Guo and Zhang (2022) employed a hybrid simulation-optimization approach combining Random Forest and NSGA-III to explore multi-objective evacuation planning. While their model improves decision-making under complex multi-factorial conditions, it relies heavily on offline optimization and does not explicitly address real-time pedestrian redirection or path redundancy. Similarly, Hassanpour et al. (2022) focused on agent-based simulation for subway evacuations but lacked formal optimization logic. Zhang et al. (2024) addressed network vulnerability rather than route assignment.

Despite the diversity in modeling paradigms and algorithms, a common limitation in much of the existing literature is the reliance on either shortest path heuristics or static route preferences, which tend to exacerbate congestion near popular exits. The potential for route redundancy and flow imbalance is rarely addressed with explicit algorithms. In response to these research gaps, our work contributes a pair of graph-theoretic algorithms tailored to subway station evacuation, addressing both individual movement efficiency and system-wide flow balance through scalable, algorithmic constructs.

2. Methodology

2.1 Network Model Construction

To abstract the spatial configuration of a subway station, we convert architectural blueprints into a directed graph G(V,E). Nodes V represent crucial locations like boarding areas, exits, junctions, and stairways. Edges V represent walkable paths, annotated with physical attributes like length, width, and directionality.

Each node includes:

• Cross-sectional width

• Node type (platform, stair, corridor, etc.)

• Each edge includes:

• Length (meters)

• Derived cost, computed as:

Cost=lengthspeed×min_width

2.2 Algorithms design

We develop two algorithms to simulate evacuation behavior under distinct routing strategies. Each strategy provides a rule set for assigning pedestrians from boarding points (sources) to exits (targets), based on the underlying graph model described in Section 2.1. The primary objective is to either minimize travel cost or distribute flow to avoid bottlenecks. The procedures for both strategies are formalized in Algorithms 1 and 2.

2.2.1 Evacuation Strategy 1: Shortest Path Routing

The first strategy assigns each passenger group to the shortest available route, where path cost is defined as a function of edge length, pedestrian speed, and cross-sectional width. Since the cost function has already been introduced in Section 2.1, it is directly embedded in the route computation logic here, as Algorithm 1 depicted.

Algorithm 1

Shortest Path Routing Strategy

This design extends traditional shortest-path models by integrating physical constraints and walking dynamics into edge weights. Unlike approaches based solely on distance, our method penalizes narrow and slow routes, better capturing movement efficiency in complex underground settings. Cost values are precomputed and stored on each edge, allowing the algorithm to find routes with the lowest cumulative cost.

Shortest-path navigation reflects intuitive decision-making and is widely used in evacuation modeling as a behavioral baseline. However, this strategy optimizes routes individually and does not account for system-wide flow balance. Under high-density conditions, this can lead to crowding and bottlenecks, highlighting the need for more balanced routing alternatives discussed in the following section.

2.2.2 Evacuation Strategy 2: Greedy Disjoint Path Routing (GDPR)

To mitigate the convergence issues of shortest-path-based routing, we introduce a greedy algorithm that incrementally constructs multiple disjoint evacuation paths between each source and target. As shown in Algorithm 2, each iteration computes the shortest remaining path and subsequently removes its intermediate nodes from the working graph, ensuring that subsequent paths do not overlap.

Algorithm 2

Greedy Disjoint Path Routing Strategy

This method encourages the use of alternative corridors and less obvious exits, resulting in a broader dispersion of pedestrian traffic. Though the resulting paths may not be individually optimal in terms of travel time or cost, the overall system benefits from reduced congestion and more balanced exit utilization.

This algorithm also introduces a tunable parameter k, which controls the number of disjoint paths generated per source-target pair. In practical applications, the parameter can be adjusted based on evacuation goals and infrastructure capacity. The method reduces redundancy by generating multiple disjoint paths, enhancing distribution and minimizing congestion at key bottlenecks.

3. Case Study: Seoul Guryong Station

3.1 Setup

Guryong Station is a multi-level underground station in Seoul, Korea, consisting of six layers. The fourth level houses mechanical systems and is excluded from evacuation. The fifth floor, which includes both platforms and concourses, connects to other levels via elevators, escalators, and staircases.

Following the methods described in Section 2, we constructed the network model for this station using its architectural blueprints. The resulting graph contains a total of 154 nodes, which include boarding points, junctions, corridors, stairways, and 6 designated exit nodes. There are 264 edges representing the walkable paths between these nodes. The full topological representation of this network model is illustrated in Figure 1.

Figure 1.

Subway station network graph

To visualize and evaluate the effectiveness of the proposed evacuation strategies, we constructed a detailed simulation model using AnyLogic 8.7 PLE version, as Figure 2 depicted. This simulation environment enables real-time analysis of pedestrian dynamics and bottleneck formations. Walking behavior in the simulation was modeled with realistic pedestrian parameters. The average walking speed was set to 1.34 m/s, reflecting typical adult movement in emergency conditions. Stair traversal speed was reduced to account for slope and physical effort, while crowd interaction effects such as queuing and local avoidance were included using built-in agent-based movement logic. These configurations were applied uniformly across both strategies to ensure that differences in evacuation performance stemmed solely from routing behavior.

Figure 2.

Guryong station simulation model

3.2 Simulation and results discussion

In the simulation phase, a total of 82 pedestrian source points were configured on the platform level, each representing a train door position. For the shortest path strategy, pedestrian logic was relatively centralized: only four pedestrian flows were created, all terminating at exit E2_1. In contrast, the GDPR strategy generated a broader variety of pedestrian movements. Specifically, it produced 56 unique pedestrian flows targeting all six available exits. This more diversified routing design helps alleviate crowd concentration and enhances global station throughput.

The distribution of starting routes per exit under the GDPR strategy is shown in Figure 3. It reveals that exit E2_1 received the highest number of routes (17), while exit E1 received the fewest (9). The remaining exits—E2_2, E3, E4_1, and E4_2—were assigned between 13 and 15 routes each. Although the route allocation is not perfectly balanced, the relatively even spread of origin points across exits reflects the strategy’s success in minimizing path repetition. This not only distributes crowd flow more equitably but also reduces the likelihood of severe congestion at any single exit. Further analysis in the following sections will evaluate how these differences translate into evacuation efficiency.

Figure 3.

Exit usage frequency statistics

Pedestrian flow intensity, expressed in pedestrians per hour per meter (ped/h/m), is a critical metric for evaluating localized congestion and the effectiveness of evacuation strategies. Following the preceding discussion on route allocation, Figures 4 present a comparative analysis of flow intensity over time for each exit under the two routing approaches. The GDPR shows a relatively balanced and moderate flow distribution across all six exits, with peak intensities ranging between 40 and 80 ped/h/m. This indicates that the strategy effectively spreads crowd movement, preventing any single exit from being overwhelmed.

In contrast, Figure 4(a) shows the pedestrian flow at exit E2_1 under the shortest path strategy. Here, the peak flow exceeds 270 ped/h/m, significantly higher than any exit under the greedy strategy.

Figure 4.

Pedestrian flow

To further evaluate the performance of the two routing strategies, evacuation time was used as a key comparative metric. Figure 5 summarizes the results of twenty simulation runs conducted for each strategy, capturing both average performance and variability. The boxplot reveals a clear distinction: the GDPR strategy consistently achieves lower and more stable evacuation times, with values concentrated around 5.18 minutes. In contrast, the Shortest Path strategy exhibits not only a higher average evacuation time, approximately 5.6 minutes, but also greater dispersion across runs. These results reinforce that by balancing route assignments, the Greedy strategy reduces bottlenecks and improves system-level evacuation efficiency.

Figure 5.

Evacuation time comparison

The comparison of the two strategies highlights key differences in route allocation and flow patterns. While the shortest path strategy minimizes individual travel cost, it tends to concentrate evacuees at nearby exits, especially those near stairs or escalators. This is evident in Figure 4(a), where flow at exit E2_1 peaks at around 275 ped/h/m and sustains that level for nearly 40 seconds, indicating significant localized congestion. In contrast, Figure 4(b) shows that flows in GDPR across all six exits stays between 40 and 80 ped/h/m, with peak durations around 20 seconds. This suggests improved load balancing and reduced pressure on any single exit.

Furthermore, the total evacuation time comparison presented in Figure 5 quantitatively affirms this advantage. The average evacuation time under the Greedy strategy is approximately 5.18 minutes, compared to 5.66 minutes for the shortest path approach—yielding a time saving of nearly 0.5 minutes, or roughly 10% of the total evacuation duration. This improvement is highly relevant in time-critical emergency contexts, especially considering that many subway safety guidelines identify a 6-minute threshold as the maximum safe evacuation window during fire or smoke events. Given the rapid development of hazardous conditions in enclosed underground spaces, even small reductions in evacuation time can substantially increase the likelihood of passengers escaping safely.

Therefore, the GDPR strategy enhances system-level resilience by better accommodating spatial constraints and uneven crowd distributions. By achieving a faster and more balanced evacuation, it provides a clear advantage for real-world disaster preparedness and emergency response planning.

4. Conclusion

This study proposed a graph-theoretic framework for optimizing pedestrian evacuation in subway stations, integrating realistic spatial attributes and behavioral considerations. Two distinct routing strategies were developed: a cost-aware shortest path algorithm, and a greedy disjoint path method aimed at flow dispersion. By constructing a detailed network model of Guryong Station and validating with simulation, we demonstrated that the GDPR significantly outperformed the conventional shortest path strategy in terms of exit utilization, congestion mitigation, and overall evacuation time. These results underscore the importance of accounting for both individual mobility efficiency and collective flow balance in evacuation planning. The proposed methodology provides valuable insights for metro infrastructure design and emergency preparedness, offering a replicable approach adaptable to other complex transit systems.