The Robotics Institute

RI | Seminar | February 7, 2006

Robotics Institute Seminar, February 7, 2006
Time and Place | Seminar Abstract | Speaker Biography | Speaker Appointments

Look Before You Book: Computer Science in the Airline Industry

Todd Williamson

Senior Computer Scientist

ITA Software,Inc.

 

 

 

 

 

Time and Place

NSH 3305
Refreshments 12:15 pm
Talk 12:30pm

Abstract

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. 

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.

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. 

Speaker Biography

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".

Speaker Appointments

For appointments, please contact Virginia Arrington (va2@andrew.cmu.edu).

The Robotics Institute is part of the School of Computer Science, Carnegie Mellon University.