A new pricing scheme for airline crew scheduling

Alexandra Makri*, Diego Klabjan

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

18 Scopus citations

Abstract

Solving LP relaxations of airline crew scheduling models is computationally challenging due to the presence of a large number of variables, complex feasibility rules to generate columns, and nonlinear cost. We perform computational experiments with a nonlinear pricing strategy. We develop a column generation scheme that uses several pruning rules to fathom column enumeration. The pruning rules are categorized into approximate and exact, where the approximate rules might prune columns that would yield an improved objective value. The pruning rules use the fact that columns are paths in a network, and we use shortest path algorithms and their extensions to obtain bounds.

Original languageEnglish (US)
Pages (from-to)56-67
Number of pages12
JournalINFORMS Journal on Computing
Volume16
Issue number1
DOIs
StatePublished - Dec 1 2004

Keywords

  • Programming, linear
  • Scheduling
  • Transportation

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'A new pricing scheme for airline crew scheduling'. Together they form a unique fingerprint.

Cite this