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 II: Parallel Local Search

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 Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
H. Milton Stewart 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 aircrafts suggests a new air transportation business: dial-a-flight, an on-demand service in which travelers call a few days in advance to schedule transportation. 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. In Part I, we introduced an integer multicommodity network flow model with side constraints for the dial-a-flight problem and showed that small instances can be solved effectively. Here, we demonstrate that high-quality solutions for large-scale real-life instances can be produced efficiently by embedding the core optimization technology in a local search scheme. To achieve the desired level of performance, metrics were devised to select neighborhoods intelligently, a variety of search diversification techniques were included, and an asynchronous parallel implementation was developed.

Key Words: air transportation; on-demand service; parallel local search
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 I: Problem Description and an Integer Multicommodity Flow Model Transportation Science, August 1, 2008; 42(3): 263 - 278. [Abstract] [PDF]