ITINERA: Integrating Spatial Optimization with Large Language Models for Open-domain Urban Itinerary Planning

• Citywalk planning involves dynamic information, individual preferences, and diverse constraints such as accessibility, while existing methods struggle with detailed demands and pure LLMs with POI grounding and optimization.Source: §1 · p. 1
• The paper defines OUIP as generating personalized travel itineraries from natural-language requests and proposes ITINERA, integrating spatial optimization with LLMs.Source: §1 · p. 1
• ITINERA uses five LLM-assisted modules: User-owned POI Database Construction, Request Decomposition, Preference-aware POI Retrieval, Cluster-aware Spatial Optimization, and Itinerary Generation.Source: §1 · pp. 1–2
• Real-world experiments and deployed-system performance show ITINERA creates personalized, spatially coherent, high-quality urban itineraries that meet user requirements.Source: §1 · p. 2

LLMs in Urban Applications

• Urban LLM studies address data processing and planning, mobility prediction, and transportation applications; TravelPlanner benchmarks multi-day planning and reveals LLM limitations on complex tasks.Source: §2 · p. 2

Itinerary Planning (IP)

• Conventional itinerary methods optimize spatial utility or impose Orienteering Problem constraints, but their personalization remains limited.Source: §2 · p. 2
• Recommendation-based itinerary methods depend on historical user behavior, while existing approaches struggle with open-domain natural-language inputs and personalized itineraries.Source: §2 · p. 2

3.1 Open-domain Urban Itinerary Planning (OUIP) Problem

• OUIP selects and orders a subset of user-owned POIs into a coherent itinerary aligned with a natural-language request and spatiotemporal considerations.The system treats the user-owned POI database as the source from which an itinerary generator constructs the ordered list.Source: §3.1 · p. 3

3.2 User-owned POI Database Construction

• The database pipeline extracts POIs and descriptions from social-media links, uses map APIs and embeddings to locate them, and is refreshed daily with trending-post POIs.The user-owned database can be customized and maintained with timely information, while the aggregated database also serves as an initial POI set for new users.Source: §3.2 · p. 3

3.3 Request Decomposition

• An LLM decomposes each request into subrequests labeled by POI- or itinerary-level granularity, specificity, and positive or negative attitude.Specificity distinguishes must-see from vague requests; granularity includes start, end, POI, and itinerary types.Source: §3.3 · p. 3

3.4 Preference-aware POI Retrieval

• Preference-aware retrieval embeds positive and negative subrequests, reranks POIs by their similarity gap, and sums scores across subrequests, assigning large scores to must-see POIs.Top-k results for positive subrequests are retrieved, then the union is ranked using the combined scores.Source: §3.4 · pp. 3–4

3.5.1 Spatial Clustering and Filtering

• A distance-threshold proximity graph is clustered, then highest-scoring clusters are added until the candidate-POI count reaches Nc.This produces spatial clusters and candidate POIs from the retrieved set.Source: §3.5.1 · p. 4

3.5.2 POI Ordering via Solving Hierarchical TSP

• Hierarchical TSP orders clusters and solves constrained within-cluster routes using endpoints chosen for proximity to adjacent clusters, then selects a start POI and restores precedence.The start POI can be selected from subrequests or prompted from the LLM using the candidate POIs and request.Source: §3.5.2 · pp. 4–5

3.6 Itinerary Generation

• The LLM selects a request-aligned subset of ordered candidates while meeting practical and time constraints, such as avoiding consecutive restaurant visits and scheduling bars in the evening.The generation prompt includes the request, candidate POIs with context, constraints, language style, and output format.Source: §3.6 · p. 5

4.1 Experimental Setup

• The dataset contains 1,233 top-rated itineraries and 7,578 POIs from four Chinese cities; GPT-4 generates final itineraries and GPT-3.5 handles other interactions.The data was collected with a travel agency specializing in single-day citywalk.Source: §4.1 · p. 5

4.2 Evaluation Metrics

• Evaluation combines rule-based measures of POI recall, route distance, intersections, and POI matching with LLM-judged POI quality, itinerary quality, and request match.The LLM-based comparisons use GPT-4 rankings, repeated at least 10 times; the paper reports consistency with human judgments.Source: §4.2 · p. 6

4.3 Overall Results

• ITINERA outperforms all baselines across all metrics, is better or comparable to ground truth, and beats GPT-4 CoT on LLM-evaluated metrics, especially Match.The authors report roughly 30% improvement in rule-based metrics over the best baseline and paths about 100 meters per POI longer than the shortest TSP-solved path.Source: §4.3 · p. 6

4.4 Ablation Study

• UPC improves GPT-4 CoT’s Recall Rate and Match; removing RD or PPR, or using GPT-3.5, lowers several quality and alignment metrics.Removing CSO worsens Average Margin and Overlaps but improves Recall Rate, POI Quality, and Match; PPR also addresses context-window limits and saves costs, while the GPT-3.5 variant outperforms the GPT-3.5 baseline.Source: §4.4 · pp. 6–7

4.5 Deployed System Performance

• Both regular users and travel assistants prefer ITINERA to GPT-4 CoT across metrics, especially Match.The evaluation involved 464 regular users and 33 travel assistants; human results aligned with LLM-evaluation win rates, while rule-based evaluation alone was insufficient.Source: §4.5 · p. 7

4.6 Qualitative Results

• For an artsy bridges-and-ferries request, ITINERA selects clustered, less-mainstream POIs and a logical route, unlike GPT-4 CoT’s distant, disordered itinerary.The example route passes Huangpu River bridges, includes a ferry crossing, and ends at Duoyun Bookstore.Source: §4.6 · p. 7, Figure 3 · p. 7

5 Conclusion

• The paper introduces OUIP as a problem of planning urban itineraries from natural-language requests.Source: §5 · p. 7
• ITINERA integrates LLMs with spatial optimization to generate personalized and spatially coherent itineraries from natural-language requests.The paper presents this system as its solution to the newly introduced OUIP problem.Source: §5 · p. 7
• Real-world dataset experiments and deployed-system performance validate the effectiveness of the approach.Source: §5 · p. 7

Limitations

• In highly complex urban environments, the spatial optimization module may face efficiency challenges.Source: Limitations · p. 8
• LLM limitations in spatial reasoning and real-time decisionmaking may affect itinerary quality in specific scenarios.Source: Limitations · p. 8

Ethical Statement

• The personalized POI database is user-owned, and data processing follows legal security and user-consent standards.Source: Ethical Statement · p. 8
• The system is designed to avoid biases in itinerary recommendations across diverse user groups.Source: Ethical Statement · p. 8
• The paper states that the system promotes sustainable urban tourism while protecting local culture and ecosystems.Source: Ethical Statement · p. 8
• The pipeline prioritizes transparency so users understand how their itineraries are generated.Source: Ethical Statement · p. 8

A Demonstration of the Deployed System

• Figure 4 shows the deployed system’s POI and itinerary views.Source: Figure 4 · p. 10
• In the POI view, users can add and filter places, then select POIs to create an itinerary.POIs can be added by searching directly or pasting a link to a travel-related post.Source: A Demonstration of the Deployed System · p. 10
• In the itinerary view, users can browse created or generated itineraries and open one to see its details.Source: A Demonstration of the Deployed System · p. 10

• Each city’s data has a POI table and an itinerary table for requests and corresponding ground-truth itineraries.Source: B Dataset · p. 11
• The POI sample lists attributes including name, address, city, description, coordinates, rating, category, and context.Source: B Dataset · p. 11, Table 4
• The POI context concatenates the preceding columns and is embedded to produce semantically rich POI representations.Source: B Dataset · p. 11
• The itinerary sample pairs each user request with a list of POI IDs representing its ground-truth itinerary.Source: B Dataset · p. 11, Table 5 · p. 11

• POIs are embedded with OpenAI’s text-embedding-ada-002 model.Source: §C.1 · p. 11
• An open-source TSP solver optimizes itinerary spatial coherence.Source: §C.1 · p. 11
• The Amap API provides POI coordinates, ratings, categories, and physical addresses.Source: §C.1 · p. 11

C.2 Baseline Settings

• Baselines share the itinerary-generation prompt; generated POIs are map-matched with fuzzy string matching, and unmatched POIs count toward failure rate.GPT-4 CoT additionally receives “thoughts”; matched POIs have attributes such as location attached for evaluation, and the baseline IP uses the PIT for time budgeting.Source: §C.2 · p. 11

D.1 SolveTSP

• SolveTSP uses simulated annealing with swap, inversion, insertion, and subroute-insertion moves, cooling from Tinit 5000 to Tmin 0 at α=0.99.The algorithm accepts an improving solution or, otherwise, may accept it according to exp(−costDifference/T); it runs until temperature reaches zero.Source: §D.1 · p. 12

D.2 SolveTSPWithEndpoints

• For each cluster’s limited candidates, SolveTSPWithEndpoints uses linear programming to optimize the TSP path with predetermined start and end points.The formulation prioritizes solution accuracy over computational efficiency.Source: §D.2 · p. 13

E Overview of the POI extraction pipeline

• The pipeline scrapes post text, images, and videos, merges OCR and speech-recognition output with original text, uses GPT-3.5 to extract POI names and locations, then looks up coordinates and generates descriptions.The database is updated every 24 hours using recent trending travel-related posts from multiple cities on social media platforms.Source: E Overview of the POI extraction… · p. 15

Prompt for Decomposing User Requests

• Request decomposition separates independent positive and negative requirements and labels each as a place, starting point, ending point, or itinerary, with mustsee marking specific places.Specific attractions must be separated; starting and ending points must be specific locations, with at most one of each.Source: §F.1 · pp. 16–17

F.2 Prompt for Indicating Travel Time of an Itinerary

• The duration prompt estimates itinerary hours from the request, defaults to 4 hours when empty, and caps specified durations at 8 hours.Stay durations and travel time between POIs are left for future research.Source: §F.2 · p. 17

F.3 Prompt for Identifying the Start POI

• Start-POI selection follows user needs and favors a POI near neighboring points, prioritizing museums or galleries and avoiding bars or clubs.If the candidate list is empty, the prompt defaults to index 0.Source: §F.3 · p. 18

F.4 Prompt for Generating the Itinerary

• Final itinerary generation presents candidate POIs in order, includes must-sees and user requests, and requires a sequence-following itinerary shorter than the estimated duration.The output includes an overall recommendation reason and descriptions for each POI.Source: §F.4 · p. 19
• ITINERA’s generation prompt selects an hours-appropriate subset of candidate POIs in sequence order, meeting keyword requirements and respecting café and bar constraints.Original user requirements should also be considered and ideally met; cafés or bars are excluded if they disrupt the POI sequence.Source: §F.4 · p. 19

F.5 Prompt for Baseline

• The GPT-4 CoT baseline prompt requires at least six POIs, step-by-step analysis of user requests, and JSON output containing thoughts, itinerary, reasons, and POI descriptions.For baselines without CoT, the “Think step by step” instruction and “thoughts” field are removed.Source: §F.5 · p. 20

F.6 Prompt for LLM-evaluated Metrics

• The paper provides a separate prompt for LLM-evaluated metrics.Source: §F.6 · p. 20

Prompt for LLM-evaluated Metrics

• The LLM-evaluation prompt ranks candidate itineraries on POI quality, itinerary quality, matchness, and language quality, returning descending-order candidate indexes as JSON.POI quality concerns interest and diversity; itinerary quality concerns overall quality and coherence; matchness concerns fit to the user query.Source: §F.6 · p. 20