TL;DR
This paper introduces "To the Globe" (TTG), a system that plans optimal travel itineraries from natural language requests. TTG uniquely combines Large Language Models (LLMs) for understanding user intent with Mixed Integer Linear Programming (MILP) solvers to guarantee feasible and optimal travel plans, all within seconds.
What Problem Does This Paper Address?
Planning travel itineraries is a complex, time-consuming task involving numerous interdependent constraints like flights, accommodations, and budgets. While LLMs have shown promise in understanding natural language, they often struggle with complex reasoning, planning, and guaranteeing factual accuracy, making them unreliable for critical tasks like travel planning where feasibility and optimality are paramount. Existing approaches often lack guarantees or require significant manual effort. TTG aims to bridge this gap by providing a system that can reliably generate optimal travel plans from natural language, addressing the need for both user-friendliness and robust decision-making.
Methods
TTG employs a hybrid architecture that leverages the strengths of both LLMs and symbolic solvers. The core workflow involves:
- Natural Language Understanding & Symbolic Translation: An LLM, fine-tuned on synthetically generated data, translates user requests from natural language into a structured symbolic representation (JSON format). This representation captures all the constraints and objectives specified by the user.
- Symbolic Planning with MILP: This symbolic representation is then fed into a Mixed Integer Linear Programming (MILP) solver. The MILP solver is used to find an optimal solution that satisfies all the constraints (e.g., budget, time, flight connections) and optimizes a defined objective (e.g., minimizing cost, prioritizing hotel quality, or flight experience).
- Natural Language Response Generation: The optimal itinerary found by the MILP solver is then translated back into natural language for the user.
A key innovation is the Symbolic Travel Generator, which creates synthetic training data by combining real-world flight data with generated hotel information and user requests in symbolic form. This pipeline avoids the need for manual annotation and allows for the generation of a large, diverse dataset.
Datasets
- Synthetic Training Data: The authors created a synthetic data pipeline to generate user requests and corresponding flight/hotel information. This pipeline generated 238k training samples and 29.8k test samples.
- Real-world Flight Data: Existing real-world, one-way US domestic flight information from Expedia was used to build the travel generator.
- Hotel Data: Public hotel information was used, with added noise to prices and other attributes to create synthetic data.
Key Insights and Ideas
- LLMs + MILP for Guaranteed Planning: The paper demonstrates that combining the natural language understanding capabilities of LLMs with the rigorous optimization guarantees of MILP solvers is a powerful approach for complex planning tasks.
- Synthetic Data Generation is Crucial: The success of the LLM fine-tuning relies heavily on the quality and scale of the synthetic data generated by their novel pipeline, which bypasses the need for expensive human annotation.
- Symbolic Representation Matters: Using JSON as the symbolic representation for MILP input offers a good balance between expressiveness and simplicity, facilitating easier generation and processing compared to code-based representations.
- User Experience is Key: The system provides multiple itinerary options (e.g., minimum cost, better hotel, better flight) and a user-friendly interface with map visualizations, catering to different user preferences.
Key Results
- High Accuracy: The NL-to-symbolic translation achieved approximately 92.0% exact match accuracy with valid JSON output.
- Near-Optimal Solutions: The generated itineraries had a cost ratio of 0.979 compared to the optimal cost of the ground truth, indicating near-optimal solutions. Even when the NL-to-symbolic translation wasn't an exact match, the solutions were still good (score of 0.726).
- Real-time Performance: The entire system responds to user requests in approximately 5 seconds, with the LLM inference being the primary bottleneck.
- Positive User Feedback: Human evaluations showed high Net Promoter Scores (NPS) of 35-40% for generated itineraries, indicating strong user satisfaction with the value and efficiency of the plans.
Limitations and Future Work
- LLM Sensitivity to Constraints: The paper notes that the LLM can be somewhat insensitive to certain airline constraints (e.g.,
must_not_basic_economy,departure_time,avoid_red_eye), leading to errors. Further filtering or fine-tuning is needed. - Data Imbalance: Performance on airline constraints decreases with a higher number of constraints, possibly due to data imbalance in the training set.
- Future Work: The authors plan to explore multi-round dialog for more adaptive planning, enhance personalization by inferring user preferences, and develop human benchmark tasks for better evaluation and improvement.
Summary updated