Our goal was to prioritize street light repairs at a neighborhood level based on the expected change in crime rate. To accomplish this goal, we needed to build two operations research programs:
- A traveling salesman algorithm to determine the approximate amount of time to fix all broken street lights in a given neighborhood
- A linear program to determine which neighborhoods to prioritize based on their total repair time and the expected change in crime rate (based off of the weighted crime rates calculated in the Data Collection & Crime Correlation segment of this project)
Traveling Salesman Problem: Repair Time by Neighborhood
We formulated a traveling salesman program in Excel to find the optimal route to repair all current broken street lights in a given neighborhood. We ran this program for the same ten neighborhoods used to analyze the correlation between street light outages and crime rate. Given the total distance of the repair route and the number of current broken street lights, we computed an approximation of total repair time for each neighborhood.
|Neighborhood||Number of Current Broken Street Lights||Total Distance Required to Repair all Lights (meters)||Total Time Required to Repair all Lights (days)|
|South of Market||26||10629.31||1.68|
|Lower Nob Hill||9||1891.41||0.57|
As an example, the Bayview repair map is shown below.
Bayview Repair Map
Once we had an approximate amount of time needed to fix all of the lights in each neighborhood, we incorporated these results in our main optimization problem.
Linear Program: Repair Optimization by Neighborhood
We built a linear program to maximize the expected change in crime in SF by fixing street lights in certain neighborhoods that had a greater correlation between street light outages and crime rate. The expected change in crime for each neighborhood was calculated by multiplying the average difference between weighted crime rates when a street light is on and off by the number of street lights that would be fixed. The main constraint in our program was a time budget, which incorporated the total repair time previously calculated for each neighborhood.
We ran the linear program nine times, exploring how the list of prioritized neighborhoods changed as we increased our time constraint from 1 day to 9 days. Below is a table of the final results. If a neighborhood has a ‘0’, it should not be prioritized. If a neighborhood has a ‘1’, the street lights in that neighborhood should be repaired.
Using the results of our linear program, we suggest the following ordered list of neighborhoods in which the street lights should be repaired to reduce crime:
Street Light Repair Order
- Civic Center
- South of Market
- Lower Nob Hill
- Downtown/Union Square
- Western Addition
- Outer Sunset
- Potrero Hill
To learn more about the methods and details of the optimization problem, refer to sections 6 and 7 of our final report.