When it comes to pricing airline tickets, the sky's the limit -- literally. Back in the day, shorter flights usually equaled cheaper tickets, but since industry deregulation in 1978, fierce competition, market fragmentation and the growth of elaborate hub-and-spoke networks have led airlines to develop a Byzantine pricing structure so complicated that it took a group of MIT grads to begin deciphering it.
Airline executives have long defended the complexity of this system by arguing that standardizing fares would make profitability difficult, if not impossible. They say that, while consistently high ticket prices would likely depress sales, uniformly cheap fares might fill planes but wouldn't cover costs.
Carriers instead use a variable pricing scheme that offers many different fares for any given flight. Each fare is governed by a specific set of rules that dictate everything from days of travel to minimum/maximum stays to permitted connection points.
Individual fares are typically composed from what are called priceable units, or PUs, which are the puzzle pieces that snap together to form a total ticket. PUs can take several different forms: one-way flights, round trips or multiple fare components that form a complete loop or form loops with one component missing, known as "open jaws."
A specific set of flights may be partitioned into fares and priceable units in many ways. For the four flights above, six possibilities are shown (there are more). Each red line represents a fare component and each yellow polygon a priceable unit. For example, a round-trip PU may be used with one fare paying for both outbound flights and one for both return flights. Alternatively two open-jaw priceable units can be used, each containing two fares, each fare paying for one flight.
Image: ITA SoftwareIn a paper titled Computational Complexity of Air Travel Planning, MIT graduate and ITA Software co-founder Carl de Marcken offers an imperfect but effective analogy: "If fares are atoms, priceable units are the molecules used to build complete tickets."
As if that's not complex enough, any given set of flights can be broken into different types of PUs and fares, and the rules associated with one PU or fare can restrict every other fare and flight on that ticket, exponentially increasing the complexity of a search.
De Marcken's paper examines a Boston to San Francisco round trip, using just one set of flights offered by American Airlines. When all of American's flights and fares on this particular route are tested against all applicable fare rules and then combined into every possible pricing unit, the result is more than 25 million different possibilities. And that's only a fraction of what's available if the search is expanded to include other airlines and connection points.
Throw in seasonal sales and fare variations based on competition on certain routes (Jeremy Wertheimer, ITA's CEO and a classmate of de Marcken's at MIT, claims that flying between New York and Boston with a connection in London was at one time cheaper than going nonstop) and the whole thing becomes still more convoluted.
The system is so complex that the problem of finding the cheapest airfare between two cities is considered mathematically unfathomable. According to a paper from the Society for Industrial and Applied Mathematics provided by ITA, "the problem of finding the cheapest airfare from point A to point B is unsolvable."
ITA's software consists of more than 200,000 lines of Common Lisp, a dialect of the Lisp programming language that's often associated with artificial intelligence research. This code is optimized at a lower level, ensuring that ITA's algorithms work quickly.
Utilizing techniques from natural-language processing, these algorithms address the complexity inherent in ticket pricing by using what's known as dynamic programming to break airfare searches into smaller overlapping sub-problems that only need to be solved once. Answers to each sub-problem are placed in a table where they can be referenced later, which makes the overall computation faster and more efficient.
It's a break from early '90s online search tools like Sabre's BargainFinder, which automated the process of reviewing fare and routing options, but examined each and every option serially, which means searches took longer and required massive amounts of computing power. "Our algorithm can handle much more data much more quickly," says Wertheimer.
Now, if only they could come find a way to make the flights leave on time.
(Check out our mileage runner's odyssey into booking a cheap, high-mileage flight in "We Love to Fly and It Shows: Inside the World of Mileage Running.")
We Love to Fly and It Shows: Inside the World of Mileage Running
