LLM 지원 기반 유연한 몬테카를로 트리 탐색을 통한 대규모 차량 경로 문제 해결기 자동 설계

Automated Large-scale CVRP Solver Design via LLM-assisted Flexible MCTS

수백에서 수천 개의 노드를 포함하는 대규모 차량 경로 문제(LSCVRP)는 최첨단 솔버에서도 여전히 해결하기 어렵습니다. 분할 정복 방식은 문제를 작은 하위 문제로 분해하여 확장성을 높일 수 있지만, 분해 로직을 설계하고 하위 솔버를 구성하는 것은 상당한 전문 지식과 노력이 필요합니다. 최근 대규모 언어 모델(LLM)은 자동 알고리즘 설계에 유망한 도구로 부상했습니다. 그러나 기존의 LLM 기반 접근 방식은 제한된 컨텍스트 창으로 인해 정교한 탐색 전략을 생성하는 데 어려움을 겪어 LSCVRP 문제 해결에 어려움을 겪습니다. 이러한 격차를 해소하기 위해, 우리는 LLM 지원 기반 유연한 몬테카를로 트리 탐색(LaF-MCTS)이라는 새로운 프레임워크를 제안합니다. 이 프레임워크는 고성능 LSCVRP 솔버의 설계를 자동화합니다. 우리는 LSCVRP를 위한 분해 정책 및 하위 솔버를 점진적으로 설계할 수 있도록 세 단계의 의사 결정 계층 구조를 개발했습니다. 알고리즘 가설 공간 내에서 효율적인 탐색을 가능하게 하기 위해, 우리는 의미적으로 중복된 코드를 제거하는 의미론적 가지치기(semantic pruning)와 코드를 재생성하고 다양성을 유지하는 가지 재생(branch regrowth)을 도입했습니다. CVRPLib 데이터 세트에 대한 광범위한 실험 결과, LaF-MCTS는 자율적으로 분해 기술을 적용하여 최첨단 CVRP 솔버들을 능가하는 솔버를 구성하고 최적화할 수 있음을 보여줍니다.

Solving large-scale CVRP (LSCVRP) with hundreds to thousands of nodes remains difficult for even state-of-the-art solvers. Divide-and-conquer can scale by decomposing the instance into size-reduced subproblems, but designing decomposition logic and configuring sub-solvers is highly expertise- and labor-intensive. Large Language Models (LLMs) have emerged as promising tools for automated algorithm design. However, existing LLM-driven approaches struggle with LSCVRP primarily due to the difficulty in generating sophisticated search strategies within a limited context window. To bridge this gap, we propose the LLM-assisted Flexible Monte Carlo Tree Search (LaF-MCTS), a novel framework that automates the design of high-performance LSCVRP solvers. We develop a three-tier decision hierarchy to enable incremental design of decomposition policies and sub-solvers for LSCVRP. To enable efficient search within the algorithmic hypothesis space, we introduce semantic pruning to eliminate semantically and structurally redundant codes, and branch regrowth to regenerate codes and preserve diversity. Extensive experiments on CVRPLib demonstrate that LaF-MCTS autonomously composes and optimizes decomposition-enhanced solvers that surpasses various state-of-the-art CVRP solvers.