기술 요약: 다중 작업 차량 경로 최적화 솔버를 위한 LLM-as-Trainer (LaT)

1. 문제 정의

차량 경로 문제(VRP)는 매우 다양한 조합 최적화 변형(예: 용량 제한 VRP, 시간 창 제약이 있는 VRP, 백홀 제약 등)을 포함합니다. 신경망 기반의 강화 학습 솔버는 실행 가능한 해를 효율적으로 생성하는 데 유망한 모습을 보여왔으나, 초기 접근 방식은 각 특정 제약 조합마다 별도의 모델을 학습시켜야 한다는 한계가 있었습니다. 이러한 확장성 부족은 실제 응용 분야에서 존재하는 60개 이상의 VRP 변형들을 고려할 때 심각한 문제입니다.

다중 작업(Multi-task) 신경망 솔버는 이러한 변형들을 하나의 모델로 통합하여 별도의 학습을 피하는 것을 목표로 합니다. 그러나 중요한 과제가 남아 있습니다. 서로 다른 VRP 변형들은 최적화 난이도가 서로 다르다는 점입니다. 기존의 다중 작업 학습 방법은 손실(loss)이나 그래디언트 균형을 통해 공유 파라미터를 조정하지만, 학습 과정 중 서로 다른 작업 간의 상대적 성능에 대한 명시적인 **단계별 피드백(stage-wise feedback)**은 결여되어 있습니다. 결과적으로 모델이 쉬운 변형에 편향될 수 있으며, 이는 전체적인 솔루션 품질을 제한합니다. 메타 러닝(Meta-learning)은 적응형 학습을 제공하지만, 일반적으로 상당한 계산 비용과 추가적인 그래디언트 업데이트를 수반하는 이중 레벨 최적화(bi-level optimization)에 의존합니다.

2. 방법론: LLM-as-Trainer (LaT)

저자들은 사전 학습된 대규모 언어 모델(LLM)을 외부 트레이너로 활용하여 다중 작업 신경망 솔버의 공동 학습을 조절하는 플러그 앤 플레이(plug-and-play) 학습 패러다임인 **LaT (LLM-as-Trainer)**를 제안합니다. 핵심 혁신은 모델의 아키텍처를 수정하거나 이중 레벨 최적화를 요구하지 않으면서, LLM을 사용하여 교차 작업 검증 지표를 분석하고 **단계별 가이드 벡터(stage-wise guidance vector)**를 생성하는 데 있습니다.

2.1 학습 프레임워크

LaT는 표준적인 자기회귀(autoregressive) 트랜스포머 인코더-디코더 아키텍처(예: POMO, CaDA, ReLD)를 기반으로 작동하지만, 각 인코더 레이어에 경량화된 **사이드 브랜치(side branch)**를 도입합니다. 프로세스는 다음과 같습니다:

1. 교차 작업 검증: 정해진 간격($T_{ctrl}$ 에포크마다)으로 현재 정책을 16개의 모든 VRP 변형에 대한 고정된 검증 세트에서 평가합니다.
2. 상태 구축: 시스템은 사전 계산된 참조 솔루션(HGS 또는 OR-Tools에 의해 생성됨)에 대해 각 작업 $k$에 대한 **상대적 참조 갭(relative reference gap, $\eta_{r,k}$)**을 계산합니다. 또한 이 갭의 변화량($\Delta \eta_{r,k}$)을 추적하고 최근 검증 기록의 이력을 유지합니다.
3. LLM 가이드 생성: 이 구조화된 학습 상태(작업 제약, 현재 갭, 갭 변화 및 이력 추세 포함)는 프롬프트로 형식화되어 동결된(frozen) 사전 학습된 LLM(실험에서는 GLM-5.1 사용)에 입력됩니다. LLM은 5개의 기초 제약(용량, 오픈 경로, 백홀, 경로 길이, 시간 창)에 대응하는 5차원 가이드 벡터 $\gamma_r = [\gamma_C, \gamma_O, \gamma_B, \gamma_L, \gamma_{TW}]$를 출력합니다.
4. 솔버 주입: 이후의 학습 에포크 동안, 가이드 벡터 $\gamma_r$은 현재 작업의 이진 제약 벡터 $z_k$와 결합됩니다. 이 결합된 벡터는 모든 인코더 레이어의 경량 사이드 브랜치에 주입됩니다. 사이드 브랜치의 출력은 학습 가능한 계수 $\alpha$를 통해 백본 출력에 더해집니다.
5. 정책 최적화: 솔버는 표준 정책 그래디언트 방법(예: POMO 스타일)을 사용하여 업데이트됩니다. LLM은 그래디언트를 받지 않으며 추론 시에는 호출되지 않습니다.

2.2 추론

학습이 완료되면 최종 가이드 벡터는 고정되며 LLM은 제거됩니다. 배포된 솔버는 학습된 사이드 브랜치와 고정된 가이드 벡터만을 보유하며, LLM API 호출이 필요 없고 계산 오버헤드가 미미합니다.

3. 주요 기여

본 논문은 세 가지 주요 기여를 강조합니다:

• 새로운 학습 패러다임: LaT는 다중 작업 차량 경로 솔버를 위해 사전 학습된 LLM을 외부 트레이너로 도입한 최초의 학습 패러다임입니다. 이는 교차 작업 검증 성능을 정책 최적화 루프에 명시적으로 통합합니다.
• 경량 가이드 메커니즘: 저자들은 검증 지표로부터 단계별 가이드 벡터를 생성하는 메커니즘을 설계했습니다. 이 벡터는 작업 제약과 결합되어 인코더 레이어에 주입되며, 이중 레벨 최적화나 내부 루프 업데이트의 계산 부담 없이 추가적인 학습 정보를 제공합니다.
• 플러그 앤 플레이 범용성: 이 방법은 핵심적인 자기회귀 정책이나 디코더 아키텍처를 변경하지 않고도 기존 신경망 솔버(ReLD 및 CaDA 백본으로 입증됨)와 통합되도록 설계되었습니다.

4. 실험 결과

실험은 5개의 기초 제약으로부터 형성된 16개의 VRP 변형에 대해 수행되었으며, 문제 크기는 50 및 100 노드였습니다.

• 학습된 변형에 대한 성능: LaT 변형(LaT-ReLD 및 LaT-CaDA)은 6개의 모든 학습 변형에 대해 백본 모델보다 일관되게 낮은 상대적 참조 갭을 달로 달성했습니다. 예를 들어, LaT-CaDA는 학습된 변형에 대한 평균 갭을 1.810%에서 1.669%로 줄였습니다.
• 제로샷 일반화(Zero-Shot Generalization): 나머지 10개의 미학습 VRP 변형에 대해 LaT는 강력한 일반화 성능을 보여주었습니다. LaT-CaDA는 20개의 모든 미학습 설정(50 및 100 노드)에서 베이스라인인 CaDA를 능가하여, 평균 갭을 5.490%에서 5.067%로 낮추었습니다.
• SOTA와의 비교: LaT 변형은 대부분의 설정에서 다른 최첨단(SOTA) 다중 작업 솔버(예: MVMoE, CCL, PoMtVRS)에 비해 가장 낮은 갭을 달이트했습니다.
• 효율성: 이 방법은 추론 시간을 거의 늘리지 않았으며(50노드 인스턴스 기준 3~4초), 이는 백본 모델과 유사한 수준입니다. 학습 시간은 주기적인 LLM 호출로 인해 1.5% 미만으로 증가했습니다.
• 절제 연구(Ablation Studies):
  • LLM 생성 가이드를 제거하고(고정 벡터로 대체) 성능이 저하되었으며, 이를 통해 적응형 가이드의 가치를 확인했습니다.
  • 작업 제약 벡터를 제거하면 성능이 악화되어, 명시적인 작업 정보의 필요성을 보여주었습니다.
  • LLM을 MLP 기반 가이드 생성기로 교체했을 때 갭이 더 높아졌으며, 이는 개선이 단순히 모델 용량의 증가가 아닌 LLM의 추론 능력에서 기인함을 시사합니다.
  • 가이드를 모든 인코더 레이어에 주입하는 것(LaT EncAll)이 입력, 출력 또는 디코더 컨텍스트에만 주입하는 것보다 우수함을 입증했습니다.

5. 의의 및 주장

본 논문은 LaT가 현재의 교차 작업 성능 차이에 명시적으로 반응함으로써 기존 다중 작업 솔버의 한계를 효과적으로 해결한다고 주장합니다. 동결된 LLM을 주기적인 "트레이너"로 활용함으로써, 이 방법은 신경 솔버가 난이도가 다른 변형들 간의 학습 균형을 맞추도록 안내하는 단계별 피드백을 제공합니다.

저자들은 LaT가 추론 효율성을 유지하면서 학습된 변형과 미학습 변형 모두에서 솔루션 품질을 향상시킨다는 점을 강조합니다. 또한 LaT가 일관된 개선을 보이지만, 그 효과는 특정 백본 아키텍처에 따라 달라질 수 있음(예: 미학습 변형에 대해 LaT-CaDA가 LaT-ReLD보다 더 일관된 이득을 보임)을 언급합니다. 결론적으로, 이 접근 방식은 복잡한 다중 제약 시나리오를 위한 일반적이고 효과적인 학습 패러다임을 제공하며, 향후 연구에서는 더 넓은 제약 집합과 다양한 솔버에 걸친 더 일관된 가이드 메커니즘을 탐구할 수 있습니다.