Как разделить на группу с ограничениями - PullRequest
Новая
       25

Как разделить на группу с ограничениями

0 голосов
/ 19 мая 2019

Я пытаюсь решить проблему оптимизации.

Например, у нас есть 10 групп людей:

Группа 1: 20

Группа 2: 5

Группа 3: 15

Группа 4: 10

Группа 5: 12

Группа 6: 26

Группа 7: 41

Группа 8: 15

Группа 9: 69

Группа 10: 9

Мы пытаемся загрузить эти группы людей в несколько автобусов, НОне может разбить группу.Каждый автобус может перевозить только 80 человек.Любые предложения по коду / функции, чтобы получить минимальное количество автобусов, необходимых.Спасибо!

Ответы [ 2 ]

1 голос
/ 20 мая 2019

Для фиксированного числа контейнеров это можно сформулировать как задачу целочисленного линейного программирования.Если g - это вектор из 10 номеров групп, а cap - это емкость, т. Е. 80, то должно быть не менее k=ceiling(sum(g) / cap) контейнеров и не более k=length(g).Таким образом, мы последовательно подбираем от минимального до максимального количества остановок контейнеров, как только мы подходим.В случае данных, показанных в задаче (см. Примечание в конце), требуется только одна итерация.

В задаче lp есть двоичные переменные k по n, и если мы упорядочим их в матрице ak по n, то i, j-й равен 1, если i-й контейнер содержит элемент j, и 0 в противном случае.

Задача lp имеет k + n ограничений.Первые k ограничений ограничивают сумму каждого из k контейнеров cap, а оставшиеся n ограничения гарантируют, что каждый элемент может встречаться только в одном контейнере. 

library(lpSolve)
stopifnot(all(g <= cap))

n <- length(g)
kmin <- ceiling(sum(g) / cap)
for(k in seq(kmin, n)) {
  objective.in <- rep(1, k * n)
  const.mat <- rbind(diag(k) %x% t(g), t(rep(1, k)) %x% diag(n))
  const.dir <- c(rep("<=", k), rep("==", n))
  const.rhs <- c(rep(cap, k), rep(1, n))
  res <- lp("min", objective.in, const.mat, const.dir, const.rhs, all.bin = TRUE)
  if (res$status == 0) break
}

# iterations
k - kmin + 1
## [1] 1

# solution - each col is an element, each row is a container 
matrix(res$solution, k, byrow = TRUE)
##      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
## [1,]    1    1    1    1    1    0    0    1    0     0
## [2,]    0    0    0    0    0    1    1    0    0     1
## [3,]    0    0    0    0    0    0    0    0    1     0

Примечание

Входные данные были такими: 

Lines <- "Group 1: 20
Group 2: 5
Group 3: 15
Group 4: 10
Group 5: 12
Group 6: 26
Group 7: 41
Group 8: 15
Group 9: 69
Group 10: 9"
g <- read.table(text = Lines)$V3

cap <- 80
0 голосов
/ 19 мая 2019

Это проблема упаковки бина, для которой вы можете найти множество подходов онлайн.

В любом случае, вот решение с жадным алгоритмом. Это не гарантирует оптимального решения, но должно быть достаточно приличным - 

grp <- c(20, 5, 15, 10, 12, 26, 41, 15, 69, 9)
cap <- 80

sorted_grp <- sort(grp, decreasing = T)

buses <- list("bus_1" = NULL)
for(g in seq_along(sorted_grp)) {
  balance_cap <- cap - sapply(buses, function(x) sum(x))
  if(any(balance_cap >= sorted_grp[g])) {
    feasible_bus <- which(balance_cap >= sorted_grp[g])[1]
    buses[[paste0("bus_", feasible_bus)]] <- c(buses[[paste0("bus_", feasible_bus)]], sorted_grp[g])
  } else {
    buses[[paste0("bus_", length(buses) + 1)]] <- sorted_grp[g]
  }
}

# > paste0("Number of buses: ", length(buses))
# [1] "Number of buses: 3"
# > buses
# $`bus_1`
# [1] 69 10
# 
# $bus_2
# [1] 41 26 12
# 
# $bus_3
# [1] 20 15 15  9  5
...