Imagine we have N houses, on a standard euclidean 2D plane. We also have N "packages", each of which contains several "objects" of different types, let's call them A, B, C, etc. We know the content of all boxes beforehand, but can't change them (they're randomly generated).

We need to send one package to every house, and we know that the person who lives in the house will need to use one or more of the objects, but we can't know which of them they will need. To use the object, they will travel to the nearest house that has it (ideally their own), use it there, and go back to their house. We need to assign a package to each house to minimize the potential distance they will have to travel.

For example:

  • Package 1 contains B, C, D, E
  • Package 2 contains A, B, D, F
  • Package 3 contains A, E, F, G
  • House 1 is at (0,0)
  • House 2 is at (0, 5)
  • House 3 is at (12, 0)

We send packages 1, 2 and 3 to houses 1, 2 and 3:

  • Owner of house 1 needs A and B: travels 5 to house 2 to get A (and back, but we're not counting that).
  • Owner of house 2 needs C and G: travels 5 to house 1 to get C, goes back, then 13 to house 3 to get G (total = 18)
  • Owner of house 3 needs A and G: travels 0 to their own house.

Total distance = 23

Since we can't know what they will want, we assume everyone needs everything. This means I need to minimize the sum of the shortest distance between every location and every type of object. Is this a known problem? How can I make an approximation algorithm for it? It sounds simple enough but I'm stumped, I have no idea how to search for it.

I was thinking along the lines of calculating a "differentness" of every package to every other one, then trying to place the "most different" packages closer to each other and the more similar ones further, but I don't really know how to do that either.

  • $\begingroup$ How many houses and objects do you have? This should be solvable using the big sledgehammer of SAT (or ILP) if the number of them is not too large. Of course, the worst-case running time might be exponential, but in practice SAT solvers often seem to do better on many problems, so this might just work well enough in practice for your needs, if the number of objects/houses isn't too large. $\endgroup$ – D.W. Mar 22 '14 at 3:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.