We study an integrated airline scheduling problem for a regional carrier. It integrates three stages of the planning process (i.e., fleet assignment, aircraft routing, and crew pairing) that are typically solved in sequence. Aircraft maintenance is also taken into account. The objective function aims at minimizing a weighted sum of the number of aircraft routes, the number of crew pairings, and the waiting times of crews between consecutive flights. In addition, it aims at maximizing the robustness of the solution by also minimizing the number of times that crews need to change aircraft. We present two mixed integer linear programming models for the integrated problem. The first formulation, called the pathpath model, can be considered as the natural model in which both the crew pairings and the aircraft routes are represented by pathbased variables. The other formulation, called the arcpath model, is a novel model in which the aircraft routes are represented by arcbased variables and the crew pairings by pathbased variables.We propose two exact methods (called pathpath method and arcpath method) for solving the integrated problem, each one based on one of the proposed models. Both methods consist of three phases. In the first phase, the linear programming relaxation of the corresponding model is solved to optimality by column generation on the pathbased variables, thus providing a lower bound. The second phase computes a heuristic solution (upper bound) by using only the variables generated in the first phase. The third phase makes use of the lower and upper bounds (obtained in the previous phases) to compute an optimal solution.We propose a bounding cut based on computing a lower bound on the number of aircraft changes that are needed in a feasible solution, and empirically show that this cut significantly speeds up the exact methods. The proposed methods are tested on realworld instances of a regional carrier with up to 172 flights and three fleet operators. The results show that the arcpath method outperforms the pathpath method as well as a heuristic approach from the literature, and derives the optimal solutions for all of the considered instances in at most two hours of computing time.
Cacchiani, V., SalazarGonzález, J. (2017). Optimal solutions to a realworld integrated airline scheduling problem. TRANSPORTATION SCIENCE, 51(1), 250268 [10.1287/trsc.2015.0655].
Optimal solutions to a realworld integrated airline scheduling problem
CACCHIANI, VALENTINA^{};SALAZAR GONZALEZ, JUAN JOSE'
2017
Abstract
We study an integrated airline scheduling problem for a regional carrier. It integrates three stages of the planning process (i.e., fleet assignment, aircraft routing, and crew pairing) that are typically solved in sequence. Aircraft maintenance is also taken into account. The objective function aims at minimizing a weighted sum of the number of aircraft routes, the number of crew pairings, and the waiting times of crews between consecutive flights. In addition, it aims at maximizing the robustness of the solution by also minimizing the number of times that crews need to change aircraft. We present two mixed integer linear programming models for the integrated problem. The first formulation, called the pathpath model, can be considered as the natural model in which both the crew pairings and the aircraft routes are represented by pathbased variables. The other formulation, called the arcpath model, is a novel model in which the aircraft routes are represented by arcbased variables and the crew pairings by pathbased variables.We propose two exact methods (called pathpath method and arcpath method) for solving the integrated problem, each one based on one of the proposed models. Both methods consist of three phases. In the first phase, the linear programming relaxation of the corresponding model is solved to optimality by column generation on the pathbased variables, thus providing a lower bound. The second phase computes a heuristic solution (upper bound) by using only the variables generated in the first phase. The third phase makes use of the lower and upper bounds (obtained in the previous phases) to compute an optimal solution.We propose a bounding cut based on computing a lower bound on the number of aircraft changes that are needed in a feasible solution, and empirically show that this cut significantly speeds up the exact methods. The proposed methods are tested on realworld instances of a regional carrier with up to 172 flights and three fleet operators. The results show that the arcpath method outperforms the pathpath method as well as a heuristic approach from the literature, and derives the optimal solutions for all of the considered instances in at most two hours of computing time.File  Dimensione  Formato  

TSCI2017_postprint.pdf
accesso aperto
Tipo:
Postprint
Licenza:
Licenza per Accesso Aperto. Creative Commons Attribuzione  Non commerciale (CCBYNC)
Dimensione
496.72 kB
Formato
Adobe PDF

496.72 kB  Adobe PDF  Visualizza/Apri 
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.