A two-stage stochastic optimization model for synchronized two-echelon routing problems

기술 요약: 동기화된 2단계 에첼 라우팅 문제를 위한 2단계 확률적 최적화 모델

문제 정의
본 연구는 도시 물류 내의 불확실성, 특히 통합 수륙 복합 운송(IWLT) 시스템에 초점을 맞춘 복잡성을 다룬다. 핵심 문제는 **위성 동기화가 포함된 2단계 멀티트립 차량 경로 문제(2E-MVRP-SS)**이다. 이 시스템에서 경량 전기 화물차(LEFV)는 1단계(도로)에서 운영되어 고객으로부터 물품을 수거하고 위성 노드에서 선박(2단계)으로 전달한다. 이 시스템은 위성에 저장 옵션이 없으므로, LEFV와 선박 간의 엄격한 시공간적 동기화를 요구한다.

다루고자 하는 주요 과제는 위성에서의 불확상적인 환적 리드 타임으로 인해 발생하는 지연의 전파이다. 이러한 불확실성은 교통 혼잡이나 운영상의 변동과 같은 지역적 요인에서 기인하며, 동기화된 운영을 방해하여 고객 지연, 운영 비용 증가 및 신뢰도 저하를 초래할 수 있다. 본 연구는 특히 재고 비용과 고객 불편을 최소ize하기 위해 적시 서비스가 중요한 역물류 시나리오(예: 폐기물 수거, 반품)를 목표로 한다.

방법론
저자들은 이러한 불확실성을 관리하기 위해 혼합 정수 복구 문제(mixed-integer recourse problem)를 포함하는 2단계 확률적 최적화 프레임워크를 제안한다.

1. 2단계 정식화:

   • 1단계 (마스터 문제): 지연이 실현되기 전에 LEFV 경로와 위성으로의 전달 작업 할당에 관한 결정을 내린다. 이 단계는 픽업을 위한 신뢰할 수 있는 서비스 시간을 우선시한다. 모델은 초기 근사치로서 LEFV가 가장 가까운 위성을 방문한다고 가정한다.
   • 2단계 (복구/부문제): 특정 지연 시나리오가 실현되면 교정 조치가 취해진다. 이는 지연의 영향을 완화하기 위해 환적 작업을 다른 위성으로 재할당하고 선박의 경로를 재최적화하는 것을 포함한다. 약속된 시간을 준수하기 위해 고객 서비스를 위한 LEFV 일정은 고정되지만, 수로 물류는 재최적화된다.

2. 알고리즘 접근 방식:

   • 2단계 비용 함수의 비볼록성(non-convexity)과 혼합 정수의 특성을 처리하기 위해, 저자들은 **조합 벤더 컷(combinatorial Benders cuts)**이 적용된 **L-형 방법(L-shaped method)**을 채택한다.
   • 알고리즘은 완화된 마스터 문제와 각 시나리오에 대한 부문제 사이를 반복한다.
   • **타당성 컷(Feasibility cuts)**은 1단계 결정이 타당한 2단계 솔루션을 허용하도록 보장한다.
   • **최적성 컷(Optimality cuts)**은 기대 2단계 비용을 근사한다.
   • 지역적 불확실성을 나타내기 위해 시나리오 기반 샘플링 접근 방식이 사용된다. 위성에서의 지연은 정규 분포 변수로 모델링되며, 계산 가능성을 유지하면서도 안정성을 확보하기 위해 유한한 시나리오 집합($N$)으로 이산화된다.

3. 실험 설정:

   • 모델은 수정된 Solomon VRPTW 인스턴스에서 파생된 소규모 네트워크 인스턴스(10개 픽업 노드, 4개 위성)에서 테스트되었다.
   • 두 가지 시스템 설계가 비교되었다: 2E-Flexible(선박이 이동식 데포 역할을 하며 LEFV와 동기화됨) 및 2E-Stationary(고정된 선박 위치).
   • 성능은 결정론적(지연 없음) 베이스라인 및 2단계 확률적 접근 방식과 비교하여 평가되었다.

주요 기여

• 동기화의 새로운 모델링: 본 연구는 저장 용량이 없는 2단계 에첼 시스템에서 위성 지연이 차량 동기화에 미치는 영향을 다룬 최초의 연구로, 높은 시공간적 협업을 요구하는 시나리오를 다룬다.
• 확률적 복구 프레임워크: 2E-MVRP-SS를 위해 혼합 정수 복구가 포함된 2단계 확률적 프로그래밍 모델을 제안한다. 비볼록한 2단계를 처리하기 위해 열거법 내에서 조합 벤더 컷을 활용한다.
• 유연성의 비교 분석: 불확실성 하에서 유연한 운송 시스템(이동식 선박)과 고정형 시스템 간의 정량적 비교를 제공하여, 지연 전파를 완화하는 데 있어 유연성의 가치를 입증한다.

결과

• 비용 절감: 제안된 확률적 프로그래밍 모델은 지연이 없다고 가정하는 결정론적 접근 방식에 비해 모든 인스턴스에서 기대 총 비용을 37% 감소시켰다.
• 시나리오 안정성: 시나리오 생성 방식은 안정성을 보여주었다. 샘플 내 시나리오의 분산은 시나리오 수가 증가함에 따라 감소하여 약 30개의 시나리오에서 안정화되었다.
• 네트워크 토폴로지의 영향:
  • 클러스터형(C) 수요 네트워크의 경우, 통합 시스템은 불확실성 하에서도 최소한의 비용 증가(0%에 근접)로 효율성을 유지했다.
  • 랜덤(R) 네트워크의 경우, 확률적 접근 방식은 지연에 민가한 픽업 위치를 더 잘 배치함으로써 결정론적 전략에 비해 가장 큰 절감 효과를 달-성했으며, 특정 인스턴스에서는 기대 비용을 최대 43%까지 줄였다.
• 시스템 성능 (Flexible vs. Stationary):
  • 2E-Flexible 시스템은 신뢰성과 모달 쉐어(modal share) 측면에서 2E-Stationary 시스템보다 크게 우수했다.
  • 불확실성 하에서 고정형 시스템은 도로 주행 시간과 지연 시간이 급격히 증가한 반면(예: RC 인스턴스에서 지연이 26 시간 단위로 증가), 유연한 시스템은 지연을 낮게 유지(9 시간 단위)하고 도로와 수로 간의 모달 쉐어를 더 균형 있게 유지했다.
  • 유연한 시스템은 도로 주행 비용 증가의 위험을 효과적으로 완화하였으며, 이를 통해 저장 단위(이 경우 환적 지점)를 재배치하는 것이 혼잡 및 신뢰성 측면에서 유연한 항행 서비스의 성능을 따라잡을 수 없음을 입증했다.

의의 및 주장
본 논문은 도시 물류, 특히 공간 경쟁으로 인해 저장 옵션이 제한된 맥락에서 오프라인 계획에 불확실성을 포함하는 것이 신뢰성과 비용 효율성을 위해 필수적이라고 주장한다. 연구는 선박이 LEFV와 동기화된 이동식 데포 역할을 하는 유연한 시스템이 고정 위치 시스템에 비해 환적 지연에 대해 우수한 회복 탄력성을 제공함을 보여준다.

저자들은 제안된 모델이 계산 집약적이지만, 소규모 인스턴스에서 관찰된 이득은 확률적 최적화가 도시 물류에서 서비스 신뢰도를 크게 향상시키고 "그린" 모달 쉐어(도로 사용)를 줄일 수 있음을 시사한다고 결론짓는다. 또한 향후 연구에서 제안된 열거 및 프라이싱 프레임워크를 활용하여 대규모 문제를 위한 휴리스틱을 개발할 수 있다고 언급했으나, 현재의 연구는 이론적 프레임워크와 소규모 해결 가능한 네트워크에서 유연성의 이점을 검증하는 데 중점을 두고 있다.