Distance minimization problem

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

User avatar
3rdtry
Posts: 152
Joined: Sat Feb 16, 2013 1:46 pm UTC

Distance minimization problem

Postby 3rdtry » Thu Mar 20, 2014 7:06 pm UTC

Yes, this is homework (just a small part of a larger project though). But I've been thinking about it for a few days and I'm stumped. There's probably a simple answer but I don't know where to go from here, so some help would be appreciated.

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:
Spoiler:
Packages:
  • Package 1 contains B, C, D, E
  • Package 2 contains A, B, D, F
  • Package 3 contains A, E, F, G
Houses:
  • 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:
Spoiler:
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.


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.

AndyG314
Posts: 99
Joined: Mon Feb 11, 2008 5:16 pm UTC
Location: Waltham MA
Contact:

Re: Distance minimization problem

Postby AndyG314 » Sat Mar 22, 2014 12:07 am UTC

I've never heard of this problem before, it has elements of the traveling salseman (Which is NP Hard). If I were to guess, I would say that this problem is also NP hard, but I don't know that, perhaps there is an elegent solution.

Also, since you don't know what items the homeowners need, you don't know what the shortest path to pick, there are two options for optimizing, the best worst case distance, or the best avarage distance, they may be distinct. Also do you need an answer that is best, or mearly good? Travling salseman is NP hard, but you can get good results that are much easier. (google maps and mapquest essentially do this)

When you are trying to come up with an algorythim, it can be educational to start with a brute force solution, then focus your inprovements where the brute force solution is most ineffeciant. The brute force solution would be O(n!), where n is the number of houses/packages. You should be able to do better than that, but who knows. I can't think of anything better than brute force, for all house/package combos compute the worst case/avarage walking distance.

If you knew what homeowners needed what, ahead of time, you could do better than O(n!) easily.
If it's dead, you killed it.

Tub
Posts: 472
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Distance minimization problem

Postby Tub » Sat Mar 22, 2014 2:39 pm UTC

I don't see any relation to the TSP; mostly I don't see a trivial way to reduce TSP to the problem at hand. It's certainly in NP, but I'm not sure if it's NP-hard.

AndyG314 wrote:If you knew what homeowners needed what, ahead of time, you could do better than O(n!) easily.

But we do know. Barring any information about their needs, we optimize under the assumption that everyone needs everything. If that helps you go below O(n!) without employing a heuristic, please show.


My first idea was to order the houses by their centrality (sum of distance to all other houses) and packages by their utility value (packages with many objects have high utility value; packages with rare objects have high utility value), then assign the package with the highest utility to the most central house. You can find a formula for the utility value that maps pretty well to the problem at hand. It's O(n^2) for an initial solution.
It may break down in a case where only two zorblaxes exist, and they both end up right in the center instead of evenly spread out, but I guess that's what the iterative optimization phase is for.

If you have a different heuristic for an initial solution, just run both and start with the better one.

AndyG314
Posts: 99
Joined: Mon Feb 11, 2008 5:16 pm UTC
Location: Waltham MA
Contact:

Re: Distance minimization problem

Postby AndyG314 » Tue Mar 25, 2014 2:33 am UTC

But we do know. Barring any information about their needs, we optimize under the assumption that everyone needs everything. If that helps you go below O(n!) without employing a heuristic, please show.


What I was thinking was that if you knew what home owners needed what you could start by placing goods that perfictly matched needs with those who needed them, this would reduce the number of packages left and you could then do single matches with good stuff for neighbors etc... This solution doesn't get you a best solution, but probably a good one. I can't think of any way to do better than O(n!) and get the best possible solution.
If it's dead, you killed it.

User avatar
3rdtry
Posts: 152
Joined: Sat Feb 16, 2013 1:46 pm UTC

Re: Distance minimization problem

Postby 3rdtry » Wed Mar 26, 2014 1:10 pm UTC

Thanks for your help everyone. I'm pretty sure it's supposed to be the Quadratic assignment problem, which as far as I can tell is solved in practice by optimization algorithms (genetic, ant colony, tabu search..).

It's not exactly the same, since in the QAP you define flows between "packages", then find the solution, whereas here the "flow" varies depending on the solution: for example, if you have two identical packages and you place them such that one is slightly closer to the rest of the houses than the other one, one of them will get no "incoming" flow at all. But I suppose the "differentness" between packages will be a good approximation.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 4 guests