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!

Answer 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