DRoC: Elevating Large Language Models for Complex Vehicle Routing via Decomposed Retrieval of Constraints

https://pure.tue.nl/ws/portalfiles/portal/354715746/9519_DRoC_Elevating_Large_Lang.pdf

논문 《DRoC: Elevating Large Language Models for Complex Vehicle Routing via Decomposed Retrieval of Constraints》는 복잡한 제약 조건이 있는 차량 경로 문제(Vehicle Routing Problems, VRPs)를 해결하기 위해 대형 언어 모델(LLMs)의 성능을 향상시키는 새로운 RAG 기반 프레임워크 DRoC (Decomposed Retrieval of Constraints)를 제안하는 ICLR 2025 논문입니다.

---

🔍 핵심 개념 요약

🔧 문제 배경

• VRPs는 복잡한 조합 최적화 문제로, 이론적/산업적으로 매우 중요함.
• 기존 최적화 솔버들(예: OR-Tools, Gurobi)은 사용법이 어렵고 제약조건이 복잡할수록 전문가 지식이 필요함.
• 최근 LLMs (GPT-4, Claude 등)은 간단한 VRP는 잘 처리하나, 복합 제약 조건이 포함된 문제는 처리 능력이 부족함.

---

🧠 DRoC의 핵심 아이디어

🎯 목표

LLM이 복잡한 제약조건이 있는 VRP를 해결할 수 있도록 외부 문서(예시 코드, 공식 문서 등)를 제약 조건 단위로 나누어 검색하여 정확한 프로그램 생성을 유도.

🧩 전체 프로세스

1. 직접 코드 생성: LLM이 내부 지식만으로 프로그램을 생성.
2. 실행 결과 확인: 코드 실행 후 에러가 발생하면, 해당 에러 정보를 수집.
3. 라우팅 결정: 에러에 따라 self-debug 또는 외부 문서 검색을 선택.
4. 선택적 수행:
   • Self-debug: LLM이 자체적으로 코드 수정 시도.
   • Decomposed Retrieval: 제약 조건들을 분해해서 각각에 맞는 외부 문서를 검색하고, 이를 통해 정확한 코드 생성.

---

🔍 기술 상세

🧷 제약 조건 기반 분해 (Decomposition)

• 문제 이름으로부터 제약조건 키워드들(예: Capacitated, Time Windows, Multiple Depots)을 추출.
• 각 제약조건마다 검색 쿼리 생성 → 문서 검색 → 필터링 → 관련 문서 취합 → LLM 코드 생성을 위한 입력 컨텍스트로 활용.

📎 두 단계 필터링

• 1차 필터: LLM이 문서의 코드 스니펫과 요약을 추출하고 관련성을 평가.
• 2차 필터: 여러 문서 중 가장 관련성 높은 문서 하나만 선택.

---

🧪 실험 결과

모델	방법	정확도 (AR ↑)	런타임 오류율 (RER ↓)
GPT-3.5	DRoC	20.83%	47.92%
GPT-4o	DRoC	45.83%	20.83%
GPT-4o	일반 프롬프트	20.83%	58.33%
GPT-4o	Self-debug	31.25%	37.50%
GPT-4o	기존 RAG	37.50%	31.25%

→ DRoC는 다른 방법보다 정확도와 오류율 모두 월등히 좋음

---

🧪 추가 실험

• LLM 일반화: Claude 3.5, LLaMA 3.1-70B 등에서도 DRoC 성능 향상 확인됨.
• Gurobi Solver 실험: OR-Tools 뿐 아니라 Gurobi 사용 시에도 DRoC 성능 향상.
• Ablation Study: Decomposed Retrieval, 필터링, Router 모두 성능에 기여.
• Token 효율성: 진화적 탐색(예: EoH, ReEvo)에 비해 적은 토큰으로 더 좋은 성능 확보.

---

🏁 결론

DRoC는 복잡한 최적화 문제에서 LLM의 실용적 사용을 가능하게 하는 효율적이고 확장 가능한 프레임워크입니다. 특히, 비전문가가 최적화 모델링 없이도 실질적인 솔루션을 얻을 수 있게 하여 물류 및 산업 응용에 매우 유용합니다.

---