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

Abstract: 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.

## introduction the advancement in the natural language understanding capabilities of large language models (llms) has transformed many tasks from manual planning to automated understanding, reasoning, and decision making based on human natural language input @xcite @xcite . for example, a transformative domain is autonomous driving @xcite , where, for safety considerations, drivers often rely on voice control for tasks such as music playback, message responses, and navigation @xcite . beyond predetermined itineraries, a more common scenario involves users knowing only their daily tasks, which consist of a series of points of interest (poi) types such as grocery stores, pharmacies, and banks, without specific ordering or poi selection. this situation introduces multiple trade-offs, including the balance between poi quality and distance, while considering various constraints such as user time limits and poi opening hours. while recent llm literature has explored spatiotemporal comprehension and route optimization capabilities, most studies conduct only simplified evaluations in toy grid environments @xcite . these works typically focus on a single objective, such as minimizing distance @xcite , while other approaches focus solely on constraint satisfaction without considering distance or poi quality @xcite @xcite . a typical use case illustrates the complexity in real-world scenario that such works fails to account for: llm needs to process qualities (e.g., ratings) for multiple pois and make weighted trade-offs between qualities and distances based on user preferences, while considering user time limits, poi opening hours, and task sequential dependencies (e.g., purchasing flowers at a florist before visiting a relative in the hospital). furthermore, the context length grows linearly with the number of pois, for example, 100 pois can require up to 20,000 tokens. in practice, these challenges are amplified by the highly heterogeneous nature of user queries, which can originate from anywhere in the world at any time. consequently, this combination of complex information, inherently multi-objective human expectations, and diverse user preferences poses a critical challenge: how can llms perform route planning based on user preferences, especially when faced with large amounts of heterogeneous and complex poi information? in this paper, we introduce llmap, a novel system that combines an llm-as-parser with a novel multi-objective optimization algorithm for user preference-based route planning, as shown in figure 1 . this architecture addresses fundamental limitations in existing approaches that rely solely on llm-as-agent. llmap supports the following capabilities: (i) trade-offs between poi quality and distance according to user preferences, (ii) adaptively tunes objective weights on a per-query basis, (iii) maximization of task completion rate, and (iv) guarantee of constraints, including user time limits, poi opening hours, and task dependencies. the llmap system exhibits inherent scalability, extending beyond these specific settings to accommodate various use cases. recall that the unique challenge in our scenario is that user locations and other information are not known a priori; each user query is highly heterogeneous and unpredictable, potentially originating from anywhere in the world at any time. to address these distinct challenges, we propose a novel solution that employs llm-as-parser to interpret human language, coupled with a multi-step graph construction with iterative search (msgs) algorithm. our main contributions can be summarized as follows. ## experiments we aim to address two key research questions in our experiments: (rq1) does our llmap system outperform pure llm solutions (i.e., llm-as-agent) in route planning tasks? (rq2) how effectively can llm-as-parser extract accurate information from human instructions? ## conclusion in this paper, we present a novel llmap system that integrates llm-as-parser with the msgs algorithm to facilitate multi-objective route planning. our system decomposes the complex task into two components: using llms to understand and extract information from human instructions, and employing msgs to generate optimal routes that satisfy both constraints and user preferences. through extensive experiments across 27 major cities in 14 countries, we demonstrate that our approach outperforms llm-as-agent solutions across multiple metrics. a future direction is to integrate richer information sources, such as user text reviews, as supplementary input to llms to enhance preference matching.