基于现有供应点，寻找满足约束的加权平均Haversine距离最小的2个新增供应点

问题描述 #

现有2个带容量限制的供应点（含经纬度），以及多个带经纬度和需求值的需求点。需新增2个供应点（确定经纬度），满足以下约束的同时，最小化加权平均Haversine距离（目标函数：$\sum(D \times V)$，其中$D$为需求点与对应供应点的Haversine距离，$V$为需求点的需求值）：

• 所有需求点的需求均被完全满足
• 现有供应点S1、S2的总供应总量不超过各自的容量上限

示例数据 #

需求点详情 #

供应点详情 #

推荐算法与实现步骤 #

1. 加权聚类（初始选址） #

通过加权K-means聚类确定新增供应点的初始经纬度，核心是让需求大的点对聚类中心的影响更大：

• 以需求点的经纬度为特征，需求值$V$作为权重，执行K-means聚类（K=2），得到的两个聚类中心即为S3、S4的初始选址。
• 这一步可快速得到接近最优的初始位置，避免后续非线性规划陷入局部最优。

2. 非线性规划（优化选址与分配） #

基于初始选址，构建非线性规划模型，同时优化供应点的经纬度和需求分配方案：

模型定义

• 决策变量：
  • S3的纬度$lat_3$、经度$lon_3$；S4的纬度$lat_4$、经度$lon_4$
  • 每个供应点向每个需求点的供应体积$x_{ij}$（$i$为供应点S1/S2/S3/S4，$j$为需求点D1~D11）
• 目标函数：
  $$\text{Minimize} \sum_{i=1}^4 \sum_{j=1}^{11} \text{Haversine}(lat_i, lon_i, lat_j, lon_j) \times x_{ij}$$
• 约束条件：
  1. 需求满足：$\sum_{i=1}^4 x_{ij} = V_j$，对所有需求点$j$
  2. 现有供应点容量限制：$\sum_{j=1}^{11} x_{1j} \leq C_1$，$\sum_{j=1}^{11} x_{2j} \leq C_2$
  3. 非负约束：$x_{ij} \geq 0$，对所有$i,j$

Python实现工具

• Haversine距离计算：自行实现或用geopy.distance库（注意统一单位，比如转成公里）
• 优化求解：使用scipy.optimize.minimize（支持带约束的非线性优化），或pyomo/gurobipy（适配更复杂约束的规划问题）

3. 迭代优化（可选） #

若初始聚类结果不够理想，可迭代执行以下步骤：

• 用当前分配方案重新计算需求点的加权中心，更新S3、S4的位置
• 再次运行非线性规划优化分配
• 重复直到目标函数值收敛

预期输出示例 #

运行优化后，会得到两类结果：

1. 新增供应点的经纬度（示例值，实际为优化结果）：
   • S3: (12.7, 77.2)
   • S4: (17.1, 78.5)
2. 需求分配矩阵（示例）：

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