A QUBO-Based Optimization Framework for ATM Cash Replenishment Scheduling

기술 요약: ATM 현금 보충 스케줄링을 위한 QUBO 기반 최적화 프레임워크

문제 정의
본 논문은 ATM(자동화 금융 단말기) 네트워크의 현금 보충 스케줄링이라는 운영상의 과제를 다룹다. 핵심 목표는 불확실하고 시간에 따라 변하는 인출 수요 속에서 높은 서비스 수준을 유지하고 현금 고갈(서비스 중단)을 방지하면서 총 운영 비용을 최소화하는 것이다. 임계값 기반 정책(현금이 특정 수준 이하로 떨어지면 보충을 트리거하는 방식)과 같은 전통적인 접근 방식은 네트워크 전체의 비용을 최적화하거나 복잡한 상호 의존성을 고려하는 데 한계가 있다. 또한, 표준 혼합 정수 선형 계획법(MILP) 공식은 이 문제에 내재된 비선형 비용 구조, 특히 한 번의 방문으로 인접한 여러 대의 ATM을 동시에 서비스할 때 발생하는 상당한 비용 할인 효과를 처리하는 데 어려움을 겪는다.

방법론
저자들은 ATM 현금 보충 문제를 이차 비제약 이진 최적화(QUBO) 모델로 공식화하는 새로운 프레임워크를 제안한다. 이 접근 방식은 이차적 비용 상호작용(공동 위치 할인)을 자연스럽게 포착하고 운영 제약 조건을 페널티 항을 통해 통합하도록 설계되었다.

• 파이프라인 아키텍처: 시스템은 일 단위 주기로 작동한다. 실시간 현금 잔액, 기기 파라미터, 과거 거래 데이터를 포함한 운영 데이터를 수집하여 시계열 예측 모듈에 전달함으로써 일일 인출량을 추정한다.
• QUBO 공식화:
  • 결정 변수: 이진 벡터 $x$가 정의되며, 여기서 $x_{i,t} = 1$은 $t$일에 ATM $i$에 대한 보충 작업이 수행됨을 나타내고, $0$은 그렇지 않음을 나타낸다.
  • 목적 함수 ($H(x)$): 이 함수는 네 가지 구성 요소와 이를 가중하는 페널티 파라미터($\lambda_k$)를 결합한다.
    1. 비용 ($H_{cost}$): 방문당 고정 비용, 투입되는 현금량에 따른 가변 비용, 잔여 현금 처리 비용을 포함한다.
    2. 할인 ($H_{discount}$): 동일한 주소에 있는 여러 대의 ATM이 같은 날에 보충될 때 비용 절감을 적용하는 이차항이다.
    3. 타당성 ($H_{feasibility}$): "최대 하나(at-most-one, AMO)" 제약 조건을 강제하여, 각 ATM이 계획 기간 내에 최대 한 번만 보충되도록 보장한다. 이는 동일 기기에 대해 여러 날을 선택하는 것에 대한 이차 페널티를 통해 인코딩된다.
    4. 서비스 수준 ($H_{service}$): 사전 계산된 부족 비용에 기반한 페널티 항이다. 이는 프로젝트된 현금 잔액이 예비 수준 미만으로 떨어질 것으로 예상되는 날에 보충을 스케줄링하는 것을 억제하여, 솔버가 가장 필요한 시점에 개입하도록 유도한다.
  • 단순화 가정: 이차 구조를 유지하기 위해, 모델은 보충이 일 마감 시점에 발생한다고 가정하며, 계획 기간을 각 ATM당 단 한 번의 보충으로 제한한다.
• 솔버: 결과물인 QUBO 인스턴스는 Data Reply에서 개발한 독점 GPU 가속 솔버인 MegaQUBO를 사용하여 해결된다. 이는 대규모 네트워크를 실용적인 계산 시간 내에 처리하기 위해 대규모 병렬 처리를 활용한다.
• 운영적 변환: QUBO 솔루션(날짜 스케줄)은 다시 운영상의 "활성화 임계값"으로 변환된다. 만약 $t+1$일에 보충이 예정되어 있다면, $t$일에 대한 임계값은 해당 기기의 최대 용량으로 설정되어 적시에 서비스 티켓이 생성되도록 한다.

주요 기여

1. 현금 물류를 위한 QUBO 공식화: 본 논문은 비선형 공동 위치 할인을 명시적으로 모델링하고 서비스 수준 제약 조건을 포함하는 ATM 보충 전용 QUBO 공식을 도입하였으며, 이는 기존 문헌에서 탐구되지 않았던 영역이다.
2. GPU를 통한 확장성 확보: 본 연구는 이론적 개념 증명을 넘어, 대규모 물류 문제를 해결하기 위해 GPU 가속 QUBO 솔버(MegaQUBO)를 실제 적용할 수 있음을 입증하여 배포 가능한 의사결정 지원 도구로서의 가능성을 보여주었다.
3. 운영적 이질성 처리: 프레임워크는 시간 인덱스를 표준화하고 인출 예측치를 집계하는 전처리 단계를 통해, 서로 다른 서비스 일정(예: 토요일 서비스 여부가 다른 ATM)을 가진 복잡한 환경을 처리한다.

결과
제안된 접근 방식은 2022년 4개월(4월, 5월, 10월, 11월) 동안 이탈리아의 276대 ATM을 포함하는 실제 데이터셋을 통해 평가되었다. 이는 표준 임계값 기반 운영 정책과 벤치마킹되었다.

• 비용 절감: QUBO 기반 최적화는 임계값 기반 전략과 비교하여 약 **15%에서 18%**의 일관된 비용 절감을 달ometric했다. 절대 금액으로는 276대 ATM 네트워크 기준으로 월간 9,200유로에서 14,500유로 사이의 절감 효과를 가져왔다.
• 서비스 수준: 평균 서비스 수준(ASL)은 99.78%에서 99.93% 사이로 매우 우수하게 유지되었으며, 이는 베이스라인(99.71%~99.91%)과 비슷하거나 약간 더 높은 수준이다.
• 트레이드오프(절충 관계): 평균 서비스 수준은 유지되었으나, 최소 서비스 수준(개별 ATM의 최악의 성능)은 일부 변동을 보였다. 특정 월(예: 10월)의 경우, 최적화 모델은 개별 기기가 안전 한계치에 더 가깝게 작동하도록 허용했는데(베이스라인 99.26% 대비 96.99%), 이는 공격적인 비용 최소화와 개별 기기의 리스크 사이의 트레이드오프를 나타내며, 페널티 파라미터를 통해 조정 가능하다.

의의 및 주장
본 논문은 QUBO 프레임워크가 GPU 기반 솔빙과 결려 대규모 ATM 현금 물류를 위한 실질적으로 배포 가능한 의사결정 지원 도구를 제공한다고 주장한다. 저자들은 이것이 단순한 이론적 연습이 아니라, 이미 인테사 산파올로(Intesa Sanpaolo)의 프로덕션 단계 파이프라인에 통합되어 운영 중임을 강조한다.

본 연구의 의의는 다음과 같다:

• 선형 모델이 비효리적으로 처리하는 비선형 비용 상호작용(공동 위치 할인)을 포착할 수 있다.
• 산업적 문제에 대해 부상하는 양자 영감 및 고전적 이차 최적화 기술을 활용한다.
• 전체 네트워크의 서비스 품질을 저해하지 않으면서 상당한 재무적 절감(두 자릿수 퍼센트 감소)을 달성한다.
• 보충 방문 횟수를 줄임으로써 차량 배출 가스 및 현금 취급량을 낮추어, 광범위한 운영 및 ESG(환경·사회·지배구조) 이점을 제공한다.

저자들은 현재 구현이 표준 ATM에 집중되어 있으나, 입금 및 인출 예측과 관련된 추가적인 복잡성을 수반하는 현금 자동 입출금기(Cash-recycling ATM)로 프레임워크를 확장하기 위해 검토 중이라고 결론지었다.