How do I group a number of villages based on their distance to each other and total cumulative population size?

I have a vector file of say 100 village points attached to atable containing data on population size and so forth. I want to group these villages such that each group contains 5-6 villages with the cumulative population of size of 5000. Hence, distance and cumulative population size should be used in my clustering of villages. I have used grouping in ArcMap 10.2 with no success. I have ArcMap 10.2.


1 Answer 1


In terms of pseudo-code I am using these steps:

  1. Define criteria for neighbours using spatial join 'one to many'. In this case it is the polygons that touch each other enter image description here

  2. Connect neighbours by links enter image description here

  3. Use network analysis package, e.g. networkx to build a graph, with weights for all links =1.

  4. Define a number of groups (N) and iterate through combination of nodes, e.g. p=itertools.combinations(aBig, 2), where aBig is a list of all graph nodes.
  5. Calculate totals of population closest to 1st and 2nd node in a pair. Compute ratio. Break, if it is equal to (N-1) within tolerance of course. The group with a smaller population is your 1st group.
  6. Reduce N by 1 and go to step 5 if N>0, otherwise stop

This show 1117 polygons split into 5 groups with approximately equal population enter image description here and this - with more or less the same area enter image description here

Note that multiple solutions are possible depending on start node. In the examples shown it was in the lower left corner.


Not the answer you're looking for? Browse other questions tagged or ask your own question.