Optimizing LLM-based trip planning

Many real-world planning tasks involve both harder “quantitative” constraints (e.g., budgets or scheduling requirements) and softer “qualitative” objectives (e.g., user preferences expressed in natural language). Consider someone planning a week-long vacation. Typically, this planning would be subject to various clearly quantifiable constraints, such as budget, travel logistics, and visiting attractions only when they are open, in addition to a number of constraints based on personal interests and preferences that aren’t easily quantifiable.

Large language models (LLMs) are trained on massive datasets and have internalized an impressive amount of world knowledge, often including an understanding of typical human preferences. As such, they are generally good at taking into account the not-so-quantifiable parts of trip planning, such as the ideal time to visit a scenic view or whether a restaurant is kid-friendly. However, they are less reliable at handling quantitative logistical constraints, which may require detailed and up-to-date real-world information (e.g., bus fares, train schedules, etc.) or complex interacting requirements (e.g., minimizing travel across multiple days). As a result, LLM-generated plans can at times include impractical elements, such as visiting a museum that would be closed by the time you can travel there.

We recently introduced AI trip ideas in Search, a feature that suggests day-by-day itineraries in response to trip-planning queries. In this blog, we describe some of the work that went into overcoming one of the key challenges in launching this feature: ensuring the produced itineraries are practical and feasible. Our solution employs a hybrid system that uses an LLM to suggest an initial plan combined with an algorithm that jointly optimizes for similarity to the LLM plan and real-world factors, such as travel time and opening hours. This approach integrates the LLM’s ability to handle soft requirements with the algorithmic precision needed to meet hard logistical constraints.