CoME: Empowering LLMs to Solve Complex Vehicle Routing Problems via Cross-Constraint Modeling Experience

Modeling and solving real-world vehicle routing problems (VRPs) with intricate constraints has long required substantial domain expertise. Large language models (LLMs) have shown promise in solving VRPs, but existing approaches face a quality-coverage trade-off. Those that integrate mature solvers preserve solution quality but lack the composition knowledge to model composite constraints; those that generate their own solvers handle composite constraints but sacrifice solution quality. Experience reuse improves LLMs without retraining by storing reflections and rationales, and can supply this knowledge. However, it requires a reliable source, which is precisely what the model's own attempts lack. To supply this knowledge reliably, we propose CoME, which automatically learns cross-constraint modeling experience from verified solver code, enabling LLMs to intelligently exploit mature solvers for VRPs with composite constraints. This experience spans constraint-level and interaction knowledge and is stored in a structured library. CoME applies this learned experience through a three-stage multi-agent pipeline with cooperative agents verifying each stage's output to ensure correctness throughout the generation. CoME outperforms existing LLM-based baselines across 88 VRP variants and standard benchmarks in both accuracy rate and solution quality. Experiments on other operations research problems and across a range of solvers validate the effectiveness and generality of our method.