4

The problem is to find the point minimizing the travel distance for around 100 persons in different regions who want to meet in the same place. Travel is by car not by plane.

Assuming that I get access to an API giving me mileage / kilometric distance in terms of highway travel between any two points, how can I find the best place to meet?

  • Are there any other constraints on the location of the meeting point? For example, your meeting point must not be in the middle of a lake. – Radar Jul 8 '13 at 20:44
  • no other constraint (middle of a lake? I'll take the nearest shore). Seriously, additional constraints might be added later, but this distance thing is my starting point. – seinecle Jul 8 '13 at 20:46
1

In the simplest terms (baring no other constraints) you are looking for the Geometric Median, which is the point minimizing the sum of distances to all other points. A solution to this problem is less simple and is often estimated.

This demo from Wolfram shows an interesting interactive example using a few points. Notice here it is referred to as the Center of Mass (of n points). They also include a link to the code used to produce this demo.

This (from Wikipedia) should help you to distinguish the Geometric Median from the Center of Mass:

Despite the geometric median's being an easy-to-understand concept, computing it poses a challenge. The centroid or center of mass, defined similarly to the geometric median as minimizing the sum of the squares of the distances to each point, can be found by a simple formula — its coordinates are the averages of the coordinates of the points — but no such formula is known for the geometric median, and it has been shown that no explicit formula, nor an exact algorithm involving only arithmetic operations and kth roots can exist in general. Therefore only numerical or symbolic approximations to the solution of this problem are possible under this model of computation.

However, it is straightforward to calculate an approximation to the geometric median using an iterative procedure in which each step produces a more accurate approximation. Procedures of this type can be derived from the fact that the sum of distances to the sample points is a convex function, since the distance to each sample point is convex and the sum of convex functions remains convex. Therefore, procedures that decrease the sum of distances at each step cannot get trapped in a local optimum.

I would recommend using the above search terms (Geometric Median, Center of Mass) on StackOverflow as there are several automated examples that may be of use to you.

If you have access to GIS software, a tool such as Near (Analysis) in ArcGIS could be used to solve this problem.

  • Follow up on stack overflow : stackoverflow.com/questions/17546404/weiszfeld-algo-for-highway-distance?noredirect=1#comment25524021_17546404 – seinecle Jul 9 '13 at 13:14
  • 2
    In this particular case, though, the problem is much easier than Wolfram makes it sound: just create one grid of travel times from each person, add them, and identify points of minimum value. Because only the network cells actually have to be rasterized, and travel time computations can be done in time proportional to the number of cells, these grids can be created rapidly even at high resolutions. – whuber Jul 9 '13 at 13:38
  • +1 The aspect of travel being measured in time is interesting - most models purely use mathematical distances, which can over-complicate real-world applications. – Radar Jul 9 '13 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.