traveling salesman - Need Algorithm to Allocating Managers to Stores

Question

Suppose you have "n" managers and "n" stores all located randomly across a geographic area. I need to be able to assign each manager to a store. The managers will travel daily from their homes to their assigned store. In general I'd like to minimize the daily distance travelled. This can be interpreted in two ways:

1. Minimize the average daily travel distance (which is also the same as minimizing the total travel distance.

2. Minimize the maximum travel distance for any single manager

Is this a known problem? Are there any obvious algorithms to solve it? It seems similar to the traveling salesman problem but it's not quite the same.

question from:https://stackoverflow.com/questions/65865175/need-algorithm-to-allocating-managers-to-stores

Answer 1

Both can be solved polynomially

I'll quickly cover both ways to define an optimal allocation as described in the question. Note that I won't make any assumption on the traveling times, such as triangle inequality. Of course such a property is likely to hold in practice, and there may be better algorithms that use these properties.

Minimize total distance

For this instance, we consider the managers and the stores to be a weighted complete bipartite graph. We then want a matching that minimizes the sum of the weights.

This is called the Balanced Assignment Problem, which is a specific case of minimum/maximum matching. Because the graph is bipartite, this can be solved polynomially. Wikipedia lists a couple of algorithms for solving this problem, most notably the Hungarian algorithm.

Minimize maximum distance

If we wish to minimize the maximum distance, we can find a solution through a binary search. Specifically, we binary search over the maximum distance and attempt to find a matching that does not violate this maximum distance.

For any given maximum distance x, we create the bipartite graph that has edges between manager M and store S if and only if d(M, S) < x. We then try to create a complete matching on this bipartite graph with any bipartite matching algorithm, and through success and failure complete the binary search for the smallest x that allows for matching, thus minimizing the maximum distance.