Vision-Assisted Foundation Model for Solving Multi-Task Vehicle Routing Problems

기술 요약: 다중 작업 차량 경로 문제(VRP) 해결을 위한 시각 보조 파운데이션 모델

문제 정의
다중 작업 차량 경로 문제(Multi-task Vehicle Routing Problems, VRPs)는 백홀 수요(B), 오픈 경로(O), 지속 시간 제한(L), 시간 창(TW)과 같은 다양한 고객 제약 조건을 충족하면서 경로 비용을 최적화하는 것을 포함합니다. 이러한 제약 조건의 조합은 지수적으로 많은 수의 VRP 변형(예: 4가지 제약 조건으로부터 파생된 16가지 변형)을 생성합니다. 기존의 신경망 솔버들은 일반적으로 그래프 기반 모달리티에 의존하며, 제약 조건을 노드 속성으로 인코딩합니다. 그러나 이러한 방식은 다음과 같은 한계에 직면합니다. 과업이 복잡해짐에 따라 복잡한 공간적 관계와 제약 조건 간의 상호작용을 학습하는 데 어려움을 겪으며, 각 변형마다 별도의 모델을 훈련하는 것은 계산적으로 매우 비효율적입니다. 또한, 기존의 시각 기반 조합 최적화 방법들은 단일 작업 시나리오(예: TSP)에 국한되어 왔으며, 시각적 표현 내에 수요나 시간 창과 같은 중요한 작업별 속성을 인코딩하는 데 실패하는 경우가 많습니다.

방법론: 시각 보조 파운데이션 모델 (VaFM)
저자들은 16가지 서로 다른 VRP 변형을 동시에 해결하기 위해 시각과 그래프 모달리티를 통합하는 파운데이션 모델인 VaFM을 제안합니다. 이 아키텍처는 세 가지 주요 구성 요소로 이루어져 있습니다:

1. 다중 작업 VRP 이미지 생성: 기존 VRP 이미지의 제약 표현 부족 문제를 해결하기 위해, 저자들은 인스턴스당 두 개의 입력 이미지인 "수요 이미지(demand image)"와 "시간 창(TW) 이미지"를 설계했습니다.

   • 시각적 인코딩: 고객 좌표는 픽셀 인덱스로 매핑됩니다. 노드의 색상 강도는 연속 변수(수요 크기 또는 시간 창 지속 시간)를 나타냅니다.
   • 제약 조건 표현: 이산적 제약 조건은 시각적 단서를 통해 인코딩됩니다. 오픈 경로(O)는 배경 색상 반전으로 표시되며, 지속 시간 제한(L)은 노드 모양 변경(직사각형에서 플러스 기호로)을 통해 나타납나며, 백홀 수요(B)는 별도의 노드 색상(라인홀은 녹색, 백홀은 파란색)을 사용합니다.
   • 입력: 두 이미지는 결합되어 CNN 기반 비전 인코더(ResNet-18)에 의해 처리됩니다.

2. 하이브리드 교차 주의 집중(Cross-Attention) 융합 모듈: 표준 패치 임베딩의 고정된 수용 영역(receptive field) 문제를 극복하고 다양한 작업 요구 사항을 수용하기 위해, VaFM은 하이브리드 융합 메커니즘을 채택합니다.

   • 메커니즘: 비전 인코더의 마지막 두 레이어에서 특징 맵(feature maps)을 추출합니다. 패치 임베딩은 이 맵들로부터 유도되며 그래프 노드 임베딩과 정렬됩니다.
   • 적응형 수용 영역: 노드 임베딩이 쿼리(query) 역할을 하고, 가장 깊은 레이어의 평탄화된 특징 맵이 키(key) 및 값(value) 역할을 하는 교차 주의 집중 메커니즘이 사용됩니다. 이를 통해 모델은 미세한 국소적 맥락(얕은 레이어)을 유지하면서도 관련 있는 전역 정보(깊은 레이어)를 효과적으로 집계할 수 있어, 다양한 제약 조건에 대해 적응형 수용 영역을 생성할 수 있습니다.

3. 제약 인식 보조 작업: 제약 조건(O 또는 L)이 다른 제약 조건(B 또는 TW)보다 더 많은 픽셀을 차지하여 모델이 후자를 간과할 수 있는 불균형한 픽셀 분포 문제를 완화하기 위해 보조 작업이 도입되었습니다.

   • 구현: 비전 인코더에 4가지 제약 조건(O, L, B, TW)의 존재 여부를 예측하는 분류기를 부착합니다.
   • 손실 함수: 이 보조 작업에 이진 교차 엔트로피(BCE) 손실이 적용되어, 시각적 두드러짐에 관계없이 모든 제약 조건에 대해 균형 잡힌 표현을 학습하도록 보장합니다.
   • 학습 목표: 전체 손실은 경로 비용 최소화를 위한 강화 학습(RL) 손실과 보조 분류 손실의 가중 합으로 구성됩니다.

주요 기여

• 최초의 다중 작업 VRP를 위한 시각 보조 파운데이션 모델: 본 연구는 단일 작업 시각 솔버를 넘어 여러 VRP 변형을 동시에 처리하기 위해 그래프와 시각 모달리티를 결합한 최초의 프레임워크를 소개합니다.
• 새로운 시각적 인코딩 및 융합: 다양한 제약 조건을 인코딩하기 위한 특정 이미지 설계와, 다중 작업 환경에서 고정된 패치 크기의 한계를 해결하는 적응형 수용 영역을 가능하게 하는 하이브리드 교차 주의 집중 융합 모듈을 제안합니다.
• 균형 잡힌 제약 학습: BCE 손실을 사용하는 제약 인식 보조 작업을 도입하여, 시각적 픽셀 수가 적은 제약 조건이 무시되는 것을 효과적으로 방지합니다.

실험 결과
모델은 50개 및 100개의 고객 노드에 대해 16가지 VRP 변형에서 HGS-PyVRP, OR-Tools 및 다양한 신경망 솔버(MTPOMO, MVMoE, RF-MoE-L)를 포함한 최첨단(SOTA) 방법들과 비교 평가되었습니다.

• 성능: VaFM(특히 VaFM-MoE-L 변형)은 N=50인 경우 16개 중 15개 케이스에서, N=100인 경우 16개 중 12개 케이스에서 최고의 성능을 달 счет했습니다.
• 복잡한 제약 조건: 제약 조건의 수가 증가함에 따라 VaFM과 그래프 전용 베이스라인 간의 성능 격차가 벌어졌습니다. 예를 들어, 3개 또는 4개의 제약 조건이 있는 작업에서 VaFM은 베이스라인인 RF-MoE-L에 비해 최적성 격차(optimality gap) 측면에서 상당한 개선을 보였습니다.
• 일반화: VaFM은 더 큰 규모(N=200) 및 보지 못한 제약 조합(혼합 백홀)에 대해 강력한 제로샷 일반화 능력을 보여주었으나, 실제 데이터셋 및 특정 시간 창 중심 작업에서는 일부 불안정성을 보였는데, 이는 대규모 인스턴스에서의 색상 기반 식별 능력에 대한 한계를 시사합니다.
• 효율성: VaFM은 비전 브랜치로 인해 그래프 전용 베이스라인보다 추론 시간이 약간 더 소요되지만, HGS-PyVRP와 같은 휴리스틱 솔버보다는 현저히 빠릅니다.

의의 및 주장
본 논문은 복잡한 다중 제약 최적화 문제를 표현하기 위해 시각 모달리티를 그래프 기반 신경 솔버에 통합하는 것이 잠재력이 있음을 입증한다고 주장합니다. 저자들은 자신들의 접근 방식이 순수 그래프 모델이 학습하기 어려운 패치 수준의 의미론(공간적 수요 분포 및 서비스 시간 패턴)을 성공적으로 포착한다고 단언합니다. 결과는 시각 보조 모델이 복잡하고 상호 작용하는 제약 조건을 가진 VRP 변형에서 특히 우월하다는 것을 시사합니다. 그러나 저자들은 현재의 시각적 인코딩(단일 색상 강도에 의존)이 대규모 인스턴스에서의 미세한 식별에 어려움을 겪을 수 있으며, 멀티모달 거대 언어 모델 등을 통해 실제 데이터셋 및 미지의 제약 조건에 대한 일반화 능력을 개선하기 위한 향후 연구가 필요함을 인정하며 한계를 겸허히 밝히고 있습니다.