A Computational Method for Solving the Stochastic Joint Replenishment Problem in High Dimensions

기술적 요약: 고차원 확률적 공동 발주 문제 해결을 위한 계산 방법

문제 공식화
본 논문은 고정된 발주 비용이 함께 주문된 품목들에 대해 공동으로 발생하는 다품목 재고 시스템의 조정을 포함하는 고전적인 재고 관리 과제인 확률적 공동 발주 문제 (SJRP) 를 다룹니다. 고려된 이산 시간 공식화에서 창고 관리자는 정기적으로 재고 수준을 검토하고 $d$개 품목의 부분집합에 대해 주문을 할지 여부를 결정합니다. 시스템은 무작위 수요, 선형 보유 비용, 그리고 미처리 벌금에 직면합니다. 목표는 무한 시간 범위 내에서 총 기대 할인 비용을 최소화하는 것입니다.

핵심적인 어려움은 '차원의 저주'에 있습니다. 0 이 아닌 고정 발주 비용 하에서 품목 수준의 의사결정은 상호의존적이 되어, 관련 마르코프 의사결정 과정 (MDP) 의 상태 및 의사결정 공간이 품목 수 ($d$) 에 따라 기하급수적으로 증가합니다. 결과적으로 표준 동적 프로그래밍 기법은 고차원 환경 (예: $d \ge 50$) 에서 계산적으로 처리 불가능해지며, 기존 문헌은 최적성에 대한 제한된 이론적 보장을 가진 휴리스틱 정책에 크게 의존해 왔습니다.

방법론
이러한 계산적 장벽을 극복하기 위해 저자들은 이산 시간 재고 제어와 연속 시간 임펄스 제어 이론 및 딥러닝을 연결하는 새로운 시뮬레이션 기반 계산 방법을 제안합니다.

1. 연속 시간 근사: 이산 시간 SJRP 는 연속 시간 임펄스 제어 문제로 근사됩니다. 이 공식화에서 누적 수요 과정은 가우시안 과정 (드리프트가 있는 브라운 운동) 으로 모델링되며, 관리자는 고정 비용으로 재고 상태를 높은 수준으로 즉시 점프시키기 위해 언제든지 개입할 수 있습니다. 이 근사는 고차원 해결 기법에 더 적합한 가치 함수의 확률적 표현을 가능하게 합니다.

2. 제약 BSDE 를 통한 확률적 표현: 거의-필연적 (almost-sure) 등식에 의존하는 표준 딥 백워드 확률 미분 방정식 (BSDE) 방법과 달리, 이 임펄스 제어 문제의 가치 함수는 제약된 BSDE 의 최소 해로 특징지어집니다. 이는 등식이 아닌 거의-필연적 부등식을 포함하는 확률적 항등식으로 이어집니다. 구체적으로, 가치 함수 $V(x)$는 기준 과정, 진행 비용, 그리고 점프 비용과 관련된 확률적 목표 조건을 만족하는 값 $v$들의 상한입니다.

3. 딥 신경망 솔버: 저자들은 딥 신경망을 사용하여 이 제약된 BSDE 를 풀기 위한 계산 알고리즘을 개발합니다.

   • 손실 함수: 부등식 제약을 처리하기 위해 새로운 손실 함수가 구성됩니다. 이는 조정 가능한 벌금 매개변수 $\beta$로 가중된 확률적 부등식 위반에 대한 벌금 항을 포함합니다.
   • 기준 과정: 포아송 과정에 의해 주도되는 무작위화된 주문 - 상한 정책과 같은 신중하게 설계된 기준 정책이 샘플 경로를 생성하는 데 사용됩니다. 이 과정은 탐색과 활용을 균형 있게 유지하도록 설계되어 신경망이 상태 공간의 관련 영역에서 훈련되도록 보장합니다.
   • 훈련 전략: 안정성을 보장하기 위해 저자들은 벌금 매개변수 $\beta$와 학습률에 대한 공동 일정을 채택합니다. 벌금은 점차 증가시키고 학습률은 감소시켜, 네트워크가 먼저 일반적인 구조를 학습한 다음 부등식 제약을 엄격하게 시행하도록 합니다.

4. 정책 추출: 가치 함수 $V$와 그 기울기 $\nabla V$가 신경망으로 근사되면 실행 가능한 정책이 도출됩니다. 이 정책은 해밀턴 - 야코비 - 벨만 (HJB) 방정식에서 유도된 '비행동' 조건을 확인합니다. 조건이 위반되면 주문이 발생합니다. 주문 - 상한 벡터는 근사된 가치 함수와 주문 비용의 합을 최소화함으로써 결정되며, 이 단계는 효율적으로 사전 계산될 수 있습니다.

주요 기여

• 고차원 확장성: 이 방법은 전통적인 MDP 기반 최적 해법이 처리 불가능한 영역인 최소 50 개 (50 개 SKU) 의 차원까지 SJRP 를 성공적으로 해결합니다.
• 새로운 손실 설계: 임펄스 제어에 필요한 제약된 BSDE 프레임워크에 맞춰 특정 손실 함수와 훈련 일정을 도입하여, 표준 딥 BSDE 방법이 처리하지 않는 거의-필연적 부등식의 문제를 해결합니다.
• 기준 과정 설계: 상태 의존적 점프를 가진 기준 과정의 설계는 효율적인 훈련과 관련 상태 공간의 커버리지를 보장하는 중요한 혁신으로 강조됩니다.
• 구현: 저자들은 문제 근사부터 정책 추출까지, 상세한 하이퍼파라미터 조정 전략과 계산 결과를 포함한 완전한 파이프라인을 제공합니다.

결과
제안된 신경망 (NN) 정책은 2, 12, 50 차원에 걸쳐 43 개의 테스트 문제에서 다양한 수요 변동성 (낮음, 중간, 높음) 및 비용 구조로 평가되었습니다.

• 낮은 차원 ($d=2$): NN 정책은 표준 MDP 해결 기법을 통해 유도된 실제 최적 정책과 비교되었습니다. 결과는 NN 정책이 최적 비용의 1% 이내에서 수행되며 최적 의사결정 경계의 기하학을 밀접하게 추적함을 보여줍니다.
• 높은 차원 ($d=12$ 및 $d=50$): 최적 해법이 처리 불가능하므로 NN 정책은 최첨단 휴리스틱인 주기적 검토 $(R, S)$, $(Q, S)$, 하이브리드 $(R, Q, S)$, 캔 - 오더, 그리고 독립적인 $(s, S)$ 정책과 비교되었습니다.
  • 12 차원에서 NN 정책은 모든 경우에 최상의 벤치마크와 일치하거나 능가했습니다. 중간 및 높은 변동성 환경에서는 종종 최상의 휴리스틱을 크게 능가했습니다 (예: 특정 높은 변동성 사례에서 $(R, S)$ 대비 최대 28% 개선).
  • 50 차원에서 NN 정책은 모든 테스트 사례에서 사용 가능한 최상의 휴리스틱을 일관되게 능가했으며, 성능 격차는 최대 5.59% 에 달했습니다.
• 계산 효율성: 훈련 시간은 차원에 따라 modest하게 증가합니다 (예: 단일 GPU 에서 50 차원 약 4 시간). 그리드 기반 방법의 전형적인 기하급수적 증가를 피합니다.

의의 및 주장
본 논문은 이 방법이 운영 관리의 오랜 과제인 고차원 확률적 공동 발주 문제에 대한 준최적 정책을 얻기 위한 계산적으로 실행 가능한 방법을 제공한다고 주장합니다. 딥러닝을 활용하여 근본적인 고차원 임펄스 제어 문제를 해결함으로써 저자들은 제한적인 구조적 가정에 의존하지 않고도 기존 최상의 휴리스틱과 일치하거나 능가하는 성능을 달성할 수 있음을 입증합니다. 저자들은 현재 이 방법이 선형 비용과 제약되지 않은 주문 벡터를 가진 SJRP 에 적용되지만, 이 프레임워크는 금융 공학 (예: 현금 흐름 관리) 및 리드타임이나 손실 판매가 있는 공급망과 같은 다른 임펄스 제어 문제로 일반화 가능하다고 언급하지만, 이러한 확장은 향후 연구에 맡겨졌습니다. 논문은 제안된 정책이 단순한 휴리스틱이 아니라 엄격한 확률적 공식화에서 유도된 최적 제어에 대한 데이터 기반 근사임을 강조합니다.