Skip to main content

Young Scientist Journal

Young Scientist Journal

Crime Prediction and Optimal Police Allocation

ABSTRACT

Police departments currently use optimization programs to evenly divide up the city into precincts so that the amount of crime in each precinct is approximately equal. While this allows for some efficiency, police departments have not fully optimized their process because they have not incorporated any crime prediction algorithms. In this project, the police allocation mechanism has been modeled as the “transportation problem,” a classical optimization problem, in order to determine which police officer needs to attend which crime. Two algorithms – a heuristic and optimal algorithm – were developed to identify which had a faster runtime and which assigned more efficient routes. Along with these two, a crime prediction algorithm based on survival analysis was developed in order to determine where police officers should be placed among precincts, based on predicted crimes. In the future, the ultimate goal of this project is to develop an open-source application for smartphones that can utilize the algorithms that we developed. By doing this, police departments are improving their allocation techniques by automating this process. This will in turn allow police officers to have greater chances at catching the criminals and helping victims.

INTRODUCTION.

Police departments focus primarily on preventing, responding to, and conducting thorough investigations on crimes that occur. Crime prevention and minimizing response times is vital for police departments to invest in because it can potentially decrease the amount of crime that occurs in certain areas and can increase the chances of catching the alleged criminal. However, the techniques that police departments use to allocate police resources throughout a precinct are often not optimal; police departments have used some optimization software to evenly divide up the city into precincts in a matter where each precinct has approximately the same amount of crime. By doing this, the police departments can evenly allocate their police resources. However, police departments are not using any crime prediction software, causing their methods to not be fully optimal. With the use of historical data and big data analysis techniques, police departments can increase the efficacy of their police systems.

Previously, a study was conducted using a machine learning algorithm with data mining principles to determine and predict the level of importance of a crime (low, medium, high) [2].  To do this, historical crime data was assessed to determine trends among crimes [1]. Relatedly, another study has been conducted on efficiently predicting future crimes based on household income, education level, and other factors [1,3].  Although a lot of studies conducted on crime prediction have been conducted, relatively few are related to police response time optimization. One such study combined several fundamental optimization problems to allocate police to an optimal position based on crimes that are currently occurring, and crimes that have occurred historically [4,5]. Although this algorithm outputs the optimal location, the algorithm requires around 24 hours to fully process the data; this longevity is impractical because police departments require this information rapidly [5].

This project focuses on using police patrol data and crime data from the Nashville Police Department in order to develop an algorithm that can accurately predict potential crimes in the future. After developing the prediction algorithm, the police can be better allocated among Nashville precincts, by developing a heuristic algorithm that minimizes response time to crimes. The police problem is modeled as the transportation problem, a classical optimization problem. There are several approaches to the transportation problem, some of which are the northwest-corner approach, the least-cost approach, and the stepping stone method. These approaches, called heuristic approaches, do not always lead to the optimal result; however, they are often used to make a forward linear programming method scalable. These methods work to optimize the cost of transportation and to fulfill the demands of the consumer. In this project, the optimal solution will also be developed and compared to the heuristic solution to determine which solution runs faster without significantly increasing the total distance traveled. Also, the crime prediction algorithm will be developed using survival analysis. This project concentrates on implementing the transportation problem and survival analysis methods into usable algorithms for the Nashville Police Department. However, testing the algorithms was not feasible because of time constraints.

MATERIALS AND METHODS.

In order to optimize police allocation, the transportation problem has been taken into consideration. Figure 1 shows a sample scenario of the transportation problem. In Figure 1, there are two suppliers that both have an available supply of 30 units. There are also three consumers with respective demands of 10, 30, and 20 units. The goal of this problem is to determine which supplier should supply to which consumer while minimizing the cost of transportation – denoted by the numbers next to the lines. The method used in this project is the least cost approach; the least cost approach is where suppliers give as many resources as they can to the cheapest consumer first. Adapting this simple scenario to the police allocation problem involves the suppliers being the police and the consumers being the crimes. The algorithm requires several arrays and for loops in order to properly traverse through the data. When adapting to the police scenario, data given by the police department is imported and incorporated into the foundational program that is developed.

Figure 1. This figure shows an example of the transportation problem where there are 2 suppliers each with a supply and 3 consumers each with a demand. Each route that the supplier can take has a transportation cost associated with it.

In order to see how much faster the heuristic algorithm is compared to the optimal solution, the optimal solution for the transportation problem has been developed in Java. To develop the optimal solution, a market-standard tool called CPLEX was used. CPLEX was a tool developed by IBM to solve optimization problems. In this project, the optimal solution was developed; however, many errors still exist and need to be debugged in the future. To develop the optimal solution, the objective function and constraints must all be coded into the program. The objective function states that the goal is to minimize the totals costs. The constraints are: 1) sum of total police allocated must be less than or equal to total number of police available, 2) sum of total police received at a crime must be greater than or equal to the total number of crimes, 3) supply must equal demand, 4) all allocations must be non-negative. The algorithm uses real-time coordinates of police officers and crimes and use them to calculate the distance between each officer and each crime. Then, the transportation problem will be used to decide which officer attends which crime.

In order to predict crime, survival analysis was used. Survival analysis is the process used to find when the next instance of a certain phenomenon will occur based on historical occurrences. The technique is usually used in biology fields; however, it can be used in this situation to develop a market-equivalent crime prediction algorithm. To develop the algorithm, a package called Rcaller was used in Java. Rcaller allows for functions from R in Java.

RESULTS.

Currently, the heuristic algorithm based on the Least Cost Method for the transportation problem has been programmed in both Java and Python. It has been developed in Java so that the algorithm can be implemented into the android app code. It has also been developed in Python in order to compare it to the optimal solution previously written in Python. The heuristic algorithm has been developed as a way to decrease the amount of time required to determine a more optimal solution. To facilitate coding the parameters of the linear programming problem for the optimal solution to the transportation problem, CPLEX, a market-standard tool for optimization problems, and Python were used to develop the optimal solution. Along with the heuristic and optimal solutions, the crime prediction algorithm has been developed. The crime prediction algorithm is based on survival analysis. The algorithm is fully developed.

DISCUSSION.

In this project, the objective was to develop an application with the potential to optimize police allocation.  This gives police officers a higher chance of helping the victim and catching the criminal.

In the future, the heuristic algorithm and the optimal solution need to be compared in order to determine which algorithm is more applicable. To achieve this, the runtimes and total costs need to be compared to see which algorithm runs faster and to see how much the costs differ. Also, an open-source smartphone application for both iPhone and Android devices needs to be developed so that all police officers can have access. The application will predict crimes using the survival analysis algorithm developed in this project, place police officers based on predicted crimes, and assign individual routes to police officers based on the transportation problem algorithms from this project.

Some limitations of this project is that no testing with police officers was feasible. This means that the algorithms functionality in accordance with police officers in real-time was not acquired. Once the application is fully developed, the application will be given to various police departments to see whether or not response times have decreased overall. Without this testing, the true functionality of the application and algorithms cannot be determined.

ACKNOWLEDGMENTS.

I would like to thank Dr. Yevgeniy Vorobeychik for allowing me to work in his lab and providing me with the project. I would also like to thank Ayan Mukhopadhyay for guiding me throughout the entire project. I would also like to thank Dr. Jordan Grigor and the School for Science and Math at Vanderbilt for assisting me through my lab experience.

REFERENCES.

  1. E. Cohen, Weather and Crime. Brit. Journal of Crim. 30, 51(1990).
  2. D. P. Farrington, Predicting individual crime rates. Crime and Justice 9, 53 (1987).
  3. R. Iqbal, An Experimental Study of Classification Algorithms for Crime Prediction. IJST. 6, 4219-4225 (2013).
  4. C. Koper, Just enough police presence: Reducing crime and disorderly behavior by optimizing patrol time in crime hot spots. Justice Quarterly 12, 649 (1995).
  5. A. Mukhopadhyay, Optimal Allocation of Police Patrol Resources Using a Continuous-Time Crime Model. Comp. Sci. and Game. Theory for Sec. 9996, 139-158 (2016).

Posted by on Tuesday, December 22, 2020 in May 2018.

Tags: , ,