MA11 - Air Transportation

In this talk, we address the Aircraft Maintenance Routing Problem, which consists of constructing routes for a heterogeneous fleet of aircraft to cover a predefined set of flights over a given planning horizon (e.g., two weeks). The routes must satisfy maintenance requirements on flying hours, number of landings, and elapsed days since the last maintenance, respect maintenance station capacity constraints, and minimize the sum of operational costs and maintenance-related penalties. These penalties account for scheduling maintenance either too early, leading to under-utilization of aircraft, or too late, increasing the risk of operational disruptions. To solve this problem, we propose a column generation–based heuristic that relies on shortest-path subproblems with resource constraints, solved using a labeling algorithm that explicitly incorporates two-sided penalties for deviations from predefined maintenance targets. In addition,  a network-reduction heuristic is applied to the pricing subproblems to reduce the computational time. Computational results on real-world instances will be presented.

Minor disruptions such as flight cancellations can quickly render crew pairings infeasible. We propose a real-time re-optimization framework combining local repair mechanisms, a space–time network to generate feasible rotations, and a mixed-integer programming model to select a consistent global solution. Experiments show rapid recovery with limited modifications to the original plan.

This work introduces the Team Crew Pairing Problem (TCPP), a team-based extension of the classical airline crew pairing problem. In the proposed setting, decision-making is performed not only on pairings, but also on crew slices, where a crew slice is a fixed subset of crew members that remains together throughout its assigned pairings. Each flight is associated with a crew composition requirement, and its coverage may involve exactly one main crew slice and a limited number of complementary crew slices.
A mathematical optimization model is proposed to jointly determine the pairings assigned to crew slices, the assignment of main and complementary crew slices on each flight, and the downranking choices. The objective is to balance operational efficiency and flexibility while preserving a coherent team structure. To solve the problem, we develop a branch-and-price approach in which pairing columns are generated through pricing subproblems formulated as shortest path problems with resource constraints on duty-based time-space networks built over pre-generated feasible duties.
Preliminary computational results will be presented to illustrate the proposed approach's behaviour and potential.

We address an integrated crew pairing and personalized scheduling problem for airline pilots over a monthly horizon. Unlike sequential approaches that first generate anonymous pairings and then assign them to crew members, our method constructs personalized rosters directly from a duty-based network, explicitly incorporating pilot preferences including flight attractiveness scores and requested days off. We formulate the problem as a set-partitioning model solved via column generation. The pricing subproblem is a shortest path problem with resource constraints on a time-space network, tracking pairing-level constraints (duties per pairing, time away from base) and roster-level constraints (monthly block hours, consecutive working days, minimum days off). The network handles vacation periods, penalizes short connections and rests for robustness, and rewards granted day-off requests. Integer solutions are obtained through a diving heuristic combining variable fixing and flight-to-pilot assignment branching.