Dynamic Multi-Depot Vehicle Routing with Online Requests: Event-Driven Transformer--DRL and Rolling-Horizon Benchmarking

기술 요약: 온라인 요청 기반의 동적 다중 데포 차량 경로 문제 (Dynamic Multi-Depot Vehicle Routing with Online Requests)

문제 정의
본 논문은 요청이 점진적으로 공개되고 차량 상태가 진화하는 특성을 가진 동적 다중 데포 차량 경로 문제(D-MDVRP)를 다룹다. 모든 요청을 배차 전에 미리 알고 있는 정적 VRP와 달리, D-MDVRP는 경로 실행 중에 새로운 서비스 요청이 도착하는 순차적 의사결정 환경을 포함한다. 디스패처는 차량 용량, 서비스 수요, 경로 지속 시간, 변화하는 차량 위치와 같은 제약 조건을 관리하면서, 어떤 데포의 어떤 차량이 각 요청을 수행할지 결정해야 한다. 이 문제는 운영 효율성(거리 및 대기 시간 최소화)과 안정성(기존 계획의 교란 최소화) 사이의 균형을 요구하는 순차적 의사결정 과정으로 프레임화된다.

방법론
저자들은 결정론적 타당성 처리(deterministic feasibility handling)와 심층 강화 학습(DRL) 및 전통적인 최적화 기법을 결합한 통합된 이벤트 기반 학습 및 벤치마킹 프레임워크를 제안한다.

• 상태 및 행동 표현: 환경은 정규화된 특징 벡터를 사용하여 요청과 차량을 모델링한다. 요청에는 위치, 수요, 우선순위, 도착 시간 및 상태(미공개, 대기 중, 할당됨, 이동 중, 서비스 중, 완료됨)가 포함된다. 차량은 위치, 잔여 용량, 상태 및 홈 데포(home depot)로 표현된다. 상태에는 시뮬레이션 시간 및 재계획 횟수와 같은 글로벌 특징이 포함된다.
• 이벤트 기반 시뮬레이션: 시스템은 이산 이벤트(요청 도착, 차량 도착, 서비스 시작/완료)를 통해 진행된다. 각 재계획 이벤트에서 경로는 고정 접두사(fixed prefix)(완료되었거나, 활성 상태이거나, 단기적으로 확정된 결정)와 **유연한 접미사(flexible suffix)**로 분해된다. 오직 유연한 접미사만이 재할당 또는 재정렬의 대상이 된다.
• 타당성 마스킹(Feasibility Masking): 결정론적 마스킹 메커니즘은 유효하지 않은 행동(예: 완료된 요청 할당 또는 용량 위반)을 방지한다. 유효하지 않은 차량-요청 쌍은 소프트맥스(softmax) 또는 그리디(greedy) 선택 전 로그릿(logits)에 음의 무한대 값을 할당하여, 훈련 및 테스트 중 100%의 타당성을 보장한다.
• 정책 아키텍처:
  • MLP 정책: 다층 퍼셉트론(Multi-Layer Perceptron)을 사용하여 요청, 차량, 글로벌 및 쌍별 특징(예: 증분 거리, 예측 대기 시간)을 바탕으로 차량-요청 쌍의 점수를 산출한다.
  • 트랜스포머(Transformer) 정책: 인코딩된 요소 간의 의존성을 모델링하기 위해 어텐션(attention) 메커니즘을 활용한다. 요청, 차량, 데포를 위한 별도의 토큰을 사용하며, 학습된 위치 임베딩과 글로벌 컨텍스트 벡터를 사용한다.
• 훈련 체계: 정책은 전문가 시연(대기 인지 삽입 또는 하이브리드 전문가와 같은 휴리스틱에서 유도됨)을 사용하는 **행동 복제(Behavior Cloning, BC)**를 거쳐 근사 정책 최적화(PPO) 미세 조정 단계로 훈련된다. 보상 함수는 거리, 대기 시간 및 경로 변경에 대한 페널티를 포함하여 평가 목적과 일치하도록 설계되었다.
• 벤치마킹: 학습된 정책을 다음 항목들과 비교한다:
  1. 동적 삽입 휴리스틱: 최근접 유효 삽입(nearest feasible), 최저 비용 추가(cheapest append), 대기 인지 삽인(waiting-aware insertion)을 포함한다.
  2. 롤링 호라이즌(Rolling-Horizon) 최적화: OR-Tools/SCIP를 사용하여 유연한 요청들에 대해 제한된 시간(1초) 동안 재최적화를 수행한다.

주요 기여

1. 통합 프레임워크: 본 논문은 이벤트 기반 D-MDVRP 환경, 결정론적 타당성 마스킹, 그리고 고정 접두사/유연한 접미사 경로 확정을 결합한 통합 프레임워크를 제시한다.
2. 안정성 인지 지표: 차량 재할당(vehicle reassignment)과 선행자 변경(predecessor change, 재순서화)을 구분하는 별도의 측정치를 도입하여, 모든 수정을 단일 지표로 취급하는 대신 경로 교란에 대한 세밀한 분석을 가능하게 한다.
3. 공통 프로토콜 벤치마킹: 학습된 정책, 휴리스틱, 롤링 호라이즌 최적화를 동일한 타당성 규칙, 확정 호라이즌 및 시나리오 시드 하에서 평가함으로써, 종종 개별적으로 연구되는 구성 요소들 간의 공정한 비교를 제공한다.
4. 전이 가능성 분석: 학습된 정책이 재학습 없이 더 큰 규모의 문제 인스턴스(최대 80개 요청)로 확장될 수 있는지 조사한다.

실험 결과
실험은 데포, 차량, 요청의 수가 다양한(총 30, 50, 80개 요청) 합성 유클리드 인스턴스를 대상으로 수행되었다.

• 휴리스틱 대비 성능: 20개 시나리오 벤치마크에서, "최근접 유효(Nearest Feasible)" 휴리스틱이 모든 학습된 정책(MLP 및 Transformer, PPO 적용 여부와 상관없이)과 롤링 호라이즌 베이스라인보다 일관되게 우수한 성능을 보였다. 최근접 유효 방식은 가장 낮은 평균 목적 함수(346.1), 가장 낮은 거리, 가장 낮은 대기 시간, 가장 높은 안정성(최소한의 경로 변경), 그리고 가장 빠른 실행 시간(0.156 ms/action)을 달면했다.
• PPO의 영향: 5회의 독립적인 훈련 실행 결과, PPO 미세 조정은 MLP 정책에 미미한 평균 개선 효과(0.13%)를 보였으나, Transformer 정책의 경우 약 2.5%의 개선을 보였으나 시드(seed)에 따른 변동성이 더 컸다.
• 확장성: 학습된 정책은 재학습 없이 더 큰 인스턴스(최대 80개 요청)로 성공적으로 전이되었으며, 밀리초 단위의 결정 시간을 유지했다. 그러나 문제 규모가 커짐에 따라 목적 함수 값과 실행 시간이 증가했으며, 여전히 가장 강력한 휴리스틱의 성능을 넘어서지 못했다.
• 롤링 호라이즌 트레이드오프: 롤링 호라이즌 최적화는 가장 낮은 대기 시간과 메이크스팬(makespan)을 달랐으나, 휴리스틱 및 학습된 정책에 비해 현저히 높은 계산 비용과 더 큰 경로 교란을 초래했다.
• 절제 연구(Ablation Study): 단기 확정(near-term commitments) 또는 재할당 페널티를 제거하면 전체 목적 함수가 증가했으며, 재할당 페널티 제거가 통계적으로 유의미한 결과(p = 0.007)를 보였다.

의의 및 주장
본 논문은 주요 기여가 더 우수한 라우팅 알고리즘의 발명이 아니라, 이러한 구성 요소들의 통합 및 엄격한 비교에 있다고 겸허히 주장한다. 실험 결과는 학습된 정책이 실행 가능한 밀리초 단위의 결정을 제공하고 인스턴스 크기에 따른 전이 가능성을 보여주지만, 경로 효율성, 서비스 응답성, 안정성 또는 온라인 계산 시간 측면에서 가장 강력한 휴리스틱(Nearest Feasible)을 능가하지 못했음을 입증한다.

저자들은 동적 라우팅을 평가할 때 강력한 휴리스틱 베이스라인의 중요성을 강조한다. 본 연구는 타당성 처리, 경로 확정 및 안정성 측도를 통합하는 것이 견고한 동적 라우팅 정책을 만드는 데 가치가 있음을 보여주지만, 현재의 학습 기반 방법론은 이 특정 설정에서 고전적 휴리스틱을 능가하지 못하고 있음을 시사한다. 본 연구는 효율성, 응답성, 안정성, 속도라는 모든 기준에서 단일 방법론이 최적일 수는 없음을 강조하며, 방법론의 선택은 실제 애플리케이션의 구체적인 운영 우선순위에 달려 있음을 시사한다.