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

📄 arXiv: 2509.12273v1 📥 PDF

作者: Liangqi Yuan, Dong-Jun Han, Christopher G. Brinton, Sabine Brunswicker

分类: cs.AI, cs.CL, cs.LG

发布日期: 2025-09-14

💡 一句话要点

LLMAP：基于LLM辅助的多目标个性化路线规划系统

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 路线规划 大型语言模型 多目标优化 自然语言理解 图搜索算法

📋 核心要点

  1. 现有路线规划方法难以兼顾LLM对自然语言的理解和处理大规模地图数据的能力。
  2. LLMAP系统利用LLM解析用户自然语言偏好，并结合多步图搜索算法寻找最优路线。
  3. 实验结果表明，LLMAP在满足时间限制、POI开放时间和任务依赖等约束下表现优异。

📝 摘要（中文）

大型语言模型（LLM）的兴起使得自然语言驱动的路线规划成为一个新兴的研究领域，它涵盖了丰富的用户目标。目前的研究主要有两种方法：使用LLM作为代理的直接路线规划和基于图的搜索策略。然而，前者难以处理大量的地图数据，而后者在理解自然语言偏好方面能力有限。此外，一个更关键的挑战来自于全球用户高度异构和不可预测的时空分布。本文介绍了一种新颖的LLM辅助路线规划（LLMAP）系统，该系统采用LLM作为解析器来理解自然语言，识别任务，提取用户偏好并识别任务依赖性，并结合多步图构建与迭代搜索（MSGS）算法作为底层求解器，以找到最佳路线。我们的多目标优化方法自适应地调整目标权重，以最大化兴趣点（POI）质量和任务完成率，同时最小化路线距离，并受限于三个关键约束：用户时间限制、POI开放时间和任务依赖性。我们使用在世界范围内14个国家和27个城市中采样的1000个具有不同复杂性的路线提示进行了广泛的实验。结果表明，我们的方法在多个约束条件下实现了卓越的性能。

🔬 方法详解

问题定义：现有基于LLM的路线规划方法要么难以处理大规模地图数据，要么无法充分理解用户的自然语言偏好，并且缺乏对用户异构时空分布的考虑。这导致无法在实际应用中提供高质量、个性化的路线规划服务。

核心思路：LLMAP的核心思路是将LLM作为自然语言解析器，提取用户偏好和任务依赖关系，然后利用图搜索算法在地图数据上寻找最优路线。通过结合LLM的语义理解能力和图搜索算法的效率，实现更智能、更灵活的路线规划。

技术框架：LLMAP系统主要包含两个模块：LLM-as-Parser和Multi-Step Graph construction with iterative Search (MSGS)。LLM-as-Parser负责解析用户输入的自然语言，提取用户偏好、任务和约束条件。MSGS算法则基于提取的信息构建多步图，并使用迭代搜索算法寻找满足约束条件的最优路线。整个流程是先由LLM理解用户意图，再由MSGS算法进行路线规划。

关键创新：LLMAP的关键创新在于将LLM和图搜索算法有机结合，利用LLM的自然语言理解能力来指导图搜索过程。此外，该方法还考虑了用户的时间限制、POI开放时间和任务依赖性等实际约束，使得路线规划结果更贴近用户的真实需求。

关键设计：LLM-as-Parser使用预训练的LLM模型，并通过prompt engineering来提高其解析用户意图的准确性。MSGS算法采用多目标优化方法，自适应地调整目标权重，以平衡POI质量、任务完成率和路线距离。具体而言，目标函数包含POI质量、任务完成率和路线距离三项，通过调整这三项的权重来满足不同用户的偏好。此外，该算法还考虑了POI的开放时间、用户的时间限制以及任务之间的依赖关系，确保生成的路线是可行的。

🖼️ 关键图片

img_0

📊 实验亮点

实验结果表明，LLMAP在14个国家和27个城市的1000个不同复杂度的路线规划提示下，能够有效地满足用户的时间限制、POI开放时间和任务依赖性等约束条件，并提供高质量的路线方案。相比于传统方法，LLMAP在POI质量和任务完成率方面有显著提升，同时保证了合理的路线距离。

🎯 应用场景

LLMAP可应用于各种需要个性化路线规划的场景，例如旅游规划、城市出行、物流配送等。它可以根据用户的兴趣、时间和任务要求，生成最佳的路线方案，提高出行效率和用户满意度。未来，LLMAP还可以与其他智能系统集成，例如智能家居、智能交通等，提供更全面的智能服务。

📄 摘要（原文）

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.