Case Study 1: Improved 3D Dijkstra’s Algorithm for Urban Flood Evacuation

Zhu et al. (2022) introduced an enhanced version of Dijkstra’s algorithm tailored for urban flood evacuation planning. Their approach incorporated three-dimensional factors such as road slope, width, and pedestrian density into the pathfinding process. By doing so, the algorithm could more accurately reflect real-world conditions, leading to more practical evacuation routes.

The study demonstrated that this improved algorithm significantly reduced evacuation times compared to traditional methods. For instance, in Meishan Town, the optimized routes led to a 17.78% increase in evacuation efficiency under a once-in-100-year flood scenario. This underscores the importance of integrating environmental and infrastructural variables into pathfinding algorithms for more effective evacuation planning.

Case Study 2: Real-Time Heuristic Evacuation Pathfinding Algorithm (RHEPFA)

A study presented a Real-Time Heuristic Evacuation Pathfinding Algorithm (RHEPFA) designed to dynamically adapt to evolving flood conditions. By integrating real-time flood forecasting data, RHEPFA could adjust evacuation routes on the fly, ensuring that evacuees avoided newly flooded areas.

Compared to traditional algorithms like Dijkstra’s and Ant Colony Optimization, RHEPFA improved the accessibility of flood protection paths by a factor of five and maintained over 90% path availability in rural flooded areas. This adaptability is crucial in flood scenarios where conditions can change rapidly, necessitating flexible and responsive evacuation strategies (Liu et al. 2022).

Data Collection

Most spatial datasets were obtained through public sources, primarily Cook County’s open data portal, as well as FEMA’s National Flood Hazard Layer and the Illinois State Flood Maps project (Cook County Government, 2024; Illinois State Water Survey; Federal Emergency Management Agency).

These included:

• Street centerlines from Cook Central’s “Streets” shapefile.

• Parcel boundaries and land use data.

• Building footprints, using the 2008 Cook County dataset.

• Flood zone polygons, accessed through FEMA’s NFHL MapServer REST service.

• Points of interest, including fire stations, schools, hospitals, and job sites.

• Municipal boundaries, clipped to the Franklin Park limits.

Each dataset was downloaded in Shapefile format and accompanied by relevant metadata to ensure spatial and semantic consistency.

GIS Preprocessing in QGIS

QGIS (QGIS Development Team, 2025) was used as the primary tool for spatial processing, visualization, and manual feature selection. Its intuitive interface and powerful geoprocessing toolkit allowed for the following:

• Clipping: All spatial layers were clipped to the Franklin Park municipal boundary to eliminate unnecessary data and focus the model scope.

• Reprojection: Each shapefile was standardized to a common Coordinate Reference System (CRS) to avoid misalignment across layers.

• Geometry Repair: Invalid geometries were fixed using the built-in “Fix Geometries” tool to enable clean simulation and map rendering.

To supplement QGIS operations, a series of custom Python scripts were developed using GeoPandas and Shapely. For example, the Floods_to_streets.py script handled:

• Reprojecting FEMA flood data to match the street network CRS.

• Unifying the street geometry to define a convex boundary for Franklin Park.

• Clipping flood layers precisely to this boundary.

• Ensuring that flood zones were strictly contained within the modeled area.

These scripts provided finer control over polygon clipping and boundary enforcement than QGIS alone, especially for overlay operations involving street and flood data.

Manual Layer Construction

In addition to automated processing, some key layers were created manually within QGIS. Since the attribute data in public datasets was not always consistent or up to date, I used the “Select Features” tool to manually identify and export:

• Fire stations.

• Schools.

• Hospitals.

• Employment sites.

• Candidate safe spaces.

These features were exported as new shapefiles using the “Export Selected Features” function, allowing for greater accuracy in representing infrastructure critical to evacuation and emergency response.

Final Environment Setup

All processed and manually created layers were visually styled in QGIS and exported with consistent naming. The final GIS environment featured:

• Layered base maps: parcels, roads, buildings.

• Overlay layers: flood zones, schools, fire stations, hospitals, job sites, and shelters.

These layers were used directly in:

• NetLogo, via gis:load-dataset for agent initialization and environment rendering.

• Python, where the road network was converted into a weighted graph for use with the A* pathfinding algorithm.

Population Scaling

To ensure computational efficiency, the simulated population was scaled from Franklin Park’s estimated 17,900 residents to 12,500, equivalent to 1 agent per 10 people, resulting in 1,250 agents (USCensusBureau2024?; DataUSA2024?). These agents were spatially distributed based on building locations and assigned to roles as follows:

• Children: schools

• Employees: job sites and hospitals

• Residents: homes

• Firefighters: fire stations

This agent setup maintained demographic realism while enabling high-performance simulation.

Spatial Environment and Flood Mapping

The ABM loads shapefiles generated in the GIS preprocessing phase using thegis:load-dataset function. These include roads, buildings, flood zones, schools, hospitals, fire stations, and job sites. The world envelope is automatically adjusted to fit the street network, ensuring the simulation space mirrors the real-world layout of Franklin Park.

Flood zones are mapped onto the environment by identifying flood centroids and labeling nearby patches as flooded (flooded? = true). This visual and functional tagging influences how agents perceive and interact with their surroundings.

ask patches [ set flooded? false ]

foreach flood-locations [

    ?location ->

        let coords gis:location-of ?location

        if coords != nobody and length coords > 1 [

            let x item 0 coords

            let y item 1 coords

            ask patches with [ distancexy x y < 1 ] [

                set flooded? true

                set pcolor 107  ;; visual indicator flooded areas

            ]

        ]

]

The build-grid-from-patches function then creates a matrix representation of the environment that is passed to the A* routing engine in Python. Each matrix cell is marked as either “flooded” or “empty.”

Agent Roles and Initialization

Population agents are created based on demographic scaling established earlier: 1 agent per 10 residents, for a total of approximately 1,250 agents. These agents are divided into four functional categories:

• Children are assigned to schools.

• Employees are dispatched to job sites and hospitals.

• Residents (including seniors) are placed in residential buildings.

• Firefighters are deployed from fire stations.

Each agent is given a role and relevant spatial coordinates. The following code snippet illustrates how employees and firefighters are created:

create-turtles 1 [

    set role "employee"

    let work-place one-of job-locations

    let loc gis:location-of work-place

    setxy item 0 loc item 1 loc

    set current-target loc

    set shape "person"

    set color black

]



create-turtles 1 [

    set role "firefighter"

    let station one-of fire-station-locations

    let loc gis:location-of station

    setxy item 0 loc item 1 loc

    set shape "dot"

    set color yellow

]

Visual attributes (color, shape, and size) help distinguish agent types in the simulation interface.

Behavioral Rules and Flood Interaction

Agents interact with their environment according to their assigned roles. In the current “daytime” scenario, most agents (children at schools, employees at job sites, residents at home) remain stationary once initialized. The only mobile agents are firefighters, who actively respond to flood zones.

Flooded areas affect the simulation primarily by:

• Defining boundaries where firefighters must switch from vehicle-based to on-foot rescue.

• Influencing the environment layout passed to the A* algorithm.

While non-firefighter agents do not yet react to floods, future iterations could incorporate self-evacuation behavior, dynamic decision-making, or congestion effects based on flood proximity.

Communication with Pathfinding Module

Finally, NetLogo serves as a bridge between the environment and the A* pathfinding algorithm implemented in Python. The function export-all-data prepares and transmits the following to the Python backend:

• The 2D grid with flood status.

• Flooded zone coordinates and population.

• Safe space location.

• Firefighter positions.

This real-time integration enables scenario-specific optimization of evacuation routes based on current agent locations, flood conditions, and infrastructure layout.

*Theoretical and Mathematical Foundations of A**

The A* algorithm is one of the most widely used search methods for computing shortest paths on weighted graphs. It is considered optimal and complete when paired with an appropriate heuristic. A* blends the exhaustive cost evaluation of Dijkstra’s algorithm with the goal-oriented strategy of Greedy Best-First Search, offering both efficiency and precision.

At each step, A* evaluates a node n using the cost function:

f(n) = g(n) + h(n)

Where:

• g(n): the cumulative cost from the start node to n.

• h(n): an admissible heuristic estimating the remaining cost from n to the goal.

• f(n): the total estimated cost of a solution that passes through n.

The algorithm expands the node with the lowest f(n), continuously updating paths until the optimal route to the goal is found.

Heuristic Functions: Euclidean vs. Manhattan

The heuristic function h(n) is central to A’s performance. It influences the search direction and determines whether A remains optimal. Two commonly used heuristics are (Patel, 2025):

1. Euclidean Distance

h(n) = sqrt((x_goal - x_n)^2 + (y_goal - y_n)^2)

• Description: This calculates the straight-line distance between two points.

• Use Case: Appropriate when agents can move freely in any direction (including diagonally), such as in continuous-space robotics or GPS-based routing.

Properties:

• Admissible: It never overestimates actual cost if movement cost equals distance.

• Consistent: Satisfies triangle inequality. Ensures no node needs to be revisited.

2. Manhattan Distance

h(n)=∣xgoal−xn∣+∣ygoal−yn∣

• Description: Measures the number of horizontal and vertical steps needed in a grid. Known as “taxicab” geometry.

• Use Case: Ideal for grid-based maps where movement is limited to up/down/left/right.

Properties:

• Admissible: As it only counts minimum steps needed, it never overestimates cost.

• Consistent: Like Euclidean, it preserves the triangle inequality.

Algorithm Selection and Experimental Setup

To determine the most suitable pathfinding algorithm for flood evacuation modeling, I implemented a comparative test using three algorithms: Breadth-First Search (BFS), Dijkstra, and A*. These were tested on a synthetic, weighted graph simulating urban terrain with disruptions such as blocked and flooded routes.

The graph was constructed using a random generator function that:

• Places 50 nodes in a 2D coordinate space.

• Connects node pairs with a 10% probability.

• Assigns edge costs based on conditions:

  • Cost 1 for normal roads.

  • Cost 5 for flooded roads (simulating delay).

  • Cost ∞ for blocked routes (impassable obstacles).

This setup allowed me to simulate real-world decision-making conditions such as selecting faster but riskier paths or avoiding known hazards altogether.

Pseudocode of Evaluation Process

1. Generate 2D coordinates and construct graph with edge weights.

2. Assign flood zones and obstacles randomly.

3. Define start and goal nodes.

4. Apply:

- BFS: to find the shortest number of steps.

- Dijkstra: to find the path with the lowest total cost.

- A*: to find a near-optimal path using cost and heuristic guidance.

5. Visualize and analyze the resulting paths.

These were the key findings from the comparative experiment with the three algorithms:


Figure 1: Comparison of Algorithms.

• Breadth-First Search (BFS) demonstrated the shortest path in terms of steps (2), but completely ignored edge weights. As a result, it selected a path that may pass through impassable or high-cost areas, which is unrealistic in emergency conditions like flooding.

• Dijkstra’s algorithm produced the lowest-cost path (4 units) by exhaustively exploring all possible routes. While it guarantees optimality, this comprehensive search makes it computationally expensive, especially when scaled to larger networks.

• *A** identified a path with a slightly higher cost (6 units), but significantly improved efficiency by using a Euclidean heuristic to focus its search. Despite a modest increase in path cost, it reduced unnecessary node exploration, achieving a result that was more directed and time-efficient.

In high-stakes contexts such as flood evacuation, where quick decision-making and efficient resource deployment are essential, A* offers a strong balance between speed and path quality. Therefore, we can conclude that A* was the most appropriate choice for this model, reducing node exploration by approximately 60% compared to Dijkstra, while still producing a high-quality route. This makes it particularly well-suited for simulations where time, scalability, and realism are equally critical.

A Pathfinding Implementation and Logic

Following the comparative analysis of pathfinding algorithms on synthetic graphs, A* was selected as the core method for route optimization in the evacuation model due to its superior efficiency in node exploration and its ability to incorporate real-world spatial heuristics. To operationalize this in a realistic flood evacuation scenario, I implemented A* in Python using two spatial layers: a street-level graph derived from GIS data, and a raster-based grid representing flood conditions.

The road network of Franklin Park was processed from shapefiles and converted into a weighted graph. Each node corresponds to a coordinate on a street segment, and each edge is weighted by the Euclidean distance between nodes. This structure allows firetrucks to navigate through the actual street layout with accurate travel costs. Simultaneously, a 2D grid overlays the same area and marks each cell as either “empty” or “flooded.” This grid is used to simulate pedestrian movement, where firefighters continue on foot after reaching the boundary of the flood zone by truck.

To maintain realism, two heuristic functions are used within the A* algorithm depending on the domain: Euclidean distance for truck movement along roads (where diagonal movement is allowed), and Manhattan distance for walking in the grid (where movement is constrained to four directions).

The evacuation process is broken into repeated missions. In each mission, the model selects the closest flooded cell that still has people awaiting rescue. The firetruck computes a route to the nearest adjacent “dry” cell where it can safely stop. From there, the firefighter proceeds on foot into the flooded zone to reach the affected individuals. After collecting up to a predefined number of people, the firefighter retraces the route back to the truck and then drives to the designated safe space. The system then automatically initiates the next rescue operation from that new location.

Each iteration yields updated data that is critical to both evaluation and decision-making:

• Flood target served: The flooded cell where people were evacuated.

• Border cell identified: The nearest reachable dry cell for vehicle transition.

• Time breakdown: Time spent on each phase — truck to flood, walking in, walking out, and truck to safe space.

• Population update: Number of people rescued in this round and the remaining in that area.

• Position update: The firefighter’s new location becomes the starting point for the next dispatch.

This logic continues until all evacuees have been rescued. Because each routing decision is dynamically recomputed based on evolving conditions, including population levels and firefighter position, the model remains responsive to real-time changes, simulating the constraints and complexity of emergency response logistics.

Pseudocode Explanation

The following pseudocode explains how the algorithm progresses through multiple rescue iterations and adapts routing based on updated conditions:

function rescue_all_people:

    while people remain in flood zones:

        1. Identify the closest flood target with remaining population.

        2. Find the nearest adjacent dry cell for the firetruck to stop.

        3. Compute A* path on the street graph from current location to dry cell (truck leg).

        4. Compute A* path on the grid from dry cell to flood target (foot leg).

        5. Reverse foot path and drive from dry cell to safe space (return leg).

        6. Update:

        - Number of people rescued at target

        - Firefighter’s current location (now at safe space)

        - Total mission time

    return overall mission path and total evacuation time

Basic Tier: Agent and Environment Initialization

At this level, the simulation initializes agents in NetLogo, using GIS shapefiles loaded via the gis:load-dataset function. Shapefiles define buildings, streets, schools, fire stations, hospitals, flood zones, and candidate shelters. Agents, children, employees, residents, and firefighters, are created and spatially placed based on demographic roles and building assignments. Each patch in the NetLogo grid is tagged as “flooded” or “empty” using the build-grid-from-patches function.

Intermediate Tier: Pathfinding Integration

The core functionality of emergency response is implemented in Python, which handles all A* routing logic. Communication between NetLogo and Python is enabled via the py extension. At each dispatch:

• NetLogo sends a real-time snapshot of the environment, including the flood grid, firefighter positions, safe-space locations, and population counts.

• Python’s A* engine computes multi-phase evacuation routes:

  • Truck routing uses Euclidean heuristics on a weighted road network derived from street shapefiles.

  • On-foot routing through flooded areas uses Manhattan heuristics over a grid matrix.

The integration ensures domain-specific pathfinding: realistic road navigation for vehicles and constrained movement through hazardous terrain for pedestrians.

Advanced Tier: Adaptive and Multi-Stop Extensions

Although the current implementation models a single firefighter vehicle in sequential trips, the architecture is designed to scale. The `rescue_all_people function in Python dynamically selects the closest flood target, computes truck and walking routes, and updates the agent’s position after each mission. This modular setup allows:

• The addition of multiple simultaneous agents.

• Real-time response to changing flood conditions.

• The inclusion of dynamic evacuation priorities.

Simulation Setup

In the baseline scenario:

• A simulated population of 1,250 agents was used, representing Franklin Park’s 17,900 residents at a scale of 1 agent per 10 people.

• Each firetruck had a maximum capacity of 15 people per trip.

• The simulation assumed only one emergency vehicle was available to serve the entire area, providing a stress-test of the model’s efficiency under extreme resource limitations.

The following figure shows the initial configuration of the agent-based flood evacuation model. Brown polygons represent building footprints, blue polygons mark flooded patches derived from FEMA flood data, and the street network is overlaid in black, with municipal boundaries delineating the study area.

Icons correspond to different agent types and facilities: grey figures for residents, blue for children, and black for employees; yellow dots for firetrucks; red house symbols for fire stations; green circles for designated safe spaces; green house icons for hospitals; and pink buildings for schools. This layout defines the environment in which evacuation and rescue operations are simulated.


Figure 2: Spatial setup of the simulation in Franklin Park.

The model followed a multi-phase rescue procedure for each mission:

1. Drive Phase: The firetruck calculates a route from its current location to the nearest accessible “dry” patch adjacent to a flooded area (referred to as the border cell). This is done using A* pathfinding on a street-based graph with Euclidean heuristics.

2. On-Foot Phase: Once at the border cell, the firefighter dismounts and walks into the flooded patch to reach residents, using A* on a grid with Manhattan heuristics.

3. Return Phase: The firefighter walks back to the truck and then drives the evacuees to a designated safe space.

Each leg of this mission was timed independently, allowing detailed analysis of the operational costs associated with each mode of movement.

Sample Mission Results

• First Trip

  • Target zone: Cell [14, 5] with 48 residents; 15 were evacuated in this first trip.

  • Border cell for vehicle stop: (14, 6)

  • Time breakdown:

    • Truck-out (dry roads): 204.2 seconds

    • Foot roundtrip (in/out of flood zone): 723.4 seconds

    • Truck-back (to shelter): 325.1 seconds

  • Total mission time: 1,252.8 seconds (~20.9 minutes)

• Final Trip

  • Target zone: Cell [24, 29] with 5 residents; all were rescued.

  • Border cell: (24, 30) (adjacent to the flooded location).

  • Time breakdown:

    • Truck-out: 678.5 seconds

    • Foot phase: 0.0 seconds (since target was directly accessible)

    • Truck-back:678.5 seconds

  • Total mission time: 1,357.0 seconds (~22.6 minutes)

Overall Mission Summary

Over the course of the simulation, the single firefighter vehicle conducted repeated evacuation cycles, adjusting its starting point each time based on the previous mission’s endpoint. This dynamic routing ensured that each new trip was as efficient as possible, given the evolving conditions.

Total time to evacuate all agents using one firetruck was: 509,547 seconds (approximately 141.5 hours or nearly 6 days of continuous operation)

This result highlights the operational strain of using a single rescue unit for an entire neighborhood during an extreme flood event. However, the architecture of the model enables easy experimentation with alternative strategies. If multiple firetrucks, such as ten operating in parallel, were deployed, the estimated total evacuation time could potentially drop to 12–14 hours, assuming that rescue zones are evenly distributed and vehicle dispatch is efficiently coordinated.

Conclusion

The simulation results demonstrate that the model:

• Effectively replicates multi-phase, agent-based evacuation under variable terrain and flood conditions.

• Provides a framework to quantify the impact of resource availability, such as the number of firetrucks, on total evacuation time, based on future scenarios.

• Surfaces potential trade-offs between speed, capacity, and routing efficiency that emergency planners may need to consider, particularly when extending the model to simulate multiple vehicles or changing flood dynamics.

Single-Vehicle Constraint

The most significant operational limitation of the current simulation is the assumption that only one firetruck is available for the entire evacuation effort. While this setup was useful for stress-testing the routing algorithm and measuring performance under constrained conditions, it does not reflect the likely scale of emergency response in a real flood event. In practice, multiple vehicles, potentially deployed from various stations or external agencies, would operate concurrently. This limitation means that while the model can provide insights into route optimization and agent behavior, its reported evacuation time (~141.5 hours) represents an upper-bound scenario under minimal resource availability.

Static Flood Zones

Another simplifying assumption is the treatment of flood zones as static polygons. Once loaded from FEMA shapefiles and processed in QGIS, these zones remain fixed throughout the simulation. This is a useful first step for establishing the spatial structure of the emergency but does not account for temporal flood dynamics such as rising water levels, flow direction, or expansion over time. Future versions of the model could incorporate dynamic flood growth using either probabilistic rules or data-driven hydrological models to more accurately simulate evolving hazards.

Agent Homogeneity

Although the simulation distinguishes between broad agent roles (children, employees, residents, and firefighters), there is still a level of homogeneity in agent behavior. All individuals within each category are assumed to remain stationary until rescued, and no agents currently self-evacuate, signal for help, or respond dynamically to environmental changes. This simplification limits the behavioral realism of the model. In reality, individuals would respond with different levels of urgency, mobility, and decision-making autonomy based on age, health, social influence, and access to information.