# NP-Hard Geolocatoin Problem

**URL:** <https://www.ruby-forum.com/t/np-hard-geolocatoin-problem/195102>\
**Category:** Ruby\
**Created:** [September 16, 2010, 11:09pm UTC](https://www.ruby-forum.com/t/np-hard-geolocatoin-problem/195102 "2010-09-16T23:09:06Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![jrgutier](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/b3f665/32.png) [@jrgutier](https://www.ruby-forum.com/u/jrgutier)\
**Post date:** [September 16, 2010, 11:09pm UTC](https://www.ruby-forum.com/t/np-hard-geolocatoin-problem/195102/1 "2010-09-16T23:09:06Z")

</div>

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 A., 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?

---

<div class="post-metadata">

**Author:** ![jrgutier](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/b3f665/32.png) [@jrgutier](https://www.ruby-forum.com/u/jrgutier)\
**Post date:** [September 17, 2010, 1:09am UTC](https://www.ruby-forum.com/t/np-hard-geolocatoin-problem/195102/2 "2010-09-17T01:09:01Z")

</div>

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:

> **[Combinatorial optimization](https://en.wikipedia.org/wiki/Combinatorial_optimization)**
>
> Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so speci Co...

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

---

<div class="post-metadata">

**Author:** ![jrgutier](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/b3f665/32.png) [@jrgutier](https://www.ruby-forum.com/u/jrgutier)\
**Post date:** [September 17, 2010, 4:01am UTC](https://www.ruby-forum.com/t/np-hard-geolocatoin-problem/195102/3 "2010-09-17T04:01:41Z")

</div>

I found a heuristic solution that has complexity O(n\*log(n)) per  
step (for 1000 elements and 16 areas, I got a good solution in 500  
steps).

The code has some constraints that are easy to remove:

- All areas must have exactly the same amount of elements
- Distances calculated assuming flat space (just rewrite Point’s  
function distance\_to)

It’s easy to customize heuristic params and remove those  
constraints

Ps.: Not sure about the complexity, you can check yourself, because  
I solved the problem during a sleepless, but it’s gone now and I’m  
going to bed. If you have some doubts ask me and I’ll answer  
tomorrow…

Solution:

class Point  
attr\_accessor :x, :y, :distances, :at  
def initialize(x, y)  
@x, @y = x.to\_f, y.to\_f  
end

def distance\_to§  
Math.sqrt sum\_of\_squares\_to§  
end

def sum\_of\_squares\_to§  
(self.x-p.x)\*\*2 + (self.y-p.y)\*\*2  
end

def calc\_distances\_to(areas)  
@distances = areas.inject({}){ |d, a| d[a] = distance\_to a.mean;  
d }  
end

def self.new\_by\_rand  
Point.new(rand(100), rand(100))  
end

def to\_s  
“(#{x},#{y})”  
end  
alias :inspect :to\_s  
end

class Area \< Array  
def mean  
@mean || mean!  
end

def entropy  
self.inject(0) do |ent, p|  
ent += mean.sum\_of\_squares\_to p  
end  
end

def mean!  
ps = self.inject( Point.new(0, 0) ) do |ps, p|  
ps.x += p.x  
ps.y += p.y  
ps  
end  
ps.x = ps.x/self.size  
ps.y = ps.y/self.size  
self.sort\_by!{ |p| p.distance\_to ps }  
@mean = ps  
end

def fix!  
self.each do |p|  
p.at = self  
end  
end

def self.refine(areas, points, n)  
area\_size = areas.first.size  
refresh\_distances(areas, points)  
doubt\_points = areas.inject([]) do |dp, area|  
dp.concat area[n…-1]  
end

```
doubt_points.each do |point|
  point.at.delete point
  point.at = nil
end

doubt_points.each do |point|
  ordered_areas = point.distances.sort_by{ |k, v| v }
  nearest_area, distance = ordered_areas.pop
  until(nearest_area.size < area_size)
    nearest_area, distance = ordered_areas.pop
  end
  nearest_area << point
  point.at = nearest_area
end

```

end

def self.refresh\_distances(areas, points)  
areas.each &:mean!  
points.each do |p|  
p.calc\_distances\_to areas  
end  
end

def self.all\_areas\_same(areas\_1, areas\_2)  
areas\_1.each\_with\_index do |a, i|  
return false if areas\_2[i] != a  
end  
return true  
end

def self.refine\_until\_good\_solution(areas, points, good\_ratio =  
0.01, max = 10\_000, n = (areas.first.size_0.9).to\_i, doubt\_region =  
max_0.05)  
areas, points = areas.clone, points.clone  
current\_entropy = last\_entropy = areas.inject(0){ |ent, a| ent +=  
a.entropy }  
enhance = 10\*good\_ratio  
count = 0  
best\_solution = areas.clone  
best\_entropy = current\_entropy  
while( count \< doubt\_region || ( count \< max && enhance \>  
good\_ratio ) )  
last\_entropy = current\_entropy  
Area.refine areas, points, n  
current\_entropy = areas.inject(0){ |ent, a| ent += a.entropy }  
enhance = (current\_entropy - best\_entropy)/best\_entropy  
if best\_entropy \> current\_entropy  
best\_entropy = current\_entropy  
best\_solution = areas.clone  
end  
count += 1  
puts “Step: #{count}, Enhance: #{enhance}, Entropy:  
#{current\_entropy}”  
end  
best\_solution.each &:fix!  
[best\_solution, best\_entropy]  
end  
end

# Example:

points = []  
areas = 16.times.map do |n|  
area = Area.new  
(1000/16).times do |i|  
p = Point.new\_by\_rand  
p.at = area  
area \<\< p  
points \<\< p  
end  
area  
end  
Area.refine\_until\_good\_solution(areas, points)

---

<div class="post-metadata">

**Author:** ![jrgutier](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/b3f665/32.png) [@jrgutier](https://www.ruby-forum.com/u/jrgutier)\
**Post date:** [September 17, 2010, 4:05am UTC](https://www.ruby-forum.com/t/np-hard-geolocatoin-problem/195102/4 "2010-09-17T04:05:47Z")

</div>

> I found a heuristic solution that has complexity O(n\*log(n)) per  
> step (for 1000 elements and 16 areas, I got a good solution in 500  
> steps).

Erratum: complexity is O(n^2\*log(n))  
\*but continue considering the lack of sleep…