5
$\begingroup$

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.

enter image description here

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – spektr Jan 12 '16 at 22:27
  • $\begingroup$ @choward thanks for the response, unfortunately I oversimplified the description of my problem. Please see my edit. $\endgroup$ – sprocket12 Jan 13 '16 at 11:44
  • $\begingroup$ 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". $\endgroup$ – Wolfgang Bangerth Jan 13 '16 at 14:49
  • $\begingroup$ @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. $\endgroup$ – sprocket12 Jan 13 '16 at 15:20
  • $\begingroup$ This sounds like a variant of either the k-nearest neighbor or the k-means problem. $\endgroup$ – Christian Clason Jan 13 '16 at 15:33
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you. A question I have is, does this method consider the requirement that when there are multiple "stations", each one cannot serve every "demand" point. The relationship is "station" 1 --> * demand points. So there will be a split, one station will take some, and the other will take others, this is the difficult part I think. $\endgroup$ – sprocket12 Jan 14 '16 at 11:19
  • $\begingroup$ The way I've described it, each demand point will be served by the closest supply station. You may have to modify things if that's not what you want. $\endgroup$ – Wolfgang Bangerth Jan 14 '16 at 19:18

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.