Inspiration
Being Computer Science freshmen, our team had went through a number of programming related modules, but lacked the opportunity to apply the skills we had learnt. That's where we drew our inspiration in search of projects where we can integrate our learning into building high scale solutions to problems, which led to us joining this hackathon and choosing the theme of Safeguarding Public Security.
What it does
Our police patrol route optimiser is a webpage with a detailed and inbuilt algorithm which is able to provide users with an optimised route for patrolling from the police station to various identified crime hotspots, and thereafter returning back to the police station. To maximise optimisation, we built our algorithm on 2 main criteria: creating a route that visits every location in the area, and creating the shortest route while traversing high crime rate roads.
How we built it
We mainly approached this optimisation problem as a graphing problem. To design the algorithm, we thus collected data on the different locations which would be used as the vertices, and different roads which would be used as the edges. Hence, we first collected data from a real time map, and identified various locations and the roads linking them.
Thereafter, we designed a graphing algorithm on an undirected weighted graph which takes in the set of vertices and set of edges, and runs Prim's algorithm to find the minimum spanning tree (MST) of the graph. This ensures that all locations are visited with the minimum amount of weight traversed. Thereafter, we manipulated the MST to make it a Eulerian graph, by identifying the odd degree vertices and linking them together to make them even degree. This then allowed us to run Hierholzer's algorithm to create a Eulerian circuit, starting from and ending at the police station vertex, which is the optimised police patrol route. This ensures that every road identified in the MST is part of the police route.
The route would then be input into a map visualiser, such that when a user uses our webpage to find the patrol route, they just have to select the police station, and the map with the patrol route would be instantaneously shown.
How does your hack answer the problem statement
Our main graphing algorithm aims to fulfil 2 main criteria of creating a patrol route that visits every location, and being the shortest route while traversing all high crime rate roads. This allowed us to be able to answer the optimisation problem, where we integrated crime hotspots into creating the optimised police route. With our algorithm being able to fulfil all these factors, we were able to successfully make our patrol route one that is able to prioritise on higher crime risk areas and shorten emergency response times.
Challenges we ran into
As our patrol route optimiser aims to fulfil 2 criteria at the same time, it was hard to design an algorithm that fulfils the two concurrently. We had to design a bigger main algorithm which contains many different smaller algorithms and parts, to be able to fulfil the 2 criteria, which took some time to place them together.
Accomplishments that we're proud of
We managed to apply what we learnt from our Data Structures and Algorithm module into solving a problem, given that we did not have much prior experience in hackathons.
Log in or sign up for Devpost to join the conversation.