Алгоритм для нахождения точки минимального общего расстояния от местоположений

Я создаю приложение, основанное на поиске "удобной точки встречи", учитывая набор мест.

В настоящее время я определяю "удобный" как "минимизирующий общее расстояние поездки". Это другая проблема, связанная с поиском центроида, как показано на следующем примере (с помощью декартовых координат, а не широты и долготы для удобства):

A находится в (0,0)
B находится в (0,0)
C находится в (0,12)

Расположение минимального общего хода для этих точек составляет (0,0) с общим расстоянием пробега 12; центроид находится на (0,4) с общим расстоянием перемещения 16 (4 + 4 + 8).

Если местоположение ограничено тем, что оно находится в одной из точек, проблема становится более простой, но это не ограничение, которое я намереваюсь иметь (в отличие, например, этот иначе похожий вопрос).

То, что я не могу сделать, это придумать какой-либо алгоритм для решения этой проблемы - приветствуются предложения!

Ответ 1

Вот решение, которое находит географическую середину, а затем итеративно исследует близлежащие позиции, чтобы скорректировать это к минимальной общей точке расстояния.

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

Этот вопрос также очень похож на

Минимальная сумма всех путешествий

Вот статья в Википедии об общей проблеме, которую вы пытаетесь решить:

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

Ответ 2

В каком-то смысле вы, кажется, ищете центр тяжести треугольника с равными весами в вершинах. Это указывает на барицентрические координаты.

Когда вы выходите за пределы треугольника, существуют решения для обобщенных барицентрических координат, и вы можете назначать приоритеты людям, изменяя вес вершин. То, что еще не учтено, - это расстояния на реальной карте (не может просто двигаться прямо в любом направлении), но это может быть начало?

Ответ 3

Один из вариантов - определить объективную (и градиентную) функцию и использовать общую библиотеку оптимизации, такую как scipy.optimize. fmin_cg будет хорошим алгоритмом для вашей проблемы. Ваша цель была бы суммой расстояний, как определено в разделе "Определение" Геометрическая медианная страница Википедии, на которую ссылается топор. Аргументом для вашей целевой функции является y.