经LLM辅助灵活MCTS的大规模CVRP求解器自动设计

用求解器解数百到数千节点的大规模CVRP（LSCVRP）即便对最先进求解器依然困难。分治法可通过把实例分解为更小的子问题来扩展，但设计分解逻辑与配置子求解器高度依赖专业知识和人力。大语言模型（LLM）已成为自动算法设计的有望工具。但既有LLM驱动方法在LSCVRP上举步维艰，主要因为难以在有限上下文窗口内生成复杂的搜索策略。为弥合差距，我们提出LLM辅助灵活蒙特卡洛树搜索（LaF-MCTS）：一个自动化设计高性能LSCVRP求解器的新框架。我们开发三层决策层级，支持增量式设计分解策略与子求解器。为在算法假设空间内高效搜索，我们引入语义剪枝以消除语义与结构冗余代码，并引入分支再生以重建代码、保持多样性。CVRPLib上的大量实验表明，LaF-MCTS自主组合并优化出的分解增强求解器超越了多种最先进CVRP求解器。