Функция оптимизации для суммы расстояния Google Maps - PullRequest
Новая
       11

Функция оптимизации для суммы расстояния Google Maps

0 голосов
/ 31 мая 2018

Я пытаюсь найти точку (широта / долгота), которая минимизирует сумму расстояний карт Google до всех остальных N точек.

Мне удалось извлечь расстояния Google Maps между массивами широты и долготы, но я не смог минимизировать свою функцию.

Код 

def minimize_g(input_g):
    gmaps1 = googlemaps.Client(key="xxx") 


def distance_f(x):
    dist = gmaps1.distance_matrix([x], np.array(input_g)[:,1:3])
    sum_ = 0
    for obs in range(len(np.array(df[:3]))):
        sum_+= dist['rows'][0]['elements'][obs]['distance']['value']   
    return sum_

 #initial guess: centroid
centroid = input_g.mean(axis=0)

optimization = minimize(distance_f, centroid, method='COBYLA')

return optimization.x

Спасибо!

1 Ответ

0 голосов
/ 31 мая 2018

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

Затем из некоторых искусственно созданных координат вы минимизировали бы расстояния до всех ваших точек с помощьючто-то вроде 

import numpy as np

lats = [12.3, 12.4, 12.5]
lons = [16.1, 15.1, 14.1]

def total_distance_to_lats_and_lons(lat, lon):
    # some summation over distances from lat, lon to lats, lons

# create two lists with 0.01 degree precision as an artificial grid of possibilities
test_lats = np.arange(min(lats), max(lats), 0.01)
test_lons = np.arange(min(lons), max(lons), 0.01)

test_distances = []  # empty list to fill with the total_distance to each combination of test_lat, test_lon
coordinate_index_combinations = []  # corresponding coordinates
for test_lat in test_lats:
    for test_lon in test_lons:
        coordinate_combinations.append([test_lat, test_lon])  # add a combination of indices
        test_distances.append(total_distance_to_lats_and_lons(test_lat, test_lon))  # add a distance

index_of_best_test_coordinate = np.argmin(test_distances)  # find index of the minimum value
print('Best match is index {}'.format(index_of_best_test_coordinate))
print('Coordinates: {}'.format(coordinate_combinations[index_of_best_test_coordinate]))
print('Total distance: {}'.format(test_distances[index_of_best_test_coordinate]))

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

...