clustering (lat,lng) pairs, with clusters having the same number of elements Imagine you have a list of (lat,lng) pairs. You have k employees. And you want each employee to visit roughly the same number of places, making the least distance possible.

I've tried to solve this with K-Means clustering, but found that it didn't produce clusters with the same number of elements.

Is this possible? Is there a known algorithm that could solve this?
This sounds like it may be a NP-hard problem. But perhaps a relatively simple heuristic will give good enough results, something like:

Use one of the heuristic approximations to the travelling salesman problem to find a (relatively) short loop that passes through all of your N locations.
Then arbitrary pick some location on that loop as a "starting" point location number 0, and number each location along that path from 0 to (N-1).
Each employee i (from 0 to k-1) gets the approximately N/k consecutive locations along that loop, from location i*N/k to location (i+1)*N/k - 1.