通过 LLM 驱动的自动启发式设计增强 CVRP 求解器

带容量约束的车辆路径问题（CVRP）是一个基础组合优化挑战，聚焦于在车辆容量约束下优化车队运营。尽管在运筹学中已被广泛研究，CVRP 的 NP 难本质持续带来显著计算挑战，对大规模实例尤甚。本研究提出 AILS-AHD（Adaptive Iterated Local Search with Automatic Heuristic Design），一种新颖方法，利用大语言模型（LLM）革新 CVRP 求解。我们的方法将进化搜索框架与 LLM 相结合，在 AILS 方法内动态生成并优化破坏（ruin）启发式。此外，我们引入基于 LLM 的加速机制以提升计算效率。对照最先进求解器（包括 AILS-II 与 HGS）的综合实验评估表明，AILS-AHD 在中等与大规模实例上均表现卓越。值得注意的是，我们的方法在 CVRPLib 大规模基准的 10 个实例中为 8 个建立了新的最优解，凸显了 LLM 驱动启发式设计在推进车辆路径优化领域的潜力。