Abstract:

The bidline scheduling problem with equity arises in several North American airlines. It consists of determining anonymous monthly schedules, called bidlines, that will be subsequently assigned to the crew members according to their bids and seniority. These bidlines must satisfy safety and collective agreement rules. Furthermore, to ensure an equity between the employees, each bidline should have as much as possible the same number of days off and the same number of credited (paid) hours. In this paper, we propose an approximate set partitioning type formulation for this problem and two heuristics for solving it. The first one is a standard branch-and-price heuristic that relies on a rounding procedure to derive integer solutions. The second one is obtained by combining this first heuristic with a dynamic constraint aggregation method that was recently proposed in the literature. Computational results show that, for the largest tested instances, the dynamic constraint aggregation heuristic can produce better quality solutions in a fraction of the computational time required by the standard branch-and-price heuristic.

Download the PDF to learn more

Abstract:

In this paper we consider the daily aircraft routing and scheduling problem (DARSP). It consists of determining daily schedules which maximize the anticipated profits derived from the aircraft of a heterogeneous fleet. This fleet must cover a set of operational flight legs with known departure time windows, durations and profits according to the aircraft type. We present two models for this problem: a Set Partitioning type formulation and a time constrained multi-commodity network flow formulation. We describe the network structure of the subproblem when a column generation technique is applied to solve the linear relaxation of the first model and when a Dantzig-Wolfe decomposition approach is used to solve the linear relaxation of the second model. The linear relaxation of the first model provides lower bounds. Integer solutions to the overall problem are derived through branch-and-bound. By exploiting the equivalence between the two formulations, we propose various optimal branching strategies compatible with the column generation technique. Finally we report computational results obtained on data provided by two different airlines. These results show that significant profit improvement can be generated by solving the DARSP using our approach and that this can be obtained in a reasonable amount of CPU time.

Download the PDF to learn more

Abstract:

This paper describes the Preferential Bidding Problem solved in the airline industry to construct personalized monthly schedules for pilots and officers. This problem consists in assigning to crew members pairings, days off, annual leaves, training periods, etc., while considering a set of weighted bids that reflect individual preferences. This assignment must be done under strict seniority restrictions: the construction of a maximum-score schedule for a particular crew member must never be done at the expense of a more senior employee. This R&D project has resulted in the PREFERENTIAL BIDDING SYSTEM which has been used at Air Canada since May 1995.

The solution process is summarized as follows. For each employee, from the most senior to the most junior, a so-called residual problem is solved: given an employee and a set of unassigned pairings, the solution to an integer linear program determines the employee’s maximum-score schedule while taking into account all the remaining employees. The residual problem is solved by column generation embedded in a branch&bound tree. Integer solutions are obtained by using very efficient cutting planes, without which it would have been impossible to solve some of these residual problems.

Keywords: Airline, crew scheduling, preferential bidding, integer linear programming, column generation, cutting planes.

Download the PDF to learn more

Abstract:

Given a set of flight legs to be flown by a single type of aircraft, the simultaneous aircraft routing and crew scheduling problem consists of determining a minimum-cost set of aircraft routes and crew pairings such that each flight leg is covered by one aircraft and one crew, and side constraints are satisfied. While some side constraints such as maximum flight time and maintenance requirements involve only crews or aircraft, linking constraints impose minimum connection times for crews that depend on aircraft connections. To handle these linking constraints, a solution approach based on Benders decomposition is proposed. The solution process iterates between a master problem which solves the aircraft routing problem, and a subproblem which solves the crew pairing problem. Because of their particular structure, both of these problems are themselves decomposed and solved by column generation. A heuristic branch-and-bound method is used to compute integer solutions. On a set of test instances based on data provided by an airline, the integrated approach produced significant cost savings in comparison with the sequential planning process commonly used in practice. The largest instance solved contains more than 500 flight legs over a three-day period.

Keywords: air transportation; integer programming; multi-commodity network flow; Benders decomposition; Dantzig-Wolfe decomposition; column generation.

Download the PDF to learn more