From: Markus Schirp <mbj@...>
Date: 2010-09-17T08:08:21+09:00
Subject: Re: NP-Hard Geolocation Problem

Hi,

I'm not calling myself an expert on those problems, but here are my toughs:

In a first step you can classify each person to a "neighbor group", this 
group could include persons in a specified region.

So the rest of your solution can work with "group" distances instead of 
inter person distances. When the "neighbor groups" include enough 
persons you'll save computational resources.

You could vary the "neighbor group" region size on demand, in your 
example Southern California would/should get twice as much neighbor 
groups as NY.

Than your algorithm "just" has to choose "target groups" with no 
"neighbor group" duplicates to get an "initial solution".

Now you can start optimizing the "total-distance", just randomly (or 
more intelligently) interchange members between the target groups and 
calculate the total distance. Once you are happy you are done.

Possible Strategy for selecting an group member to interchange:

Look at group A, find two members A1 and A2 where (group) distance 
between A1, and A2 is minimal. Try to push A1 to another group without 
negatively affecting the "total-distance", if okay: proceed with group 
B, if not try to push A2, and so on.

Additionally you can apply any scheme from:

http://en.wikipedia.org/wiki/Combinatorial_optimization

Once I have to implement an Vehicle Routing Problem Solver in *evil* VBA 
(Bachelor Thesis for a friend), I did not do the math part, but it was 
an interesting challenge.

Please let me know how you solved your problem, I'll have to solve one 
similar in the future ;)

Regards,

Markus


On 09/16/2010 11:09 PM, J.R. Gutierrez wrote:
> I am trying to create a program that maximizes the distances of
> addresses in Y amount of groups, essentially trying to decrease the
> chance that you are in the same group as your neighbors.
>
> Here is an example n it's simplest form. Say there are four people, two
> living in Los Angeles, one in New York, and one in Chicago that needed
> to be divided into two groups. The logical grouping would be {LA, CHI}
> and {LA, NY).
>
> Now a more complex example. Imagine 1000 people, 400 of which reside in
> the Southern California area, 200 in the NY area, 100 in the Northern
> California area, and the rest peppered in the area within the country.
> We need to separate them into 16 groups. Ideally, depending on
> distances, there would be 400/16 SoCal residents in a group.
>
> I've been trying hard to find out how to characterize this problem in a
> way that can be calculated with a computer using Ruby. The only way I
> can get an optimal answer by brute-forcing the distance between X people
> (X! calculations) and then doing something with that information to
> divide them into evenly distributed groups. I've also tried to think of
> this as reverse gravity problem, where the closer two people live to
> each other, the more they repel each other when deciding groups.
>
> So my question is, is there any kind of similar problem where I can
> borrow some kind of algorithm to compute an optimal answer? Or can
> anyone at least point me in the right direction?