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.

How it works

Given an incoming user query, we first pass the query to an LLM, which for our system is a version of our latest Gemini models. The LLM suggests an initial trip plan consisting of a list of activities along with relevant details, such as the suggested duration and level of importance to the user query. The initial plan is well-tailored to the user’s interests but may have feasibility issues, like suggesting an establishment that has recently closed.

To address the feasibility issues, we add a few components on top of the LLM. We start by grounding the initial itinerary with up-to-date opening hours and travel times. In parallel, we also use search backends to retrieve additional relevant activities that serve as potential substitutes in case the LLM-suggested plan needs to be modified. The initial plan, substitute activities, and grounding data are then fed into an optimization algorithm to find a trip plan similar to the initial plan that also ensures feasibility.

There are two main stages to the algorithm. The first stage operates on the level of a single day within the trip. For each subset of activities (up to a reasonable maximum size), we determine an optimal scheduling of those activities in a day. We then assign it a quality score determined primarily based on similarity to the original plan and feasibility of the scheduling subject to opening hour and travel time constraints (e.g., a completely infeasible schedule would receive a score of zero). Since the number of activities within a day is small, we found that the scores can be computed by exhaustive search with a sufficiently optimized dynamic programming-based implementation.

In the second stage, we search for an overall itinerary (i.e., sets of activities for each day) that maximizes the total score of the days, subject to the constraint that no two days' activities can overlap. This is a weighted variant of the set packing problem, which is well-known to be NP-complete and thus computationally intractable. However, given that our optimization objective tries to stay close to the initial itinerary by design, we found that local search heuristics were effective. Starting from the initial itinerary, we make local adjustments by exchanging activities between pairs of days so long as this would increase the total score. This procedure is repeated until convergence, resulting in the final itinerary.

Examples

The following query illustrates how the detailed understanding LLMs provide can better serve the user’s needs than a traditional retrieval system.

Query: “Plan me a weekend trip to NYC visiting lots of lesser known museums and avoiding large crowds.”

Our system produces an itinerary matching the user’s request, suggesting museums such as the Museum of the Moving Image and the New York Transit Museum. If we remove the LLM suggestion and rely only on the search-retrieved activities, the resulting itinerary includes some lesser known museums but also the Metropolitan Museum of Art and the Guggenheim Museum, famous museums directly contradicting the user’s request.

On the other hand, the next query demonstrates a case where the hybrid system corrects an issue with the original LLM-suggested itinerary:

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

During our testing, the LLM suggested a number of good attractions, such as the de Young museum (which also includes an observation tower) and the iconic Coit Tower. However, the itinerary scheduled the activities for one of the days in an unnatural way, requiring the user to travel across the city. We were able to correct this in the optimization step, resulting in a logistically feasible plan that preserves the original intent.

Future work

Beyond trip planning, LLMs can be applied to many other everyday tasks, such as organizing an event or scheduling errands. For these types of applications, it is crucial to develop systems that allow LLMs to reliably navigate the constraints of the real world. Our trip planning work is part of a larger ongoing effort to address this challenge — stay tuned for further updates in this space.

Acknowledgements

This blog post is based on work done in collaboration with Wei Chen, Lucas Guzman, Shirley Loayza Sanchez, and Weiye Yao. We also thank Sreenivas Gollapudi, Kostas Kollias, and Gokul Varadhan for helpful guidance.