CRAFT: Constrained Route planning with Adaptive Framework and Template-based code generation

Shahd Elmahallawy, Ahmed EldawyarXiv 2026 · arXiv

TL;DR

CRAFT is a novel framework that bridges the gap between natural language routing queries and robust graph algorithms. By using a Large Language Model (LLM) to generate query-specific search logic for a generic, state-expanded solver, it achieves over 90% accuracy on complex, multi-constraint trips that baffle both traditional planners and raw LLMs.

What Problem Does This Paper Address?

Standard navigation systems are excellent at finding the shortest path from point A to point B. However, real-world requests are rarely that simple. A user might say: "I'm driving an EV with 10% battery; find the shortest route to my destination that stops at a park with a playground, then a Thai restaurant, without running out of charge."

This is a Resource-Constrained Shortest Path (RCSP) problem. Traditionally, solving this requires a specialized algorithm for every unique combination of constraints (e.g., one for EV charging, another for ordered stops). Furthermore, while LLMs are great at understanding the intent of such queries, they are notoriously bad at spatial reasoning, often hallucinating distances or fabricating non-existent locations.

Figure 1: User Query Example

Methods

The authors introduce CRAFT (Constrained Route planning with Adaptive Framework and Template-based code generation). The core philosophy is a "separation of concerns": use the LLM to interpret the query and write the logic, but use a rigorous graph-search engine to execute that logic on real map data.

The system consists of three main components:

  1. Spec Builder: This stage "grounds" the LLM. It loads the actual POI (Point of Interest) schema and road attributes from the database so the LLM doesn't invent categories. it parses the natural language into a structured JSON and normalizes units (e.g., converting "10% battery" into meters of range).
  2. ORCStrator: This is the code-generation heart. Instead of asking the LLM to find a route, it asks the LLM to fill a Python template with four "core functions":
  3. Start: Initializes the trip state.
  4. Expand: Defines how resources (like battery or time) change when moving across an edge.
  5. IsGoal: Checks if all constraints (like visiting all stops) are met at the destination.
  6. Dominates: Provides pruning logic to discard suboptimal paths.
  7. SE-RCSP Solver: A query-agnostic search engine based on Dijkstra’s algorithm. It treats the trip as a State-Expanded problem, where the "state" includes not just the current intersection, but also the current resource levels (battery, stops visited, etc.).
Figure 2: CRAFT System Overview

Datasets

The researchers evaluated CRAFT using road networks extracted from OpenStreetMap (via OSMnx) for Southern California (SoCal) and the entire state of California.

They built a massive benchmark of 2,600 natural language queries, categorized into:

  • Main Sets (Q1-Q5): EV routing, ordered/unordered stops, and "itinerary planning" (visiting as many places as possible within a budget).
  • Specialized Sets (Q6-Q8): Highway avoidance, semantic POI filters (e.g., "park with a playground"), and long-distance statewide trips.
  • External Set (Q9): 1,000 queries adapted from the existing LLMAP benchmark.

Key Insights and Ideas

  • Don't Let LLMs Plan, Let Them Program: By forcing the LLM to output executable code rather than a route, CRAFT eliminates spatial hallucinations. The route is guaranteed to exist on the actual road network because it is found by a traditional graph algorithm.
  • State Expansion is the Universal Key: By formalizing the problem as SE-RCSP, the authors show that vastly different routing problems (EV, Orienteering, Sequenced Route) can all be solved by the same engine if you correctly define the "state" and "resource update" functions.
  • Semantic Grounding: To handle vague requests like "a park with a playground," CRAFT uses a two-step process: vector embeddings for a broad search, followed by a local LLM check to confirm the POI actually meets the user's qualitative description.

Key Results

CRAFT significantly outperformed existing baselines across multiple LLM backends (GPT-4, Gemini, and open-source models):

  • Correctness: CRAFT achieved up to 93% correctness on the main benchmark. In contrast, an "LLM-only" approach succeeded on less than 27% of queries, and the previous state-of-the-art (LLMAP) reached only 42%.
  • Optimality: On route-planning tasks, CRAFT’s solutions were nearly optimal, with a Mean Absolute Percentage Error (MAPE) of less than 2.21% compared to a brute-force exact solver.
  • Scalability: By implementing A heuristics within the generated code, the system reduced median search times for long-distance trips from 3 seconds down to just 0.5 seconds*.

Limitations and Future Work

  • Hard Constraints: Currently, CRAFT treats all constraints as "hard." If a route is slightly over a time budget, it is discarded. The authors suggest moving toward "soft" constraints where the solver can rank and relax less important requirements if no perfect route exists.
  • Self-Correction: While the system is robust, it doesn't currently feed execution errors (like a Python syntax error in the generated code) back to the LLM for a retry. Implementing a feedback loop could push correctness even closer to 100%.

Summary updated

Abstract

Everyday routing requests are rarely a point-to-point shortest path. A driver may need to visit stops, sometimes in a fixed order, under time budgets or distance limits, and perhaps recharge their EV car along the way. Each combination is a distinct routing problem that classically requires its own algorithm, so no fixed solver covers the space of queries users may ask. This paper presents CRAFT, which takes a constrained routing query as free text and returns a route that satisfies the user's requirements on a real road network. An LLM parses the query and generates four search functions, which a generic graph-search engine executes on the road network. We formalize the underlying problem as State-Expanded RCSP (SE-RCSP), which extends resource-constrained shortest paths (RCSP) with non-additive state such as node-dependent resets and discrete progress tracking. We evaluate CRAFT on 2,600 natural-language queries over California road networks against two baselines, analyzing correctness, constraint violations, long-distance scalability, and semantic POI filtering.
BibTeX
@misc{elmahallawy2026craft,
  author = {Shahd Elmahallawy and Ahmed Eldawy},
  title = {{CRAFT: Constrained Route planning with Adaptive Framework and Template-based code generation}},
  year = {2026},
  eprint = {2611.25128},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.25128},
}
Figure