Look Before You Book: Computer Science in the Airline Industry
Senior Computer Scientist
Refreshments 12:15 pm
A provably hard optimization problem involving ambiguous data. Communication with dubious hardware via arcane protocols. Real-time software constraints, with a very low tolerance for processing errors. No, it's not a new robotics project, it's the world of airline pricing and distribution. As anyone who does much flying soon learns, the airline industry has (largely unwittingly) made the problem of finding the lowest fare and successfully booking it a daunting problem.
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
This talk will introduce the structure of the airline industry, how tickets are priced and sold, and some of the reasoning behind the complexity in airline price structures. Simple combinatorics show that the low fare search problem is in general too large to solve optimally in a reasonable amount of time or space. Once the user chooses a solution to purchase, a robust distributed transaction must be executed, involving the exchange of messages with several airline databases and keeping a synchronized local copy. The talk will outline how we attack these problems with algorithms spanning the fields of graph theory, parsing, databases, optimization, and distributed systems.
Finally, the talk will introduce some recent projects at ITA, both deployed and in development, showing how we're continuing to tackle challenging problems and revolutionize the travel industry.
Todd Williamson is currently a Senior Computer Scientist at ITA Software, Inc., where he works on challenging travel planning problems. He received his Ph.D. in Robotics from CMU in 1998, working on the NAVLAB project. His dissertation was about using real-time stereo vision to detect obstacles on the road. He spent 4 years as the Vice President of R&D for Zaxel Systems, Inc., where he invented and implemented a real-time method for doing "Virtualized Reality".
For appointments, please contact Virginia Arrington (firstname.lastname@example.org).