4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ How does the effort required to visit them all depend on the matrix and the assignment of groups? I don't understand how the effort is defined. Is the effort to visit a group the length of the shortest path that visits every node in the group at least once, without visiting any node outside the group? Is the total effort the sum of the efforts associated with each individual group? Are you looking for a practical solution or the theoretical complexity? If you want a practical solution, about how large is the group and about how large are $x,y$? $\endgroup$ – D.W. Feb 22 '18 at 23:58
  • $\begingroup$ @D.W. Sorry about the confusion. I think effort would be better defined as the shortest path that visits every node in the group at least once as you said it. But it's not set in stone. I'm looking for a practical solution. In one of the examples i have 91 locations, and i would like groups to have between 8 and 11 locations. $\endgroup$ – tiagosilva Feb 23 '18 at 1:00
  • $\begingroup$ OK. Can you edit the question to incorporate that information into the question, so people don't have to read the comments to understand the question? If the problem statement isn't set in stone, I think you probably first need to figure out what exactly the problem statement is, before you can look for algorithms to solve it. $\endgroup$ – D.W. Feb 23 '18 at 6:10
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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