Hybrid LLM-Optimization System for Trip Planning with Real-World Constraints

google · Tech · 2025 · source Agentic: no · promotional bias: low · source-backed · extracted with prompt 0.5.6 (schema v2)

Generated from extraction.json — do not edit by hand. Every claim cites verbatim source evidence; stated means the quote directly asserts the claim, implied means it supports it indirectly.

Problem

Domain: consumer trip planning with real-world logistical constraints

Google needed AI-generated day-by-day travel itineraries that preserve a user's qualitative preferences while satisfying hard logistical constraints such as opening hours, travel time, budgets, and multi-day scheduling feasibility.

Constraints:

• LLMs are good at soft qualitative preferences but less reliable with quantitative logistical constraints
• itineraries need up-to-date real-world information such as opening hours and travel times
• generated plans can contain infeasible items such as closed museums or inefficient cross-city travel
• the system must remain similar to the LLM's user-tailored plan while correcting feasibility issues
• single-day scheduling must respect opening hours and travel-time constraints
• multi-day itinerary optimization is a weighted set-packing variant and computationally intractable in general

Architecture

Google's AI trip ideas feature uses a hybrid LLM-plus-optimization architecture. An incoming trip-planning query is first sent to a Gemini model, which creates an initial itinerary with activities, suggested durations, and importance levels reflecting the user's qualitative preferences. The system then grounds that itinerary with current opening hours and travel times, retrieves additional relevant substitute activities from search backends, and feeds the initial plan, substitutes, and grounding data into a two-stage optimizer. Stage one optimizes each day with dynamic programming over feasible activity subsets. Stage two treats the whole itinerary as a weighted set-packing variant and uses local search from the initial LLM itinerary to exchange activities between days until the total score no longer improves.

Diagram confidence: explicit (topology described by the source).

flowchart LR
  Trip_planning_query["Trip-planning query"] --> Gemini_itinerary_generator["Gemini itinerary generator"]
  Gemini_itinerary_generator --> Grounding_data_fetcher["Grounding data fetcher"]
  Search_backend_retrieval["Search backend retrieval"] --> Optimization_algorithm["Optimization algorithm"]
  Grounding_data_fetcher --> Optimization_algorithm
  Gemini_itinerary_generator --> Optimization_algorithm
  Optimization_algorithm --> Single_day_dynamic_programming_stage["Single-day dynamic programming stage"]
  Single_day_dynamic_programming_stage --> Multi_day_local_search_stage["Multi-day local search stage"]
  Optimization_algorithm --> Multi_day_local_search_stage
  Multi_day_local_search_stage --> Final_itinerary["Final itinerary"]

Components

Data flow

A user submits a natural-language trip-planning query. Gemini generates an initial itinerary with activity details, duration, and importance. The system fetches opening hours and travel times, retrieves substitute activities from search backends, and sends the initial plan, substitutes, and grounding data to an optimizer. The optimizer scores feasible single-day schedules with dynamic programming, then improves the multi-day itinerary with local activity exchanges, returning a final plan that stays close to the LLM suggestion while satisfying real-world constraints.

Why this architecture

The system is hybrid because neither an LLM nor a traditional retrieval/optimization system is sufficient on its own. The LLM understands qualitative travel preferences such as lesser-known museums or kid-friendly restaurants, but it may hallucinate feasibility. Search and grounding provide current facts, while the optimizer enforces travel-time and opening-hour constraints without discarding the LLM's user-tailored intent.

Models used: Gemini models · large language models · dynamic programming optimizer · local search heuristic

Scale

• The production feature suggests day-by-day itineraries in Google Search.
  “We recently introduced AI trip ideas in Search, a feature that suggests day-by-day itineraries”article, stated
• The single-day optimizer searches subsets of activities up to a reasonable maximum size.
  “For each subset of activities (up to a reasonable maximum size), we determine an optimal scheduling of those activities in a day.”article, stated
• The itinerary-level problem is a weighted set-packing variant and NP-complete in general.
  “This is a weighted variant of the set packing problem, which is well-known to be [NP-complete]”article, stated
• The example use cases include a weekend trip to NYC and a trip to San Francisco.
  “Query: “Plan me a weekend trip to NYC visiting lots of lesser known museums and avoiding large crowds.””article, stated

  “Query: “Plan me a trip to San Francisco. I want to visit art museums and go somewhere with panoramic views of the city.””article, stated

Alternatives considered (roads not taken)

Use the LLM-generated itinerary directly

Rejected because: The initial LLM plan can be user-tailored but logistically infeasible due to stale or complex real-world constraints.

Use search-retrieved activities without LLM preference modeling

Rejected because: The NYC example shows retrieval-only results contradicting the user's stated preference to avoid famous crowded museums.

Solve the multi-day itinerary exactly

Rejected because: The itinerary-level problem is NP-complete, so the team uses local search heuristics that work because the objective starts near the initial LLM plan.

Patterns

tool-use-orchestration (system-design)

The production pipeline orchestrates Gemini, search backends, real-world grounding data, dynamic programming, and local search instead of relying on a single model call.

rag-retrieval (retrieval)

Search backends retrieve substitute activities and grounding data so the itinerary is not limited to stale LLM knowledge.

safety-policy-enforcement (reliability)

The optimizer enforces hard logistical feasibility constraints that the LLM alone may violate.

eval-driven-development (quality)

The team uses examples and testing to compare LLM-only, search-only, and hybrid behavior against preference and feasibility failures.

latency-optimization (operations)

The optimizer uses exhaustive dynamic programming only where day-level activity sets are small, then switches to local search for the intractable itinerary-level problem.

Tradeoffs

Hybrid LLM plus optimizer

Chose LLM initial plan corrected by algorithmic optimization over pure LLM trip planning.

Rationale: The LLM captures soft preferences, while the optimizer enforces hard constraints such as opening hours and travel time.

Retrieve substitutes in parallel with grounding

Chose search-backed substitute activities over only modifying or deleting LLM-suggested activities.

Rationale: Substitutes give the optimizer alternatives when the original plan needs to change for feasibility.

Dynamic programming for single-day planning

Chose exhaustive search with optimized dynamic programming within a day over a heuristic for every part of the problem.

Rationale: The number of activities within a day is small enough to compute high-quality day scores exactly or near-exactly.

Local search for the multi-day itinerary

Chose incremental activity exchanges until convergence over exact global set-packing optimization.

Rationale: The global problem is NP-complete, but starting near the LLM itinerary makes local improvements effective.

Gotchas (what bit them)

LLMs can satisfy preferences while violating real-world feasibility.

Root cause: Quantitative logistics depend on current opening hours, travel times, and interacting constraints that may not be in the model's knowledge.

Resolution: Ground the LLM itinerary with current data and optimize the schedule against opening-hour and travel-time constraints.

Search-only retrieval misses nuanced user intent.

Root cause: Traditional retrieval can return relevant attractions that conflict with qualitative constraints such as avoiding large crowds.

Resolution: Use the LLM's preference understanding to form the initial plan, then use search as a source of grounding and substitutes rather than as the sole planner.

Exact itinerary optimization does not scale cleanly across multiple days.

Root cause: The overall itinerary problem is a weighted set-packing variant and is NP-complete.

Resolution: Use local search from the LLM's initial itinerary, exchanging activities between pairs of days until convergence.

Optimizing feasibility can accidentally erase the LLM's qualitative intent.

Root cause: A plan could become logistically valid but no longer match the user's original preferences.

Resolution: Score schedules primarily on both similarity to the original LLM plan and practical feasibility.

Evaluation

The article demonstrates evaluation qualitatively through examples: an NYC query showing that LLM suggestions preserve user preference better than search-only retrieval, and a San Francisco query showing the optimizer correcting an LLM itinerary's impractical cross-city travel.

Metrics: qualitative match to user preference · opening-hour feasibility · travel-time feasibility · similarity to original LLM plan · optimization score convergence

Outcomes

• The hybrid system was launched as AI trip ideas in Search.
• The NYC example preserves the user's request for lesser-known museums and avoiding large crowds better than search-only retrieval.
• The San Francisco example reorganizes a qualitatively good but logistically awkward LLM plan into a feasible itinerary.
• The architecture provides a reusable pattern for LLM applications that need to operate under hard real-world constraints.

The article is a product/research writeup rather than a benchmark report; it does not disclose latency, traffic, or aggregate success-rate metrics. Its strongest evidence is the explicit system architecture and qualitative examples.