ROAM: Retrieval-Augmented Optimization for Feasible Multi-Day Itinerary Planning
Organizations: Department of Systems Engineering, City University of Hong Kong
Abstract
Large language models (LLMs) can draft plausible travel itineraries, but the plans they produce are frequently infeasible: attractions are grouped into days without regard for geography, opening hours are ignored, and a single generation pass cannot reliably organize a multi-day trip. We present ROAM, a retrieval-augmented agentic framework for spontaneous multi-day itinerary planning that couples semantic preference retrieval with explicit spatiotemporal optimization. ROAM embeds the natural-language request, retrieves a compact candidate set from a curated point-of-interest (POI) database, partitions candidates into day groups through maximal-clique analysis and K-means, orders each day with a quality-biased simulated-annealing TSP solver, and repairs hard opening-hour violations with greedy exchange. A spatiotemporal retrieval layer injects weather forecasts, real road distances and POI operating hours into the prompt, after which the LLM renders a structured, map-ready itinerary; an interactive ReAct-style replanning agent then supports natural-language edits while re-checking feasibility. Across four Chinese cities and 510 POIs, ROAM produces 27.5 POIs per three-day plan versus 19.3 for a bare LLM and 17.0 for a retrieval-only baseline (+42% and +62%), while reducing route dispersion from 2,101 to 677 (3.1x). Ablations show that spatial optimization is the dominant driver of route efficiency and that hard time-window repair prevents roughly 30% of attractions from violating operating hours.
Figures & tables
| City | POIs | Queries | Trip length | Scenario groups |
|---|---|---|---|---|
| Fuzhou | 130 | 9 | 3 days | sunny / rainy / sightseeing / exploration |
| Guangzhou | 132 | 9 | 3 days | sunny / rainy / sightseeing / exploration |
| Shenzhen | 121 | 9 | 3 days | sunny / rainy / sightseeing / exploration |
| Shanghai | 127 | 9 | 3 days | sunny / rainy / sightseeing / exploration |
| Total | 510 | 36 | – | – |
| Metric | Symbol | Definition | Dir. |
|---|---|---|---|
| Coverage | POI | : total POIs in the plan | |
| Semantic match | SM | : preference relevance | |
| Travel ratio | TT | ||
| Compactness | CE | ||
| Balance | DB | coefficient of variation of daily POI counts | |
| Route cost | RC | , in metres |
| City | Method | POI | SM | TT(%) | CE(%) | DB | RC(m) |
|---|---|---|---|---|---|---|---|
| Fuzhou | Bare LLM | 21 | 0.3 | 3.9 | 0.3 | 0.1 | 411.8 |
| Baseline | 16 | 0.3 | 0.0 | 1.0 | 0.1 | 3,856.9 | |
| Roam | 28 | 0.3 | 7.6 | 0.5 | 0.1 | 554.8 | |
| Guangzhou | Bare LLM | 20 | 0.4 | 8.2 | 4.8 | 0.1 | 869.6 |
| Baseline | 19 | 0.4 | 0.0 | 0.6 | 0.2 | 1,433.9 | |
| Roam | 21 | 0.3 | 6.8 | 0.7 | 0.1 | 626.3 |
| City | Method | POI | SM | TT(%) | CE(%) | DB | RC(m) |
|---|---|---|---|---|---|---|---|
| Fuzhou | Bare LLM | 18 | 0.3 | 3.4 | 0.4 | 0.2 | 421.9 |
| Baseline | 16 | 0.2 | 0.0 | 0.0 | 0.1 | 1,360.4 | |
| Roam | 33 | 0.3 | 5.6 | 0.4 | 0.0 | 454.4 | |
| Guangzhou | Bare LLM | 18 | 0.3 | 4.4 | 0.8 | 0.2 | 536.0 |
| Baseline | 19 | 0.3 | 0.0 | 0.6 | 0.1 | 1,905.1 | |
| Roam | 33 | 0.3 | 7.0 | 1.0 | 0.0 | 555.5 |
| Scenario | Method | POI | SM | TT(%) | CE(%) | DB | RC(m) |
|---|---|---|---|---|---|---|---|
| Sightseeing | Bare LLM | 15.5 | 0.4 | 5.1 | 2.0 | 0.08 | 735.1 |
| Baseline | 17.3 | 0.4 | 0.0 | 0.4 | 0.15 | 1,438.4 | |
| Roam | 34.5 | 0.4 | 10.8 | 11.8 | 0.08 | 993.3 | |
| City exploration | Bare LLM | 18.0 | 0.3 | 3.9 | 4.5 | 0.13 | 501.7 |
| Baseline | 17.0 | 0.3 | 0.0 | 0.9 | 0.13 | 1,392.2 | |
| Roam | 23.3 | 0.3 | 5.8 | 1.8 | 0.23 | 482.3 |
| Variant | Removed component | Observed effect |
|---|---|---|
| – Retrieval | semantic retrieval (stage 2) | POI selection becomes random; SM drops; plans drift toward generic landmarks |
| – Spatial opt. | day partitioning + TSP ordering | RC degrades to 2,000 m (baseline level); days mix distant districts |
| – Time windows | hard time-window repair | 30% of visits arrive after closing time; coverage looks high but plans are infeasible |
| – RAG | spatiotemporal context (stage 4) | plans ignore the weather and duplicate outdoor visits on rainy days; transit modes become unrealistic |
| – Quality bias | in Eq. ( 4 ) | aggregate metrics nearly unchanged, but high-rated attractions are no longer prioritized (perceived quality drops) |
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
| Service | Role | Fallback on failure |
|---|---|---|
| wttr.in | multi-day weather forecast | omit weather block from the prompt |
| OSRM | real road distance and duration | Haversine distance |
| Amap geocoding | hotel / POI coordinates | pre-stored coordinates in the database |
| Amap ratings | POI quality score | static rating column in the database |
| Amap tiles | map base layer | OpenStreetMap tiles |
| BGE-small-zh | query and POI embeddings | lighter local embedding model |