带约束的K-means聚类：自动售货机路线重聚类技术求助

你的需求属于带空间、数量与销售额三重约束的聚类问题，普通K-means仅优化空间距离，无法满足均衡要求，以下是针对性的实现方案：

核心方案1：clue包约束K-means（兼顾空间紧凑与数量均衡） #

clue支持为K-means添加集群大小约束，结合销售额加权可间接实现销售额均衡：

• 先对坐标按销售额加权，让高销售额点位在聚类中获得更高权重
• 指定每个集群的数量上下限（比如总数量/集群数 ±5%）

示例代码：

# 安装依赖包
install.packages(c("clue", "dplyr"))
library(clue)
library(dplyr)

# 假设数据集为vending_data，包含lon, lat, sales字段
cluster_num <- 5  # 替换为实际需要的集群数量
total_count <- nrow(vending_data)
# 设置数量约束：每个集群数量在目标值的95%-105%之间
min_size <- floor(total_count/cluster_num * 0.95)
max_size <- ceiling(total_count/cluster_num * 1.05)

# 按销售额加权坐标，强化高销售额点位的聚类优先级
vending_data <- vending_data %>%
  mutate(weighted_lon = lon * sqrt(sales),
         weighted_lat = lat * sqrt(sales))

# 构建约束规则
constraints <- list(size = rep(c(min_size, max_size), cluster_num))

# 运行约束K-means
set.seed(123)  # 固定种子保证结果可复现
constrained_kmeans <- cl_clustering(
  kmeans_model(vending_data[, c("weighted_lon", "weighted_lat")], centers = cluster_num),
  constraints = constraints
)

# 提取聚类结果
vending_data$cluster <- as.integer(constrained_kmeans)

核心方案2：redist包遗传算法重划分（精准满足销售额约束） #

如果需要严格的销售额均衡，redist包专为区域重划分设计，可同时设置数量、销售额与空间紧凑性约束：

install.packages(c("redist", "sf", "ggplot2"))
library(redist)
library(sf)
library(ggplot2)

# 将数据转换为空间格式
vending_sf <- st_as_sf(vending_data, coords = c("lon", "lat"), crs = 4326)
target_count <- total_count/cluster_num
target_sales <- sum(vending_data$sales)/cluster_num

# 运行遗传算法重划分，同时约束数量与销售额
set.seed(456)
redist_result <- redistricting(
  vending_sf,
  ndists = cluster_num,
  pop_tol = 0.05,  # 数量允许的误差比例（±5%）
  # 自定义销售额约束惩罚函数
  constraint_fn = function(plan) {
    sales_per_cluster <- tapply(vending_data$sales, plan, sum)
    # 计算销售额偏离目标的比例总和，越小越优
    sum(abs(sales_per_cluster - target_sales)/target_sales)
  },
  objective = "compact"  # 保证区域空间紧凑，适配运维路线需求
)

# 提取最优方案（选约束满足度最高的结果）
best_plan <- redist_result$plans[which.min(redist_result$constraint)]
vending_data$cluster <- best_plan

# 可视化验证结果
ggplot(vending_data, aes(x=lon, y=lat, color=factor(cluster), size=sales)) +
  geom_point() +
  theme_minimal()

关键注意事项 #

• 合理设置约束误差：不要追求绝对均分，比如数量±5%、销售额±10%的误差空间，避免聚类结果过于分散，影响运维路线的合理性
• 固定随机种子：所有聚类/重划分操作前添加set.seed()，保证结果可复现
• 先确定集群数：确保总售货机数量、总销售额能被集群数大致均分，否则约束可能无法满足

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