torhaa1/response_time_minimization

Optimal placement of police units to minimize response time to events in police districts.

response_time_minimization's Issues

Exceeding max capacity per car

Problem started at Commit: Improved sampling of car points

1. created function generate_high_density_polygon() to make polygon of high density of simulated points.
2. sample car points within this polygon.

Obs: noticed that the Capacity constraints was slightly exceeded for some reason. E.g.:
Police car id: 8228357538 handles 293 events | Capacity: 104.64% | ...

Next commit: Move functions into utilityModule.py

Noticed even more exceedance of max_capacity constraint again (even when solving the MILP problem):
Police car id: 2012771318 handles 291 events | Capacity: 111.92% | ...

---

New constraint:

# Police Car Placement Constraint
problem += pulp.lpSum([x[i] for i in P]) == K, "NumberOfPoliceCars"

# Event Assignment Constraint
for j in E:
    problem += pulp.lpSum([y[(i, j)] for i in P if (i, j) in CostMatrix_dict_reduced]) == 1, f"EventAssignment_{j}"

# Validity Constraint
for (i, j) in CostMatrix_dict_reduced:
    problem += y[(i, j)] <= x[i], f"Validity_{i}_{j}"

# Capacity Constraint
for i in P:
    problem += pulp.lpSum([y[(i, j)] for j in E if (i, j) in CostMatrix_dict_reduced]) <= M * x[i], f"Capacity_{i}"

Ideas:

• check old vs new constraints
• test minimal preprocessing of CostMatrix (no problem reduction)
• check how the percentage is computed at the final plotting

Expand Oslo analysis to entire Oslo police district

Expand the Oslo analysis to include the entire Oslo police district (Oslo, Asker, Bærum).
Most useful to perform analysis district-by-district.

"Oslo politidistrikt er det største politidistriktet i landet målt etter folkemengde - og det minste distriktet målt i areal. Tidligere Asker og Bærum politidistrikt og Oslo politidistrikt er slått sammen. Fra 1.1.2020 ble Røyken og Hurum kommuner en del av Asker kommune, og således også innunder Oslo politidistrikt. Totalt har de tre kommunene ca. 928.156 innbyggere (per 1.kv. 2022). Distriktet har i underkant av 3400 ansatte."

Estimate number of cars per district

Need to roughly estimate the number of police cars per police district based on public data.
Potential sources to base estimate on:

• district population
• number of police employees in district
• number of police cars in district

Uncertainties will be large as there is large variation between the districts, and the Oslo district likely holds additional resources and personnel for other departments.

Correct travel time since police cars drive faster than speed limit

Idea 1 - static multiplier

Use a static speed multiplier of 0.2-0.3 to cut the travel time by 20-30%.
Quick to implement and adjust between runs. Can be applied directly on CostMatrix.

Idea 2 - dynamic multiplier

Adjust speed multipliers based on road type:

• Highways: On highways, a higher multiplier of around 1.3 to 1.5 might be more appropriate, since there will be fewer stops and less complex traffic conditions.
• Urban Streets: In urban areas with more frequent stops and lower base speed limits, a lower multiplier such as 1.1 to 1.2 could be more realistic.

Need to filter graph and modify the original edge weights.

Stability issues with the kernel density function

Stability issues with the kernel density function utilityModule.plot_population_density_and_event_points() when the high density clusters happen at the boundary. E.g. In South-East District have clusters in south east side(Drammen).
Looks like it is trying to draw a polygon shape, but get cutoff by the district boundary.

https://github.com/torhaa1/ResponseTimeMinimization/blob/4fbc9128b26d1c44869827219791b852c7f85606/main_analysis/utilityModule.py#L91C1-L164C29

Function is not critical for the analysis, it only constrains the sampling of car nodes closer to the simulated event points.
Currently just skip this function when dealing with a problematic district and filter car nodes more heavily based on network centrality stats.

OSMnx has problems with northern Rogaland roads

Not able to fetch complete OSM road network for South-East police district.
OSMnx has problems fetching roads north in Rogaland, bordering to Vestland county.
Even when combining graphs (incl. service roads) for both Rogaland and Vestland county, some of the northern roads of Rogaland is still missing.

See image below, with Rogaland (green) and Vestland (blue).

How to make model results between districts comparable?

Idea 1 - fixed population multiplier:

A fixed population multiplier for all districts that directly maps population density on 250x250m grids into nr of simulated events in that cell.

Have to create a minimum acceptable nr of points in Finnmark (lowest population density). Then use same multiplier for Oslo (highest population density) resulting in many more points. This could be more than computationally reasonable for a MILP problem.

Finnmark has 401 events, using population multiplier: 0.008347656250000002
Oslo has 7652 events, using population multiplier: 0.008347656250000002

Pro:

• Most straightforward, direct link between population and nr of simulated points for all districts

Con:

• Large variation in population density between districts cause few simulated points in Finnmark (401) and many in Oslo (7652).
• Too many points can make MILP problem intractable

Idea 2 - flexible population multiplier:

Find a fixed number (interval) nr of points to generate in each district. It should be enough points to spatially represent the population satisfactory, while not too many points to be computationally reasonable for a MILP problem.

With a target range of [1500, 1550] points, we get a median multiplication multiplier of 0.006172363281250001 from all the districts. This can be used as a "standard" multiplication multiplier.

For each district we use a flexible population mulitplier to generate a suitable nr of points in target range of [1500, 1550].
Then we compare the population multiplier used against the standard multiplication multiplier to get a correction factor.
The correction factor is applied to the response time to scale it up or down accordingly.

Correction factor example for the districts with the highest and lowest population density:

• std_pop_mult / oslo_mult = 2.991244676
• Oslo is ca 3 times as population dense as median -> we multiply the response time with 3, to simulate 3 times as many events (from the exact same locations)
• std_pop_mult / finnmark_mult = 0.2397034284
• Finnmark is ca 1/4 times as population dense as median -> we multiply the response time with 1/4, to simulate 1/4 times as many events (from the exact same locations)

Pro:

• Always a suitable number nr of events for a efficient MILP problem

Con:

• When scaling up/down the response time, we assume more/less events from the exact same locations, while they would be more spatially diverse.
• For a high population density district like Oslo, we would generate most points in the central areas. Then we would apply the correction factor, simulating 3 times as many events from these central locations. While using a fixed population multiplier would include more points from remote areas, which would push towards a longer average response time.

East police district needs to include Oslo roads

For East police district, much of the road network of Oslo needs to be included for correct travel times. Much of the fast roads from south to north pass through Oslo.
E.g. driving from Kolbotn to Lørenskog, would be fast and logical through Oslo, while a major detour if constrained to Akershus road network.

Include whole/parts of Oslo Network as a subgraph/something, while considering:

• avoid simulating events in Oslo
  • should be ok, population layer is pre-cut after East police district
• avoid placing car locations in Oslo
  • maybe can cut Oslo from the new high_density_polygon that constrain area to sample car points from.

Also check if the East road network stretch into Oslo in the south-east (kinda looks like it)

Optimal locations plot: looks like bug with assigned events to each car

In the plot of optimal locations:

• It looks like the colorized assigned events to each police car don't fully match the police car locations.
• Several points that should belong to another closer police car. Even though the capacity is 100% for a couple of cars.
• 13_Oslo_PuLP_v2.0.ipynb - was working fine
• 17_Ost_PuLP_v3.0.ipynb - started notice problem/bug

See image below: