Per-seat, on-demand air transportation Part II: Parallel local search

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

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


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.

Original languageEnglish
Pages (from-to)279-291
Number of pages13
JournalTransportation Science
Issue number3
StatePublished - Aug 2008


  • Air transportation
  • On-demand service
  • Parallel local search


Dive into the research topics of 'Per-seat, on-demand air transportation Part II: Parallel local search'. Together they form a unique fingerprint.

Cite this