Team #49 - Inferno

Inspiration

We were inspired by the growing national and global concerns about fire incidents. To demonstrate the applicability and effectiveness of our algorithms in simulating fire station locations and response times, we based our prototype on a densely packed metropolitan area such as Denver, CO. The Denver area experienced an increase in fire incidents from 2019 - 2022 (123K - 128K)[^1]. Concerns about climate change's impact on dry areas such as Denver also underpin the need for developing strategies to combat downstream issues (ex. exacerbated flammability due to drought).

[^1]: 2023 Denver Fire Department Annual Report

What does it do?

Our application simulates city/route planning to optimize the location of fire-fighting stations to improve response time and analyze existing station configurations. There is functionality for identifying optimal configurations of fire station locations to reduce incident response time. Users can analyze custom configurations of station placement to assess their effectiveness in reducing response times to randomly generated test incidents. Also, there is a feature that allows users to simulate one-off instances of fire-station placements and their response times to a selected fire incident (indicated by the user).

How did we build it?

Tech stack

Our prototype contains three components: the web UI, the Python web server, and a GraphHopper server instance for route computation. The web UI was built using vanilla HTML, CSS, and JavaScript, while leaflet.js was used for map visualization. The backend web server was built using Python and the FastAPI web framework, which communicated with a self-hosted GraphHopper server that was used to compute the fastest route between two points. The GraphHopper server needed street data of the serviced region to model a network of roads, and this was obtained by cropping Colorado state OpenStreetMap data using Osmosis.

Algorithmically

1) Average response time This involved creating a large random set of fire locations in the rectangular region of the metropolitan area in hopes of it covering a majority of the serviced area. From there, we then computed the shortest response time for every fire to any of the given fire stations in the configuration. This was then averaged amongst all of the fire locations

2) Optimal fire station configuration For a positive integer n, we once again used the large random set of fire locations to approximately cover the region. We then used a simple k-means algorithm to "cluster" these fires, assigning a fire station to the centroid of each fire cluster. This was performed iteratively until the fire station locations stabilized

3) Single emergency instance Given a configuration of fire stations and a single fire location, we take the fastest time from any fire station to the fire

Challenges + Learning Moments

• Implementation of k-means clustering algorithm for optimization: in our fire station configuration optimization algorithm, we utilized the k-means clustering algorithm. The issue was that the standard implementation of k-means clustering utilizes Euclidean distance to delineate the boundaries of a cluster of randomly generated emergencies (which then informed where the best locate fire stations). This required a tweak to implementing this algorithm that utilized route time queried from GraphHopper as a distance metric for the clustering algorithm. This allowed us to deepen our understanding of this algorithm and how it can be applied to a broader range of problems outside its standard use.

• Modeling multiple emergencies occurring simultaneously: for our "Emergency Instance" simulation, we had initially planned to create functionality for simulating multiple fire incidents at a given moment and how increasing the number of fire stations would impact this simulation. Given the time constraint, we could not tackle many more variables that must be considered. For example, if we simulated the user placement of a single station and multiple incidents, then the simulated fire-fighting squad would have to deal with these instances sequentially. This would have likely required modeling the time taken to deal with each of the situations and considering the capacity of the fire station. This problem becomes more involved when considering multiple stations in the event of multiple incidents.

• Overall, this project allowed us to confront the many challenges that come with attempting to model real-world situations that are contingent on cartographic/traffic data.

What are we proud of?

We are proud of building a functional simulation in < 36 hours. For most of our group, this was our first hackathon, so we are glad we could design a product that we were all satisfied with.

What can be improved?

As mentioned in the challenges, we can certainly look into implementing capacity facility problem solutions for a more accurate representation of real-world situations. We can also certainly improve upon the optimization algorithm, as k-means clustering is not known for its speed. Perhaps we can make use of GraphHopper's Clustering endpoint, as it is likely better suited for working with route networks. In our original plans, we also planned to model more than just fire incidents, but other emergency instances such as medical (responded to by hospital/urgent care ambulances) and criminal cases (responded to by law enforcement station cars). Perhaps we can move forward by integrating these components in future versions of Inferno. Another consideration would be potentially giving users the ability to model historic fire incidents in an area and to optimize station location to assess the risk of failure associated with the location configuration at the time of said historic incident.

Built With

• css3
• fastapi
• html
• javascript
• leaflet.js
• numpy
• openstreetmap
• python
• shapely