Pairing cartesian coordinates for minimum distance I have n start locations, defined by their x,y coordinates on a two-dimensional plane.
I have a further n destination locations (again, as x,y coordinates) that differ from the start locations.
All locations are effectively random.
I'd like to pair each start location with one of the destination locations, in such a way as to minimize the sum of the distances between the start and destination locations for each pair.
I have multiple sets of points I'd like to solve, with N<=15.
I've tried to use Excel to solve. I can calculate the distance between any pair of x,y coordinates by: =SQRT((x1-x2)^2+(y1-y2)^2)) I thought I'd just list the start locations and then permutate the list of destination locations while summing the distance results. The trouble with that approach is that the number of permutations for the sort order of a list of 15 items is 15 factorial which is a discouragingly huge number (over a trillion). Any ideas how to approach this?
 A: This is the linear assignment problem, and it can be solved in polynomial time via specialized algorithms or linear programming.
Here is SAS code to solve the problem for your sample data.  The first approach uses the linear programming solver, and the second approach uses the linear assignment problem algorithm implemented in the network solver.
data SourceData;
   input x y @@;
   source = compress('Source_'||_N_);
   datalines;
0 7  0 17  6 1  8 7  16 17  24 7  24 17  40 7  50 7  50 15  52 20  60 11
;

data DestinationData;
   input x y @@;
   destination = compress('Destination_'||_N_);
   datalines;
2 5  2 16  6 24  10 22  16 26  28 16  20 26  40 22  44 6  48 28  54 30  38 24
;

data PlotData;
   set SourceData(in=IsSource) DestinationData;
   group = IsSource;
run;

proc optmodel;
   /* declare parameters and read data */
   set <str> SOURCES;
   set <str> DESTINATIONS;
   num xs {SOURCES}, ys {SOURCES};
   num xd {DESTINATIONS}, yd {DESTINATIONS};
   read data SourceData into SOURCES=[source] xs=x ys=y;
   read data DestinationData into DESTINATIONS=[destination] xd=x yd=y;
   num cost {s in SOURCES, d in DESTINATIONS} = sqrt((xs[s] - xd[d])^2 + (ys[s] - yd[d])^2);

   /* declare linear programming (LP) problem */
   var Assign {SOURCES, DESTINATIONS} >= 0;
   min TotalCost = sum {s in SOURCES, d in DESTINATIONS} cost[s,d] * Assign[s,d];
   con AssignSource {s in SOURCES}:
      sum {d in DESTINATIONS} Assign[s,d] = 1;
   con AssignDestination {d in DESTINATIONS}:
      sum {s in SOURCES} Assign[s,d] = 1;

   /* call LP solver */ 
   solve;

   /* create output data set */
   create data SolutionData from 
      [source destination]={s in SOURCES, d in DESTINATIONS: Assign[s,d].sol > 0.5}
      x1=xs[s] y1=ys[s] x2=xd[d] y2=yd[d]
      function='line' drawspace='datavalue';
quit;

/* plot solution */
proc sgplot data=PlotData sganno=SolutionData noautolegend;
   scatter x=x y=y / group=group;
run;



proc optmodel;
   /* declare parameters and read data */
   set <str> SOURCES;
   set <str> DESTINATIONS;
   num xs {SOURCES}, ys {SOURCES};
   num xd {DESTINATIONS}, yd {DESTINATIONS};
   read data SourceData into SOURCES=[source] xs=x ys=y;
   read data DestinationData into DESTINATIONS=[destination] xd=x yd=y;
   set LINKS = SOURCES cross DESTINATIONS;
   num cost {<s,d> in LINKS} = sqrt((xs[s] - xd[d])^2 + (ys[s] - yd[d])^2);
   set <str,str> ASSIGNMENTS;

   /* call network solver */
   solve with network / linear_assignment direction=directed links=(weight=cost) out=(assignments=ASSIGNMENTS);

   /* create output data set */
   create data SolutionData from 
      [source destination]={<s,d> in ASSIGNMENTS}
      x1=xs[s] y1=ys[s] x2=xd[d] y2=yd[d]
      function='line' drawspace='datavalue';
quit;

/* plot solution */
proc sgplot data=PlotData sganno=SolutionData noautolegend;
   scatter x=x y=y / group=group;
run;

The solution found by @Cesareo is indeed optimal:

