At any moment there are between 2,000 and 10,000 commercial airliners in the sky, part of a dense network that provides, for example, more than 100,000 practical paths from Boston to the San Francisco area every day. At its core, finding a sequence of flights that meets the user’s stated time constraints is a path-planning problem which can be solved with well-known techniques. But the airfare search problem is much more complex than that. In fact, the airlines’ price structure is so rich that finding the cheapest price for a simple round-trip journey is in the general case provably undecidable. Even if one bounds the size of solutions to a small number of flights there may be more than 1020 reasonable answers to a simple travel query. The problem is compounded by the fact that airline revenue management systems are constantly and dynamically adjusting the prices for each flight along a discretized scale.Seriously though, how is this even possible ? There are a finite number of routes at any given time, and i am assuming that no one pays me to fly (I'm ignoring voluntary bumps of course), so the total path length must increase if I take longer and more byzantine routes...
Update (2/3): Michael Mitzenmacher indicates that there is more to the problem that meets the eye. In fact, he goes further:
If you have any smart students who are looking for a job in a "real-world" company, I'd strongly recommend they look at ITA software. Obviously I've drunk the Kool-Aid, but I think they'll continue to be an innovative, leading company in the travel space. And heck, how many companies do you know that even think to advertise themselves by giving a talk about the undecidable problems they are tackling!
I remember, from a similar talk a couple years ago, that the airline industry has interesting pattern matching rules that allow one to construct hard tiling problems that are undecidable. These are rules like (hypothetically) "this fare can be used if this is the second leg of a three-leg open-jaw trip that does not start on a Saturday". You know, when one can show Conway's Game of Life is Turing complete...
ReplyDeletePosted by Maverick Woo
The point is that the assumption of uncomputability only holds under rather unrealistic assumptions (e.g. arbitrarily low fares are needed, and no fully unrestricted fares).
ReplyDeletePosted by Anonymous
It's a pity I can't hear the talk. I'd really like to know what circumstances conspire to make any version of this problem undecidable.
ReplyDeletePosted by Suresh
This talk is given by people from ITA software. I have been doing some consulting for them during my sabbatical (they are located here in Cambridge). I can vouch that this is a very exciting company, with a lot of very smart people, and a lot of very interesting problems. I started using their basic product -- essentially a search engine for flight reservations -- back when it was a demo version and fell in love with it. They're moving on to tackle further interesting problems.
ReplyDeleteAn anonymous commenter suggested that uncomputability held only under rather unrealistic assumptions. This is perhaps partially true, but the result is obtained using the model and rule set that the airlines actually use! Like most theoretical results, this result is not meant to suggest that the problem of finding the lowest price is undecidable in practice, but that it is very hard, and that you have to do something to the model or rules to have any hope at all of making the problem tractable.
If you have any smart students who are looking for a job in a "real-world" company, I'd strongly recommend they look at ITA software. Obviously I've drunk the Kool-Aid, but I think they'll continue to be an innovative, leading company in the travel space. And heck, how many companies do you know that even think to advertise themselves by giving a talk about the undecidable problems they are tackling!
Posted by Michael Mitzenmacher
but the result is obtained using the model and rule set that the airlines actually use!
ReplyDeleteNot so. Here are the details. Assume, as is the case in practice, that every ticket costs at least $1 and that there are unrestricted free tickets (business class). To find the cheapest ticket from A to B all you need to do is
(a) find an upper bound in the price by using a connectivity algorithm on the flight schedule over business class only. Let B be the price in dollars of this ticket.
(b) using branch and bound exhaustively try all possible flight combinations composed of at most B segments.
(c) select the cheapest ticket found.
That is a decidable algorithm.
Posted by Anonymous traveller
unrestricted free tickets
ReplyDeleteI meant free as in freedom, not gratis.
Posted by Anonymous traveller
Every ticket from point A to point B costs at least $1. Legs might have negative costs, but that is not visible to a person making the connections. One cannot assemble a single flight while choosing the legs, one can only choose tickets from A to B and piece them together. That selection is done by the airlines.
ReplyDeletewhy should there be any unrestricted tickets? Can't they sell out?
In practice: no. As salespersons know well, if you purchase a full fare unrestricted business ticket you are getting on the next plane, even if, as they say, if the airline has to kick the pilot out to make space :-).
In theory if every single passenger had bought a full fare business ticket (something in the order of $5,000 to cross the Atlantic in an economy class seat!) then sure, they would have sold out, but that is an extremely unrealistic assumption.
Posted by Anonymous