A QUBO-Based Optimization Framework for ATM Cash Replenishment Scheduling

Resumo Técnico: Um Framework de Otimização Baseado em QUBO para Escalonamento de Reabastecimento de Numerário de ATMs

Definição do Problema
O artigo aborda o desafio operacional de escalonar o reabastecimento de numerário para redes de Caixas Eletrônicos (ATMs). O objetivo central é minimizar os custos operacionais totais enquanto se mantém altos níveis de serviço e se evita a falta de dinheiro (interrupções de serviço) diante de uma demanda de saques incerta e variável no tempo. Abordagens tradicionais, como políticas baseadas em limiares (que disparam o reabastecimento quando o saldo de caixa cai abaixo de um nível fixo), falham em otimizar os custos em toda a rede ou em considerar interdependências complexas. Além disso, formulações padrão de Programação Linear Inteira Mista (MILP) têm dificuldade com as estruturas de custo não lineares inerentes ao problema, especificamente os descontos significativos de custo alcançados ao atender múltiplos ATMs localizados no mesmo endereço em uma única visita.

Metodologia
Os autores propõem um novo framework que formula o problema de reabastecimento de ATMs como um modelo de Otimização Binária Quadrática Não Restrita (QUBO). Esta abordagem é projetada para capturar naturalmente as interações de custo quadrático (descontos de co-localização) e incorporar restrições operacionais por meio de termos de penalidade.

• Arquitetura do Pipeline: O sistema opera em um ciclo diário. Ele ingere dados operacionais (resíduos de caixa em tempo real, parâmetros da máquina, transações históricas) e alimenta um módulo de previsão de séries temporais para estimar os volumes de saques diários.
• Formulação QUBO:
  • Variáveis de Decisão: Um vetor binário $x$ é definido onde $x_{i,t} = 1$ indica uma intervenção de reabastecimento para o ATM $i$ no dia $t$, e $0$ caso contrário.
  • Função Objetivo ($H(x)$): A função combina quatro componentes ponderados por parâmetros de penalidade ($\lambda_k$):
    1. Custo ($H_{cost}$): Inclui custos fixos por visita, custos variáveis baseados no volume de caixa carregado e custos para manuseio de caixa residual.
    2. Descontos ($H_{discount}$): Um termo quadrático que aplica uma redução de custo quando múltiplos ATMs no mesmo endereço são reabastecidos no mesmo dia.
    3. Viabilidade ($H_{feasibility}$): Impõe uma restrição de "no máximo um" (AMO - at-most-one), garantindo que cada ATM seja reabastecido no máximo uma vez dentro do horizonte de planejamento. Isso é codificado via uma penalidade quadrática para a seleção de múltiplos dias para a mesma máquina.
    4. Nível de Serviço ($H_{service}$): Um termo de penalidade baseado em custos de escassez pré-calculados. Ele desencoraja o agendamento de reabastecimento em dias nos quais o saldo de caixa projetado cairia abaixo de um nível de contingência, efetivamente direcionando o solver para a intervenção necessária mais precoce.
  • Premissas Simplificadoras: Para manter a estrutura quadrática, o modelo assume que o reabastecimento ocorre ao final do dia e limita o horizonte de planejamento a um único reabastecimento por ATM.
• Solver: As instâncias de QUBO resultantes são resolvidas usando o MegaQUBO, um solver proprietário acelerado por GPU desenvolvido pela Data Reply. Este aproveita o paralelismo massivo para lidar com redes de grande escala dentro de tempos de computação práticos.
• Tradução Operacional: A solução QUBO (um cronograma de dias) é traduzida de volta para "limiares de ativação" operacionais. Se um reabastecimento é agendado para o dia $t+1$, o limiar para o dia $t$ é definido como a capacidade máxima da máquina, garantindo que um ticket de serviço seja gerado a tempo.

Principais Contribuições

1. Formulação QUBO para Logística de Caixa: O artigo introduz uma formulação QUBO específica para o reabastecimento de ATMs que modela explicitamente descontos de co-localização não lineares e restrições de nível de serviço, uma lacuna anteriormente inexplorada na literatura.
2. Solução Escalável via GPU: O estudo demonstra a aplicação prática de um solver QUBO acelerado por GPU (MegaQUBO) a um problema logístico do mundo real, indo além de provas de conceito teóricas para uma ferramenta de suporte à decisão implantável.
3. Tratamento de Heterogeneidade Operacional: O framework aborda a complexidade de cronogramas de serviço mistos (por exemplo, ATMs com e sem serviço aos sábados) através de uma etapa de pré-processamento que padroniza os índices de tempo e agrega previsões de saques, permitindo uma estrutura QUBO uniforme.

Resultos
A abordagem proposta foi avaliada em um conjunto de dados reais composto por 276 ATMs na Itália durante quatro meses de 2022 (abril, maio, outubro, novembro). Foi comparada com uma política operacional padrão baseada em limiares.

• Redução de Custos: A otimização baseada em QUBO alcançou reduções de custos consistentes de aproximadamente 15% a 18% em comparação com a estratégia baseada em limiares. Em termos absolutos, isso se traduziu em economias mensais entre €9.200 e €14.500 para a rede de 276 ATMs.
• Níveis de Serviço: O nível de serviço médio (ASL) permaneceu excelente, variando de 99,78% a 99,93%, o que é comparável ou ligeiramente superior à linha de base (99,71%–99,91%).
• Trade-offs: Embora o nível de serviço médio tenha sido mantido, o nível de serviço mínimo (desempenho de pior caso para ATMs individuais) mostrou alguma variância. Em meses específicos (ex: outubro), o modelo otimizado permitiu que máquinas individuais operassem mais próximas de seus limites de segurança (96,99% vs. 99,26% para a linha de base), indicando um trade-off entre a minimização agressiva de custos e o risco individual da máquina, que pode ser ajustado via parâmetros de penalidade.

Significância e Alegações
O artigo afirma que o framework QUBO, aliado à resolução baseada em GPU, fornece uma ferramenta de suporte à decisão praticamente implantável para a logística de caixa de larga escala de ATMs. Os autores enfatizam que isto não é meramente um exercício teórico; a metodologia já foi integrada em um pipeline de produção na Intesa Sanpaolo.

A significância reside na capacidade de:

• Capturar interações de custo não lineares (descontos de co-localização) que modelos lineares lidam de forma ineficiente.
• Aproveitar técnicas emergentes de otimização quadrática clássica e inspiradas em computação quântica para problemas industriais.
• Entregar economias financeiras substanciais (reduções de dois dígitos percentuais) sem comprometer a qualidade do serviço da rede como um todo.
• Oferecer benefícios operacionais e de ESG mais amplos ao reduzir a frequência de viagens de reabastecimento, diminuindo assim as emissões de veículos e os volumes de manuseio de caixa.

Os autores concluem que, embora a implementação atual foque em ATMs padrão, o framework está sendo avaliado para extensão aos ATMs de reciclagem de caixa, que introduzem complexidade adicional em relação à previsão de depósitos e saques.