Algorithm for finding the point of minimum total distance from locations

Question

I am creating an application based on the search for a “convenient meeting point”, given the set of places.

Currently, I define "comfortable" as "minimizing the overall trip distance." This is another problem associated with finding a centroid, as shown in 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 the minimum total stroke for these points is (0,0) with a total distance of 12; the centroid is at (0.4) with a total displacement distance of 16 (4 + 4 + 8).

If the location is limited by the fact that it is at one of the points, the problem becomes simpler, but this is not the limitation that I intend to have (unlike, for example, this otherwise similar question ).

What I cannot do is come up with some kind of algorithm to solve this problem - suggestions are welcome!

Answer 1

Here is a solution that finds a geographic middle and then iteratively explores nearby locations in order to adjust this to the minimum common point of distance.

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

This question is also very similar to

The minimum amount of all trips

Here is a Wikipedia article about a common problem you are trying to solve:

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

Answer 2

In a way, you seem to be looking for the center of gravity of a triangle with equal weights at the vertices. This indicates barycentric coordinates.

When you go beyond the triangle, there are solutions for generalized barycentric coordinates, and you can assign priorities to people by changing the weight of the vertices. What has not yet been taken into account are the distances on the real map (cannot just move right in any direction), but can this be the beginning?

Answer 3

One option is to define an objective (and gradient) function and use a common optimization library such as scipy.optimize . fmin_cg would be a good algorithm for your problem. Your goal would be the sum of the distances, as defined in the Definition section of the Geometric Median Wikipedia Page that the ax refers to. The argument for your objective function is y.