1

I have two lists of addresses, List 1 and List 2. I want to find the nearest neighbors of the list--but without assigning more than one point to any point. So say point 1A is the nearest neighbor of points 2A and 2B, but point 2A is closer. Then I want point 1A to match with point 2A, and point 2B to match with its own next nearest neighbor. Basically, every point is paired and there are no 3+ point clusters.

Is this possible to do using R?

  • 1
    Do you have the same number of points in List 1 and List 2? A sequential algorithm over List 2 like you describe could end up with the last pair being really far apart - which might not be ideal for your application. Would you rather construct a permutation of List 1 onto List 2 that minimises the total distances? That's an interesting problem... – Spacedman Sep 26 '18 at 21:30
  • There aren't the same number of points in each list, so one list could end up having extra points remaining. Right now I have been researching matching algorithms like the Hungarian method, but so far I am at a loss at how to implement them. – JenJen Sep 26 '18 at 21:36
  • So what happens when there's a different number of points and all the points in List 1 have been assigned neighbours from List 2? What to do with the remaining points in List 2? – Spacedman Sep 26 '18 at 21:42
  • So this is to assign volunteers to different locations, and there are fewer volunteers than locations. In that case those locations would not get a volunteer. – JenJen Sep 26 '18 at 22:37
  • and the other way round some volunteers won't get a location. So its okay to always loop over the smaller set and allocate neighours from the larger set? – Spacedman Sep 27 '18 at 7:02
4

Here's a sequential algorithm that used FNN::get.knnx to get the nearest neighbour of each point in list1 in succession, dropping the nearest neighbour from list2 and keeping track of its index in the original list2:

pairup <- function(list1, list2){
    keep = 1:nrow(list2)
    used = c()
    for(i in 1:nrow(list1)){
        nearest = FNN::get.knnx(list2, list1[i,,drop=FALSE], 1)$nn.index[1,1]        
        used = c(used, keep[nearest])
        keep = keep[-nearest]
        list2 = list2[-nearest,,drop=FALSE]
    }
    used
}

Sample usage on 100 random points in both sets in unit square:

> p1 = cbind(runif(100), runif(100))
> p2 = cbind(runif(100), runif(100))
> m12 = pairup(p1,p2)

quick plot function:

segs <- function(p1, p2, map){
    plot(rbind(p1,p2),type="n",asp=1)
    points(p1, col="green")
    points(p2, col="red")
    segments(p1[,1] , p1[,2], p2[map,1], p2[map,2])
}

segs(p1, p2, m12)

enter image description here

As you can see some of the neighbours are close but as the last few points are done there's not many left from list 2 so the distances are large.

If what you really want is to minimise the total distance between matched pairs from List 1 and List 2 then although this is pretty good, there are probably better algorithms.

As a quick test I tried matching random permutations of List 1 to List 2. For 1000 points in each set, generated as uniform on a unit square, and doing 10000 random permutations, the total distance ranged from about 490 to 550. Seems reasonable since you have 1000 distances in a square of side 1, so on average they are length=0.5. In contrast my pairup function returned an arrangement with a total distance of about 58.

I would be tempted to use pairup to get an initial good solution, and then borrow methods from things like the travelling sales problem to refine it by making adjustments, working on the longer paths first. Obviously changing one path is going to have a ripple effect on the whole set, so there's still a bit of programming to do...

Another idea might be to keep track of how isolated every other point in List 1 gets when a point in List 2 is allocated, and then dealing with those isolated points before they get too isolated. So instead of iterating over 1 to N, the order would be to deal with the point with the largest nearest neighbour next.... This might be fairly easy to implement, in fact its taken me about half an hour. It generates good solutions but with total distance as the criterion it doesn't seem to be as good as the iterative approach of pairup. I suspect this is because pairup is likely to have fewer, but longer pair distances once it gets to the end of its algorithm, but my new algorithm, pairupfar will have on average longer distances but fewer extreme ones.

Anyway, I suspect this is nothing new and there is extensive literature out there on this in the operational research and management science realm.

1

Spacedman's answer pointed me in the right direction to answer my own question. I implemented the Hungarian algorithm through use of of solve_LSAP from the clue package.

For my purposes I first created a distance matrix between my locations using distm, and then fed that into solve_LSAP. Here is a simpler example, inspired by Spacedman:

library(clue)
p1 <- cbind(runif(100),runif(100))
p2 <- cbind(runif(100),runif(100))
m <- dist(p1,p2)
hungarian <- solve_LSAP(m)
plot(rbind(p1,p2),type="n",asp=1)
points(p1, col="green")
points(p2, col="red")
segments(p1[,1] , p1[,2], p2[hungarian,1], p2[hungarian,2])

Hungarian output example

This should optimize the total distance over the entire set. This problem is matching people to locations with the idea that it would minimize driving distance for everyone. solve_LSAP appears to produce the "fairest" solution. I'll probably have more locations than people so it will shorten driving distance even more.

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.