<p>This sounds like it may be a NP-hard problem. But perhaps a relatively simple heuristic will give good enough results, something like:</p>

<p>Use one of the heuristic approximations to the <a href="http://en.wikipedia.org/wiki/travelling_salesman_problem" rel="nofollow">travelling salesman problem</a> to find a (relatively) short loop that passes through <em>all</em> 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.</p>

CC BY-SA 2.5
2011-04-07T20:12:35.907Z
2011-04-07T20:12:35.907Z
David Cary
<p><a href="https://stackoverflow.com/questions/5452576/k-means-algorithm-variation-with-equal-cluster-size">k-means-algorithm-variation-with-equal-cluster-size</a>
has Python code:
"A simple greedy postprocess after k-means may be good enough, if your clusters from k-means are roughly equal-sized."</p>

CC BY-SA 3.0
2011-09-12T10:59:37.177Z
2011-09-12T10:59:37.177Z
2017-05-23T12:40:09.333Z
Denis
<p>This sounds like it may be a NP-hard problem.
But perhaps a relatively simple heuristic will give good enough results, something like:</p>

<ul>
<li>use some arbitrary clustering algorithm to divide the N locations into k uneven clusters.
Then repeat:</li>
<li>Find the centroid of each cluster.</li>
<li>Figure out which clusters have "too many" locations -- more than ceil(N/k).</li>
<li>Figure out which clusters have "too few" locations -- less than floor(N/k).</li>
<li>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.</li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2011-04-08T08:06:46.727Z
Hi David, I think it would be better if you combine your answers into one.
Kaveh
CC BY-SA 2.5
2011-04-07T20:07:52.433Z
2011-04-07T20:07:52.433Z
David Cary
<p>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.</p>

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

<p>Is this possible? Is there a known algorithm that could solve this?</p>

CC BY-SA 2.5
2011-03-24T14:32:14.670Z
Could you explain "roughly the same"? What degree of imbalance would be acceptable?
Marcus Ritt
CC BY-SA 2.5
2011-03-30T15:42:46.823Z
Honestly I expect the same number of elements. But I know it's probably easier if I relax to "roughly the same" number of elements. I guess I accept a pretty good degree of imbalance.
rubenfonseca
CC BY-SA 2.5
2011-04-07T19:56:17.690Z
Something else to think about:
Just because one group of destinations covers less (convex hull) area than another doesn't mean they will take less time to physically visit on Earth. Historical accidents in highway placement make some places much further apart (in travel minutes) than you might think from their as-the-crow-flies distance.
David Cary
<ds.algorithms><clustering>
clustering (lat,lng) pairs, with clusters having the same number of elements
rubenfonseca
# clustering (lat,lng) pairs, with clusters having the same number of elements

(Asked by: username_0 on 2011-03-24)

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?

**Tags:** ds.algorithms, clustering
> **Comments:**
> **username_1**: Could you explain "roughly the same"? What degree of imbalance would be acceptable?  
> **username_0**: Honestly I expect the same number of elements. But I know it's probably easier if I relax to "roughly the same" number of elements. I guess I accept a pretty good degree of imbalance.  
> **username_2**: Something else to think about: Just because one group of destinations covers less (convex hull) area than another doesn't mean they will take less time to physically visit on Earth. Historical accidents in highway placement make some places much further apart (in travel minutes) than you might think from their as-the-crow-flies distance.  

---

## 3 answers

### Answer by username_2 on 2011-04-07. Score: 1 | Accepted answer

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](http://en.wikipedia.org/wiki/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.


---

### Answer by username_3 on 2011-09-12. Score: 1

[k-means-algorithm-variation-with-equal-cluster-size](https://stackoverflow.com/questions/5452576/k-means-algorithm-variation-with-equal-cluster-size)
has Python code:
"A simple greedy postprocess after k-means may be good enough, if your clusters from k-means are roughly equal-sized."


---

### Answer by username_2 on 2011-04-07. Score: 0

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.
  Then repeat:
* 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.

> **Comments:**
> **username_4**: Hi David, I think it would be better if you combine your answers into one.  

---

