A hybrid scatter search heuristic for personalized crew rostering in the airline industry

The crew scheduling problem in the airline industry is extensively investigated in the operations research literature since efficient crew employment can drastically reduce operational costs of airline companies. Given the flight schedule of an airline company, crew scheduling is the process of assigning all necessary crew members in such a way that the airline is able to operate all its flights and constructing a roster line for each employee minimizing the corresponding overall cost for personnel. In this paper, we present a scatter search algorithm for the airline crew rostering problem. The objective is to assign a personalized roster to each crew member minimizing the overall operational costs while ensuring the social quality of the schedule. We combine different complementary meta-heuristic crew scheduling combination and improvement principles. Detailed computational experiments in a real-life problem environment are presented investigating all characteristics of the procedure. Moreover, we compare the proposed scatter search algorithm with optimal solutions obtained by an exact branch-and-price procedure and a steepest descent variable neighbourhood search.     

Airline Crew Scheduling: State-of-the-Art

The airline industry is faced with some of the largest scheduling problems of any industry. The crew scheduling problem involves the optimal allocation of crews to flights. Over the last two decades the magnitude and complexity of crew scheduling problems have grown enormously and airlines are relying more on automated mathematical procedures as a practical necessity. In this paper we survey different approaches studied and discuss the state-of-the-art in solution methodology for the airline crew scheduling problem. We conclude with a discussion about promising areas for further work to make it possible to get very good solutions for the crew scheduling problem.     

Crew pairing at Air France

In the airline industry, crew schedules consist of a number of pairings. These are round trips originating and terminating at the same crew home base composed of legal work days, called duties, separated by rest periods. The purpose of the airline crew pairing problem is to generate a set of minimal cost crew pairings covering all flight legs. The set of pairings must satisfy all the rules in the work convention and all the appropriate air traffic regulations. The resulting constraints can affect duty construction, may restrict each pairing, or be imposed on the overall crew schedule.The pairing problem is formulated as an integer, nonlinear multi-commodity network flow problem with additional resource variables. Nonlinearities occur in the objective function as well as in a large subset of constraints. A branch-and-bound algorithm based on an extension of the Dantzig-Wolfe decomposition principle is used to solve this model. The master problem becomes a Set Partitioning type model, as in the classical formulation, while pairings are generated using resource constrained shortest path subproblems. This primal approach implicitly considers all feasible pairings and also provides the optimality gap value on a feasible solution. A nice feature of this decomposition process is that it isolates all nonlinear aspects of the proposed multi-commodity model in the subproblems which are solved by means of a specialized dynamic programming algorithm.We present the application and implementation of this approach at Air France. It is one of the first implementations of an optimal approach for a large airline carrier. We have chosen a subproblem network representation where the duties rather than the legs are on the arcs. This ensures feasibility relative to duty restrictions by definition. As opposed to Lavoie, Minoux and Odier (1988), the nonlinear cost function is modeled without approximations. The computational experiments were conducted using actual Air France medium haul data. Even if the branch-and-bound trees were not fully explored in all cases, the gaps certify that the computed solutions are within a fraction of one percentage point of the optimality. Our results illustrate that our approach produced substantial improvements over solutions derived by the expert system in use at Air France. Their magnitude led to the eventual implementation of the approach.     

A Decision Support System for Crew Planning in Passenger Transportation Using a Flexible Branch-and-Price Algorithm

This paper discusses a decision support system for airline and railway crew planning. The system is a state-of-the-art branch-and-price solver that is used for crew scheduling and crew rostering. Since it is far from trivial to build such a system from the information provided in the existing literature, technical issues about the system and its implementation are covered in more detail. We also discuss several applications. In particular, we focus on a specific aircrew rostering application. The computational results contain an interesting comparison of results obtained with the approach in which crew scheduling is carried out before crew rostering, and an approach in which these two planning problems are solved in an integrated manner.     

How Airlines and Airports Recover from Schedule Perturbations: A Survey

The explosive growth in air traffic as well as the widespread adoption of Operations Research techniques in airline scheduling has given rise to tight flight schedules at major airports. An undesirable consequence of this is that a minor incident such as a delay in the arrival of a small number of flights can result in a chain reaction of events involving several flights and airports, causing disruption throughout the system. This paper reviews recent literature in the area of recovery from schedule disruptions. First we review how disturbances at a given airport could be handled, including the effects of runways and fixes. Then we study the papers on recovery from airline schedule perturbations, which involve adjustments in flight schedules, aircraft, and crew. The mathematical programming techniques used in ground holding are covered in some detail. We conclude the review with suggestions on how singular perturbation theory could play a role in analyzing disruptions to such highly sensitive schedules as those in the civil aviation industry.     

Genetic algorithm based approach for the integrated airline crew-pairing and rostering problem

Airline crew scheduling problem is a complex and difficult problem faced by all airline companies.To tackle this problem, it was often decomposed into two subproblems solved successively. First, the airline crew-pairing problem, which consists on finding a set of trips – called pairings – i.e. sequences of flights, starting and ending at a crew base, that cover all the flights planned for a given period of time. Secondly, the airline crew rostering problem, which consists on assigning the pairings found by solving the first subproblem, to the named airline crew members. For both problems, several rules and regulations must be respected and costs minimized.It is sure that this decomposition provides a convenient tool to handle the numerous and complex restrictions, but it lacks, however, of a global treatment of the problem. For this purpose, in this study we took the challenge of proposing a new way to solve both subproblems simultaneously. The proposed approach is based on a hybrid genetic algorithm. In fact, three heuristics are developed here to tackle the restriction rules within the GA’s process.     

A branch-and-price approach for operational aircraft maintenance routing

In recent years, considerable effort in the field of operations research has been paid to optimizing airline operations, including the logistics of an airline’s fleet of aircraft. We focus on the problem of aircraft routing, which involves generating and selecting a particular route for each aircraft of a sub-fleet that is already assigned to a set of feasible sequences of flight legs. Similar studies typically focus on long-term route planning. However, stochastic events such as severe weather changes, equipment failures, variable maintenance times, or even new regulations mandated by the Federal Aviation Administration (FAA) play havoc on these long-term plans. In addition, these long-term plans ignore detailed maintenance requirements by considering only one or two of the primary maintenance checks that must be performed on a regular, long-term basis. As a result, these plans are often ignored by personnel in airline operations who are forced on a daily basis to develop quick, ad hoc methods to address these maintenance requirements and other irregular events. To address this problem, we develop an operational aircraft maintenance routing problem formulation that includes maintenance resource availability constraints. We propose a branch-and-price algorithm for solving this problem, which, due to the resource constraints, entails a modification of the branch-on, follow-on branching rule typically used for solving similar problems. Through computational testing, we explore the efficiency of this solution approach under a combination of heuristic choices for column (route) generation and selection.     

Modeling and solving a Crew Assignment Problem in air transportation

A typical problem arising in airline crew management consists in optimally assigning the required crew members to each flight segment of a given time period, while complying with a variety of work regulations and collective agreements. This problem called the Crew Assignment Problem (CAP) is currently decomposed into two independent sub-problems which are modeled and solved sequentially: (a) the well-known Crew Pairing Problem followed by (b) the Working Schedules Construction Problem. In the first sub-problem, a set of legal minimum-cost pairings is constructed, covering all the planned flight segments. In the second sub-problem, pairings, rest periods, training periods, annual leaves, etc. are combined to form working schedules which are then assigned to crew members.In this paper, we present a new approach to the Crew Assignment Problem arising in the context of airline companies operating short and medium haul flights. Contrary to most previously published work on the subject, our approach is not based on the concept of crew-pairings, though it is capable of handling many of the constraints present in crew-pairing-based models. Moreover, contrary to crew-pairing-based approaches, one of its distinctive features is that it formulates and solves the two sub-problems (a) and (b) simultaneously for the technical crew members (pilots and officers) with specific constraints. We show how this problem can be formulated as a large scale integer linear program with a general structure combining different types of constraints and not exclusively partitioning or covering constraints as usually suggested in previous papers. We introduce then, a formulation enhancement phase where we replace a large number of binary exclusion constraints by stronger and less numerous ones: the clique constraints. Using data provided by the Tunisian airline company TunisAir, we demonstrate that thanks to this new formulation, the Crew Assignment Problem can be solved by currently available integer linear programming technology. Finally, we propose an efficient heuristic method based on a rounding strategy embedded in a partial tree search procedure.The implementation of these methods (both exact and heuristic ones) provides good solutions in reasonable computation times using CPLEX 6.0.2: guaranteed exact solutions are obtained for 60% of the test instances and solutions within 5% of the lower bound for the others.     

Genetic algorithms for the bus driver scheduling problem: a case study

This paper describes an application of genetic algorithms to the bus driver scheduling problem. The application of genetic algorithms extends the traditional approach of Set Covering/Set Partitioning formulations, allowing the simultaneous consideration of several complex criteria. The genetic algorithm is integrated in a DSS but can be used as a very interactive tool or a stand-alone application. It incorporates the user's knowledge in a quite natural way and produces solutions that are almost directly implemented by the transport companies in their operational planning processes. Computational results with airline and bus crew scheduling problems from real world companies are presented and discussed.     

Modeling and Solving an Airline Schedule Generation Problem

Since opening a new flight connection or closing an existing flight has a great impact on the revenues of an airline, the generation of the flight schedule is one of the fundamental problems in airline planning processes.In this paper we concentrate on a special case of the problem which arises at charter companies. In contrast to airlines operating on regular schedules, the market for charter airlines is well-known and the schedule is allowed to change completely from period to period. Thus, precise adjustments to the demands of the market have a great potential for minimizing operating costs.We present a capacitated network design model and propose a combined branch-and-cut approach to solve this airline schedule generation problem. To tighten the linear relaxation bound, we add cutting planes which adjust the number of aircraft and the spill of passengers to the demand on each itinerary.For real-world problems from a large European charter airline we obtain solutions within a very few percent of optimality with running times in the order of minutes on a customary personal computer for most of the data sets.     

A network model for airline cabin crew scheduling

Airline crew scheduling problems have been traditionally formulated as set covering problems or set partitioning problems. When flight networks are extended, these problems become more complicated and thus more difficult to solve. From the current practices of a Taiwan airline, whose work rules are relatively simple compared to many airlines in other countries, we find that pure network models, in addition to traditional set covering (partitioning) problems, can be used to formulate their crew scheduling problems. In this paper, we introduce a pure network model that can both efficiently and effectively solve crew scheduling problems for a Taiwan airline using real constraints. To evaluate the model, we perform computational tests concerning the international line operations of a Taiwan airline.     

Solving Large Airline Crew Scheduling Problems: Random Pairing Generation and Strong Branching

The airline crew scheduling problem is the problem of assigning crew itineraries to flights. We develop a new approach for solving the problem that is based on enumerating hundreds of millions random pairings. The linear programming relaxation is solved first and then millions of columns with best reduced cost are selected for the integer program. The number of columns is further reduced by a linear programming based heuristic. Finally an integer solution is obtained with a commercial integer programming solver. The branching rule of the solver is enhanced with a combination of strong branching and a specialized branching rule. The algorithm produces solutions that are significantly better than ones found by current practice.     

A genetic local search algorithm with a threshold accepting mechanism for solving the runway dependent aircraft landing problem

As the demand for air transportation continues to grow, some flights cannot land at their preferred landing times because the airport is near its runway capacity. Extra fuel consumption and air pollution are then caused by the landing delays. Moreover, such delays may possibly yield extra costs for both passengers and airline companies that result from rescheduling transfer passengers and crew members. Consequently, how to increase the handling efficiency of congested airports is a crucial management issue. Building new runways at existing airports is often not feasible due to environmental, financial and geographical constraints. Therefore, devising a method for tackling the aircraft landing problem (ALP) in order to optimize the usage of existing runways at airports is the focus of this paper. This paper aims to develop a solution procedure based on a genetic local search (GLS) algorithm for solving the ALP with runway dependent attributes. A set of numerical experiments were conducted to test the validity of the proposed algorithm based on five test instances created and investigated by previous studies. The numerical results showed that the proposed GLS algorithm can effectively and efficiently determine the runway allocation, sequence and landing time for arriving aircraft for the five test cases by minimizing total delays under the separation constraints in comparison with the outcomes yielded by previous studies.     

A model for designing the meteorologically most reliable airline schedule

Due to meteorological conditions certain airports in some regions have to be frequently closed during winter months. An immediate consequence is an increase in the number of cancelled flights, which is a disruption of airline schedules on the overall transportation network. In this paper a research concerning the reliability of airline scheduling as related to meteorological conditions is conducted and an indicator for quantifying the adaptability of airline schedules to meteorological conditions is proposed. A heuristic algorithm for minimizing the number of needed aircraft for given traffic volume is also presented. In case where more than one solution with the same number of engaged aircraft is possible the solution chosen is the one with the minimum number of passengers whose flights are expected to be cancelled on account of meteorological conditions. The proposed algorithm is illustrated by an appropriate numerical example.     

Bregman Proximal Relaxation of Large-Scale 0–1 Problems

We apply a recent extension of the Bregman proximal method for convex programming to LP relaxations of 0–1 problems. We allow inexact subproblem solutions obtained via dual ascent, increasing their accuracy successively to retain global convergence. Our framework is applied to relaxations of large-scale set covering problems that arise in airline crew scheduling. Approximate relaxed solutions are used to construct primal feasible solutions via a randomized heuristic. Encouraging preliminary experience is reported.     

A discussion of scalarization techniques for multiple objective integer programming

In this paper we consider solution methods for multiobjective integer programming (MOIP) problems based on scalarization. We define the MOIP, discuss some common scalarizations, and provide a general formulation that encompasses most scalarizations that have been applied in the MOIP context as special cases. We show that these methods suffer some drawbacks by either only being able to find supported efficient solutions or introducing constraints that can make the computational effort to solve the scalarization prohibitive. We show that Lagrangian duality applied to the general scalarization does not remedy the situation. We also introduce a new scalarization technique, the method of elastic constraints, which is shown to be able to find all efficient solutions and overcome the computational burden of the scalarizations that use constraints on objective values. Finally, we present some results from an application in airline crew scheduling as evidence. This research is partially supported by University of Auckland grant 3602178/9275 and by the Deutsche Forschungsgemeinschaft grant Ka 477/27-1.     

A partially integrated airline crew scheduling approach with time-dependent crew capacities and multiple home bases

Crew scheduling for airlines requires an optimally scheduled coverage of flights with regard to given timetables. We consider the crew scheduling and assignment process for airlines, where crew members are stationed unevenly among home bases. In addition, their availability changes dynamically during the planning period due to pre-scheduled activities, such as office and simulator duties, vacancy, or requested off-duty days.We propose a partially integrated approach based on two tightly coupled components: the first constructs chains of crew pairings spaced by weekly rests, where crew capacities at different domiciles and time-dependent availabilities are considered. The second component rearranges parts of these pairing chains into individual crew schedules with, e.g., even distribution of flight time. Computational results with real-life data from an European airline are presented.     

The daily tail assignment problem under operational uncertainty using look-ahead maintenance constraints

The tail assignment problem is a critical part of the airline planning process that assigns specific aircraft to sequences of flights, called lines-of-flight, to satisfy operational constraints. The aim of this paper is to develop an operationally flexible method, based upon the one-day routes business model, to compute tail assignments that satisfy short-range—within the next three days—aircraft maintenance requirements. While maintenance plans commonly span multiple days, the methods used to compute tail assignments for the given plans can be overly complex and provide little recourse in the event of schedule perturbations. The presented approach addresses operational uncertainty by using solutions from the one-day routes aircraft maintenance routing approach as input. The daily tail assignment problem is solved with an objective to satisfy maintenance requirements explicitly for the current day and implicitly for the subsequent two days. A computational study will be performed to assess the performance of exact and heuristic solution algorithms that modify the input lines-of-flight to reduce maintenance misalignments. The daily tail assignment problem and the developed algorithms are demonstrated to compute solutions that effectively satisfy maintenance requirements when evaluated using input data collected from three different airlines.     

Constraint Programming Based Column Generation for Crew Assignment

Airline crew assignment problems are large-scale optimization problems which can be adequately solved by column generation. The subproblem is typically a so-called constrained shortest path problem and solved by dynamic programming. However, complex airline regulations arising frequently in European airlines cannot be expressed entirely in this framework and limit the use of pure column generation. In this paper, we formulate the subproblem as a constraint satisfaction problem, thus gaining high expressiveness. Each airline regulation is encoded by one or several constraints. An additional constraint which encapsulates a shortest path algorithm for generating columns with negative reduced costs is introduced. This constraint reduces the search space of the subproblem significantly. Resulting domain reductions are propagated to the other constraints which additionally reduces the search space. Numerical results based on data of a large European airline are presented and demonstrate the potential of our approach.