Hi.

This problem probably already here but I could not find the right words to find it.

I have a list with 1700 points (geographic coordinates) and a need to separate into 17 groups with 100 nearest. I mapped this as a graph where each node is the point and each edge weight is the real distance of points connected by this. Then the problem is how to partition this graph into 17 groups of 100 elements each that minimizes the sum of the inter-partition edges weight.

Someone has a better idea to map this problem?

I tried to use METIS but the best result was using the edge-cut that minimize the sum of the weights of the edges removed (for this case I use the inverse of the distance as weight). I also tried using k-means but it does not guarantee the number of elements in each group.

Thanks in advance!