The Dial-a-Flight-Problem

Wednesday, July 27, 2005 - 10:15am - 11:00am
EE/CS 3-180
Almost 3,000 businesses in the United States provide on-demand air charter services. The on-demand air charter industry provides a vital transportation link for medical services, important cargo needed to promote commerce, and personal travel supporting the growth of the economy. The companies use smaller aircraft to meet the customized needs of the traveling public for greater flexibility in scheduling and access to almost every airport in the country. Flights are planned according to the customer's schedule, not the operator's.

DayJet Inc. is a startup company in this space that will soon provide air taxi services. There are obvious advantages to an air taxi system. More than 1.5 million people board commercial airliners each day. Most fly with hundreds of other passengers to and from a limited number of major hub airports that are heavily congested and often located many miles from their homes and final destinations. Missed connections and flight delays add to their frustrations. An air-taxi system gives travelers the option of using small jets that fly to and from less-congested outlying airports, without packed parking lots, long lines at security checkpoints, flight delays, and lost luggage, that are closer to where they live and where they want to go. While commercial flight service now exists at only about 550 airports in the United States, air taxis will be able to land at 5,000 of the nation's 14,000 public and private runways. And all that at comparable fares.

A key challenge in setting up an air taxi system is the development of a scheduling engine that takes requests for transportation and schedules planes and pilots in a cost effective way to satisfy these requests. The dial-a-flight problem captures the essential characteristics of the scheduling problems encountered by an air taxi service.

The dial-a-flight problem is concerned with the scheduling of a set of passenger reservations for air transportation during a single day. A reservation specifies an origin airport, an earliest acceptable departure time at the origin, a destination airport, and a latest acceptable arrival time at the destination. A fleet of airplanes operable by a single pilot is available to provide the requested air transportation. Each airplane has a home base, is available for a certain period during the day, and returns home at the end of the day. A set of pilots, stationed at the home bases of the airplanes, is available to fly the airplanes. A pilot departs from the home base where he is domiciled at the start of his duty and returns to the home base where he is domiciled at the end of his duty. A pilot schedule has to satisfy FAA regulations governing flying hours and duty period, i.e., a single pilot cannot fly more than 8 hours in a day and his duty period cannot be more than 14 hours. To ensure acceptable service a passenger itinerary will involve at most two flights, i.e., a single intermediate stop is allowed. A turnaround time at an airport, i.e., the minimum time between an arrival at an airport and the next departure, is given. The objective is to minimize the costs, while satisfying all requests. A dispatcher has to decide which planes and pilots to use to satisfy the reservations and what the plane and pilots itineraries will be, i.e., the flight legs and associated departure times.

We present a variety of optimization approaches for the solution of the dial-a-flight problem.

In our time-discretized integer multicommodity network flow model, the key events from the perspective an airplane are modeled, e.g., arrival at an airport, dropping off passengers at the airport, preparing for the next flight (which one depends on whether there were indirect passengers on board), loading new direct flight passengers, and loading new indirect flight passengers. To keep the size of the model within acceptable limits a flexible concept of time-discretization has been designed and implemented. Each airplane has its own time-discretization and the number of time instants as well as their values are completely flexible. This flexibility is crucial, because we extensively employ dominance relations between itineraries to reduce the network size.

In our column generation formulation, reservations are represented by rows and plane itineraries are represented by columns. The multicommodity flow model is modified to solve the pricing problem. A customer constrained shortest path algorithm is developed for its solution. Specialized branching schemes are employed in a branch-and-price approach to identify high quality schedules.

Joint work with...

Mo Bazaraa, Daniel Espinoza, Renan Garcia, Marcos Goycoolea, George Nemhauser : Georgia Tech

Emilie Danna and Zonghau Gu : ILOG, Inc.

Alex Khmelnitsky and Eugene Taits : DayJet?, Inc.