寻找覆盖最多受限门店的30个15英里半径最优坐标点

我拥有500家美国门店的经纬度坐标数据，需要选出30个唯一坐标点，需满足：

• 每个点的15英里半径范围内覆盖最多的"受限"门店
• 各点的覆盖范围无重叠
• 同时最小化中心点到覆盖门店的平均距离

当前采用经纬度网格遍历法在Python中实现，但运行效率极低，代码如下：

# 定义15英里半径对应的公里数
RADIUS_KM = 15 * 1.60934

# 生成指定经纬度范围的网格点
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

# 生成候选网格点（以得克萨斯州为例）
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)

# 存储每个网格点的计算结果
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 <= RADIUS_KM and row['Constraint Check'] == 'Constrained':
            constrained_distances.append(distance)
    
    constrained_count = len(constrained_distances)
    average_distance = np.mean(constrained_distances) if constrained_distances else float('inf')
    
    results.append({
        'Location': point,
        'Constrained Count': constrained_count,
        'Average Distance': average_distance
    })

内容的提问来源于stack exchange，提问作者Guest