4

So, I have a packaging center A. And I have n points scattered around A. Let's call them i1, i2 ... in.

I have a maximum distance threshold, called D.

My task is to break those n points into groups of at maximum m each points. Each group cannot exceed m points, in such a manner that a person starting from A and going to all points belonging to a particular group is traveling for an optimized distance.

For example, A -> i1 -> i4 -> i10 -> A <= D

What I've described above is a TSP problem. Currently, what I've done is break them into clusters using the K-means algorithm and then manually break them down into more groups such that each group cannot have more than m points.

Is there a better approach to this problem?

In short, I'm looking for a clustering algorithm in which:

  1. Each cluster cannot exceed a particular number of points.
  2. Clustering happens on distance (latitude/longitude in my case).
5
  • 4
    K-means clustering?
    – Davislor
    Sep 26, 2015 at 2:22
  • Do you want to find just one valid clustering, or do you want to optimize the clustering according to some optimizing goal?
    – Doc Brown
    Sep 26, 2015 at 8:33
  • @DocBrown: Just optimiziing it. Sep 26, 2015 at 13:46
  • To help everyone understand the underlying (fundamental) issue, could you please try to perform some exhaustive search on a small-sized data set, and plot some diagrams on the optimal travel paths found, so that we can get an intuitive sense of what the optimal paths might look like? (This is a very non-scientific-formalism way of approaching the problem, but we as humans are far more comfortable and productive with this approach than the formalism approach.)
    – rwong
    Nov 25, 2015 at 18:17
  • Juste a note : clustering always happens on distance, you group two datas because they're somewhat "near" each other, whatever "near" means. But do you really need to cluster it ? This really seems more like a graph problems with the following constraints : the path cannot exceed k nodes. Each path of nodes has a value that correspond to the distance, the distance cannot exceed D.
    – Walfrat
    May 24, 2016 at 13:35

3 Answers 3

2

https://en.wikipedia.org/wiki/K-means_clustering

This is a massive research area, I mean defining whether you want to use centroids versus medoids alone changes the complexity of your algorithms. Simple answer is there are many ways documented. Without data it's hard to opine correctly. If you could start with a graph made on MATLAB or free Octave then you might find a suitable similar approach.

Octave is free and contains a k-means algorithm.

I recall Kurzweil's latest book How To Create a Mind described about his speech recognition clustering if you wanted an application example for context.

1

You could try another form of clustering: agglomerative hierarchical clustering.

Specifically, agglomerative hierarchical clustering begins with each observation in its own cluster; pairs of clusters are then merged as you move up through the hierarchy.

enter image description here

This clustering algorithm fits well the requirement that:

Each cluster cannot exceed a particular number of points

Also K-means clustering requires prior knowledge (or a vague idea) of K (or number of clusters), whereas in hierarchical clustering doesn't need the number of clusters as input.

Every major ML / scientific software implements hierarchical clustering (e.g. Octave linkage function, Mathematica Agglomerate function, SciKit AgglomerativeClustering object...).

0

Maybe look at https://en.wikipedia.org/wiki/Travelling_salesman_problem gives some algorithms you might want to consider. I'd probably go for nearest neighbour (NN) algorithm (a greedy algorithm) and pick a few different start points at random. Thats if you dont have a d-wave to throw at it.

Your Answer

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

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