- https://pubsonline.informs.org/doi/10.1287/trsc.2015.0655
Final published version

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

In: Transportation Science, Vol. 51, No. 1, 02.2017, p. 250-268.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Cacchiani, V & Salazar-Gonzalez, J-J 2017, 'Optimal solutions to a real-world integrated airline scheduling problem', *Transportation Science*, vol. 51, no. 1, pp. 250-268. https://doi.org/10.1287/trsc.2015.0655

Cacchiani, V., & Salazar-Gonzalez, J.-J. (2017). Optimal solutions to a real-world integrated airline scheduling problem. *Transportation Science*, *51*(1), 250-268. https://doi.org/10.1287/trsc.2015.0655

Cacchiani V, Salazar-Gonzalez JJ. Optimal solutions to a real-world integrated airline scheduling problem. Transportation Science. 2017 Feb;51(1):250-268. Epub 2016 Apr 11. doi: 10.1287/trsc.2015.0655

@article{d785466e476c4f77a9ad7aaab38ace41,

title = "Optimal solutions to a real-world integrated airline scheduling problem",

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 path-path model, can be considered as the “natural model” in which both the crew pairings and the aircraft routes are represented by path-based variables. The other formulation, called the arc-path model, is a novel model in which the aircraft routes are represented by arc-based variables and the crew pairings by path-based variables. We propose two exact methods (called path-path method and arc-path 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 path-based 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 real-world instances of a regional carrier with up to 172 flights and three fleet operators. The results show that the arc-path method outperforms the path-path 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.",

keywords = "integrated airline scheduling, exact algorithm, column generation",

author = "Valentina Cacchiani and Juan-Jose Salazar-Gonzalez",

year = "2017",

month = feb,

doi = "10.1287/trsc.2015.0655",

language = "English",

volume = "51",

pages = "250--268",

journal = "Transportation Science",

issn = "0041-1655",

publisher = "INFORMS",

number = "1",

}

TY - JOUR

T1 - Optimal solutions to a real-world integrated airline scheduling problem

AU - Cacchiani, Valentina

AU - Salazar-Gonzalez, Juan-Jose

PY - 2017/2

Y1 - 2017/2

N2 - 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 path-path model, can be considered as the “natural model” in which both the crew pairings and the aircraft routes are represented by path-based variables. The other formulation, called the arc-path model, is a novel model in which the aircraft routes are represented by arc-based variables and the crew pairings by path-based variables. We propose two exact methods (called path-path method and arc-path 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 path-based 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 real-world instances of a regional carrier with up to 172 flights and three fleet operators. The results show that the arc-path method outperforms the path-path 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.

AB - 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 path-path model, can be considered as the “natural model” in which both the crew pairings and the aircraft routes are represented by path-based variables. The other formulation, called the arc-path model, is a novel model in which the aircraft routes are represented by arc-based variables and the crew pairings by path-based variables. We propose two exact methods (called path-path method and arc-path 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 path-based 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 real-world instances of a regional carrier with up to 172 flights and three fleet operators. The results show that the arc-path method outperforms the path-path 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.

KW - integrated airline scheduling

KW - exact algorithm

KW - column generation

U2 - 10.1287/trsc.2015.0655

DO - 10.1287/trsc.2015.0655

M3 - Journal article

VL - 51

SP - 250

EP - 268

JO - Transportation Science

JF - Transportation Science

SN - 0041-1655

IS - 1

ER -