Em sistemas de filas, como os encontrados em supermercados, é fundamental dimensionar corretamente os recursos para garantir a eficiência do atendimento. No nosso caso, o problema envolve a alocação conjunta de dois tipos de recursos:

A restrição do sistema é que o throughput – definido como o mínimo entre a capacidade total dos caixas (30 × x) e a capacidade dos buffers (15 × y) – deve ser de pelo menos 90 clientes/hora. Assim, para se atender essa meta, o sistema necessita, no mínimo, de 3 caixas (pois 30×3 = 90) e 6 vagas de espera (pois 15×6 = 90).

Além disso, definimos uma função de custo que combina os dois recursos de forma ponderada:

\[ Z = (1-\alpha)x + \alpha\,y, \]

em que o parâmetro \(\alpha\) (variando entre 0 e 1) determina a importância relativa entre o custo dos caixas e o dos buffers. Por exemplo, se \(\alpha = 0.2\), os caixas terão peso 0.8 e os buffers 0.2 na função de custo; se \(\alpha = 0.8\), a ênfase é maior no custo dos buffers.

Modelagem do Problema

Restrições e Viabilidade

Para garantir o throughput mínimo de 90 clientes/hora, o sistema deve satisfazer:

  • \(30 \times x \geq 90\) → \(x \geq 3\);
  • \(15 \times y \geq 90\) → \(y \geq 6\).

Qualquer solução que não satisfaça essa restrição é considerada inviável e, para isso, a função objetivo retorna um valor de penalidade muito alto.

Função de Custo

\[ Z = (1-\alpha)x + \alpha\,y. \]

Esta formulação permite, através da variação de \(\alpha\), ponderar o custo relativo dos caixas e dos buffers. Embora a restrição de throughput determine uma configuração mínima (3 caixas e 6 buffers), o valor numérico do custo final varia conforme \(\alpha\).

Descrição do Código

O código é dividido em várias seções, cada uma responsável por uma etapa da implementação.

Função Simulated Annealing (SA)

A função sa_algorithm é uma implementação genérica do algoritmo SA. Ela recebe:

  • sol_init: solução inicial (vetor com \(x\) e \(y\));
  • objective: a função objetivo que avalia o custo de uma solução;
  • perturb: a função que gera uma solução vizinha (por meio de uma pequena alteração);
  • T_init: temperatura inicial (nesse exemplo, 100);
  • cooling_rate: taxa de resfriamento, que diminui gradualmente a temperatura a cada iteração (valor usado foi 0.999 em execuções diferentes);
  • max_iter: número máximo de iterações (10000).

No loop do algoritmo, a solução é perturbada, seu custo é calculado e, se o novo custo for menor (ou for aceito probabilisticamente, de acordo com \(\exp(-\Delta/T)\)), a solução corrente é atualizada. O histórico do custo é armazenado para permitir a visualização da convergência.

Função Objetivo – objective_BSAP_supermarket

Essa função avalia uma solução (vetor \([x, y]\)) para um determinado valor de \(\alpha\). Ela:

  • Extrai \(x\) (número de caixas) e \(y\) (número de vagas de espera);
  • Verifica se a restrição de throughput é atendida (usando \(\min(30 \times x,\,15 \times y) \geq 90\)). Se não for, retorna 1e6 (penalidade);
  • Se a restrição é satisfeita, retorna o custo calculado como \((1-\alpha)x + \alpha\,y\).

Função de Perturbação – perturb_BSAP

Essa função gera uma solução vizinha ao alterar aleatoriamente um dos componentes (x ou y) em +1 ou -1, garantindo que o valor mínimo seja 1 (para evitar soluções inválidas).

Execução para Diferentes Valores de \(\alpha\)

O código testa três valores de \(\alpha\) (0.2, 0.5 e 0.8). Para cada valor:

  • Define uma solução inicial, aqui \([5, 8]\), que satisfaz as restrições;
  • Executa o SA com uma taxa de resfriamento (0.999 para uma convergência mais suave) e um número de iterações (10000);
  • Armazena os resultados (melhor solução, custo mínimo e histórico do custo).

Gráfico da Convergência do Custo (Gráfico 1)

Os dados do histórico de custo são compilados em um data frame (df_history) com as colunas:

  • Iteration: número da iteração;
  • Cost: custo da solução na iteração;
  • Alpha: valor de \(\alpha\) correspondente.

  • Alta variação inicial: Nas primeiras iterações, o custo apresenta picos altos (devido à exploração do espaço e soluções inviáveis);
  • Convergência: Após um determinado número de iterações o custo se estabiliza próximo a valores baixos (por volta de 5);
  • Comparação entre \(\alpha\): As linhas para diferentes \(\alpha\) apresentam padrões semelhantes, mas os valores finais da função custo variam conforme \(\alpha\).

Em seguida, os dados são transformados para formato longo (df_opt_long) para criar um gráfico de barras empilhadas, que mostra para cada valor de \(\alpha\) como os recursos estão distribuídos. Nos resultados apresentados, a solução ótima foi consistente para todos os \(\alpha\):

  • 3 caixas e 6 buffers, resultando em custos diferentes conforme a fórmula de custo:

    • Para \(\alpha = 0.2\): custo 3.6
    • Para \(\alpha = 0.5\): custo 4.5
    • Para \(\alpha = 0.8\): custo 5.4

Isso demonstra que, embora a estrutura da solução seja fixada pela restrição de throughput, o valor da função custo é influenciado pela ponderação \(\alpha\).

Interpretação dos Resultados

O gráfico de convergência evidencia que o algoritmo SA, após explorar amplamente o espaço de soluções (com custos inicialmente altos e grande variabilidade), converge para uma região de baixo custo (custo próximo a 5) após muitas iterações. Isso mostra a eficácia do SA em encontrar uma solução viável e de baixo custo mesmo em um problema com restrição forte.

Código Anexo

# Carrega as bibliotecas necessárias
library(tidyverse)    # dplyr, tidyr, ggplot2, etc.
library(tidyplots)    # para visualizações didáticas

# ----------------------------------------------
# Função Simulated Annealing (SA) Genérica
# ----------------------------------------------
sa_algorithm <- function(sol_init, objective, perturb, T_init = 100, cooling_rate = 0.95, max_iter = 1000) {
  current_sol <- sol_init
  current_obj <- objective(current_sol)
  best_sol <- current_sol
  best_obj <- current_obj
  cost_history <- numeric(max_iter)
  
  T <- T_init
  for (i in 1:max_iter) {
    new_sol <- perturb(current_sol)
    new_obj <- objective(new_sol)
    delta <- new_obj - current_obj
    
    # Critério de aceitação: aceita se melhora ou com prob. exp(-delta/T)
    if (delta < 0 || runif(1) < exp(-delta/T)) {
      current_sol <- new_sol
      current_obj <- new_obj
      if (current_obj < best_obj) {
        best_sol <- current_sol
        best_obj <- current_obj
      }
    }
    cost_history[i] <- current_obj
    T <- T * cooling_rate
  }
  list(best_sol = best_sol, best_obj = best_obj, cost_history = cost_history)
}

# ----------------------------------------------
# Modelagem BSAP para Filas de Supermercado
# ----------------------------------------------
# x: número de caixas (servidores)
# y: número de vagas de espera (buffers)
#
# Cada caixa atende 30 clientes/hora e cada vaga "suporta" 15 clientes/hora.
# Requisito: throughput = min(30*x, 15*y) >= 90.
#
# Função de custo: Z = (1 - alpha)*x + alpha*y, onde alpha varia entre 0 e 1.
# Por exemplo, para alpha = 0.2, o custo dos servidores pesa 0.8 e dos buffers 0.2.

objective_BSAP_supermarket <- function(sol, alpha, mu = 30, gamma = 15, Theta_min = 90) {
  x <- sol[1]  # número de caixas
  y <- sol[2]  # número de vagas de espera
  if (min(mu * x, gamma * y) < Theta_min) return(1e6)  # penalidade para soluções inviáveis
  return((1 - alpha) * x + alpha * y)
}

# Função de perturbação: altera aleatoriamente x ou y em ±1 (garante mínimo 1)
perturb_BSAP <- function(sol) {
  new_sol <- sol
  idx <- sample(1:2, 1)        
  change <- sample(c(-1, 1), 1)
  new_sol[idx] <- new_sol[idx] + change
  if (new_sol[idx] < 1) new_sol[idx] <- 1
  return(new_sol)
}

# ----------------------------------------------
# Executa SA para diferentes valores de alpha
# ----------------------------------------------
alphas <- c(0.2, 0.5, 0.8)
results <- list()

for (a in alphas) {
  set.seed(123)  # para reprodutibilidade
  sol_init <- c(5, 8)  # solução inicial que satisfaz as restrições (5 caixas, 8 vagas)
  res <- sa_algorithm(
    sol_init,
    objective = function(sol) objective_BSAP_supermarket(sol, alpha = a),
    perturb = perturb_BSAP,
    T_init = 100,
    cooling_rate = 0.999,
    max_iter = 10000
  )
  results[[as.character(a)]] <- res
}

# ----------------------------------------------
# Prepara dados para visualização do histórico de custo
# ----------------------------------------------
df_history <- bind_rows(lapply(names(results), function(a) {
  tibble(
    Iteration = 1:length(results[[a]]$cost_history),
    Cost = results[[a]]$cost_history,
    Alpha = as.numeric(a)
  )
}))

# Convert Alpha para fator (para mapeamento de cor no tidyplot)
df_history <- df_history %>% mutate(Alpha = as.factor(Alpha))

# Cria gráfico da convergência do custo utilizando tidyplot
p1 <- tidyplot(df_history, x = Iteration, y = Cost, color = Alpha) %>%
  add_line(linewidth = 1) %>%
  adjust_title("Convergência do Custo (BSAP - Filas de Supermercado)") %>%
  adjust_x_axis(title = "Iteração") %>%
  adjust_y_axis(title = "Custo") %>%
  adjust_legend_title("α") %>%
  theme_minimal_xy(fontsize = 12)%>% 
  adjust_size(width = 200, height = 200)

# Exibe o gráfico p1
print(p1)

# ----------------------------------------------
# Prepara um resumo das melhores soluções para cada alpha
# ----------------------------------------------
df_opt <- tibble(
  Alpha = as.numeric(names(results)),
  Cashiers = sapply(results, function(res) res$best_sol[1]),
  Buffers  = sapply(results, function(res) res$best_sol[2]),
  Cost     = sapply(results, function(res) res$best_obj)
)

# Converte Alpha para fator para a visualização
df_opt <- df_opt %>% mutate(Alpha = as.factor(Alpha))

# Prepara dados em formato longo para plotagem em barras
df_opt_long <- df_opt %>%
  pivot_longer(cols = c("Cashiers", "Buffers"), names_to = "Resource", values_to = "Count")



# ----------------------------------------------
# Exibe resumo final no console
# ----------------------------------------------
print(df_opt)