Looking for a good algorithm to divide the nodes of a complete graph into groups

Question

I have a set of locations, around 100, I want to divide into groups.

I say these locations are in a graph because the geometric proximity (straight line distance) doesn't matter to me, and I have a matrix of the distance (non straight line distance) and time, that would take to travel from any location to another. Either one, time or distance, can be used as edge weights for this complete graph.

The idea is to assign a group of locations to a person that will visit the locations in it, (there is no obligation to do a traveling salesmen or visit them in a specific order or to avoid passing on a repeated node).

Ideally these groups have a minimum of 8 locations, and a maximum of 11 locations. (For simplicity maybe a set amount of 10 per group would suffice). And I want to minimize the sum of weights needed to visit all the nodes in a group at least once.

All locations must belong to one group, and only one group.

Where do i go from here? I'm kind of rusty on graph theory. Is there a good algorithm for this already? It doesn't need to be optimal and I do understand that this will probably be an NP hard problem and not very efficient. Because i'm treating it as a graph i keep finding graph algorithms but most i find are not suited for weighted graphs or complete graphs.

Answer 1

One possible approach would be to use local search. This probably won't find the optimal solution, and there are no guarantees, but if you're lucky, it might find a solution that is decent.

In local search, given a candidate solution, you need a way to randomly pick a neighboring solution. In the context of your problem, one way to do that might be to pick a pair of groups and a vertex $v$ in the first group, and remove $v$ from the first group and add it to the second group. (This will only be legal if the first group is not already at the minimum size, and the second group is not already at the maximum size.)

You could then apply a technique like simulated annealing. You'll probably need to experiment with the tuning parameters, and experiment with the method, to see whether it produces useful solutions or not.

This will require you to be able to quickly compute the effort associated with a single group, given the list of vertices in the group. You might want to ask separately about that problem. It sounds related to the Traveling Salesman Problem, which is NP-hard, but there are off-the-shelf solvers that implement sophisticated algorithms for finding a solution, and for the group sizes you are talking about (8-11 vertices), this might be relatively fast. The twist in your situation is that the TSP doesn't allow visiting a vertex more than once, but it sounds like you are willing to allow repeated visits, so we need to make adjustments to make to allow that. The following method should suffice: use an all-pairs shortest paths algorithm to compute the distance $d(u,v)$ between each pair of vertices, then replace the edge weight on the edge $u \to v$ with $d(u,v)$, then find the TSP solution; after this adjustment, no repeated visits will be needed any longer.