acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
optimization
Keywords:
Vehicle Routing Problems, LLMs, Multi-Agent, Experience Learning

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_uUfKOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes CoME, a framework that enables LLMs to automatically generate solver-integrated code for complex vehicle routing problems involving multiple interacting constraints. A major premise of the approach is that grounding experience in verified reference code improves the correctness and reliability of generated optimization programs. The authors report high success and accuracy rates across complex VRP variants and several solver backends.

Critical strengths

The paper identifies an important limitation of existing LLM-based VRP modeling methods, namely their insufficient understanding of constraint interactions. The focus on cross-constraint modeling is meaningful and more specific than simply improving LLM-based code generation.

Critical weaknesses
  1. The methodological novelty of CoME appears limited. The most challenging cross-constraint modeling knowledge is already provided through expert-written reference implementations, while the proposed framework mainly extracts, organizes, and retrieves this knowledge to guide code generation. This resembles a structured RAG pipeline rather than a fundamentally new approach to constraint reasoning Moreover, when a new problem involves constraints or interaction rules that are not covered by the knowledge library, CoME still relies on the LLM's own reasoning. This limits the scope of its claimed generalization capability.

2.The "w/o Interaction Hints" configuration appears to remove both interaction rules and search strategies. Consequently, the observed performance degradation cannot be uniquely attributed to the absence of cross-constraint modeling knowledge. Separate ablations are needed to distinguish improvements in modeling correctness from those arising from solver search configuration.

  1. The paper matches CoME's computational budget to AFL, but RF-POMO operates with a substantially different inference-cost profile. In Table 2, RF-POMO is often much faster than CoME. Therefore, claiming superior optimization performance without sufficiently emphasizing computational differences can be misleading. A more informative presentation would report solution quality, end-to-end wall-clock time, and inference cost separately, distinguishing solver execution from LLM code-generation overhead.
Questions for authors

See Weaknesses

2 comments

Response to W1: CoME's Methodology and generalization

Thank you for this comment. CoME builds on RAG and contributes an automated method for extracting, representing, and reusing cross-constraint integration knowledge. Per-constraint retrieval leaves the compostion of interacting implementations to the LLM. CoME makes these requirements explicit through rules describing which constraints interact and how their implementations must change when combined, then selects applicable rules for code generation. Expert reference programs supply the underlying modeling knowledge because solver documentation and isolated examples offer limited guidance on complex joint implementations. CoME extracts this knowledge from a small set of expert-curated variants and makes it reusable across many constraint compositions. Our generalization claim concerns new compositions of standard VRP constraints for which applicable atomic and interaction knowledge is available. When a new constraint or an uncovered interaction arises, the LLM attempts its implementation using its own reasoning and any relevant existing hints.

Response to W2: Interaction hints and search guidance ablations

Thank you for identifying this confound. Our original ablation removed search guidance together with interaction hints because search guidance is retrieved according to the identified constraint combination. We have added a separate “w/o Search Guidance” condition in Table 4 that retains interaction hints. Comparing this condition with full CoME isolates the contribution of search guidance, while comparing the two conditions without search guidance assesses the contribution of interaction hints. Removing only search guidance reduces AR while leaving SR unchanged for both LLMs. Removing interaction hints when search guidance is already absent substantially reduces SR. These results support a contribution from interaction knowledge beyond retrieved search configuration, while search guidance provides an additional improvement in BKS matching in this evaluation. PyVRP has no separate retrieved search guidance, so the additional search-guidance ablation applies only to OR-Tools.

Table: Ablation results on DRoC’s 48 VRP variants. AR and SR are reported (%) for each configuration on OR-Tools and PyVRP. N/A denotes that the search-guidance ablation does not apply to PyVRP, which has no separate retrieved search guidance.

ConfigurationLLMOR-Tools AROR-Tools SRPyVRP ARPyVRP SR
w/o Interaction HintsClaude Opus 4.566.6772.9273.5376.47
w/o Interaction HintsQwen3.6-35b56.2562.5061.7667.65
w/o PlanningClaude Opus 4.583.3098.9591.1897.05
w/o PlanningQwen3.6-35b77.0885.4276.4776.47
w/o Evaluation-RevisionClaude Opus 4.583.3098.9594.1197.05
w/o Evaluation-RevisionQwen3.6-35b81.2595.8388.2491.17
w/o Search GuidanceClaude Opus 4.581.2598.95N/AN/A
w/o Search GuidanceQwen3.6-35b79.1795.83N/AN/A
CoMEClaude Opus 4.585.4198.9594.1197.05
CoMEQwen3.6-35b83.3095.8391.1794.11

Response to W3: Solution quality, runtime, and computational cost

Thank you for highlighting the computational differences between these methods. Table 2 reports both solution gaps and runtimes. We have revised the discussion in lines 409–410 to explicitly acknowledge that RF-POMO has substantially shorter runtimes than CoME, demonstrating its advantage in inference speed, while its gaps exceed 40% on several multi-depot variants. The time-budget matching described in the paper applies to CoME and AFL. We therefore interpret the comparison with RF-POMO as a solution-quality/runtime trade-off: RF-POMO provides faster solutions, while CoME obtains lower gaps under the reported solver budgets. Table 2 does not separately quantify LLM code-generation overhead, so these results do not establish equivalent end-to-end inference costs across the methods.

Thank you for the detailed response and the additional experiments. The new results do partially alleviate some of my concerns, but several issues remain.

W1. My main concern about the limited methodological novelty remains unresolved. The authors have not yet demonstrated that the proposed structured approach to experience extraction and reuse provides sufficient added value over a simple RAG approach using the same expert-written reference code.

W2. The additional ablation experiments largely address my concern by better isolating the roles of interaction hints and search guidance, which makes the issue clearer.

W3. I understand the explanation regarding runtime differences, but there is still a lack of quantitative evidence on LLM code-generation overhead and end-to-end computational cost.

Overall, I maintain my original rating of 2.

Reviewer_A93XOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes CoME, a framework that helps LLMs write solver code for vehicle routing problems with composite constraints. Offline, an LLM distills atomic constraint hints, cross-constraint interaction hints, and search strategies from 17 human-curated gold-standard programs into a structured library. Online, a three-stage multi-agent pipeline (constraint identification, library-guided planning, and code generation) uses this library to produce code that calls mature solvers such as OR-Tools and PyVRP. On 88 VRP variants and standard benchmarks, CoME reports higher accuracy and lower gaps than DRoC, AFL, and RF-POMO. The problem is practically important, and reusing mature solvers is a sensible design. However, no baseline has access to the same gold-standard code, so it is unclear whether the gains come from the proposed hints or from the gold code itself. Also, the evaluation is hard to verify and relies on program-level metrics checked against a single small instance per variant.

Critical strengths

S1. Important and practical problem. Real-world vehicle routing problems combine many attributes, such as capacity, time windows, multiple depots, and backhauls. Writing solver code for each combination needs expert knowledge. The paper studies 88 multi-attribute VRP variants built from 13 constraint types. This setting is relevant to logistics practice and is a promising direction for LLM-based optimization.

S2. Practical approach. The method uses a small set of reference implementations (17 variants) to guide an LLM. The LLM then writes code that calls mature solvers, such as OR-Tools and PyVRP, for many other variants. This approach reuses existing solvers instead of building new algorithms from scratch, so it keeps the solution quality of those solvers. It is a practical and reasonable way to reduce the expertise barrier.

Critical weaknesses

W1. CoME's hints come from 17 human-curated gold programs that cover 12 of the 13 constraint types (Table 6). No baseline has access to these programs, and every ablation in Table 4 keeps hints derived from them. So it is unclear whether the gain comes from the hints or from the gold code itself. Please compare a strong coding agent without task-specific tuning (e.g., Claude Code with Opus 5.5) in two settings: with the raw gold programs (including parameters), and with CoME's hint library.

W2. The paper lacks detailed descriptions and releases no code, so its results are hard to verify. For example, it omits the hint-extraction LLM, the Jaccard threshold, the Table 1 time limit, and the SR feasibility check. AR/SR count programs, not instances. According to DRoC, Table 1 uses one small instance per variant, with HGS or OR-Tools (100 s) references that are not certified optima. Because AR requires an exact match, both a better solution and a constraint-dropping solution count as failures. Please describe the instances, check feasibility independently, and count solutions that match or beat the reference as successes.

Questions for authors

Q1. Please submit code, the hint library, and the 88-variant benchmark as supplementary material, so that Tables 1–4 can be reproduced.

Q2. In Tables 2 and 8, "-" denotes a zero gap, but in Table 3 it means "cannot model". Readers usually read "-" as "no result". Please write "0.00" for zero gaps.

2 comments

Response to W1: Reference-code access and the hint representation

Thank you for highlighting this distinction. CoME’s hints are abstractions of the expert reference programs, and a capable coding agent may derive similar modeling guidance from those programs. CoME’s contribution is to perform this distillation offline, organizing atomic implementations and cross-constraint integration instructions into a persistent library. Subsequent tasks retrieve applicable guidance, allowing the reference analysis to be reused across many constraint compositions. The intended efficiency benefit is to reduce repeated reference-processing work and provide focused modeling guidance during online generation. This distinguishes the source of knowledge from the procedure used to extract, represent, and reuse it.

Response to W2 and Q1: Reproducibility, evaluation, and code availability

Thank you for highlighting these reproducibility and evaluation issues. Hint extraction and code generation use the same LLM within each experimental setting. Search-configuration retrieval prioritizes exact matches, then stored subsets, followed by a weighted Jaccard score with a 0.6 fallback threshold. Table 1 uses a 30-second solver time limit per instance.

Constructing feasible instances across complex compositions requires substantial effort. Table 1 follows DRoC’s protocol of using one expert-designed, feasible instance per variant. Once the generated program is successfully verified on a single instance, it can be applied to all problem instances of the same structure (e.g., the same types of constraints and input parameters). Generated programs are checked using independent validator. An independent validator checks the generated model for missing required constraints and feasibility of constraints as clarified in Appendix B (lines 847–849). SR counts independently verified feasible outputs, while AR measures exact BKS agreement. Reference objectives for all 88 variants come from DRoC and RouteFinder, as described in Appendix C, and are treated as BKS values rather than certified optima.

We have organized CoME into a standalone codebase and will publicly release the code, experiment-specific hint libraries, and 88-variant benchmark upon acceptance. The release will include dependency versions, benchmark data and reference objectives, splits, prompts, model and solver configurations, backend coverage, and instructions for reproducing Tables 1–4.

Response to Q2: Zero-gap notation

Thank you for pointing out this ambiguity. We have replaced the dashes representing zero gaps in Tables 2 and 8 with 0.00. This makes zero-gap results explicit and distinguishes them from the dash used for “cannot model” in Table 3.

I carefully read the answer. Most of my concerns are unsolved. I maintain my score.

Reviewer_RUZEOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper is motivated by the observation that current LLMs can write OR-Tools or PyVRP code for a vehicle routing problem (VRP) with one constraint but fail when constraints interact. The approach extracts "interaction hints" from expert-written programs and stores them in a library. Inference then composes them into a plan and finally code. Reported accuracy on DRoC's 48-variant benchmark is significant, with far fewer tokens than DRoC or AFL.

Critical strengths

Hinting at interactions explicitly is a good idea to capture compositional constraint knowledge, and a sensible alternative to retrieving one constraint at a time. The empirical gains are large and consistent across solvers and LLMs. The proposed method uses fewer tokens than the baselines. The learned hints appear to help on constraint combinations absent from the training variants.

Critical weaknesses
  1. The evaluation of generated solver code relies only on the objective value returned by heuristic solvers with time limits. Therefore, a program that omits a constraint that does not bind at the optimum can be counted as correct, both in hint verification and in AR. On the other hand, an excellent heuristic, outperforming the gold standard (or underperforming due to time limits), can be counted as incorrect. Since the generated function returns only an objective, it is unclear how SR checks feasibility. Moreover, optima are needed for 88 variants but reference code exists for 17, so it is unclear where the other optima come from.

  2. The scope of the method is restricted to problems whose variants combine constraints from a fixed, predefined set of known constraints. Each new problem class or solver requires expert inputs (hand-written descriptions, reference code, one library per solver). This reduces, but does not remove, the need for expertise that motivates the paper.

  3. The paper positions CoME against experience-reuse methods in the introduction and argues that self-generated experience methods perform poorly on compositional tasks, but none of these methods is evaluated.

  4. Table 1 and Table 4 disagree on the method's own number (83.30 vs 85.41). The text says the evaluation loop is off by default; the ablation counts it as part of the method.

Questions for authors
  1. Section 3.1 gives mixed backhaul with multi-depot as an example interaction rule, but none of the 17 training variants contains both constraints. Where did this rule come from?
  2. Many held-out variants combine constraint pairs never seen together in training, so the library has no rule for them. Table 10 therefore does not show whether the library or the LLM is handling those pairs. Consider splitting the held-out variants by whether all their interacting pairs have a library rule, and report AR on each half.
  3. Since the generated function only returns the objective value, how does SR verify that the solution satisfies all constraints?
  4. The standard prompting baseline is surprisingly weak (20% failures on single-constraint variants). Could you break down its failures (runtime error, incorrect objective, ...) and clarify whether it receives the same execution-repair loop as CoME?
  5. Which configuration gives the headline numbers, with or without the evaluation loop?
  6. Did you run experiments with experience-reuse methods on your benchmark?
3 comments

Response to W1 and Q3: Evaluation validity, feasibility checks, and reference objectives

Thank you for raising these evaluation concerns. During hint verification and final evaluation, generated solvers are checked using independent validator. An independent validator checks the generated model for missing required constraints and feasibility of constraints. Candidate hints are accepted only when both checks pass. During evaluation, a program counts as successful under SR only when it passes both checks, and under AR only when its objective additionally matches the BKS; all evaluated programs remain in the denominator. A validated solution with a different objective therefore remains a success under SR. The route-based feasibility procedure is clarified in Appendix B (lines 847–849). Reference objectives for all 88 variants are inherited from DRoC and RouteFinder, as described in Appendix C; the 17 reference programs constitute the subset used for hint learning. These references are treated as BKS values without assuming certified optimality. Our reported metrics describe performance on the tested benchmark instances.

Response to W2 and Q2: Constraint coverage, generalization, and expert inputs

Thank you for this comment. Expert reference programs provide composition knowledge because solver documentation and isolated examples offer limited guidance on composite complex constraints. CoME learns reusable modeling and interaction knowledge from a small set of expert-curated variants and applies it across many compositions. Expert input supplies the initial reference implementations, while knowledge extraction and reuse are automated. Table 10 summarizes the interacting constraint pairs represented in the library; their rules guide code generation when applicable. A held-out variant can therefore recombine covered interactions without reproducing a training variant. When a new constraint or an uncovered interaction arises, the LLM attempts its implementation using its own reasoning and any relevant available hints. Our focus is compositional reuse of standard VRP knowledge, with LLM reasoning as a fallback beyond library coverage.

Response to W3 and Q6: Comparison with experience-learning methods

Thank you for this suggestion. Our original comparison focused on optimization-specific baselines. We have added ExpeL as a representative experience-learning baseline and adapted it to OR-Tools code generation. During learning, it accumulates reusable knowledge from past attempts using generic feedback indicating a runtime error, no valid solution, or a feasible solution. Table 1 reports its AR, SR, and RER with Claude Opus 4.5 and Qwen3.6-35b. ExpeL outperforms standard prompting in this evaluation, while CoME achieves higher AR and SR and lower RER under both LLMs.

Table 1.1. Comparison of AR, SR, and RER between CoME and external solver integrated baselines on DRoC’s 48-variant benchmark. OptiTree uses MILP modeling with Gurobi. The solver time limit is 30 seconds per instance.

MethodSolverClaude Opus 4.5 ARClaude Opus 4.5 SRClaude Opus 4.5 RERQwen3.6-35b ARQwen3.6-35b SRQwen3.6-35b RER
StandardOR-Tools33.3335.4220.8031.2531.2527.08
StandardPyVRP55.8955.8917.6535.2935.2923.51
OptiTreeGurobi18.7518.7529.1716.6716.6733.33
DRoCOR-Tools56.2558.3320.8041.6745.8322.92
ExpeLOR-Tools54.1762.5018.7543.7550.0020.80
CoMEOR-Tools83.3098.950.0081.2595.830.00
CoMEPyVRP94.1197.050.0088.2491.170.00

Response to W4 and Q5: Headline configurations and the evaluation-revision loop

Thank you for requesting this clarification. The headline results in Table 1 use CoME's default configuration with the optional evaluation-revision loop disabled to reduce token consumption, as already described in the paper. Table 4 reports both settings: for Claude Opus 4.5 with OR-Tools, the 83.30% AR in the "w/o Evaluation-Revision" row corresponds to the default configuration in Table 1, whereas the 85.41% AR in the full CoME row uses the loop enabled. These values therefore describe different configurations. Enabling the optional loop provides additional review and revision at the cost of more LLM calls and tokens.

Response to Q1: Correction of the interaction example

Thank you for pointing out this error. The intended interaction in Section 3.1 is capacity and multi-depot in PyVRP; “mixed backhaul” was an incorrect label. We have corrected the example accordingly. PyVRP places depot locations before clients, so reordering input nodes requires applying the same permutation to both axes of the distance matrix and to the demand assignments. This keeps each customer’s demand aligned with its location when capacity is enforced. A corresponding implementation appears in the PyVRP OCVRPMD reference program included in CoME’s 17-variant learning set.

Response to Q4: Standard-prompting failures and execution-repair fairness

Thank you for this question. Standard prompting receives the same execution-error feedback and runtime-repair loop as CoME, as clarified between manuscript lines 319 and 320. Table 1 now reports RER, which counts final execution failures after the permitted repairs. Across the full benchmark, standard prompting with OR-Tools has RER of 20.80% for Claude and 27.08% for Qwen. Under the stated counting rules, 100 − SR − RER represents no-solution or validation failures, including detected constraint omissions and infeasible returned routes, while SR − AR captures validated outputs that do not match the BKS. An objective mismatch alone is therefore not classified as infeasibility.

Thank you for the detailed response. I believe Q1, Q4, W3 and W4 are resolved. I don't think other points are fully resolved. So I will maintain the original score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.