用大模型+搜索自动设计高效大规模车辆路径求解器。
Automated Large-scale CVRP Solver Design via LLM-assisted Flexible MCTS
- 构建三层决策架构，逐步生成分解策略与子求解器
- 通过语义剪枝和分支再生，提升搜索效率与多样性
- 在CVRPLib上超越现有最优求解器，全自动完成设计
求解包含数百至数千个节点的大规模车辆路径问题（LSCVRP）对现有最优求解器仍具挑战。分治法可通过将实例分解为规模更小的子问题实现扩展，但设计分解逻辑与配置子求解器高度依赖专业知识且耗时。大语言模型（LLMs）在自动化算法设计中展现出潜力，但现有方法在处理LSCVRP时受限于有限上下文窗口下难以生成复杂搜索策略。为此，我们提出一种基于大模型的灵活蒙特卡洛树搜索框架（LaF-MCTS），自动设计高性能的LSCVRP求解器。我们构建三层次决策架构，支持对分解策略与子求解器的渐进式设计。为在算法假设空间中高效搜索，引入语义剪枝以消除语义与结构冗余代码，并采用分支再生机制重新生成代码以保持多样性。在CVRPLib上的大量实验表明，LaF-MCTS能自主组合并优化增强型分解求解器，在多个基准上超越多种现有最优求解器。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。