Learning Optimization Proxies for Sequential Contextual Stochastic Programs: An Order Fulfillment Application

기술 요약: 순차적 문맥적 확률 계획을 위한 학습 기반 최적화 프록시

문제 정의

본 논문은 대규모 이커머스의 **옴니채널 주문 이행(omnichannel order fulfillment)**에 초점을 맞추어, 실시간 의사결정 시스템에서의 순차적 문맥적 확률 계획(sequential contextual stochastic programs) 문제를 다룹니다. 이 환경에서 의사결정자는 미래의 배송 시간 및 수요에 대한 불확실성 하에서 도착하는 주문을 물류 센터(DC)와 운송 서비스에 할당해야 합니다.

핵심적인 어려움은 **지연 시간 제약(latency constraint)**에 있습니다. 상용 최적화 솔버를 통해 **문맥적 샘플 평균 근사법(C-SAA)**으로 고품질의 결정을 오프라인에서 생성할 수 있지만, 이러한 솔버는 일반적으로 인스턴스당 수 초에서 수 분이 소java요합니다. 이는 분당 수백 건의 주문을 처리해야 하는 피크 운영 시간(예: 명절 세일 기간)에는 불충분합니다. 결과적으로, 운영 시스템은 모델링된 불확실성을 무시하는 더 단순한 휴리스틱으로 회귀하게 되며, 이는 비용 및 서비스 수준의 최적화 실패로 이어집니다.

문제는 다음과 같은 2단계 문맥적 확률 계획으로 정식화됩니다:

1. 1단계: 현재의 문맥(주문 속성, 재고 수준, 운송 비용)과 미래 불확실성의 샘플 시나리오를 기반으로 주문의 제품을 DC 및 운송 서비스에 즉시 할당합니다.
2. 2단계: 1단계 결정에 의해 소비된 재고를 고려할 때, 미래의 주문($t+1 \dots T$)에 대해 예상되는 미래 배송 및 품절 비용을 나타내는 집계된 후속 조치(recourse)를 계산합니다.

목표는 배송, 비대칭적 배송 시간 페널티(지연 vs 조기 도착), 통합 할인, 품절 페널티를 포함한 총 예상 비용을 최소화하면서 재고 제약을 준수하는 것입니다.

방법론

저자들은 매 에포크(epoch)마다 솔버를 호출하는 대신, 신경망의 단일 순전파(forward pass)와 그 뒤를 잇는 제약 조건 준수 디코더(feasibility-enforcing decoder)로 대체하는 학습 기반 최적화 프록시를 제안합니다.

1. 아키텍처: 시나리오 임베디드 계층적 신경망
점 예측(point forecast)에 의존하는 기존의 최적화 프록시와 달리, 이 모델은 **시나리오 인식형(scenario-aware)**입니다. 모델은 다음을 입력으로 받습니다:

• 문맥적 특징(Contextual Features): 주문 상세 정보, DC 재고 상태, 운송 비용 행렬.
• 시나리오 세트: 적합된 예측기(수요를 위한 Multi-Horizon Quantile RNN, 배송 시간을 위한 Multi-Quantile MLP)에 의해 생성된 미래 수요 및 배송 시간 편차의 샘플 실현값.

네트워크는 순서가 없는 시나리오 세트를 처리하기 위해 DeepSets 스타일의 인코더를 사용하여, C-SAA 목적 함수의 기댓값 구조를 근사하기 위해 임베딩을 평균화합니다. 아키텍처는 계층적입니다:

• DC 헤드: 각 물류 센터에 대한 로짓(logit)을 예측합니다.

• **운송 헤드:** 선택된 DC를 조건으로 하는 각 운송 서비스에 대한 로짓을 예측합니다.
  

이러한 인수 분해($p(j) \cdot p(k|j)$)는 전체 결합 할당 공간을 학습하는 복잡성을 줄여줍니다.

2. 학습 전략: 복합 손실 함수(Composite Loss Function)
프록시는 C-SAA 솔버로부터 생성된 레이블을 사용하여 오프라인에서 학습됩니다. 학습 목표는 세 가지 항을 결합합니다:

• 레이블 모방(선택 손실): C-SAA 솔루션에서 도출된 주요 DC 및 운송 선택에 대한 교차 엔트로피 손실입니다.
• 제약 위반 페널티: 가용 재고를 초과하는 할당에 대해 벌점을 부여하여 모델이 하드 제약을 준수하도록 보장하는 Straight-Through Gumbel-Softmax 기반의 자기 지도 학습 항입니다.
• 비용 정렬: 샘플링된 시나리오에서 관찰된 즉각적인 비용을 바탕으로 확률 질량을 낮은 비용의 (DC, 운송) 쌍으로 끌어당기는 자기 지도 학습 정규화 항입니다.

3. 추론: 재고 가중 디코딩(Inventory-Weighted Decoding)
런타임 시, 신경망은 로짓을 출력하며 이는 확률로 변환됩니다. 이후 전용 디코더가 제약 조건을 준수하도록 합니다:

• 각 DC의 분율 재고 커버리지($min\{Inv/q, 1\}$)에 따라 예측된 확률을 재가중합니다.
• 적격한 DC와 운송 서비스를 그리디 스캔(greedy scan)하여, 주문이 이행되거나 재고가 소진될 때까지 수요를 할당합니다.
• 이 과정은 최종 결정이 엄격히 실행 가능함(재고 캡 준수 및 수요 충족)을 보장하며, $O(|J| \log |J| + |J||K|)$ 시간 복잡도를 가집니다.

주요 기여

본 논문은 네 가지 주요 기여를 합니다:

1. 시나리오 조건부 프록시: 점 예측이 아닌 샘플링된 시나리오 세트에 명시적으로 의존하여, 즉각적인 확률적 비용과 자원 소비의 순차적 영향을 모두 포착하는 새로운 아키텍처를 제안합니다.
2. 순차적 이행 모델: 즉각적인 주문 할당을 재고 소비의 기회비용과 명시적으로 연결하는 2단계 문맥적 확률 계획을 구축합니다.
3. 이론적 보장: 저자들은 재고 가중 디코더가 로그-선형 시간 복잡도로 실행 가능한 결정을 생성함을 증명합니다. 또한, 프록시의 기대 비용이 최적의 2단계 목적 함수를 상한(upper-bound)하며, 그 표본 외(out-of-sample) 성능이 편향되지 않고 일관된 추정치를 허용함을 입증합니다.
4. 실증적 검증: JD.com의 거래 기록과 독자적인 운송 데이터를 사용하여 보정된 시뮬레이터를 통한 종합적인 계산 연구를 수행했습니다.

결과

보정된 시뮬레이터에서 제안된 프록시는 솔버 기반 베이스라인 및 확립된 휴리스틱 정책보다 유의미한 개선을 보여주었습니다:

• 지연 시간: 결정 지연 시간이 온라인 유한 샘플 C-SAA 참조 모델 대비 약 2,800배 감소하여, 서브 세컨드(sub-second) 응답이 가능해졌습니다.
• 비용 효율성: 프록시는 C-SAA 베이스라인(이미 고품질이지만 느린 모델) 대비 실현 이행 비용을 3.3% 개선하였으며, 기존의 이행 정책 대비 총 실현 비용을 최소 10.7% 절감했습니다.
• 서비스 수준: 프록시는 가장 강력한 고전적 베이스라인들의 지연 배송률을 거의 절반으로 줄여, 고객 만족도를 결정짓는 정시 배송 지표를 직접적으로 개선했습니다.

의의

본 논문은 이커머스 이행과 같이 볼륨이 크고 지연 시간에 민선한 운영에서, 최적화 품질과 계산 속도 사이의 트레이드오프가 핵심적인 병목 구간임을 주장합니다. 솔버가 생성한 레이블로부터 학습하면서 동시에 시나리오를 통해 불확실성을 명시적으로 모델링하는 프록시를 개발함으로써, 저자들은 최적에 가까운 의사결정 품질과 실시간 추론 속도를 동시에 달eric 수 있음을 입증했습니다. 이 접근 방식은 문맥적 확률 최적화의 이론적 이점과 산업 규모의 실시간 의사결정 시스템의 실제 제약 사이의 간극을 메워줍니다. 본 연구는 전통적인 솔버가 온라인 배포에 너무 느린 환경에서 이러한 프록시가 휴리스틱의 유효한 대안이 될 수 있음을 시사합니다.