Learning to Route Electric Trucks Under Operational Uncertainty

다음은 "운영 불확실성 하의 전기 트럭 라우팅 학습" 논문에 대한 상세한 기술 요약입니다.

1. 문제 정의: 전기 트럭 함대 라우팅 문제 (eTFRP)

본 논문은 중형 전기 트럭에 맞춰진 고전적인 차량 라우팅 문제 (VRP) 의 복잡한 확장인 **전기 트럭 함대 라우팅 문제 (eTFRP)**를 다룹니다. 표준 라우팅 문제와 달리, eTFRP 는 다음과 같은 특징을 가진 물류 및 에너지 관리의 결합된 과제를 포함합니다:

• 공유 충전 인프라: 여러 트럭이 유한한 용량을 가진 충전소의 제한된 충전 포트에 경쟁하여 내생적 대기 지연을 초래합니다.
• 운영 불확실성: 교통 체증과 날씨의 영향을 받는 이동 시간, 에너지 소비, 하역 시간은 확률적이며 (절단된 가우시안 분포로 모델링됨) 불확실합니다.
• 현실적인 충전 역학: 문제는 배터리 충전 상태 (SoC) 가 증가함에 따라 충전 전력이 감소하는 비선형 DC 급속 충전 동작 (정전류 - 정전압 또는 CCCV) 을 포함하며, 선형 충전을 가정하지 않습니다.
• 함대 수준의 결합: 의사결정은 상호 의존적입니다. 한 트럭의 경로 실행 가능성은 함대 내 다른 트럭들의 행동에 달려 있습니다 (예: 다른 트럭으로 인해 충전소가 혼잡한 경우).

목표는 배터리 고갈을 방지하여 에너지 실행 가능성을 보장하면서, 이동, 충전, 대기, 하역 시간을 포함한 전체 함대의 모든 배송 완료에 소요되는 기대 총 시간을 최소화하는 것입니다.

2. 방법론

저자들은 eTFRP 를 해결하기 위해 **강화 학습 (RL)**을 사용하는 학습 기반 프레임워크를 제안합니다. 핵심 구성 요소는 다음과 같습니다:

A. 문제 공식화

문제는 **이벤트 기반 준마코프 의사결정 과정 (SMDP)**으로 모델링됩니다.

• 상태 공간: 의사결정은 트럭이 "작업 대기" 상태에 진입할 때 (예: 노드에 도착한 후) 만 이루어집니다. 상태는 트럭, 배송 지점, 충전소라는 세 가지 노드 유형을 포함하는 이종 그래프로 표현됩니다.
• 행동 공간: 행동 공간은 변수이며 상태에 의존적입니다. 여기에는 배송 또는 충전기로 이동하거나 충전 지속 시간을 선택하는 작업이 포함됩니다. 운영 실행 가능성을 보장하기 위해 규칙 기반 행동 마스크가 적용되어 정책을 허용 가능한 행동 (예: 배터리 에너지가 부족할 경우 목적지로 이동하는 것을 방지) 으로만 제한합니다.
• 보상 함수: 총 운영 시간을 최소화하기 위해 시간 기반 보상을 사용하며, 실패 (배터리 고갈) 에 대해서는 패널티를, 완료된 배송에 대해서는 보너스를 부여합니다.

B. GraphPPO 아키텍처

저자들은 이종 그래프 인코더를 기반으로 한 그래프 신경망 (GNN) 기반 근접 정책 최적화 (PPO) 알고리즘인 GraphPPO를 소개합니다.

• 상태 인코더: 시스템 상태 그래프를 처리하기 위해 이종 상호작용 계층을 갖춘 이종 그래프 인코더를 사용합니다. 이를 통해 모델은 엔티티 수에 불변성을 유지하면서 (확장성) 트럭, 인프라, 배송 간의 상호작용을 포착할 수 있습니다.
• 행동 인코더: 실행 가능한 행동 집합도 그래프로 인코딩됩니다. 액터 네트워크는 전역 상태 임베딩을 조건으로 하여 이러한 행동 노점에 점수를 매겨 실행 가능한 행동에 대한 확률 분포를 생성합니다.
• 학습: 모델은 일반화된 이점 추정 (GAE) 을 사용한 PPO 알고리즘으로 학습되며, 안정적인 정책 업데이트를 보장하기 위해 클리핑된 대리 목적 함수를 최적화합니다.

C. 시뮬레이션 환경

학습 및 벤치마킹을 지원하기 위해 (Gymnasium 기반) 맞춤형 이벤트 기반 시뮬레이션 환경이 개발되었습니다. 이는 다음을 시뮬레이션합니다:

• 확률적 이동 및 에너지 소비.
• 비선형 CCCV 충전 곡선.
• 충전소의 선입선출 (FCFS) 대기.
• 캘리포니아의 실제 도로 네트워크 데이터.

3. 주요 기여

1. 현실적인 문제 공식화: 본 논문은 공유 충전 자원, 확률적 이동/에너지, 비선형 충전 동작을 명시적으로 모델링하는 이벤트 기반 SMDP 로 eTFRP 를 공식화하여, 기존 문헌에서 발견되는 단순화된 추상화를 넘어섭니다.
2. 그래프 기반 실행 가능성 인식 RL: 명시적인 행동 실행 가능성 마스크와 GNN 을 결합한 GraphPPO의 도입입니다. 이는 RL 에이전트가 사후 복구 메커니즘에 의존하지 않고도 배터리 제약 및 충전소 용량을 준수하는 운영상 유효한 정책을 학습하도록 보장합니다.
3. 종합적 벤치마킹: 통합 시뮬레이션 환경의 개발을 통해 일관된 확률적 가정 하에서 학습 기반 접근법, 수학적 최적화 (MILP), 메타휴리스틱 기준 간의 직접적인 비교가 가능해졌습니다.
4. 확장성 및 일반화: 프레임워크는 단일 트럭에서 대규모 함대 시나리오 (최대 100 대의 트럭) 로 확장하는 능력을 보여주며, 강력한 제로샷 일반화 능력을 입증했습니다.

4. 실험 결과

이 연구는 다양한 함대 크기 (1~100 대) 에 걸쳐 GraphPPO 를 수학적 최적화 (Math. Opt.), 휴리스틱, 일반 PPO, 그리고 마스크 PPO (그래프 구조 없이 행동 마스크가 적용된 PPO) 와 비교 평가했습니다.

• 함대 크기에 따른 성능:

  • GraphPPO는 모든 함대 크기에서 일관되게 최적에 가까운 성능 (정규화 보상 0.987~1.005) 을 달성했으며, 높은 성공률을 유지했습니다 (예: 50 대 트럭 기준 76.5% 성공률 vs 일반 PPO 의 0%).
  • 일반 PPO는 복잡한 실행 가능성 제약을 처리하지 못해 더 큰 설정에서 완전히 실패했습니다 (0% 성공률).
  • MaskPPO는 작은 설정에서는 잘 수행되었으나 함대 크기가 증가함에 따라 크게 저하되었습니다 (100 대 트럭 기준 성공률 2% 로 하락), 이는 함대 수준의 혼잡을 포착하기 위한 그래프 기반 상태 표현의 필요성을 강조합니다.
  • **수학적 최적화 (Math. Opt.)**는 강력한 기준을 제공했으나 대규모 확률적 설정에서 확장성과 계산 시간 측면에서 어려움을 겪었습니다.

• 제로샷 일반화:

  • 오직 100 대 트럭 설정 (100T3S) 에서만 학습된 정책이 재학습 없이 더 작고 더 큰 구성에 적용되었습니다.
  • 해당 정책은 효과적으로 일반화되어 대규모 혼잡 시나리오에서 보수적인 수학적 최적화 기준을 종종 능가했습니다 (50~100 대 트럭 기준 승률 70% 이상).

• 단일 트럭 eVRP:

  • 단일 트럭 설정 (1T20S) 에서 GraphPPO 는 수학적 최적화의 99.7% 에 달하는 근사 최적 보상을 달성하면서 계산 시간을 대폭 단축했습니다 (수학적 최적화 233 초 대비 0.8 초).

• 운영 통찰:

  • GraphPPO 는 휴리스틱보다 배터리를 더 효율적으로 활용했습니다 (잔여 SoC 감소) 그리고 MaskPPO 보다 충전 대기열을 더 잘 관리하여 총 대기 시간을 줄였습니다.

5. 의의

본 논문은 녹색 물류 및 자율 함대 관리 분야에 중요한 기여를 합니다:

• 격차 해소: 수학적 프로그래밍의 이론적 최적성과 학습 기반 방법의 확장성 사이의 격차를 성공적으로 연결합니다.
• 불확실성 처리: 실시간에서 전통적인 휴리스틱 및 정적 최적화를 무력화시키는 복잡한 결합 불확실성 (교통, 에너지, 대기) 을 RL 이 효과적으로 관리할 수 있음을 입증합니다.
• 실제 배포: 제안된 프레임워크는 대규모 혼잡 함대에서도 실시간 (초단위 추론) 으로 고품질 실행 가능한 라우팅 의사결정을 할 수 있는 실제 전기 화물 운영을 위한 실용적인 솔루션을 제공합니다.
• 미래 영향: 이 작업은 그리드 제약, 동적 가격 책정, 예약 시스템을 학습 기반 물류에 통합하기 위한 기초를 마련하여 화물 운송의 탈탄소화를 진전시킵니다.