-
-
Crime heat map that we have made use of to extrapolate crime rate at various MRT stations. https://wilsoncwc.github.io/neighbourhood-watch/
-
Illustration of how the gradient from one station to the next is used to decide on the next station to move to.
Inspiration
With the entire team having served our National Service in the Singapore Police Force, we have personally seen the value of optimised patrol routes, being able to cover the areas with the greatest risks. The implementation of this solution would ensure officers are at crime-prone locations to minimise response time for incidents. This is done while not neglecting less crime-prone area and ensures an efficient use of resources. This is especially vital in today’s world, with a shrinking population, many public services such as law enforcement are facing a manpower crunch, thus the importance of efficient allocation of manpower is of utmost importance.
What it does
Our project takes in an n number of stations to be generated and the station, x, from which the patrol should start from as input. The Optimised Patrol Route Generator would then return the first n stations that are of highest priority to be patrolled. This takes into account the total number of crimes committed at a station and the distance to the station from the starting station initially and the preceeding stations after that. This allows the authorities to patrol the stations which are considered to be crime hotspots. Furthermore with use of a database to keep track of the frequency at which stations are being visited, we are able to ensure that the same few stations are not repeatedly patrolled while still giving higher priority to the stations with a higher crime rate. This database can be reset as required.
How we built it
After deciding on this project, we had to first gather relevant data, such as the time between any 2 stations, and the crime rates of different stations. However, the data for the crime rates are unavailable due to its sensitivity and secrecy, as such we had used data from a crime heatmap in 2013, and extrapolated to today. We had used SQLite for the integration of a database, and Dijkstra's algorithm for pathfinding to find the shortest travel time between stations. We had then used a levelling method for the purpose of finding the next station with the greatest priority, by taking into account both the distance to the station, and the relative crime rate. A graphical user interface was also integrated for the purpose of allowing users to customise certain variables for the purpose of adaptive planning.
Challenges we ran into
1) Updated datasets on crime data were hard to find due to confidentiality. As such we have made use of a 2013 crime heat map to obtain results that are closer to the current state.
2) Datasets with lists of adjacent stations were also not readily available. As such solutions to this would have been to make use of image processing techniques in order to obtain an adjacency list from the Singapore MRT Map. However due to time constraints, we opted for a manual implementation of just the SPF 'G' Division zone for our testcase.
Accomplishments that we're proud of
1) Firstly we needed a metric that was able to take into consideration both the distance that needs to be traveled from one station to another and the number of crimes committed at a particular station. To tackle this, we have made use of the properties of a triangle to find the common metric between the two variables which would be the gradient from one station to the next. A picture has been included in the "Project Media" section to illustrate the effect of this gradient from one station to the next that we have used.
2) To implement variety and fairness, we utilised a SQLite database(can be reset) to keep track of a dictionary where the key value pair is {station: frequency of visits by police on that day}. Using this frequency we adjusted the crime rate of each station by multiplying it by the reciprocal of the stations frequency of visits in the database (crime rate = crime rate/freq, if frequency is 0 just use original crime rate). Hence, this prevents the same few stations from being visited repeatedly while still giving priority to those with higher crime rate. Furthermore, realising that users might also wish to reset the database to reset the frequency of visits to the stations back to 0, we have also included the abitlity for them to prompt a reset of the database.
3) From each station we needed to find the shortest path to the station with the highest level of importance. Made use of the Djikstra’s Algorithm and a Priority Queue as our chosen path finding algorithm and data structure to find the shortest duration taken to get from one station to the next.
4) Implemented Argparsing so that variables such as the starting station as well as number of stations to visit can be easily changed and resetting the database from the command line for easier testing as well as improved user experience
What we learned
In terms of technical knowledge, we have learnt about the implementation of Dijkstra's algorithm for graph traversal and pathfinding. We have also learned the importance of using data to drive decisions and adapt strategies over time. In terms of soft skills, we have definitely learnt project management for software projects as this is our first hackathon and first software project that we are working on as a group. Through this hackathon, we have learnt to recognise the importance of efficiency and scalability in the solutions we provide, for the sake of expanding throughout Singapore and seamless integration into the Police Force.
What's next for DriversLicense-Optimised Patrol Route Generator
1) Usage of Google Maps API for more precise crime data location, expansion to whole of Singapore, implementation of supervised learning to predict future hotspots, incorporation of other modes of transports
2) Other variables besides time, crime rate and frequency to determine optimised stations e.g proximity/distance of other Police Officers to selected stations can be calculated to ensure that there isn't a case where multiple patrol teams are going to the same stations and the teams are relatively spread out to maximise manpower
3) If the data becomes readily available, we can even break down the crime rate by the different types of crime committed e.g outrage of modesty or theft
Log in or sign up for Devpost to join the conversation.