I was looking at flights today and found a feature on Travelocity I hadn’t seen before: a “1 seat left” warning. While helpful, I don’t find this feature that big a deal (Amazon’s long had a similar “only 2 left, order soon (more on the way)”) but Travelocity clearly does:

They’ve filed a patent for the feature.

Now, to be fair, Travelocity has to do a lot more work than Amazon to figure out how many items are left. Consider the complexity:

6. If you want to do a simple round-trip from BOS to LAX in two weeks, coming back in three, willing to entertain a 24 hour departure window for both parts, then limiting to “reasonable” routes (at most 3 flights and at most 10 hours or so) you have about 5,000 ways to get there and 5,000 ways to get back. Listing them is a mostly trivial graph-search (there are a few minor complications, but not many), that anybody could do in a fraction of a second.

7. The real challenge is that a single fixed itinerary (a fixed set of flights from BOS to LAX and a fixed set back) with only two flights in each direction may have more than 10,000 possible combinations of applicable “fares”, each fare with complex restrictions that must be checked against the flights and the other fares. That means that the search space for this simple trip is of the order 5000 x 5000 x 10000 [= 250 billion], and a naive program would need to do a _lot_ of computation just to validate each of these possibilities.

When your pricing is so complicated your resellers feel the need to patent a “Supplies are running out!” message, it’s well past time to fire somebody.

This entry was posted on Sunday, January 8th, 2006 at 2:57 pm and is filed under Geekery, Travel.. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.