This sounds like it may be a NP-hard problem.
But perhaps a relatively simple heuristic will give good enough results, something like:
- use some arbitrary clustering algorithm to divide the N locations into k uneven clusters.
- Find the centroid of each cluster.
- Figure out which clusters have "too many" locations -- more than ceil(N/k).
- Figure out which clusters have "too few" locations -- less than floor(N/k).
- grow the clusters with "too few" locations by grabbing locations that are near the centroid of that cluster (but not already part of that cluster), preferentially stealing from clusters that have "too many" locations.
Repeat until close enough.
I agree that "exactly the same" may not be what you want.
If slightly more than half of your locations are on one island,
and slightly less than half are on another distant island,
and you have 3 employees,
it's probably better to (somehow) split the larger island among 2 employees
and give the slightly smaller island to the 3rd employee,
rather than forcing (at least) one employee to travel long distances over water in order to divide the N locations perfectly evenly among them.