Поиск верхних точек координат X, которые охватывают большинство магазинов в радиусе X миль ⇐ Python

[Anonymous]

У меня есть список из 500 магазинов и их координаты по широте и долготе. Я пытаюсь найти 30 уникальных точек координат, которые охватывают наибольшее количество "ограниченных" магазинов в радиусе 15 миль без перекрытия и минимизации среднего расстояния от центральной точки до магазинов.
Мой подход заключался в создании сетки широты и долготы и проверке каждой точки в Python, но, похоже, это слишком медленный подход. Все магазины находятся в США.
Вот мой код:
# Define the 15-mile radius in kilometers
RADIUS_KM = 15 * 1.60934

# Define a grid with a given range of latitudes and longitudes
def generate_grid(lat_range, lon_range, lat_step, lon_step):
latitudes = np.arange(lat_range[0], lat_range[1], lat_step)
longitudes = np.arange(lon_range[0], lon_range[1], lon_step)
return [(lat, lon) for lat, lon in product(latitudes, longitudes)]

def calculate_distance(lat1, lon1, lat2, lon2):
return geodesic((lat1, lon1), (lat2, lon2)).km

# Create a grid of candidate points (this is for Texas as an example)
lat_range = (25.83, 43)
lon_range = (-106.6466, -93.5072)
lat_step = .05
lon_step = .05

grid = generate_grid(lat_range, lon_range, lat_step, lon_step)

# Create a list to store results for each grid point
results = []

for point in grid:
constrained_distances = []
for index, row in Texas.iterrows():
distance = calculate_distance(point[0], point[1], row['Latitude'], row['Longitude'])
if distance

Подробнее здесь: https://stackoverflow.com/questions/784 ... ons-within