基于R语言ompr包的电池调度排列组合优化问题求解

问题核心 #

确定电池的激活顺序，让惩罚后的总输出最大化。
惩罚规则：激活顺序中，后续激活的电池若与已激活电池在Left_Battery或Right_Battery列存在偏移，该电池的输出会被扣除对应惩罚值。

数据集 #

简化测试数据集（3行） #

simple_battery_data <- data.frame(
  Battery_ID = c(1, 2, 3),
  Base_Output = c(100, 120, 90),
  Left_Battery = c(NA, 1, 2),
  Right_Battery = c(2, 3, NA)
)

原始数据集（10行） #

original_battery_data <- data.frame(
  Battery_ID = 1:10,
  Base_Output = c(95, 110, 105, 90, 120, 85, 100, 115, 98, 102),
  Left_Battery = c(NA, 1, 2, 3, 4, 5, 6, 7, 8, 9),
  Right_Battery = c(2, 3, 4, 5, 6, 7, 8, 9, 10, NA)
)

惩罚计算函数（function2） #

用于计算给定激活顺序下的最终总输出：

function2 <- function(activation_order, battery_data) {
  total_output <- 0
  activated <- c()
  
  for (battery in activation_order) {
    current_output <- battery_data$Base_Output[battery_data$Battery_ID == battery]
    penalty <- 0
    # 遍历已激活电池，计算偏移惩罚
    for (act in activated) {
      # Left_Battery偏移惩罚
      if (!is.na(battery_data$Left_Battery[battery_data$Battery_ID == battery]) && 
          battery_data$Left_Battery[battery_data$Battery_ID == battery] != act) {
        penalty <- penalty + 10
      }
      # Right_Battery偏移惩罚
      if (!is.na(battery_data$Right_Battery[battery_data$Battery_ID == battery]) && 
          battery_data$Right_Battery[battery_data$Battery_ID == battery] != act) {
        penalty <- penalty + 10
      }
    }
    total_output <- total_output + (current_output - penalty)
    activated <- c(activated, battery)
  }
  return(total_output)
}

# 测试示例：激活顺序1->2->3
test_order <- c(1, 2, 3)
cat("惩罚后总输出：", function2(test_order, simple_battery_data), "\n")
# 输出：惩罚后总输出： 280

基于ompr的混合整数规划实现 #

安装依赖包 #

install.packages(c("ompr", "ompr.roi", "ROI.plugin.glpk"))
library(ompr)
library(ompr.roi)
library(ROI.plugin.glpk)

模型构建与求解 #

定义二进制变量x[i,k]表示电池i在第k位激活，y[i,j]表示电池i在j之前激活，通过约束和目标函数求解最优顺序：

# 以简化数据集为例，替换为original_battery_data即可处理原始数据
battery_data <- simple_battery_data
n_batteries <- nrow(battery_data)
battery_ids <- battery_data$Battery_ID
base_output <- battery_data$Base_Output
left_battery <- battery_data$Left_Battery
right_battery <- battery_data$Right_Battery

# 构建MIP模型
model <- MIPModel() %>%
  # 定义激活位置变量
  add_variable(x[i, k], i = 1:n_batteries, k = 1:n_batteries, type = "binary") %>%
  # 定义激活顺序变量
  add_variable(y[i, j], i = 1:n_batteries, j = 1:n_batteries, i != j, type = "binary") %>%
  
  # 约束：每个电池仅激活一次
  add_constraint(sum_over(k = 1:n_batteries, x[i, k]) == 1, i = 1:n_batteries) %>%
  # 约束：每个位置仅一个电池
  add_constraint(sum_over(i = 1:n_batteries, x[i, k]) == 1, k = 1:n_batteries) %>%
  
  # 约束：关联y变量与x变量的顺序关系
  add_constraint(sum_over(k = 1:n_batteries, k * x[i, k]) < sum_over(k = 1:n_batteries, k * x[j, k]) + n_batteries * (1 - y[i, j]), 
                i = 1:n_batteries, j = 1:n_batteries, i != j) %>%
  add_constraint(sum_over(k = 1:n_batteries, k * x[i, k]) >= sum_over(k = 1:n_batteries, k * x[j, k]) - n_batteries * y[i, j], 
                i = 1:n_batteries, j = 1:n_batteries, i != j) %>%
  
  # 目标函数：最大化总输出（基础输出减去惩罚）
  set_objective(
    sum_over(i = 1:n_batteries, base_output[i] * sum_over(k = 1:n_batteries, x[i, k])) -
      sum_over(i = 1:n_batteries, sum_over(j = 1:n_batteries, j != i, 
        # 计算j在i前激活时的偏移惩罚
        ifelse(!is.na(left_battery[i]) && left_battery[i] != battery_ids[j], 10, 0) * y[j, i] +
        ifelse(!is.na(right_battery[i]) && right_battery[i] != battery_ids[j], 10, 0) * y[j, i]
      )),
    "max"
  )

# 求解模型
result <- solve_model(model, with_ROI(solver = "glpk"))

# 提取最优激活顺序
activation_order <- result %>%
  get_solution(x[i, k]) %>%
  filter(value == 1) %>%
  arrange(k) %>%
  pull(i) %>%
  map_chr(~battery_ids[.x]) %>%
  as.integer()

cat("最优激活顺序：", paste(activation_order, collapse = " -> "), "\n")
cat("最优总输出：", get_objective_value(result), "\n")

3电池激活顺序示例 #

图注：直观展示3个电池不同激活顺序下的偏移惩罚逻辑

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