League and Divisions problem (np-hard)

Question

There is a League. And there are Divisions, that are the disjoint subsets of this League. There are n teams (unique locations are given, let's assume it's x and y for simplicity reasons). Every team must belong to exactly one Division. There are min and max - minimal and maximal amount of teams per division. Every team travels once to every other team inside one division. The target is to divide the league into divisions in a way, that the total traveling distance for the whole league is minimized.

Input:
n - amount of teams
min - minimum teams per division
max - maximum teams per division
teams - array of teams (name,x,y)

Input example:
n = 10
min = 2
max = 3
teams = [{a,1,1},{b,2,1},{c,5,3},{d,9,8},{e,6,8},{f,5,1},{g,1,7},{h,6,6}{i,7,2},{j,2,7}]

Output:
League

Output example:
League = [[a,b,c],[d,e],[f,g,h],[i,j]]
One sub array stands for one division. It means that the teams a,b and c belong to one division and each of them will visit every other team from this division.
This is not the optimal solution

This is what an output of a real-world case could look like

I am struggling with selecting an algorithm for this issue. It is not a traveling salesman since we are not interested in simply visiting all of the locations. Neither the clustering approach is applicable since we need to keep the min and max in mind and it's not what clustering does. What kind of algorithms can be used to tackle down this problem?

Answer 1

Balanced k-means clustering would probably work reasonably well here. Unfortunately the true cost structure can't be modelled with this (or any clustering algorithm that I know of); you would need to instead use some increasing function of the distance from the cluster centroid (this could be just the distance itself, or e.g. a small positive power). Balanced k-means will then try to cluster the teams into divisions in such a way that the sum of these per-team costs is minimised, while enforcing a hard upper bound (your max) on the number of teams in a division. The chosen number k of divisions, as well as these upper bounds, implies a lower bound on the division size, though this won't necessarily agree with your desired min. Hopefully, playing with the parameters a bit could get you close.

The idea is basically the same as regular k-means clustering, except that in the assignment phase, instead of assigning each point (team) to its nearest cluster (division), you solve an instance of the Assignment Problem in which each team is represented as a worker and each division is represented as max job slots: this enforces that each division receives at most max teams. The problem can be solved with e.g. the Hungarian algorithm.

There's a paper here, but it seems to be behind a paywall unfortunately: https://link.springer.com/chapter/10.1007/978-3-662-44415-3_4

Answer 2

One approach would be to use a local search optimization method, such as hill climbing or simulated annealing.

The configuration describes the assignment of teams to divisions; and you can define a set of operations that can be applied to a configuration to change it to another one (e.g., pick two teams in different divisions and swap which division they are assigned to; pick a team in a division with at least min+1 teams, and move it to a division that has at most max-1 teams). Then, you can apply one of those algorithms to try to find an optimal assignment.

The problem is NP-hard (I suspect), so I don't expect any algorithm to be always efficient and always find the optimal solution, but this might give a "good-enough" solution.

To get better results, you might repeat it multiple times with different starting configurations. Also, the choice of the initial configuration might be important to its success. You might try using a clustering algorithm to generate a starting configuration (e.g., assign cluster centroids using k-means clustering, with that idea that each centroid reflects a single division, and then iterate over the centroids in a round-robin fashion and for each centroid, find the unassigned team that's closest to it and assign it to that division, until all teams are assigned).