Per-seat, on-demand air transportation Part I: problem description and an integer multicommodity flow model

D. Espinoza, R. Garcia, M. Goycoolea, G. L. Nemhauser, M. W.P. Savelsbergh

Research output: Contribution to journalArticlepeer-review

31 Scopus citations

Abstract

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, largeneighborhood, local search scheme to produce high-quality solutions efficiently for large-scale real-life instances.

Original languageEnglish
Pages (from-to)263-278
Number of pages16
JournalTransportation Science
Volume42
Issue number3
DOIs
StatePublished - Aug 2008

Keywords

  • Air transportation
  • Integer multicommodity flow
  • On-demand service

Fingerprint

Dive into the research topics of 'Per-seat, on-demand air transportation Part I: problem description and an integer multicommodity flow model'. Together they form a unique fingerprint.

Cite this