기술 요약: COAgents – 라우팅 문제를 위한 다중 에이전트 프레임워크

문제 정의

용량 제한 차량 라우팅 문제 (CVRP) 와 시간 창이 있는 차량 라우팅 문제 (VRPTW) 를 포함한 차량 라우팅 문제 (VRP) 는 물류 및 제조업의 핵심이지만, 조합적 복잡성으로 인해 대규모 규모에서 계산적으로 해결하기 어렵습니다. 전통적인 휴리스틱 방법은 지역 최적점을 탈출하기 위해 지역 개선 및 다양화 (점프) 를 위한 수동 제작 규칙에 의존합니다. 그러나 이러한 정적 규칙 집합은 다양한 인스턴스 간 일반화가 부족하고, 튜닝을 위해 광범위한 도메인 전문 지식을 요구하며, 진화하는 문제 분포에 적응할 수 없습니다. "학습 기반 탐색 (Learn-to-Search, L2S)"접근법이 등장했지만, 많은 방법들은 탐색 이력이나 광범위한 탐색 공간 구조를 효과적으로 모델링하지 못한 채 연산자 선택이나 현재 상태 결정에만 초점을 맞추고 있습니다.

방법론: COAgents 프레임워크

저자들은 VRP 탐색 과정을 그래프 탐색으로 모델링하는 협력형 다중 에이전트 프레임워크인 COAgents를 제안합니다. 핵심 혁신은 **부분 탐색 그래프 (Partial Search Graph, PSG)**로, 이는 탐색된 솔루션을 노드로, 지역 이동 또는 대규모 교란 (점프) 을 엣지로 나타내는 동적으로 구축된 부분 그래프입니다.

1. 부분 탐색 그래프 (PSG)

PSG 는 이력 인식 상태 인코딩 역할을 합니다. 이는 방향성이 있고 분리된 그래프로, 다음과 같은 특징을 가집니다:

• 노드: 탐색 중 발견된 개별 솔루션을 나타냅니다.
• 엣지: 이웃 이동 (지역 정제) 또는 점프 (대규모 교란) 를 나타냅니다.
• 구조: 그래프는 연결된 구성 요소 (샘플) 로 분해되며, 각 구성 요소는 지역 최적점 주변의 이웃을 탐색합니다. 이 구조는 시스템이 탐색의 궤적을 추적하고 탐색 패턴을 식별할 수 있게 합니다.

2. 다중 에이전트 아키텍처

COAgents 는 PSG 위에서 작동하는 세 가지 학습된 에이전트를 사용하며, 모두 게이트형 그래프 합성곱 네트워크 (GGCN) 와 트랜스포머로 구성된 공통 신경 백본을 공유합니다:

• 노드 선택 에이전트 (NSA): PSG 에서 다음 지역 탐색 단계의 현재 솔루션 (incumbent) 으로 작용할 후보 솔루션 (노드) 을 선택합니다. 이는 역사적 데이터를 기반으로 탐색 공간의 유망한 영역을 우선시합니다.
• 이동 선택 에이전트 (MSA): 선택된 솔루션에 적용할 가장 유망한 이웃 연산자 (이동) 를 예측하여 지역 집중을 주도합니다.
• 점프 에이전트 (JA): 탐색이 정체될 때 (반복된 실패 시도로 표시됨) 발동되며, 이 에이전트는 탐색 이력을 바탕으로 처음부터 완전히 새로운 솔루션을 생성합니다. 표준 연산자와 달리 점프 에이전트는 지역 최적점을 탈출하고 탐색을 미탐색 영역으로 유도하기 위해 학습된 재시작을 수행합니다.

3. 모델 아키텍처 및 학습

• 인코딩: 솔루션은 전역 속성 (목적 함수 값, 실현 가능성) 과 내부 구조 행렬 ($V_i$) 을 포착하는 노드 특징 ($u_i$) 으로 인코딩됩니다. 위치 임베딩은 PSG 구조에 대한 랜덤 워크 인코더와 솔루션 위상에 대한 문제 특화 인코더를 통해 유도됩니다.
• 핵심 블록: 네트워크는 PSG 내의 지역 구조적 패턴을 포착하기 위해 교차된 GGCN 레이어와 모든 노드 간의 장거리 의존성을 모델링하기 위해 트랜스포머 레이어를 사용합니다. 문제 특화 엔드 투 엔드 (E2E) 모듈은 조합 문제의 내부 구조를 정제합니다.
• 학습:
  • NSA 및 MSA: 최적에 가장 가까운 솔루션과 최상의 다음 이동을 각각 식별하기 위해 이진 분류 작업으로 공동 학습되며, 결합 이진 교차 엔트로피를 최소화합니다.
  • 점프 에이전트: 새로운 솔루션을 나타내는 확률적 인접 행렬을 예측하도록 별도로 학습되며, 레이블 모호성을 줄이기 위해 준최적 참조 솔루션 집합에 대해 학습됩니다.
• 추론: 프레임워크는 NSA 가 노드를 선택하고, MSA 가 이동을 선택하며, PSG 가 업데이트되는 루프를 실행합니다. 정체가 발생하면 JA 가 호출됩니다. 이는 계산 예산 (시간 또는 노드 제한) 에 도달할 때까지 계속됩니다.

주요 기여

1. 새로운 학습 에이전트: 이동 선택 에이전트와 함께 노드 선택 에이전트 및 점프 에이전트 도입. 이러한 에이전트들은 수동 제작 규칙을 대체하여 솔루션 선택, 연산자 적용 및 다양화를 위한 적응형 데이터 기반 의사결정 정책을 가능하게 합니다.
2. 통합된 가중치 공유 아키텍처: 모든 에이전트가 공통 신경 백본을 공유하여 데이터 효율적인 학습, 새로운 문제 변형으로의 전이 가능성, 그리고 전문가 튜닝 필요성 감소를 촉진합니다.
3. 부분 탐색 그래프 표현: 에이전트 의사결정을 주도하는 일반적이고 이력 인식 상태 인코딩으로서 PSG 의 형식화. 이는 현재 상태에만 의존하는 방법들과 구별됩니다.
4. 솔버 및 문제 적응형 프레임워크: COAgents 는 기존 지역 탐색 루틴과 신경 솔버를 감싸서, 다양한 VRP 변형에 원활하게 적응하는 적응형 정책으로 이를 강화합니다.

실험 결과

이 프레임워크는 10,000 개의 학습 인스턴스와 표준 테스트 세트 (예: 1,000 개의 VRPTW 인스턴스) 를 사용하여 CVRP 및 VRPTW 벤치마크에서 평가되었습니다.

• VRPTW 성능: COAgents 는 학습 기반 방법 중 새로운 최첨단 (state of the art) 을 달성했습니다.
  • 가장 강력한 신경 솔버 (POMO) 대비 최적성 갭을 N=100 에서 14%, N=50 에서 44% 감소시켰습니다.
  • 적응형 대규모 이웃 탐색 (ALNS) 대비 갭을 N=100 에서 21%, N=50 에서 40% 감소시켰습니다.
  • VRPTW 테스트 세트에서 모든 신경 베이스라인, OR-Tools, ALNS 를 능가했습니다.
• CVRP 성능: COAgents 는 컴팩트한 문제 특화 인코딩 모듈을 사용함에도 불구하고 최첨단 학습 기반 탐색 베이스라인과 경쟁력을 유지하며 효과성을 입증했습니다.
• 절대성 연구 (Ablation Study): 점프 에이전트를 제거하면 최적성 갭이 거의 두 배로 증가했습니다 (3.7% 에서 7.8% 로), 이는 지역 최적점 탈출에 있어 점프 에이전트의 결정적 역할을 강조합니다. 노드 및 이동 선택 에이전트 또한 성능에 크게 기여했습니다.
• ALNS 와의 비교: ALNS 에게 27 개의 추가 파괴 - 수리 쌍을 포함한 더 큰 수동 제작 연산자 풀에 대한 접근 권한이 부여되었음에도 불구하고, COAgents 는 일관되게 ALNS 를 능가하여 정적 휴리스틱보다 학습된 정책의 우월성을 입증했습니다.

중요성 및 주장

이 논문은 COAgents 가 정적 수동 제작 휴리스틱에서 탐색 이력으로부터 학습하는 적응형 다중 에이전트 시스템으로의 중요한 전환을 나타낸다고 주장합니다. 탐색 공간을 명시적으로 그래프로 모델링하고 부분 탐색 그래프를 활용함으로써, 이 프레임워크는 전통적인 방법들이 달성할 수 없는 집중 및 다양화에 대한 정보에 기반한 의사결정을 에이전트들이 내릴 수 있게 합니다.

저자들은 COAgents 를 복잡한 VRPTW 문제와 같이 일반화와 적응성이 중요한 경우에 고전적 휴리스틱 및 기존 학습 기반 구축/탐색 방법에 대한 매력적인 대안으로 위치시킵니다. 현재 Python 구현이 C/C++ 기반 휴리스틱 (LKH3 및 HGS 등) 보다 느리고, 이차적 주의 비용으로 인해 매우 큰 인스턴스로의 확장성이 여전히 과제임을 인정하면서도, 이 프레임워크는 학습된 이력 인식 탐색 제어가 라우팅 문제에서 최선 알려진 솔루션과의 갭을 크게 좁힐 수 있음을 보여줍니다.