An Agentic Framework with LLMs for Solving Complex Vehicle Routing Problems¶

🕒 Published (v1): 2026-01-01 · Source: ICLR · Venue: ICLR 2026 · link

Why this paper was selected

Agentic LLM framework for complex vehicle routing; bridges NL intent to combinatorial solvers

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

AFL (Agentic Framework with LLMs) is a multi-agent system that autonomously solves complex Vehicle Routing Problems end-to-end—from raw VRPLIB-format input to feasible solution—without handcrafted modules, external solvers, or human intervention. Four specialized LLM agents (generation, judgment, revision, error analysis) collaborate across three subtasks: problem description, code generation, and solution derivation. Evaluated on 60 VRP variants, AFL achieves near-100% code reliability and solution feasibility, competitive with expert-designed algorithms.

Problem¶

Existing LLM-based VRP solvers fall into one of two failure modes: (1) methods like ARS and DRoC handle complex VRPs but depend on handcrafted modules or external solvers (OR-Tools) during framework design and require human involvement during execution, breaking full automation; (2) fully self-contained methods like SGE are limited to simple problems (TSP) and lack mechanisms for complex constraints. None achieve all three simultaneously: self-containment, full automation, and high trustworthiness (\(\geq\)95% code reliability and solution feasibility).

Method¶

AFL structures VRP solving into three sequential subtasks, each handled by a collaborative agent ensemble:

Problem Description (Subtask 1): Given a VRPLIB-format instance \(G\), the Generation Agent (GA) produces \(D(G) = \{P, S, K, X, Y, Z\}\)—problem type, textual description, constraint set, input/output specs, and objective. The Judgment Agent (JA) verifies consistency; the Revision Agent (RA) iteratively corrects until JA approves.
Code Generation (Subtask 2): GA generates a destroy-insert heuristic solver as a sequence of interdependent Python functions (read_vrp, distance, cost, initial, destroy, insert, validate, main), guided by \(D(G)\). Each function is verified and revised by JA/RA before the next is generated. Simulated annealing drives iterative improvement over \(T\) steps.
Solution Derivation (Subtask 3): The generated code is executed. If runtime errors occur, the Error Analysis Agent (EAA) diagnoses root causes and produces fix suggestions, which RA/JA use to patch the code iteratively. Completed (description, code) pairs are cached in a buffer for reuse on identical problem types.

Key Contributions¶

First LLM-based VRP framework achieving all three properties simultaneously: self-containment (no external solvers or handcrafted modules), full automation (raw input → solution with zero human steps), and high trustworthiness (\(\geq\)95% code reliability and solution feasibility).
Four-agent architecture (GA, JA, RA, EAA) with cross-agent iterative refinement loops that enforce constraint satisfaction and logical soundness at each pipeline stage.
Evaluation on 60 VRP variants including 48 benchmark problems with 8 constraint types (C, L, TW, O, MD, B, MB), 8 practical electric VRPs (E), and 4 classical VRPs; coverage of JSON/CSV input formats beyond VRPLIB.
Buffer mechanism for caching generated code, enabling instant reuse when the same VRP type recurs.

Results¶

vs. traditional/neural baselines (48 standard benchmarks): AFL at \(T=10000\) achieves gap of ~0.34%–5.80% vs. HGS-PyVRP reference, outperforming OR-Tools on most variants and competitive with RF-POMO; runtime ~2–83 minutes at \(T=10000\).
Code reliability and solution feasibility: AFL achieves rates close to 100% across evaluated benchmarks, substantially outperforming ARS, DRoC, and SGE baselines which exhibit significant execution failures.
Electric VRPs: AFL solves practical EVRP variants that remain challenging for traditional solvers.
Ablation: Iterative JA/RA loops in problem description and code generation subtasks each contribute measurably to feasibility; removing either degrades performance.

Limitations¶

Solution quality (objective gap) is still 1–8% worse than HGS-PyVRP (a meticulously tuned expert algorithm), especially on harder variants like OCVRPBLTW.
Runtime scales with \(T\); high-quality runs (\(T=10000\)) take up to ~84 minutes—much slower than neural solvers.
Performance depends on LLM code generation quality; complex constraint combinations may still produce hard-to-debug logic errors.
The destroy-insert heuristic framework is fixed by design; the framework cannot discover alternative algorithmic paradigms.
Evaluation uses VRPLIB instances; generalization to highly irregular real-world data formats beyond JSON/CSV is not fully explored.

Relevance to Agentic AI / LLM Agents¶

AFL is a concrete example of multi-agent specialization with iterative self-refinement—a core design pattern for agentic systems—applied to a non-trivial combinatorial optimization domain. The decompose-generate-judge-revise loop, with a dedicated error analysis agent for runtime failures, directly addresses the reliability gap that prevents LLM agents from operating autonomously in code-execution pipelines. The buffer/caching mechanism for reusing prior agent outputs across instances is a form of episodic memory that improves efficiency in repeated tasks. For researchers tracking agentic AI, this work demonstrates how agent role specialization and cross-agent consistency enforcement can replace brittle single-pass generation in domains requiring both semantic understanding and executable correctness.