League and Divisions problem (np-hard) 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?
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