I tried to simplify it, I hope I didn't make it too confusing in the process (I tend to do that a lot).
Imagine you have N houses, on a standard euclidean 2D plane. You also have N "packages", each of which contains several "objects" of different types, let's call them A, B, C, etc. You know the content of all boxes beforehand, but can't change them (they're randomly generated). 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: (0,0)
- House 2: (0, 5)
- House 3: (12, 0)
Now, imagine that you need to send one package to every house, and you know that the person who lives in the house needs to use one or more of the objects, but you DON'T know which of them they need. If the object they need is in the package they receive, great. If it's not, they will have to travel to the nearest house that has it, use it there, and go back to their house. We want to minimize the distance they will have to travel. Example:
- 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.
So obviously I need to minimize the sum of the shortest distance between every location and every type of object. I was thinking along the lines of calculating the "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, hopefully without having to do a particle simulation or something. But is this a well-known problem? It seems like something that should have been studied before, but I have no idea where to look for it (other than clicking random Wikipedia links).
We have to use a general optimization algorithm to improve the result by the way, but obviously I want to have a good starting solution if I can.