A QUBO-Based Optimization Framework for ATM Cash Replenishment Scheduling

Technical Summary: A QUBO-Based Optimization Framework for ATM Cash Replenishment Scheduling

Problem Definition
The paper addresses the operational challenge of scheduling cash replenishment for networks of Automated Teller Machines (ATMs). The core objective is to minimize total operational costs while maintaining high service levels and preventing cash-outs (service interruptions) amidst uncertain and time-varying withdrawal demand. Traditional approaches, such as threshold-based policies (triggering replenishment when cash falls below a fixed level), fail to optimize costs across the network or account for complex interdependencies. Furthermore, standard Mixed Integer Linear Programming (MILP) formulations struggle with the non-linear cost structures inherent in the problem, specifically the significant cost discounts achieved when servicing multiple co-located ATMs in a single visit.

Methodology
The authors propose a novel framework that formulates the ATM cash replenishment problem as a Quadratic Unconstrained Binary Optimization (QUBO) model. This approach is designed to naturally capture the quadratic cost interactions (co-location discounts) and incorporate operational constraints through penalty terms.

• Pipeline Architecture: The system operates on a daily cycle. It ingests operational data (real-time cash residuals, machine parameters, historical transactions) and feeds a time-series forecasting module to estimate daily withdrawal volumes.
• QUBO Formulation:
  • Decision Variables: A binary vector $x$ is defined where $x_{i,t} = 1$ indicates a replenishment intervention for ATM $i$ on day $t$, and $0$ otherwise.
  • Objective Function ($H(x)$): The function combines four components weighted by penalty parameters ($\lambda_k$):
    1. Cost ($H_{cost}$): Includes fixed costs per visit, variable costs based on cash volume loaded, and costs for handling residual cash.
    2. Discounts ($H_{discount}$): A quadratic term that applies a cost reduction when multiple ATMs at the same address are replenished on the same day.
    3. Feasibility ($H_{feasibility}$): Enforces an "at-most-one" (AMO) constraint, ensuring each ATM is replenished at most once within the planning horizon. This is encoded via a quadratic penalty for selecting multiple days for the same machine.
    4. Service Level ($H_{service}$): A penalty term based on precomputed shortage costs. It discourages scheduling replenishment on days where the projected cash balance would fall below a contingency level, effectively steering the solver to the earliest necessary intervention.
  • Simplifying Assumptions: To maintain the quadratic structure, the model assumes replenishment occurs at the end of the day and limits the planning horizon to a single replenishment per ATM.
• Solver: The resulting QUBO instances are solved using MegaQUBO, a proprietary GPU-accelerated solver developed by Data Reply. This leverages massive parallelism to handle large-scale networks within practical computation times.
• Operational Translation: The QUBO solution (a schedule of days) is translated back into operational "activation thresholds." If a replenishment is scheduled for day $t+1$, the threshold for day $t$ is set to the machine's maximum capacity, ensuring a service ticket is generated in time.

Key Contributions

1. QUBO Formulation for Cash Logistics: The paper introduces a specific QUBO formulation for ATM replenishment that explicitly models non-linear co-location discounts and service level constraints, a gap previously unexplored in the literature.
2. Scalable Solution via GPU: The study demonstrates the practical application of a GPU-accelerated QUBO solver (MegaQUBO) to a real-world logistics problem, moving beyond theoretical proofs of concept to a deployable decision-support tool.
3. Handling Operational Heterogeneity: The framework addresses the complexity of mixed service schedules (e.g., ATMs with and without Saturday service) through a preprocessing stage that standardizes time indices and aggregates withdrawal forecasts, allowing a uniform QUBO structure.

Results
The proposed approach was evaluated on a real dataset comprising 276 ATMs in Italy over four months in 2022 (April, May, October, November). It was benchmarked against a standard threshold-based operational policy.

• Cost Reduction: The QUBO-based optimization achieved consistent cost reductions of approximately 15% to 18% compared to the threshold-based strategy. In absolute terms, this translated to monthly savings between €9,200 and €14,500 for the 276-ATM network.
• Service Levels: The average service level (ASL) remained excellent, ranging from 99.78% to 99.93%, which is comparable to or slightly higher than the baseline (99.71%–99.91%).
• Trade-offs: While the average service level was maintained, the minimum service level (worst-case performance for individual ATMs) showed some variance. In specific months (e.g., October), the optimized model allowed individual machines to operate closer to their safety limits (96.99% vs. 99.26% for the baseline), indicating a trade-off between aggressive cost minimization and individual machine risk, which can be tuned via penalty parameters.

Significance and Claims
The paper claims that the QUBO framework, coupled with GPU-based solving, provides a practically deployable decision-support tool for large-scale ATM cash logistics. The authors emphasize that this is not merely a theoretical exercise; the methodology has already been integrated into a production-grade pipeline at Intesa Sanpaolo.

The significance lies in the ability to:

• Capture non-linear cost interactions (co-location discounts) that linear models handle inefficiently.
• Leverage emerging quantum-inspired and classical quadratic optimization techniques for industrial problems.
• Deliver substantial financial savings (double-digit percentage reductions) without compromising overall network service quality.
• Offer broader operational and ESG benefits by reducing the frequency of replenishment trips, thereby lowering vehicle emissions and cash handling volumes.

The authors conclude that while the current implementation focuses on standard ATMs, the framework is being evaluated for extension to cash-recycling ATMs, which introduce additional complexity regarding deposit and withdrawal forecasting.