# What category is this problem?

My first question, please excuse me if its too basic.

I have a matrix of evenly spaced geographical points; say 10 x 10, which I will call seed points. Each seed point has a lat/long and the spacing can vary.

Then I place $n$ random points on the same matrix. I call these demand points.

What algorithm can I use to calculate a variable $n$ seed points which will minimize the distance to all the demand points in the matrix?

The user will decide if he/she needs a single seed or multiple seeds to satisfy all the demand points. If a single seed is selected its similar to an average of the demand points, a centroid. But what if multiple seed points need to be selected, say 2. So the problem becomes, which two seed points if selected would give the minimum distance to all the demand points. Each demand point will connect to a single seed and not both. What I would ideally like is this problem identified as a MIP / LP problem, its name given (i.e. "Travelling Salesman"). Then I can go and research how to solve it using a solver. But that is only if it is possible with a solver.

• I believe this is technically an optimization problem. You could go about trying to solve it by computing a centroid of the demand points and then finding the point in the seed points that is closest to this centroid. Given that the seed points aren't time varying, you could stick them in a KDTree and do a nearest neighbor search using the centroid of the demand points to find the optimal seed point. – spektr Jan 12 '16 at 22:27
• @choward thanks for the response, unfortunately I oversimplified the description of my problem. Please see my edit. – sprocket12 Jan 13 '16 at 11:44
• I think it would greatly help if you used formulas to concisely explain what you mean by "calculate a variable $n$ seed points which will minimize the distance to all the demand points in the matrix". – Wolfgang Bangerth Jan 13 '16 at 14:49
• @WolfgangBangerth unfortunately I do not know the maths notation, but I can draw a picture which I hope will explain it, please see my edit. – sprocket12 Jan 13 '16 at 15:20
• This sounds like a variant of either the k-nearest neighbor or the k-means problem. – Christian Clason Jan 13 '16 at 15:33

This is actually a trivial problem to solve for a moderate number $k$ of "stations" (i.e., the subset of seed points that serve the demand points):
• Try $k=1$. For each of your $i=1\ldots N=10^2$ seed points, compute the sum of distances between the demand points and a proposed station at $i$: $D^{(1)}_i=\sum_{\nu=1}^n \|x_{\text{demand},\nu} - x_{\text{seed,i}}\|$. Among all possible station locations, choose the location $i^\ast$ that minimizes $D^{(1)}_i$ and call the distances to the best location $D^{(1)}=D^{(1)}_{i^\ast}=\min_i D^{(1)}_i$.
• Try $k=2$. There are $N(N-1)/2$ possible locations for two stations. Let's say they are at seed points $i,j$. Then compute the sum of distances, $D^{(2)}_{ij}=\sum_{\nu=1}^n \min\left\{\|x_{\text{demand},\nu} - x_{\text{seed,i}}\|,\|x_{\text{demand},\nu} - x_{\text{seed,j}}\|\right\}$. Among these possibilities, select those locations $i^\ast,j^\ast$ that minimizes these distances and call the best distances $D^{(2)}=D^{(2)}_{i^\ast j^\ast}=\min_{i,j} D^{(2)}_{ij}$.
• Repeat for $k=3,4,\ldots$. The effort will quickly grow for larger $k$, but you're probably not interested in the case $k=100$ supply stations.
• Then compare $D^{(1)},D^{(2)},\ldots$ to see which one is smallest, and that is the number of stations you need.