Column generation and the airline crew pairing problem

DOI10.4171/DMS/1-3/65MaRDI QIDQ1126867zbMATH OpenFDO

Authors Ranga Anbil, John J. H. Forrest, William R. Pulleyblank

Publication date 6 August 1998

Published in Documenta Mathematica (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/224537, http://www.emis.de/journals/DMJDMV/xvol-icm/17/Pulleyblank.MAN.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

airline planningapproximate solutionscrew pairing

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Case-oriented studies in operations research (90B90) Boolean programming (90C09) Integer programming (90C10)

Review text

Summary: The cost of flight crews is the second largest operating cost of an airline. Minimizing it is a fundamental problem in airline planning and operations, and one which has leant itself to mathematical optimization. We discuss several recent advances in the methods used to solve these problems. After describing the general approach taken, we discuss a new method which can be used to obtain approximate solutions to linear programs, dramatically improving the solution time of these problems. This is the so-called volume algorithm. We also describe several other ideas used to make it routinely possible to get very good solutions to these large mixed integer programs.

Recommendations

• A new approach for crew pairing problems by column generation with an application to air transportation
• A column generation approach to airline crew scheduling
• The Column Generation Principle And The Airline Crew Scheduling Problem
• Solving large airline crew scheduling problems: Random pairing generation and strong branching
• scientific article; zbMATH DE number 1294631

Cited in

(17)

• A new heuristic branching scheme for the crew pairing problem with base constraints
• Dynamic constraint aggregation for solving very large-scale airline crew pairing problems
• Dantzig-Wolfe decomposition and branch-and-price solving in G12
• An effective deflected subgradient optimization scheme for implementing column generation for large-scale airline crew scheduling problems
• scientific article; zbMATH DE number 1294631 (Why is no real title available?)
• Column-Generation in Integer Linear Programming
• scientific article; zbMATH DE number 2153000 (Why is no real title available?)
• scientific article; zbMATH DE number 2159151 (Why is no real title available?)
• The Column Generation Principle And The Airline Crew Scheduling Problem
• From High-Level Model to Branch-and-Price Solution in G12
• Combined bus and driver scheduling
• Solving a real-world multi-depot multi-period petrol replenishment problem with complex loading constraints
• A comparison of stochastic programming and bi-objective optimisation approaches to robust airline crew scheduling
• Integrated commercial and operations planning model for schedule design, aircraft rotation and crew scheduling in airlines
• Dual variable based fathoming in dynamic programs for column generation
• Airline crew scheduling: state-of-the-art
• BoxStep methods for crew pairing problems

This page was built for publication: Column generation and the airline crew pairing problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1126867)