OK, this is a fun one, but I don't have time right now to tackle it. Maybe later tonight... I'll say straight out, I'm not a spatial expert, but have done a bit with spatial data over the years.
One of the key facets of this type of problem is setting up the question correctly. Is this a predictive problem, or is it a location optimisation. In this case, as the clusters can take any shape, rather than choosing from possible clusters, this looks more like a predictive problem. I expect, that you've got an idea of the number of clusters whether it be closer to 10 or 1000. Having the distance from the most populous hex, rather than the centre of the cluster will be another issue to overcome, and may make it a multi-stage refinement.
- What I need to be able to do is form contiguoous clusters of these hexagons with constraints on the total premises able to be contained within a cluster and the maximum distance of any hexagon's centroid from that of the cluster 'core' which should be the mostpremises-dense hex in a given cluster.
So, they have to be contiguous but the cluster core is determined by the most premises-dense. I would need to play with it a bit to see what works, but my initial investigation would include:
- Sampling: I would use a Map Input to draw a shape around an area (London for instance) and spatially match that to the hexagons to sample a set that makes sense. This will enable playing with the data in a quicker timeframe.
- K-centroids clustering. Create a centroid (as X,Y) for each hexagon and use K-centroids to cluster them on distance. This will require some testing to play with the number of clusters. As you increase the number of clusters, processing time will increase dramatically.
- Putting weighting in based on the Premises somehow would be the key. Could be done brute force by basically creating multiple records to represent multiple premises, but that would definitely require rounding.
- The final solution will most likely involve the summarize tool to group the clusters as that has lots of options around spatial.
My theory being that if we created something for London, that could be expanded to the rest. Purely anecdotally, I would expect more dense areas to have different facets to the clusters in terms of hitting max premises rather than max distance and so analysing the clusters will be interesting.
One last thought, when clustering, the algorithms are comparing everything and so if you divided it up into X groups with overlapping segments then you could get faster processing, and a rough answer. No point comparing groups that are never going to be in the same cluster (Scotland and London for instance).
Hopefully, that provides some ideas at least.
