Algorithm to find point of minimum total distance from locations

Question

I'm building an application based around finding a "convenient meeting point" given a set of locations.

Currently I'm defining "convenient" as "minimising the total travel distance". This is a different problem from finding the centroid as illustrated by the following example (using cartesian coordinates rather than latitude and longitude for convenience):

• A is at (0,0)
• B is at (0,0)
• C is at (0,12)

The location of minimum total travel for these points is at (0,0) with total travel distance of 12; the centroid is at (0,4) with total travel distance of 16 (4 + 4 + 8).

If the location were confined to being at one of the points, the problem appears to become simpler, but this isn't a constraint I intend to have (unlike, for example, this otherwise similar question).

What I can't seem to do is come up with any sort of algorithm to solve this - suggestions welcomed please!

Solution 1

Here is a solution that finds the geographical midpoint and then iteratively explores nearby positions to adjust that towards the minimum total distance point.

http://www.geomidpoint.com/calculation.html

This question is also quite similar to

Minimum Sum of All Travel Times

Here is a wikipedia article on the general problem you're trying to solve:

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

Solution 2

In a way what you appear to be looking for is the center of mass of a triangle with equal weights at the vertices. That would point to barycentric coordinates.

When going beyond a triangle there are solutions for generalized barycentric coordinates and you could give priorities to persons by modifying the weight of the vertices. What that still would not account for is distances on a real map (can't just travel straight in any direction) but it may be a start?

Solution 3

One option is to define an objective (and gradient) function and use a generic optimization library, such as scipy.optimize. fmin_cg would be a good algorithm to try for your problem. Your objective would be the sum of distances as defined in the "Definition" section of the Geometric median Wikipedia page referenced by hatchet. The argument to your objective function is y.

Comments

[Kristian Glass]

That question, and most of the answers, involve the "location is one of the points" constraint that I don't want; however the solution you link seems viable, thanks

[hatchet - done with SOverflow]

@KristianGlass - Check out the wikipedia article, it doesn't consider that constraint, and it mentions the approach of the first link as a commonly used solution.

[Cameron Chandler]

All of these answers are looking at the geometric median for some reason, which does not answer the question at all. All you need to do is find the centroid with L1 norm instead of L2 norm.