BOS-SFO Trip Study: The Complexity of Airfare Search

The problem of finding and pricing flights in response to a user's search request may not seem particularly difficult. However, any serious attempt to find the best solutions to a user's search unveils the true complexity of the problem, which is staggering. First, we'll give a simplified, but hopefully intuitive, back-of-the-envelope explanation and then we'll look at a specific example with some real numbers from an actual query that our QPX search engine performed.

Getting a feel for the numbers

There are more ways than you might imagine to fly from one city to another. As an example, let's look at flights from Boston (BOS) to San Francisco (SFO). There are usually around 15 nonstop flights each day, on various carriers, between the two cities. However, if you're willing to consider connecting in an intermediate city on the way (such as Chicago or Denver), the possibilities mount exponentially. Considering flights on all airlines, departing at different times of day, through various connection cities, there are very easily 400 reasonable ways to fly from Boston to San Francisco. For a round trip, there are easily 400 ways to fly from San Francisco back to Boston. Taken together, this gives us 400 x 400 = 160,000 different possible itineraries for a Boston to San Francisco round trip.

But that's just the beginning. Airlines publish many different fares for travel between city pairs. Each fare has a different set of conditions that are associated with it, as well as a price (roughly speaking, the more the conditions, the cheaper the price). The conditions of the fare must be met before it can be used in the pricing of a particular itinerary. For example, a fare might require that traveler purchase their ticket at least 2 weeks in advance of the beginning of their trip, or might require the passenger to stay at their destination over a Saturday night, or even require the passenger to be a child to qualify for the fare. It's very common for an airline to have as many as 200 different fares for travel between two cities (say, Boston and Chicago). To make things even more complicated, multiple fares can be combined together in various ways to arrive at a particular price for the entire trip. All things considered, there are typically 10,000 different ways to overlay the fares onto a *single* Boston to San Francisco round trip itinerary.

So, for *each one* of the 160,000 possible different Boston to San Francisco round trip itineraries that we identified earlier, there are usually somewhere on the order of 10,000 different ways to price *each one*, resulting in 160,000 x 10,000 = 1,600,000,000 (1.6 billion) options!

Of course, these numbers can all vary greatly, depending on the origin and destination cities, the number and kinds of fares airlines have filed for all the possible routes between those cities, the dates of the trip, how far out you purchase the trip, the number and types of passengers (adults, children, etc), taxes, fees, and many, many other factors.

There's another major step that further complicates the situation - seat availability. Performed after QPX identifies all the possible itineraries, and before determining which fares can be used, seat availability is an incredibly complex process, for which information is updated as often as hundreds of times per second. You can be confident that seat availability and all of the processes described above have been validated prior to QPX presenting you with the results.

A specific example

Let's look at a particular example with some real numbers:

Boston (BOS: Boston Logan airport) to San Francisco (SFO: San Francisco International airport)

Depart anytime on October 15, 2010

Return anytime on October 22, 2010

1 adult passenger

QPX produced these numbers (all availability-checked and available for purchase):

Number of outbound flights considered (BOS-SFO): 403

Number of return flights considered (SFO-BOS): 402

Total number of journey itineraries: 403 x 402 = 162,006

Average number of ways to overlay fares onto each journey itinerary: 14,749

Total number of priced solutions generated by QPX: 162,006 x 14,749 = 2,389,402,117

Let's try the same search, this time without checking seat availability. This search returns all possible flight/fare combinations, regardless of whether they are actually available for purchase:

QPX produced these numbers (without checking seat availability):

Number of outbound flights considered (BOS-SFO): 403

Number of return flights considered (SFO-BOS): 402

Total number of journey itineraries: 403 x 402 = 162,006

Average number of ways to overlay fares onto each journey itinerary: 22,248

Total number of priced solutions generated by QPX: 162,006 x 22,248 = 3,604,439,023

Of course, even though QPX calculates all the possible solutions to find the lowest or best solution, it does not return all 3,604,439,023 solutions -- or even all 2,389,402,117 solutions that are available for purchase. No user would want to sort through that many options! Instead, QPX spends considerable effort weighing many factors (price, convenience, and so forth) to return only the very best options for you to consider.

For more information about the combinatorics of airfare pricing, see:
Computational Complexity of Air Travel Planning

by Carl de Marcken