I'm working on a NetLogo model that simulates police units patrolling in different beats. I'm trying to find the best relocation points for police units within their respective beats such that the sum of their travel time to all other nodes within the beat is minimized. The street network and beats are GIS-based, loaded into the NetLogo world, and I've built a table to keep track of nodes in the network.
I've considered using a clustering algorithm to partition each beat into x number of clusters, where x is the number of police units in that beat, and then placing one police unit at the node with the highest weighted closeness centrality of each cluster.
I am getting the street network from GIS shapefiles which I gather from OSM through OSMnx. I have also thought that I might identify the nodes in preprocessing. Any suggestion to how would also be welcome!
Is there a better way to do this? Would these 'best' points also be well-distributed across the street network, or do I need a separate approach for that?
This is the standard way to do this.
What clustering algorithm have you tried?
From your question, it seems that you may not have tried anything yet. You should! Then you will be able to ask specific questions about particular problems you get stuck with.
Suggestion: Start with something as simple as possible e.g. the K-Means algorithm ( https://en.wikipedia.org/wiki/K-means_clustering ). This will allow you to develop the necessary infrastructure ( data storage, input and output display ) and get some interesting results to think about. Then you can implement other algorithms using the same infrastructure and make meaningful comparison in the context of your particular instance.
This suggests to me that you are thinking of every street as homogeneous. From the police point of view that is certainly untrue, some streets need a lot more attention than others. Have you looked at the paper by Dinc & Dinc ( https://ieeexplore.ieee.org/document/8478908 )that explores how to include past crime statistics in this sort of work?
The code in this repository uses the agglomerative hierarchical clustering algorithm to locate police stations ( blue dots ) at the center of historical crime location clusters ( red dots ). The diagram is the result of a simulation run using random crime locations.
Of course, we cannot leave the police placements floating at random locations. So, I have added code to place them at the closest point on a way downloaded from Open Street Map to the crime clusters' center of gravity.