谷歌地图距离总和的优化功能

Question

我试图找到一个点(纬度/经度(，使谷歌地图到所有其他N个点的距离之和最小化。

我能够提取我的纬度和经度数组之间的谷歌地图距离，但我无法最小化我的函数。

法典

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

谢谢！

Answer 1

如果要在地图上查找到列表中所有坐标的距离最短的任何点，则可以尝试编写一个函数来计算从一个坐标到另一个坐标的距离。如果您准备好了该功能，则只需计算从测试点到所有点的总距离即可。

然后，从一些人工创建的坐标中，您将最小化到所有点的距离，如下所示：

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]))

这种暴力方法有一些精度限制，并且很快就会成为一个昂贵的循环，因此您也可以使用每轮后找到的最小值迭代应用此方法，从而迭代地提高精度并减少测试坐标列表中的起点和终点。经过几次迭代后，您应该有一个非常精确的估计。另一方面，这种迭代方法可能会收敛到多个局部最小值之一，仅产生多个解决方案中的一个。