Присвойте дату динамически отсортированным элементам по количеству складских мест со значением сброса

Question

Короче говоря, я назначаю товары для нашей складской команды для подсчета циклов каждый день, но у каждого товара может быть разное количество мест.Мне нужно, чтобы общее количество мест было как можно ближе к определенному числу, скажем, 43 места в день.

У меня есть список всех моих предметов, которые мне нужно посчитать за квартал с количеством мест.Я хочу назначить дату каждому элементу, группируя их как можно ближе к 43 точкам в день.Я хотел бы, чтобы элементы подсчитывались как можно более случайным образом, а не только элементы с большим количеством мест, подсчитываемых в последующие дни.Предметы с одним местоположением было бы неплохо сохранить для заполнения пробелов.

Я также могу использовать только рабочие дни, исключая праздничные дни.

В качестве бонуса, если предмет имеет более 43 мест,Я хотел бы разделить это на несколько дней и использовать остаток, если возможно, чтобы объединить его с другими элементами.

Для удобства, скажем, мы хотим, чтобы количество мест было 15 в день (кодэто могло бы динамически изменить это число, используя переменную, было бы здорово.)

Вот пример:

 Item       Loc
 43127      2
 15065      5
 43689      1
 99100      5
 9681352    1
 9680537    1
 10013      1
 55600      3
 43629      1
 PAL001     2
 9950056    1
 467L86     4
 17028      2
 10324      2
 99235REV   12
 LIT003     2

С результатом, являющимся чем-то вроде этого (Действительно нужны только Item и Date, но помощникс колонками тоже все в порядке):

 Item      Loc  Cum Date
                Sum 
 43127      2   2   3/1/2019
 15065      5   7   3/1/2019
 PAL001     2   9   3/1/2019
 467L86     4   13  3/1/2019
 10324      2   15  3/1/2019
 99235REV   12  12  3/4/2019
 55600      3   15  3/4/2019
 99100      5   5   3/5/2019
 43629      1   6   3/5/2019
 LIT003     2   8   3/5/2019
 17028      2   10  3/5/2019
 43689      1   11  3/5/2019
 9680537    1   12  3/5/2019
 10013      1   13  3/5/2019
 9950056    1   14  3/5/2019
 9681352    1   15  3/5/2019

Я начал использовать цикл R, но не могу понять, как получить дату для перемещения и отметить, что я уже посчитал элемент.

Данные

test.df <- data.frame(Item=c('43127', '15065', '43689', '99100', 
                               '9681352', '9680537', '10013', '55600', 
                               '43629', 'PAL001', '9950056', '467L86', 
                               '17028', '10324', '99235REV', 'LIT003'), 
                      Loc=c(2, 5, 1, 5, 1, 1, 1, 3, 1, 2, 1, 4, 2, 2, 12, 2))

Функция

spreadDates <- function(df, loc_day) {
  # SPREAD DATES BASED ON LOCATION VALUE
  # Args: 
  #   df: Data Frame with Items and number of locations
  #   loc_day: Number of locations to count per day
  # Returns:
  #   Data Frame with key on new date
  df$Date_Switch <- 0
  df$Cum_Sum     <- 0
  for (i in 1:nrow(df)) {
    if (i==1) {                                       
      # First day 
      df[i, 4] <- df[i, 2]                              
      # Cum Sum is no of item locations
    } else {
      if ((df[i - 1, 4] + df[i, 2]) < loc_day) {         
        # If previous cumsum plus today's locations is less than max count
        df[i, 4] <- (df[i - 1, 4] + df[i, 2])            
        # Then add previous cumsum to today's locations
      } else if ((df[i - 1, 4] + df[i, 2]) > loc_day) {  
        # This is where I don't know how to look for next item to count and then 
        # mark it as already counted 
      } else {                                    
        # Previous cumsum plus today=max count
        df[i, 4] <- (df[i - 1, 4] + df[i, 2])          
        # Add previous cumsum to today
        df[i, 3] <- 1                              
        # Make Date_Switch=1 to later change date 
      }
    }
  }
  return(df)
}

test.func <- spreadDates(test.df, 15)

Если есть векторный способ сделать это или пакетЯ бы с этим согласился ... но мне действительно нужен способ автоматизировать это, поскольку у меня есть тысячи предметов, и я должен делать это ежеквартально.

Answer 1

Правка: добавлено идеальное решение снизу с использованием пакета adagio: вау!

Вот быстрая и грязная попытка, которая может быть достаточно хорошей.Я предполагаю, что оптимальное общее количество мест в день - 15, но 14 или 16 в порядке.Для этого первого шага, я не слишком увлекаюсь тасовкой.

Кстати, это, похоже, разновидность «проблемы множественного ранца» (я только что узнал об этом 5 минут назад), для которой существуют специализированные пакеты оптимизации, которые могут подходить к этому с гораздо большей мощностью.(Например: https://rdrr.io/cran/adagio/man/mknapsack.html)

Сначала я сделаю несколько больших тестовых данных, чтобы помочь оценить подход.

library(tidyverse)
n = 1000
set.seed(42)
test.df2 <- tibble(
  Item = sample(10000:99999, n, replace = FALSE),
  Loc = sample(c(rep(1:4, 8), 1:12), n, replace = TRUE)  # Most small, some up to 15
)

daily_loc_tgt <- 15   # Here's my daily total target per location

Попробуйте 1: Наивное задание

Не прибегая кпросто используйте целочисленное деление на кумулятивную сумму. Каждый раз, когда кумулятивная сумма превышает кратное 15, начинайте новую группу.

baseline <- test.df2 %>%
  mutate(cuml = cumsum(Loc),
         naive_grp  = 1 + cuml %/% daily_loc_tgt) %>%
  group_by(naive_grp) %>%
  mutate(grp_sum = cumsum(Loc)) %>%
  ungroup()

Как это работает? Для фальшивых данных примерно половина временигруппировки находятся в пределах 1 из 15.

eval_soln(baseline)   # Function defined at bottom

Попытка 2: Сдвиг переключается на одну

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

shuffle <- test.df2 %>%
  mutate(cuml = cumsum(Loc),
         grp  = 1 + cuml %/% tgt) %>%
  arrange(grp, -Loc) %>%
  group_by(grp) %>%
  mutate(grp_sum = cumsum(Loc)) %>%
  ungroup() %>%

  # Shift down overruns
  mutate(grp = if_else(grp_sum > tgt + 1,
                       grp + 1,
                       grp)) %>%
  group_by(grp ) %>%
  mutate(grp_sum = cumsum(Loc)) %>%
  ungroup()

eval_soln(shuffle)

Это скромное улучшение. Сейчас около 60% групп близки к 15. Но все еще есть справедливыечисло, которое далеко от 15 ...

Попробуйте 3: Положитесь на умных людей, которые решили это десятилетия назад

В поискеЯ узнал, что это можно назвать «проблемой множественных ранцев», и ее можно решить более эффективно с помощьюупакованные пакеты типа adagio.https://rdrr.io/cran/adagio/man/mknapsack.html

Единственная хитрость заключалась в установке количества групп в разделе k Capacities.Когда я изначально установил его с использованием 240 (вывод sum(test.df2$Loc) / 15), он заставил R зависать дольше, чем я хотел ждать.Немного понизив это, он нашел точное решение примерно за 10 секунд, и все 240 групп имели 15 локаций.

library(adagio)

# p is the "profit" per item; I'll use `Loc`
p <- test.df2$Loc

# w is the "weights", which cannot exceed the capacities. Also `Loc`
w <- test.df2$Loc

# Capacities:  all tgt
k <- rep(tgt, 239)

adagio_soln_assignments <- mknapsack(p, w, k)
adagio_soln <- test.df2 %>%
  mutate(grp = adagio_soln_assignments[["ksack"]]) %>%
  arrange(grp) %>%
  group_by(grp) %>%
  mutate(grp_sum = cumsum(Loc)) %>%
  ungroup()

eval_soln(adagio_soln)

Вуаля!

---

Вот код, который я использовал для составления графика результатов:

eval_soln <- function(df, tgt = 15, ok_var = 1) {
  stats <- df %>%
    group_by(grp) %>%
    summarize(sum_check = max(grp_sum),
              sum = sum(Loc))

  df_name <- substitute(df)

  ok_share <- mean(stats$sum >= tgt - ok_var & stats$sum <= tgt + ok_var)

  ggplot(stats, aes(sum, 
           fill = sum >= tgt - ok_var  &  sum <= tgt + ok_var)) +
    geom_histogram(binwidth = 1, color = "white") +
    scale_fill_manual(values = c("gray70", "gray20")) +
    coord_cartesian(xlim = c(0, 30)) +
    guides(fill = FALSE) +
    labs(title = df_name,
         subtitle = paste0("Share of groupings within ", ok_var,
                        " of ", tgt, ": ", 
                        scales::percent(ok_share, accuracy = 0.1)))
}