The problem of finding a work assignment for airline crew members in a given time horizon is addressed. In the literature this problem is usually referred to as the Airline Crew Rostering problem. It consists of constructing monthly schedules for crew members by assigning them pairings, rest periods, annual and sick leave, training periods, union activities, and so forth, so as to satisfy the collective agreements and security rules. We formulate the Airline Crew Rostering problem as a 0-1 Multicommodity Flow problem where each employee corresponds to a commodity; determining a monthly schedule for an employee is the same as computing a path on a suitably defined graph while still satisfying union conventions. A preprocessing phase is performed which reduces the dimension of the graph. To tighten the linear programming formulation of our model, we propose some families of valid inequalities that have proved to be computationally effective. Some of them can be treated implicitly when constructing the graph. Computational results obtained with a commercial integer programming solver (CPLEX) are analyzed. Keywords. Transportation, scheduling, personnel: crew rostering and Programming, integer, cutting plane/facet: valid inequalities.

A MULTI-COMMODITY FLOW APPROACH TO THE CREW ROSTERING PROBLEM / P. CAPPANERA; G. GALLO. - In: OPERATIONS RESEARCH. - ISSN 0030-364X. - ELETTRONICO. - 52:(2004), pp. 583-596. [10.1287/opre.1040.0110]

A MULTI-COMMODITY FLOW APPROACH TO THE CREW ROSTERING PROBLEM

CAPPANERA, PAOLA;
2004

Abstract

The problem of finding a work assignment for airline crew members in a given time horizon is addressed. In the literature this problem is usually referred to as the Airline Crew Rostering problem. It consists of constructing monthly schedules for crew members by assigning them pairings, rest periods, annual and sick leave, training periods, union activities, and so forth, so as to satisfy the collective agreements and security rules. We formulate the Airline Crew Rostering problem as a 0-1 Multicommodity Flow problem where each employee corresponds to a commodity; determining a monthly schedule for an employee is the same as computing a path on a suitably defined graph while still satisfying union conventions. A preprocessing phase is performed which reduces the dimension of the graph. To tighten the linear programming formulation of our model, we propose some families of valid inequalities that have proved to be computationally effective. Some of them can be treated implicitly when constructing the graph. Computational results obtained with a commercial integer programming solver (CPLEX) are analyzed. Keywords. Transportation, scheduling, personnel: crew rostering and Programming, integer, cutting plane/facet: valid inequalities.
2004
52
583
596
P. CAPPANERA; G. GALLO
File in questo prodotto:
File Dimensione Formato  
OR-ACR.pdf

Accesso chiuso

Tipologia: Altro
Licenza: Tutti i diritti riservati
Dimensione 176.58 kB
Formato Adobe PDF
176.58 kB Adobe PDF   Richiedi una copia

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1805
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 56
  • ???jsp.display-item.citation.isi??? 47
social impact