Year
1999
Abstract
The Crew Pairing Problem in air transportation consists in assigning pilots, stewarts and hostesses to sequences of flights so that every flight of the company is covered by a crew, and the total sum of rest periods is minimized.This optimization problem can be modelled as a very large-scale integer 0-1 linear program. It can be solved by specialized techniques for set covering problems, called “column generation”. We define some classes of problems where the sub-problem associated with the greedy approach is solvable in polynomial time.
ALFANDARI, L. (1999). The Greedy Approach for the Crew Pairing Problem: Some Cases of Polynomial Subproblems. Cahiers du Lamsade (Laboratoire d’Analyse et de Modélisation de Systèmes d’Aide), pp. 1-10.