This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Espinoza, D. Articles by Savelsbergh, M. W. P. Search for Related Content

Per-Seat, On-Demand Air Transportation Part I: Problem Description and an Integer Multicommodity Flow Model

School of Industrial Engineering, Universidad de Chile, Santiago, Chile
DayJet Corporation, Boca Raton, Florida 33431
School of Business, Universidad Adolfo Ibáñez, Santiago, Chile
H. Milton School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
H. Milton School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
daespino{at}dii.uchile.cl
renan.garcia{at}dayjet.com
marcos.goycoolea{at}uai.cl
george.nemhauser{at}isye.gatech.edu
martin.savelsbergh{at}isye.gatech.edu

The availability of relatively cheap small jet planes has led to the creation of on-demand air transportation services in which travelers call a few days in advance to schedule a flight. A successful on-demand air transportation service requires an effective scheduling system to construct minimum-cost pilot and jet itineraries for a set of accepted transportation requests. We present an integer multicommodity network flow model with side constraints for such dial-a-flight problems. We develop a variety of techniques to control the size of the network and to strengthen the quality of the linear programming relaxation, which allows the solution of small instances. In Part II, we describe how this core optimization technology is embedded in a parallel, large-neighborhood, local search scheme to produce high-quality solutions efficiently for large-scale real-life instances.

Key Words: air transportation; on-demand service; integer multicommodity flow
History: Received: July 2007; revised: November 2007; accepted: December 2007.

This article has been cited by other articles:

				D. Espinoza, R. Garcia, M. Goycoolea, G. L. Nemhauser, and M. W. P. Savelsbergh Per-Seat, On-Demand Air Transportation Part II: Parallel Local Search Transportation Science, August 1, 2008; 42(3): 279 - 291. [Abstract] [PDF]