# LLMAP: LLM-Assisted Multi-Objective Route Planning with User Preferences

arXiv: https://arxiv.org/abs/2509.12273 · HTML: https://mlsanity.com/paper/2509.12273/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 42 references that are in the map.
- First posted on arXiv 14 Sep 2025.

## Builds on (most cited first, 28 of 28)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Gemma 2: Improving Open Language Models at a Practical Size](https://mlsanity.com/paper/2408.00118/) (2024)
- [Phi-3 Technical Report: A Highly Capable Language Model Locally on Your Phone](https://mlsanity.com/paper/2404.14219/) (2024)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [LM-Nav: Robotic Navigation with Large Pre-Trained Models of Language, Vision, and Action](https://mlsanity.com/paper/2207.04429/) (2022)
- [Understanding the planning of LLM agents: A survey](https://mlsanity.com/paper/2402.02716/) (2024)
- [TravelPlanner: A Benchmark for Real-World Planning with Language Agents](https://mlsanity.com/paper/2402.01622/) (2024)
- [On the Planning Abilities of Large Language Models : A Critical Investigation](https://mlsanity.com/paper/2305.15771/) (2023)
- [Exploring the Potential of Large Language Models (LLMs) in Learning on Graphs](https://mlsanity.com/paper/2307.03393/) (2023)
- [Large Language Models on Graphs: A Comprehensive Survey](https://mlsanity.com/paper/2312.02783/) (2023)
- [LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks](https://mlsanity.com/paper/2402.01817/) (2024)
- [Test of Time: A Benchmark for Evaluating LLMs on Temporal Reasoning](https://mlsanity.com/paper/2406.09170/) (2024)
- [Real-Time Anomaly Detection and Reactive Planning with Large Language Models](https://mlsanity.com/paper/2407.08735/) (2024)
- [LLM-Assist: Enhancing Closed-Loop Planning with Language-Based Reasoning](https://mlsanity.com/paper/2401.00125/) (2023)
- [Can Large Language Models be Good Path Planners? A Benchmark and Investigation on Spatial-temporal Reasoning](https://mlsanity.com/paper/2310.03249/) (2023)
- [LLM-A*: Large Language Model Enhanced Incremental Heuristic Search on Path Planning](https://mlsanity.com/paper/2407.02511/) (2024)
- [Can Graph Learning Improve Planning in LLM-based Agents?](https://mlsanity.com/paper/2405.19119/) (2024)
- [Graph Machine Learning in the Era of Large Language Models (LLMs)](https://mlsanity.com/paper/2404.14928/) (2024)
- [ToolPlanner: A Tool Augmented LLM for Multi Granularity Instructions with Path Planning and Feedback](https://mlsanity.com/paper/2409.14826/) (2024)
- [LLM A*: Human in the Loop Large Language Models Enabled A* Search for Robotics](https://mlsanity.com/paper/2312.01797/) (2023)
- [Perceive, Reflect, and Plan: Designing LLM Agent for Goal-Directed City Navigation without Instructions](https://mlsanity.com/paper/2408.04168/) (2024)
- [Route Planning in Transportation Networks](https://mlsanity.com/paper/1504.05140/) (2015)
- [To the Globe (TTG): Towards Language-Driven Guaranteed Travel Planning](https://mlsanity.com/paper/2410.16456/) (2024)
- [LLM-Personalize: Aligning LLM Planners with Human Preferences via Reinforced Self-Training for Housekeeping Robots](https://mlsanity.com/paper/2404.14285/) (2024)
- [Device-Cloud Collaborative LLM Inference with Multi-Modal, Multi-Task, Multi-Turn Conversations](https://mlsanity.com/paper/2502.11007/) (2025)
- [Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps](https://mlsanity.com/paper/2311.11793/) (2023)

## Built on by (most cited first, 5 of 5)

- [Next-Generation LLM for UAV: From Natural Language to Autonomous Flight](https://mlsanity.com/paper/2510.21739/) (2025)
- [Extracting Recurring Vulnerabilities from Black-Box LLM-Generated Software](https://mlsanity.com/paper/2602.04894/) (2026)
- [CompassLLM: A Multi-Agent Approach toward Geo-Spatial Reasoning for Popular Path Query](https://mlsanity.com/paper/2510.07516/) (2025)
- [LLM-Aided A* Search in Non-Geometric Network Graphs](https://mlsanity.com/paper/2606.23136/) (2026)
- [KNOWPLAN: Knowledge-Driven AI Agents for Smart Degree Pathway Planning](https://mlsanity.com/paper/2608.06530/) (2026)

## Abstract (arXiv)

The rise of large language models (LLMs) has made natural language-driven route planning an emerging research area that encompasses rich user objectives. Current research exhibits two distinct approaches: direct route planning using LLM-as-Agent and graph-based searching strategies. However, LLMs in the former approach struggle to handle extensive map data, while the latter shows limited capability in understanding natural language preferences. Additionally, a more critical challenge arises from the highly heterogeneous and unpredictable spatio-temporal distribution of users across the globe. In this paper, we introduce a novel LLM-Assisted route Planning (LLMAP) system that employs an LLM-as-Parser to comprehend natural language, identify tasks, and extract user preferences and recognize task dependencies, coupled with a Multi-Step Graph construction with iterative Search (MSGS) algorithm as the underlying solver for optimal route finding. Our multi-objective optimization approach adaptively tunes objective weights to maximize points of interest (POI) quality and task completion rate while minimizing route distance, subject to three key constraints: user time limits, POI opening hours, and task dependencies. We conduct extensive experiments using 1,000 routing prompts sampled with varying complexity across 14 countries and 27 cities worldwide. The results demonstrate that our approach achieves superior performance with guarantees across multiple constraints.