Embark Now: User Demand Oriented Framework for Multi-day Urban Travel Itinerary Planning

Planning a multi-day trip in a large city is a complex optimization problem involving thousands of Points of Interest (POIs), strict spatiotemporal constraints (like opening hours and travel times), and highly subjective user preferences. Existing solutions often struggle to balance the flexibility of natural language interaction with the rigorous computational requirements of multi-day planning, often resulting in either infeasible plans or excessive computation times.

The authors propose a hybrid framework that bridges the gap between Large Language Models (LLMs) and traditional heuristic optimization. The process consists of two primary stages:

1. Preference Analysis Pipeline: A dual-step LLM process translates natural language user requests into structured inputs, such as specific POI requirements, time budgets, and dining preferences.
2. Enhanced GRASP Planner: The system uses a Greedy Randomized Adaptive Search Procedure (GRASP) to construct itineraries. This is augmented with a "Clustering and Substitution" strategy, which improves the rationality of the routes and ensures that the generated plans adhere to real-world constraints while remaining computationally efficient.

Experiments conducted on 5,040 user cases across Beijing and Tianjin demonstrate that the proposed framework significantly improves itinerary quality and efficiency. The method achieved an average increase in itinerary scores of at least 4.52% and 11.09% compared to state-of-the-art methods. Furthermore, the algorithmic enhancements led to substantial gains in computational speed, with performance improvements of up to 26.07% in specific metrics while reducing the time required to generate feasible, high-quality multi-day plans.

This research provides a practical solution for building intelligent travel assistants that can handle the nuance of human preferences without sacrificing the mathematical rigor required for complex, multi-day scheduling. By effectively combining the reasoning capabilities of LLMs with the optimization power of heuristic algorithms, the framework offers a scalable way to deliver personalized, feasible travel experiences in large urban environments.