Multi-Exit Dynamic Assignment Problem in Crowd Evacuation

Problem Description: During emergencies in large public spaces (such as stadiums, subway stations), crowds need to evacuate through multiple exits. The multi-exit dynamic assignment problem studies how to dynamically guide people to different exits based on real-time changes in the distribution of the evacuating crowd, exit capacities, and path congestion, with the goal of minimizing the overall evacuation time and preventing some exits from becoming overcrowded while others remain underutilized.

Core Challenges: Uneven crowd distribution, individuals' blind choices of exits, delays in obtaining and feeding back real-time information.

Detailed Problem-Solving Process:

Step 1: Problem Modeling – Translating the Physical Scenario into a Mathematical Model

1. Environment Discretization: Divide the evacuation area into small grids (e.g., 1m × 1m), where each grid can only be occupied by one person at a given moment. This is analogous to converting continuous space into discrete cells that a computer can process.
2. Defining Key Parameters:
   • Crowd Density Distribution (ρ(x, y, t)): The number of people per unit area around position (x, y) at time t. This changes dynamically.
   • Exit Capacity (C_i): The maximum number of people that exit i can pass per unit time (people/second). This is determined by the physical width of the exit (typically calculated as 0.5 meters per person).
   • Path Travel Time (T_j): The estimated time for an individual j to reach a specific exit i from their current location, which depends on the path length and the congestion level along the path.
3. Establishing the Objective Function: Our goal is to minimize the total evacuation time (T_total), i.e., the time when the last person leaves the venue. Mathematically, this is equivalent to balancing the utilization of all exits over time as much as possible to avoid creating "bottlenecks."

Step 2: Static Optimal Assignment – The Benchmark Under Ideal Conditions
At the start of the evacuation, if we knew the precise locations of all individuals and assumed constant movement speeds and no congestion during the evacuation, we could calculate a theoretical optimal assignment. This is typically achieved by solving a transportation problem:

• Idea: Treat the "crowd" as "goods" to be transported and the "exits" as "destinations." Each exit has a maximum capacity (capacity × time). The objective is to assign all people with the minimum total "transportation cost" (which could be total walking distance or time).
• Method: Use linear programming or network flow algorithms. For example, construct a cost matrix where each element represents the cost (e.g., distance) of assigning a person from a specific location to a specific exit, then solve it.
• Limitations: This is only a static, idealized starting point. In reality, the crowd is moving, and congestion occurs, so we need a dynamic strategy.

Step 3: The Core of Dynamic Assignment Strategy – Real-Time Feedback and Adjustment
The core of dynamic assignment is that the system (or guidance signage) can adjust guidance strategies based on real-time conditions. There are two main approaches:

1. Centralized Assignment Based on Global Information:

   • How it works: Real-time monitoring of crowd density and movement speed across the entire area via cameras and sensor networks. A central computer recalculates the optimal assignment every few seconds based on this data, then updates guidance directions via variable message signs (e.g., electronic indicators).
   • Key Technologies: Real-time data fusion, fast path planning algorithms (e.g., variants of Dijkstra's algorithm that account for congestion costs).
   • Example: The system detects severe congestion ahead of Exit A while the path to Exit B is relatively clear. It immediately changes some signs originally pointing to Exit A to point to Exit B.

2. Distributed Guidance Based on Local Rules:

   • How it works: Does not rely on a central system. Instead, intelligent local guidance signs are set up, allowing individuals to make choices beneficial to the whole based on local information. This is more robust (fault-tolerant).
   • Common Rules:
     • Shortest Estimated Time Principle: Signs not only show direction but also dynamically display the "estimated time" to each exit. People naturally choose the exit with the shortest time.
     • Congestion Avoidance Rule: When the density in a certain direction exceeds a safety threshold, the directional arrow for that path turns red or closes, forcing guidance to other directions.

Step 4: Algorithm Implementation – Example of Centralized Dynamic Assignment
A simplified algorithm flow is as follows:

1. Data Input: Obtain real-time crowd density ρ and average movement speed v for each grid cell (v decreases when congested).
2. Cost Map Update: Generate a "cost map" for each exit i. The cost value for each cell on the map is no longer the geometric distance to the exit but the estimated travel time. Estimated time = distance / current average speed along the path. The average speed along the path needs to be estimated based on the real-time density on that path (e.g., using an empirical formula: speed v is a function of density ρ; the higher ρ, the lower v).
3. Assignment Calculation: For each person (or group) in the area, the system calculates their estimated time to each exit. The goal is to assign each person to an exit so that the estimated maximum completion times for all exits are as close as possible. This can be achieved through an iterative algorithm:
   a. Initial Assignment: Assign based on the shortest estimated time.
   b. Check Balance: Calculate the "load" for each exit (total number of people assigned to that exit divided by its capacity, yielding an estimated completion time).
   c. Adjustment: Find the most heavily loaded exit A and the most lightly loaded exit B. Reassign some people originally assigned to A but relatively closer to B, to B.
   d. Repeat steps b and c until the loads (estimated completion times) of all exits are roughly balanced.
4. Instruction Issuance: Convert the new assignment plan into guidance instructions and update the electronic signs on-site.

Step 5: Considering Human Behavioral Factors – Making the Model More Realistic
A purely mathematical optimal solution may fail due to human behavior, so the following must be considered:

• Familiarity Preference: People tend to choose familiar exits (e.g., the entrance) even if the system suggests other paths. Strategy: Use very clear, strong signals (e.g., flashing lights, voice broadcasts) for guidance.
• Herd Mentality: People follow the movement of the majority. Strategy: Early intervention is crucial, diverting flow before congestion forms.
• Information Credibility: If the guidance system has made errors before, people will distrust it. Strategy: The system must be reliable, with clear and consistent information.

Summary:
Solving the multi-exit dynamic assignment problem is a progressive process from static modeling to dynamic feedback and then to behavioral correction. The key lies in establishing a closed loop capable of perceiving the environment (real-time data) -> analyzing and deciding (optimization algorithms) -> executing interventions (guidance system), while fully considering the complexity of real human behavior throughout this process to design efficient and safe evacuation plans.