0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Could you explain "roughly the same"? What degree of imbalance would be acceptable? $\endgroup$
    – Marcus Ritt
    Mar 24, 2011 at 14:32
  • $\begingroup$ 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. $\endgroup$
    – rubenfonseca
    Mar 30, 2011 at 15:42
  • $\begingroup$ 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. $\endgroup$
    – David Cary
    Apr 7, 2011 at 19:56

3 Answers 3

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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."

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Hi David, I think it would be better if you combine your answers into one. $\endgroup$
    – Kaveh
    Apr 8, 2011 at 8:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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