Algorithm to find point of minimum total distance from locations

17
votes

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!

3
algorithmcoordinatesdistance
In what language would you prefer to implement your solution? – calebds
Python would be ideal, but I'll take pretty much anything that isn't APL / INTERCAL or similar – Kristian Glass

3 Answers

12
votes

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

3
votes

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?

1
votes

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.