# Dynamic Model for Scheduling Crew Shifts

Authors: Vojtech Graf; Dusan Teichmann; Jiri Horinka; Michal Dorda
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

In regular as well as nonscheduled air transport, extraordinary situations occasionally occur, which may fundamentally disrupt the flight schedule. Fundamental disruptions of flight schedules affect not only passengers but also the airline. One of the areas that are negatively affected by the disruption is the crew plan. Due to extraordinary events, it happens that a flight is delayed, and the crew will not be at the destination airport at the prescribed time and the airline will not be able to assign it on further flights according to the original plan. Such situations can be resolved either by deploying any other available crew or by delaying the flight appropriately until the previously planned crew is available. Assigning a new crew entails additional costs for the airline, as it has to assign more flight staff than had been originally planned. Furthermore, delayed flights lead to paying passengers financial compensation, incurring additional costs for airlines. Therefore, it is important that the airline is able to resolve any irregularity situations so that the additional costs incurred to deal with the irregularity situations are kept at a minimum. The paper presents one possible approach, a mathematical model that can be used to solve such a situation. The presented mathematical model may be the basis for the decision support system of the operations center worker who is responsible for the operational management of flight crews. The model will primarily aim at smaller airlines that cannot afford expensive software and often rely on manual solutions. However, a manual solution may not always be the best, as the operator, who plans the processes, may not consider all the constraints. Another important factor that makes the decision processes more difficult is that it is usually necessary to decide in a short period of time. The solution proposed in this paper will allow the operator to make a quick decision that will also be the most advantageous for the airline. This is because the proposed method is an exact approach, which guarantees finding the optimum solution. In this article, we are only dealing with pilot crews.


---

## Body

## 1. Aim and Motivation

The airline usually creates flight schedules with a validity of six months.The actual process of creating a timetable for airlines consists of several substeps, each of which can be partially described as a separate planning problem. The individual steps are connected so that the outputs from one step are input data for the next step.As a first step, the airline must establish a portfolio of destinations to which it wishes to conduct flights. Unless it is a brand new airline, the existing portfolio of destinations is largely taken over from the past. Where appropriate, the existing portfolio is complemented by destinations that the airline intends to include in the coming season or vice versa; flights to certain destinations may be restricted or even stopped by the airline.If an airline has a flight plan in place, it is necessary to make a schedule. Departure and arrival times must be specified for each flight. The airline is primarily interested in setting departure and arrival times so that they meet the requirements of the target group of its potential customers as much as possible. However, the departure and arrival times can be considerably limited by the slot policy at the airport, as the slots in which the airline would like to operate the flights may not always be available.After planning the flights and allocating departure and arrival times, there is a third phase of planning, the allocation of aircraft that will man the flights. When assigning aircraft, it is necessary to pay particular attention to the technical and performance parameters of the aircraft type. In addition to basic technical parameters such as range or runway lengths at airports, aircraft equipment must also be monitored. For some flights (flights over large uninhabited areas such as the sea or deserts), the aircraft needs special equipment.Planning of flight crews takes place during an already implemented flight schedule and is created at monthly intervals. In the following text, flight crew will mean a pair of pilots. The flight crew planning process can be divided into 3 steps. In the first step, it is necessary to create viable pairs of pilots who can form a flight crew. The crews created and the number of aircraft assigned to the flights are the input information for the following steps in which individual crews are assigned to aircraft making scheduled flights to selected destinations and short- and long-term service plans are created.However, even the best planned flight schedule and pilot roster will not guarantee that there will be no irregularity during operation which may significantly affect the plan. The causes of disruption to regular operations can vary:(i)
Adverse weather conditions at the start, during flying, or at destination airport(ii)
Volcanic activity(iii)
Occurrence of technical defect on the aircraft and its subsequent repair(iv)
Lack of fuel(v)
Delays due to other circumstances of take-off or landing at the airport (heavy traffic, technical problems of other aircraft, crisis situation of another aircraft, etc.)(vi)
Safety or health problems for passengers on board(vii)
Medical complications of one or more of the crew members(viii)
Redirection of flight by air traffic control(ix)
Complete closure of airspace for all air traffic(x)
Complete closure of airspace for a particular airplane type(xi)
Strikes of employees of airports, airlines, or other companies involved in the implementation of individual flightsThese causes may result in delay, diversion to another airport, or even cancellation of one or more flights.In order to minimize the impact of emergencies on corporate operations, airlines establish operational management units. These departments ensure that the negative effects of irregularity operations have the smallest possible impact on the planned operation and thus on the company’s management. In essence, there are two procedures for resolution, recreating aircraft routes and crew schedules or increasing the robustness of the flight schedule. The subject of the article is the issue of rescheduling of crews.As mentioned above, in addition to generating time losses for passengers, the aforementioned emergencies may, in particular, cause significant financial costs for the airline itself. In addition to the cost of new crews and changes to the flight plan, each airline is obliged to take care of passengers on its flights in case of any problems. In addition to refreshments provided to the extent proportional to the time of delay, accommodation, and transport from the airport to the accommodation and back, passengers are also entitled to financial compensation for the delay. Passengers’ entitlement to financial compensation for the delay is governed by Regulation (EC) No. 261/2004 of the European Parliament and of the Council [1], laying down common rules on compensation and assistance to air passengers in the event of denied boarding, cancellation, or long delay of flights. The level of this compensation depends on the length of the flight and the delay time; see Table 1.Table 1
Amount of financial compensation for passengers [1].
Flight length (km)Minimum delay time (h)Amount of compensation paid to the passenger (EUR)0;150022501500;350034003500;∞4600The proposed approach takes into account both the costs associated with the transfer of crews to the flights and the costs of financial compensation for passengers for the flight delays. These costs are the main cost items related to the occurrence of the flight delays. The proposed solution will greatly speed up and facilitate decision-making for the managers of the smaller airlines who would have to make a decision only on the basis of their judgment and experience. Because it is an exact approach, the result cannot only facilitate the solution process but also mainly provides the optimal solution, which may not always be achieved when making a decision without its support.


## 2. State of the Art

The issue of flight crew planning is addressed in a chapter of the book in [2], the authors of which generally describe the principles of crew planning and formulate various optimization problems related to it and deal with the basic methods used to solve them. The issue of crew schedule planning for normal operations is usually divided into two problems, namely, the issue of crew schedule planning (pairing) and the creation of long-term plans or rosters (rostering and assignment).Optimization procedures are a significant group of approaches to crew schedule planning; they can be applied also in other fields of air transport [3]. In order to create an optimization approach, an optimization criterion must first be defined. In order to achieve the most accurate results, some authors propose solving multiple planning problems at the same time, which provides better conditions for finding a global optimum; however, this often causes computational problems as complicated optimization problems are also difficult to compute and they can also cause a situation where a global optimum will not be found. Therefore, many authors approach the decision-making problems using different heuristic methods. However, these methods can often be inaccurate or time-consuming. Therefore, some methods are applied which speed up the calculation process and improve the quality of the solution [4]. However, the main disadvantage of the heuristic approaches is that, unlike the exact methods, they cannot guarantee finding an optimal solution. This fact was one of the motivations why we created the exact model.The authors of the article in [5] deal with the issue of rostering, taking into account all necessary restrictions resulting from air and other legislative restrictions. In addition to these basic constraints, the authors add constraints stemming from the needs of employees themselves and undertake a multicriterial task using heuristics in combination with genetic algorithms. The same issue is addressed in the articles [6, 7], where the authors use the column generation method.A similar approach was followed by the authors of the publication [8] who have presented two algorithms. One is a column generation algorithm and the other is a heuristic method based on the tree search method. Tests were first performed for each method separately. Subsequently, the authors combine both methods to achieve the best possible solution while eliminating the drawbacks and disadvantages of both methods. Tests were conducted based on real data of two airlines.An alternative approach is chosen by the authors of [9], where they build on their work presented in the publication [10]. The optimization criterion is the even distribution of working time among all pilots. The problem is divided into two phases. In the first phase, pilots are assigned work and rest days, creating a long-term roster schedule. The second phase of the problem is the control phase, which serves to identify the feasibility of the proposed plans created in the first part. Based on the outcome of the second phase, the rosters created in the first stage of the solution are eventually modified and the whole procedure is repeated until the created rosters are feasible.The combination of both of the abovementioned planning problems (allocation of work days and rest days and crew roster arrangements) is addressed in the article [11], where the authors approach these problems as one integrated problem. For problem solving, they have again utilized the column generation method.The integrated approach is also utilized by the authors of the article [12] who have applied it to conditions of operational planning. The model published in this article is designed to deal with unpredictable events. After the occurrence of an unpredictable event, a complete rescheduling and emergence of new crew schedules and new long-term plans are necessary.Some authors focus not only on integrated models for crew planning but also on integrated models that resolve crew schedules (pairing) and aircraft flight routes at the same time. The authors of the paper [13] address a problem that has the conditions of a homogeneous fleet and uses a combination of column generation and branch and bound algorithm. The same topic is also dealt with in the publication [14], where the problem is resolved using Benders decomposition and the column generation method. To improve the results, the authors made it possible to create time frames within which departure times of aircraft can be altered. The aim of the optimization was to minimize operating costs. It has been shown that allowing for even minor changes in departure times can have a significant cost reduction effect. Subsequently, the authors in the publication in [15] summarize all the knowledge they have gained in solving the problem with Benders decomposition. Unlike in the previous articles [13, 14], there is a more sophisticated model presented here with a new optimization criterion, which is the number of aircraft route passes and the number of crews. The goal of optimization is to minimize the values of both criteria. The authors of the article [16] applied the integrated model for crew pairing and flight routing under conditions of a big airline.In addition to preparing crews, a number of authors focus on developing optimization approaches applicable to situations where flight crew failures occur, or they present approaches to prevent such adverse situations. Accumulated passenger time loss [17] or the number of delayed flights [18] is chosen as optimization criterion. It often happens that the delays are divided into two categories: ground-based delays and in-flight delays (both delays are minimized during optimization).In the proposed approaches, two basic methods are considered for the dealing with emergencies and the elimination of resulting delays: either the operational rescheduling of crew schedules or increasing the robustness of the plans created. The authors of the publication [19] have created a model in which several variants related to aircraft route planning are considered. In the publication [20], the authors focus on operational crew rescheduling using the original heuristic method in order to minimize the cost of rescheduling. The advantage of their proposed algorithm is its flexibility.The authors of the publication [21] are the first to publish a mathematical model dealing with the issue of operative rescheduling of crews, namely, the problem of pairing in the conditions of a network air airline. The solution is used by a combination of the column generation method and the branch and bound algorithm. The authors of the publication in [22] model the disruption of the flight schedule by random phenomena and solve the problems of the crews’ schedule by combining Markov processes and the Monte Carlo method. In the publication [23], the authors present a decision support tool designed to optimize the assignment of crews to flights following an emergency. The algorithm is used in forming a solution with the smallest deviation from the original plan in order to restore as many flights as possible with minimal costs resulting from the situation. Operational planning in air transport has also been addressed in the publications [24–26].Another way to deal with an irregularity operation, to prevent it, is to increase the robustness of the model results. In the paper [27], the authors describe the basic principles leading to increased robustness. The first option is to prepare a larger number of reserve crews who will be ready to take up duty in the event of any problems that might disrupt the plan. For flights where there is a high risk of emergency, two crews may be assigned simultaneously. The second approach is the early exchange of crews, which can provide a safety margin in the event of a continuing flight risk of exceeding the permitted duty time. The authors of the article [28] deal with the problem of reserve crew planning as well. The authors try to predict calling up the pilots to the reserve crews so that it is not too late and at the same time they do not waste their valuable time by waiting in reserve. The issue of reserve crew planning is further addressed in the publications [29–31].In approaches based on increasing the robustness of the flight schedule, two criteria come into conflict: the cost of operating flights to be minimized and the numbers of standby crews that are increased in robust flight schedules. There are two approaches in the existing literature. The first approach is represented by the so-called two-phase solution presented in [32], where the authors first minimize flight operation costs, and in the second phase they test the impact of increased amount of crews on the increase in flight operation costs and the robustness of the solution found. The second approach is described in the publications [33, 34], where the authors select the delay amount in different numbers of crews employed as an optimization criterion.The publications in [17, 18, 35] contain a real-time optimization problem restoring the original flight plan. Such models serve as a tool to support the decision-making of the staff of the airline’s operational department, as described in the publications in [36–39]. The authors of [39] combine an optimization approach with simulation experiments using a simulation model to predict the occurrence of problems in operation and the optimization approach based on the heuristic method to solve the resulting situation leading to the fastest return to the original flight schedule.The presented article refers to conference papers published at the conferences [40, 41].The analysis of the state of the art has revealed that planning problems in air transport are addressed by many authors. Most of them apply different heuristic methods or a combination of heuristic and exact methods. This fact led us to look at the solution process from the purely exact point of view. The main advantage of an exact solution is the certainty of finding the optimal solution. Finding the optimal solution, although on small-scale tasks, can consequently serve as a standard for heuristic methods, for which finding the optimal solution is not always guaranteed. In other words, if we know the optimum solution, we will be able to modify the heuristic method so that its results are as close as possible to the optimum. Linear programming was chosen because we have not found any article that deals with the application of this method in the conditions of operational flight crew rescheduling.


## 3. Theoretical Background: General Principles of Forming Flight Crews and Their Rosters

Flight crew planning is a rather complex process that is influenced by a number of factors. In other words, there are many reasons why two pilots can or cannot fly together. The factors affecting the composition of flight crew are as follows:(i)
Pilot qualification for the aircraft type(ii)
The composition of the crew in terms of the permissibility of the pair of pilots(iii)
Crew composition in terms of time limits(iv)
Seniority(v)
Age(vi)
Destination category(vii)
Interpersonal relationships


### 3.1. Pilot Qualification for the Aircraft Type

One of the main factors influencing the creation of crews is the pilot’s license for the piloting of a particular aircraft type. Both crew pilots must have the appropriate license type approval for the specific aircraft type.


### 3.2. Composition of the Crew in Terms of the Permissibility of the Pair of Pilots

The second group of factors influencing the crew planning process includes the factors influencing the crew composition. The crew always consists of the captain and the copilot. This implies one of the basic conditions, namely, the fact that two copilots cannot form a crew together.


### 3.3. Time on Duty

The third group of factors to be taken into account in the formation of crews is the time limits defined by Regulation 1899/2006 of the European Parliament and of the Council (EU-OPS), Title Q [42], where flight crew performance limitations are clearly identified:(i)
The total duty period of a crew member does not exceed 190 hours in 28 consecutive days(ii)
The total duty period of a crew member does not exceed 60 hours in 7 consecutive days(iii)
The total flight time for which the crew member is assigned does not exceed 900 hours per a calendar year(iv)
The total flight time on which the crew member is assigned has not exceeded 100 hours in any 28 consecutive daysThe regulations stipulate that the basic daily duty period for a crew member is 13 hours. When assigning pilots to flight rosters, the regulations recommend that the distribution be even.


### 3.4. Seniority

Seniority is largely related to the knowledge of the airline’s internal regulations and procedures, which may vary considerably between companies. When creating crews, there is an effort to create crews consisting of one pilot marked as experienced and the other pilot marked as inexperienced. It is not a condition that the captain of the airplane must be kept as experienced.In addition to seniority, the pilot’s actual experience and flight hours, i.e., the total number of hours flown or the number of hours flown on the aircraft type, are taken into account. This also depends on which position he/she had occupied while flying, whether the captain or the position of the first officer.


### 3.5. Age

When creating crews, it is desirable to combine younger pilots with older pilots. For safety reasons, it is forbidden for the crew to consist of two pilots over 60 years of age.


### 3.6. Training

Another crew combination is a combination of pilot instructor and pilot in training. When the pilot is in the training phase, a pilot instructor must also be part of the crew. Both the captain and the first officer may be a pilot in training. However, only the captain may be an instructor.


### 3.7. Destination Category

Airports are divided into three categories, A, B, and C, depending on the difficulty of take-off and landing. Pilots landing or taking off from airports of a given type must have appropriate training and knowledge of the airport and its surroundings.


### 3.8. Interpersonal Relationships

Crew formation can also be significantly influenced by personal and family reasons. Two pilots cannot form a crew together, for example, because of personal aversion, which could have a negative effect on safety during flight. The same is true for married couples, where the effort is not to be part of one crew. The pair is always one of the dominant pair, which could endanger the position of the commander and negatively affect his decision-making in crisis situations. It is strongly recommended not to create crews from former spouses.Based on the abovementioned factors, it is possible to form a set of admissible crews from a set of pilots to operate each planned flight. In most articles, the authors do not consider the interpersonal relationships between individual pilots. At present, it is a trend for airlines to consider the requirements of individual pilots when creating the flight crews. Taking into consideration the interpersonal relationships should contribute to good atmosphere in the cabin of the aircraft, which leads to increasing the safety of the flight itself. The set of permissible crews in Table2 thus takes into account all the above-mentioned factors, including the interpersonal relations between the pilots.Table 2
Incidence matrix with assigned numbers for individual crews.
CaptainFirst officer123456789101¯1xX234x5xx2¯x6Xxx78910x3¯xx1112x13x14x154¯1617X1819x20x21225¯xx232425x262728x6¯293031xx32xx33x7¯343536x37x38x39408¯xxXxxxx41xx9¯xxXxxxxx42x


## 3.1. Pilot Qualification for the Aircraft Type

One of the main factors influencing the creation of crews is the pilot’s license for the piloting of a particular aircraft type. Both crew pilots must have the appropriate license type approval for the specific aircraft type.


## 3.2. Composition of the Crew in Terms of the Permissibility of the Pair of Pilots

The second group of factors influencing the crew planning process includes the factors influencing the crew composition. The crew always consists of the captain and the copilot. This implies one of the basic conditions, namely, the fact that two copilots cannot form a crew together.


## 3.3. Time on Duty

The third group of factors to be taken into account in the formation of crews is the time limits defined by Regulation 1899/2006 of the European Parliament and of the Council (EU-OPS), Title Q [42], where flight crew performance limitations are clearly identified:(i)
The total duty period of a crew member does not exceed 190 hours in 28 consecutive days(ii)
The total duty period of a crew member does not exceed 60 hours in 7 consecutive days(iii)
The total flight time for which the crew member is assigned does not exceed 900 hours per a calendar year(iv)
The total flight time on which the crew member is assigned has not exceeded 100 hours in any 28 consecutive daysThe regulations stipulate that the basic daily duty period for a crew member is 13 hours. When assigning pilots to flight rosters, the regulations recommend that the distribution be even.


## 3.4. Seniority

Seniority is largely related to the knowledge of the airline’s internal regulations and procedures, which may vary considerably between companies. When creating crews, there is an effort to create crews consisting of one pilot marked as experienced and the other pilot marked as inexperienced. It is not a condition that the captain of the airplane must be kept as experienced.In addition to seniority, the pilot’s actual experience and flight hours, i.e., the total number of hours flown or the number of hours flown on the aircraft type, are taken into account. This also depends on which position he/she had occupied while flying, whether the captain or the position of the first officer.


## 3.5. Age

When creating crews, it is desirable to combine younger pilots with older pilots. For safety reasons, it is forbidden for the crew to consist of two pilots over 60 years of age.


## 3.6. Training

Another crew combination is a combination of pilot instructor and pilot in training. When the pilot is in the training phase, a pilot instructor must also be part of the crew. Both the captain and the first officer may be a pilot in training. However, only the captain may be an instructor.


## 3.7. Destination Category

Airports are divided into three categories, A, B, and C, depending on the difficulty of take-off and landing. Pilots landing or taking off from airports of a given type must have appropriate training and knowledge of the airport and its surroundings.


## 3.8. Interpersonal Relationships

Crew formation can also be significantly influenced by personal and family reasons. Two pilots cannot form a crew together, for example, because of personal aversion, which could have a negative effect on safety during flight. The same is true for married couples, where the effort is not to be part of one crew. The pair is always one of the dominant pair, which could endanger the position of the commander and negatively affect his decision-making in crisis situations. It is strongly recommended not to create crews from former spouses.Based on the abovementioned factors, it is possible to form a set of admissible crews from a set of pilots to operate each planned flight. In most articles, the authors do not consider the interpersonal relationships between individual pilots. At present, it is a trend for airlines to consider the requirements of individual pilots when creating the flight crews. Taking into consideration the interpersonal relationships should contribute to good atmosphere in the cabin of the aircraft, which leads to increasing the safety of the flight itself. The set of permissible crews in Table2 thus takes into account all the above-mentioned factors, including the interpersonal relations between the pilots.Table 2
Incidence matrix with assigned numbers for individual crews.
CaptainFirst officer123456789101¯1xX234x5xx2¯x6Xxx78910x3¯xx1112x13x14x154¯1617X1819x20x21225¯xx232425x262728x6¯293031xx32xx33x7¯343536x37x38x39408¯xxXxxxx41xx9¯xxXxxxxx42x


## 4. Problem Formulation and Mathematical Model

### 4.1. Problem Formulation

A number of flights are defined asI, which were not under way when the time the delay occurred, including delayed flight (element of the set I represents the airline’s base airport 0 where the crews start and finish their shift). For every flight i∈I the planned start of preflight preparation is known as ti, the time spent by the crew to man it is Ti (including the time required to complete all postflight operations at the destination airport), and the number of passengers who have purchased a ticket for the flight and who may need to be compensated if the delay period prescribed by the regulation is exceeded is Ni [1].There are also a number of crewsK available, meeting interpersonal relationships requirements (the crews form an indivisible unit) which the airline may assign to man its flights. For each crew k∈K, there is a known time sk that the crew has already been on duty on that day (this is the time the crew has already worked in terms of their daily limit).In addition, two three-dimensional matrices are introduced in the model,P and Q. The elements of these matrices represent the cost and time of crew transfers between the airports of arrival and the airports of subsequent flights. Values of matrix elements P and Q are calculated based on information about the current crew position.Elementpijk expresses the costs of a nonproductive transfer of the crew k∈K to man the flight j∈I∪0 after manning flight i∈I∪0 (matrix element p0jk represents the costs incurred by a nonproductive transfer of the crew k∈K to airport departure flight j∈I from the base airport; element matrix pi0k represents the costs incurred by a nonproductive transfer of the crew k∈K from destination airport flight i∈I to the base airport).Elementqijk expresses the time spent by the nonproductive transfer of the crew k∈K to man the flight j∈I∪0 after manning flight i∈I∪0 (matrix element q0jk represents the time spent by a nonproductive transfer of the crew k∈K to the airport of departure j∈I from the base airport; element matrix qi0k represents the time spent by a nonproductive transfer of the crew k∈K from the destination airport i∈I to the base airport).Let us also consider a situation where financial compensation is paid according to EP and ER Regulation No. 261/2004 when a significant delay arises. The airline is therefore obliged to pay to each passenger from the flighti∈I financial compensation of oi (the value of the compensation paid to the passenger depends on the length of the flight in km).The optimization task is to decide on the transfer of crews between flights so as to minimize the airline’s costs associated with transporting crews to man individual flights and the costs of delays, including compensation for passengers who have incurred delays.It should also be noted that all time data contained in the model will be given in selected time units that have elapsed from a predefined reference time point. For example, if the reference time point is 0.00 (model time 0) and the selected time unit is 1 minute, then, for example, the real time point 6.30 will be replaced by 390. If the selected unit of time is 1 hour, then the same real time point 6.30 will be replaced by 6.5, and so forth.


### 4.2. Mathematical Model

Five groups of variables will be introduced into the model.The first group will consist of variablesxijk with a domain of definition: values 0 and 1. If the result of the optimization calculation will be xijk=1, then the crew k∈K after manning the flight i∈I∪0 will move on to man flight j∈I∪0; if it holds that x0jk=1, then this means that for manning flight j∈I a new crew had been sent from the base; if xi0k=1, then it means the crew k∈K will fulfill the daily plan after manning flight i∈I. If it holds after optimization calculation that xijk=0, then the crew k∈K after manning flight i∈I∪0 will not move on to man flight j∈I.The second group will consist of variablesyik with a domain of definition: a set of nonnegative real numbers. The value of the variable will represent the real flight arrival delay after the optimization calculation i∈I when the crew is assigned k∈K.The third group will consist of variableszi with a domain of definition: values 0 and 1. If it holds after the optimization calculation that zi=1, then the passengers of flight i∈I will have to be financially compensated. If, after the optimization calculation, zi=0 is true, then the passengers of flight i∈I will not have to be financially compensated.The last two groups of variables will be variablesh¯k and h¯¯k with domains of definition: sets of real nonnegative numbers. Variables h¯k and h¯¯k are auxiliary variables ensuring the setting of daily periods in service of individual crews, relative to the beginning of their daily service. Variables h¯k represent the lower limit of the time of day on duty k∈K; variables h¯¯k represent the upper limit of the time of day on duty k∈K.The optimization criterion in the proposed model will be the total cost of two components: the first component will be the airline’s costs associated with the redeployment of crews to provide a defined set of flights and the second component will be the airline’s costs associated with compensation paid to delayed passengers and the optimization process will aim to find such a solution where the optimization criteria will be as minimal as possible.The mathematical model for rescheduling flight crews shall be(1)minfx,y,z,h¯k,h¯¯k=∑i∈I∪0∑j∈I∪0∑k∈Kpijk·xijk+∑i∈I∑k∈Koi·Ni·zi+ε·∑k∈Kh¯¯k−h¯ksubject to(2)∑i∈I∪0∑k∈Kxijk=1,j∈I,(3)∑i∈I∪0xijk=∑i∈I∪0xjik,j∈Iandk∈K,(4)yjk≤M·∑i∈I∪0xijk,j∈Iandk∈K,(5)∑j∈Ix0jk≤1,k∈K(6)∑k∈Kyik≤bi+zi·M,i∈I,(7)ti+Ti+yij+qijk≤tj+yjk+M·1−xijk,i∈I∪0j∈Iandk∈K,(8)h¯k≤tj−q0jk·xojk+M·1−x0jk,j∈Iandk∈K,(9)ti+Ti⋅xi0k+yik+qi0k⋅xi0k≤h¯¯k,i∈I,k∈K(10)sk+h¯¯k−h¯k≤L,k∈K,(11)h¯¯k−h¯k≥0,k∈K(12)xijk∈0,1,i∈I∪0,j∈I∪0,k∈K,(13)yik∈R0+,i∈I,k∈K,(14)zi∈0,1,i∈I,(15)h¯k∈R0+,k∈K,(16)h¯¯k∈R0+,k∈K,Formula (1) expresses the cumulative optimization criterion whose value is to be minimized. It consists of three parts. The first part represents the total cost of nonproductive crew transfers between flights, the second part represents the cost of compensation paid to passengers in the event of delay in flights exceeding the statutory limits, and the third part ensures that the range between the lowest and highest limits of daily roster is kept at a minimum. In order for the difference between value h¯k and h¯¯k not to affect the resulting value of costs, this difference is multiplied by the separation constant ε where ε=0,001. Constraints (2) will ensure that every unmanned flight to this moment will be manned. Constraints (3) will ensure crew continuity before and after flight. Constraints (4) will only allow a delayed departure for the crew that will be deployed to man the flight. Constraints (5) will ensure that each crew is deployed no more than once to man unmanned flights. Constraints (6) will ensure that compensation paid to passengers is done only once the time limit set by legislation has been exceeded. Constraints (7) shall ensure that there is no transfer of crews between flights in cases of temporal infeasibility of such transfers. Constraints (8) and (9) bind to the variables representing the lower and upper limits of the rosters of each crew. Constraints (10) shall ensure that the roster time of each crew is maintained. Constraints (11) will ensure that the difference is correct. Finally, constraints (12)–(16) define domains of definition of the variables used in the model.


## 4.1. Problem Formulation

A number of flights are defined asI, which were not under way when the time the delay occurred, including delayed flight (element of the set I represents the airline’s base airport 0 where the crews start and finish their shift). For every flight i∈I the planned start of preflight preparation is known as ti, the time spent by the crew to man it is Ti (including the time required to complete all postflight operations at the destination airport), and the number of passengers who have purchased a ticket for the flight and who may need to be compensated if the delay period prescribed by the regulation is exceeded is Ni [1].There are also a number of crewsK available, meeting interpersonal relationships requirements (the crews form an indivisible unit) which the airline may assign to man its flights. For each crew k∈K, there is a known time sk that the crew has already been on duty on that day (this is the time the crew has already worked in terms of their daily limit).In addition, two three-dimensional matrices are introduced in the model,P and Q. The elements of these matrices represent the cost and time of crew transfers between the airports of arrival and the airports of subsequent flights. Values of matrix elements P and Q are calculated based on information about the current crew position.Elementpijk expresses the costs of a nonproductive transfer of the crew k∈K to man the flight j∈I∪0 after manning flight i∈I∪0 (matrix element p0jk represents the costs incurred by a nonproductive transfer of the crew k∈K to airport departure flight j∈I from the base airport; element matrix pi0k represents the costs incurred by a nonproductive transfer of the crew k∈K from destination airport flight i∈I to the base airport).Elementqijk expresses the time spent by the nonproductive transfer of the crew k∈K to man the flight j∈I∪0 after manning flight i∈I∪0 (matrix element q0jk represents the time spent by a nonproductive transfer of the crew k∈K to the airport of departure j∈I from the base airport; element matrix qi0k represents the time spent by a nonproductive transfer of the crew k∈K from the destination airport i∈I to the base airport).Let us also consider a situation where financial compensation is paid according to EP and ER Regulation No. 261/2004 when a significant delay arises. The airline is therefore obliged to pay to each passenger from the flighti∈I financial compensation of oi (the value of the compensation paid to the passenger depends on the length of the flight in km).The optimization task is to decide on the transfer of crews between flights so as to minimize the airline’s costs associated with transporting crews to man individual flights and the costs of delays, including compensation for passengers who have incurred delays.It should also be noted that all time data contained in the model will be given in selected time units that have elapsed from a predefined reference time point. For example, if the reference time point is 0.00 (model time 0) and the selected time unit is 1 minute, then, for example, the real time point 6.30 will be replaced by 390. If the selected unit of time is 1 hour, then the same real time point 6.30 will be replaced by 6.5, and so forth.


## 4.2. Mathematical Model

Five groups of variables will be introduced into the model.The first group will consist of variablesxijk with a domain of definition: values 0 and 1. If the result of the optimization calculation will be xijk=1, then the crew k∈K after manning the flight i∈I∪0 will move on to man flight j∈I∪0; if it holds that x0jk=1, then this means that for manning flight j∈I a new crew had been sent from the base; if xi0k=1, then it means the crew k∈K will fulfill the daily plan after manning flight i∈I. If it holds after optimization calculation that xijk=0, then the crew k∈K after manning flight i∈I∪0 will not move on to man flight j∈I.The second group will consist of variablesyik with a domain of definition: a set of nonnegative real numbers. The value of the variable will represent the real flight arrival delay after the optimization calculation i∈I when the crew is assigned k∈K.The third group will consist of variableszi with a domain of definition: values 0 and 1. If it holds after the optimization calculation that zi=1, then the passengers of flight i∈I will have to be financially compensated. If, after the optimization calculation, zi=0 is true, then the passengers of flight i∈I will not have to be financially compensated.The last two groups of variables will be variablesh¯k and h¯¯k with domains of definition: sets of real nonnegative numbers. Variables h¯k and h¯¯k are auxiliary variables ensuring the setting of daily periods in service of individual crews, relative to the beginning of their daily service. Variables h¯k represent the lower limit of the time of day on duty k∈K; variables h¯¯k represent the upper limit of the time of day on duty k∈K.The optimization criterion in the proposed model will be the total cost of two components: the first component will be the airline’s costs associated with the redeployment of crews to provide a defined set of flights and the second component will be the airline’s costs associated with compensation paid to delayed passengers and the optimization process will aim to find such a solution where the optimization criteria will be as minimal as possible.The mathematical model for rescheduling flight crews shall be(1)minfx,y,z,h¯k,h¯¯k=∑i∈I∪0∑j∈I∪0∑k∈Kpijk·xijk+∑i∈I∑k∈Koi·Ni·zi+ε·∑k∈Kh¯¯k−h¯ksubject to(2)∑i∈I∪0∑k∈Kxijk=1,j∈I,(3)∑i∈I∪0xijk=∑i∈I∪0xjik,j∈Iandk∈K,(4)yjk≤M·∑i∈I∪0xijk,j∈Iandk∈K,(5)∑j∈Ix0jk≤1,k∈K(6)∑k∈Kyik≤bi+zi·M,i∈I,(7)ti+Ti+yij+qijk≤tj+yjk+M·1−xijk,i∈I∪0j∈Iandk∈K,(8)h¯k≤tj−q0jk·xojk+M·1−x0jk,j∈Iandk∈K,(9)ti+Ti⋅xi0k+yik+qi0k⋅xi0k≤h¯¯k,i∈I,k∈K(10)sk+h¯¯k−h¯k≤L,k∈K,(11)h¯¯k−h¯k≥0,k∈K(12)xijk∈0,1,i∈I∪0,j∈I∪0,k∈K,(13)yik∈R0+,i∈I,k∈K,(14)zi∈0,1,i∈I,(15)h¯k∈R0+,k∈K,(16)h¯¯k∈R0+,k∈K,Formula (1) expresses the cumulative optimization criterion whose value is to be minimized. It consists of three parts. The first part represents the total cost of nonproductive crew transfers between flights, the second part represents the cost of compensation paid to passengers in the event of delay in flights exceeding the statutory limits, and the third part ensures that the range between the lowest and highest limits of daily roster is kept at a minimum. In order for the difference between value h¯k and h¯¯k not to affect the resulting value of costs, this difference is multiplied by the separation constant ε where ε=0,001. Constraints (2) will ensure that every unmanned flight to this moment will be manned. Constraints (3) will ensure crew continuity before and after flight. Constraints (4) will only allow a delayed departure for the crew that will be deployed to man the flight. Constraints (5) will ensure that each crew is deployed no more than once to man unmanned flights. Constraints (6) will ensure that compensation paid to passengers is done only once the time limit set by legislation has been exceeded. Constraints (7) shall ensure that there is no transfer of crews between flights in cases of temporal infeasibility of such transfers. Constraints (8) and (9) bind to the variables representing the lower and upper limits of the rosters of each crew. Constraints (10) shall ensure that the roster time of each crew is maintained. Constraints (11) will ensure that the difference is correct. Finally, constraints (12)–(16) define domains of definition of the variables used in the model.


## 5. Computational Experiments

The functionality of the model was tested on data obtained from real traffic. Computational experiments were performed in the Xpress-IVE optimization software on a PC with a 3.3 GHz processor and 8 GB RAM corresponding to common office equipment.A sample of a part of the airline’s fleet, whose base airport is Brno-Turany International Airport (Czech Republic), the black heptagon depicted in Figure1, was selected for the computational experiment. The operation of three Boeing B 737 aircraft was monitored. During one day, the aircraft made 21 flights. The flights were made to 7 destinations: Ostrava (OSR), Burgas (BOJ), Antalya (AYT), Kos (KGS), Rhodes (RHO), Zakynthos (ZTH), and Lamezia Terme (SUF). The flight plan is shown schematically in Figure 1. The daily traffic data of these aircraft was obtained from their records published on the web-based real-time monitoring application [43]. Regarding the pilots, they do not represent a real set of pilots of the selected airline; the data are fictional. Information about the crews and the delays is model data as well.Figure 1
Scheme of scheduled flights.The airline has a total of 19 pilots at its disposal. There are 9 pilots qualified as captain and 10 pilots qualified as first officer. These pilots (due to the requirements in Chapter 3) can create 42 possible crews (see Table2), where the numbers of created crews are already listed. If pilots cannot create a crew (such a crew would contradict the rules in Chapter 3), then the “x” symbol is at the position of the relevant element.The following situation was simulated for experimental verification of functionality of the mathematical model. At time 700, there was an incident on Flight 1 which caused a delay of 200 minutes. At the time the incident was reported, 10 flights were left to be made (including the flight on which the incident occurred) to 6 destinations: Ostrava (OSR), Burgas (BOJ), Kos (KGS), Rhodes (RHO), Zakynthos (ZTH), and Lamezia Terme (SUF); see Figure2.Figure 2
Unmanned flights at the time of irregularity situation.Flight start timesti, their duration Ti, and the expected numbers of passengers on flights to be manned are summarized in Table 3.Table 3
Input valuesti,Ti,Ni.
Flight12345678910ti (min)750935960965106511251135124513851395Ti (min)130125125150132160175130160170Ni (passengers)160180175170165160173174175180The minimum delay times beyond which compensation is paid and the amount of compensation is set for each passenger on the flight, based on the calculated flight lengths, are shown in Table4.Table 4
Input valuesbi,oi.
Flight12345678910bi (min)120120120180120180180120180180oi (min)250250250400250400400250400400Table5 contains the times that individual crews were taken from the daily limits. The values contained in the table were determined as the maximum of the values, which each pilot spent on duty on a given day, from which the crew can be formed.Table 5
Time spent ogn duty (crew).
Crewk1234567891011skmin150170150220200220220200220220170Crewk1213141516171819202122skmin170220200170150140170140140140140Crewk2324252627282930313233skmin200200200200200200150805022050Crewk343536373839404142skmin15080801408080802000The task is to reschedule the rosters of existing crews to minimize the value of the optimization criterion (1).There were 12 pilots in the original schedule; 7 pilots were divided between airport standby at the airport and home standby within driving distance. Pilots1¯,6¯,3, and 4 (make up crews 2 and 31) were not deployed in the original plan but were allocated as a backup and can be used in case of irregularity. Pilots 9¯,2, and 7 are not included in the original plan because they cannot form a crew with each other.Crews made up of pairs of pilots have the following rosters according to the original plan; see Table6. As this will be the current crew deployment at the time of reporting the incident, the column marked Crew roster does not contain fictitious transfers from the base airport.Table 6
Original crew rosters.
CrewCaptainFirst officerCrew rosterThe color of the flight manned by the crew7263–0153105–10–016411–2–025554–7–039798–9–041886–0From Table6, it is evident, for example, that crew 7 consisting of captain 2 and first officer 6 was designated to man Flight 3 at the time of reporting an incident on Flight 1, etc.The original crew rosters, from the time when the operation center received the information about the delay, are shown in Figure3.Figure 3
The original solution with delayed flight.An incident and thus a delay of 200 minutes from Zakynthos to Brno were reported to the airline’s operations center at time 700. The graph in Figure3 shows the delayed flight marked with a red arrow.


### 5.1. Irregularity Situation Manning

The control center must create a new plan to man the remaining flights respective of current crew positions.After the optimization calculation was finished, the optimal solution was reached; see Figure4. The figure shows a snapshot of the output from the Xpress-IVE optimization software. The results show that the model contains 4309 constraints and 4246 variables for the experiment. Furthermore, the table provides information about the value of the objective criterion which is 40000.2 (best solution) and that the solution found is optimal (status). The computation time was 0.3 s (time).Figure 4
Results from Xpress-IVE optimization software.Nonzero values of the main variablesxijk,yjk, and zi are listed in Table 7.Table 7
Results of variablesxijk,yjk, and zi.
xijkxijkyjkzix092=1x0231=1y102=105z1=1x9102=1x2331=1y615=72x1002=1x3031=1y116=200x0515=1x0441=1y331=100x5615=1x4741=1y841=65x6015=1x7841=1x0116=1x8041=1x1016=1The delay that occurred on Flight 1 led to modifications of the originally created rosters to the following form; see Table8. The experiment shows that only 5 crews will be used to operate the remaining flights, namely, crews 2, 15, 16, 31, and 41 (see the 1st column). The composition of these crews is presented in columns 2 and 3. The fourth column represents the schedule of each crew. All the crews finish their daily schedule at the base airport (Brno). The penultimate column shows that none of the crews has exceeded the maximum daily duty limit which is equal to 700 minutes. The last column assigns a color to each crew to depict flights that are served during their schedules in Figure 5.Table 8
Change of crew rosters after rescheduling.
CrewCaptainFirst officerNew crew rosterTime in dutyminThe color of the flight manned by the crew2149–10–0500153105–6–046216411–048031630–2–3–030041884–7–8–0675Figure 5
Graphical representation of crew rosters.Rosters of individual crews are shown in the graph on Figure5.A total of 5 crews will be assigned after rescheduling. Redeployment reduced the number of crews needed. This reduction was probably achieved thanks to the possibility of delays of individual flights. Unlike the original plan, crews 7, 25, and 39 were not involved in the new plan. On the other hand, crews 2 and 31, who were originally allocated as standby crews at the airport, joined the scheduled flights.Due to rescheduling and crew reductions, there was a delay in five flights. The delay affected flights 1, 3, 6, 8, and 10. However, only passengers with Flight 1 are entitled to compensation, with a delay of 200 minutes, which exceeds the permitted delay time by 50 minutes; therefore the airline is obliged to pay compensation to passengers. It follows that the value of the objective function corresponds to the product of the number of passengers on Flight 1 (N1) and the cost of compensation for one passenger on that flight (o1) 160·250=40000 monetary units.The value of the objective function is 40000.2. The occurrence of value of 0.2 is only due to minimizing the range between variablesh¯k and h¯¯k delimiting the lower and upper limit of day duty for each crew. This is only an ancillary value and does not affect the cost of the irregularity.When rescheduling crews as a result of an irregularity situation while operating Flight 1, the following changes in flights occurred:(a)
A decrease in the number of crews from 6 to 5(b)
Exclusion of crews 7, 25, and 39, which were included in the original plan crew(c)
Inclusion of crews 2 and 31 in the new flight management planThe comparison of the crews’ rosters during irregularity situations is clearly summarized in Table9. Symbol X labels the crews that are not assigned to any flight.Table 9
The crews’ rosters during irregularity situations.
CrewOriginal rosterRoster after rescheduling2X9–10–073–0X155–10–05–6–0161–2–01–0254–7–0X31X2–3–0398–9–0X416–04–7–8–0


## 5.1. Irregularity Situation Manning

The control center must create a new plan to man the remaining flights respective of current crew positions.After the optimization calculation was finished, the optimal solution was reached; see Figure4. The figure shows a snapshot of the output from the Xpress-IVE optimization software. The results show that the model contains 4309 constraints and 4246 variables for the experiment. Furthermore, the table provides information about the value of the objective criterion which is 40000.2 (best solution) and that the solution found is optimal (status). The computation time was 0.3 s (time).Figure 4
Results from Xpress-IVE optimization software.Nonzero values of the main variablesxijk,yjk, and zi are listed in Table 7.Table 7
Results of variablesxijk,yjk, and zi.
xijkxijkyjkzix092=1x0231=1y102=105z1=1x9102=1x2331=1y615=72x1002=1x3031=1y116=200x0515=1x0441=1y331=100x5615=1x4741=1y841=65x6015=1x7841=1x0116=1x8041=1x1016=1The delay that occurred on Flight 1 led to modifications of the originally created rosters to the following form; see Table8. The experiment shows that only 5 crews will be used to operate the remaining flights, namely, crews 2, 15, 16, 31, and 41 (see the 1st column). The composition of these crews is presented in columns 2 and 3. The fourth column represents the schedule of each crew. All the crews finish their daily schedule at the base airport (Brno). The penultimate column shows that none of the crews has exceeded the maximum daily duty limit which is equal to 700 minutes. The last column assigns a color to each crew to depict flights that are served during their schedules in Figure 5.Table 8
Change of crew rosters after rescheduling.
CrewCaptainFirst officerNew crew rosterTime in dutyminThe color of the flight manned by the crew2149–10–0500153105–6–046216411–048031630–2–3–030041884–7–8–0675Figure 5
Graphical representation of crew rosters.Rosters of individual crews are shown in the graph on Figure5.A total of 5 crews will be assigned after rescheduling. Redeployment reduced the number of crews needed. This reduction was probably achieved thanks to the possibility of delays of individual flights. Unlike the original plan, crews 7, 25, and 39 were not involved in the new plan. On the other hand, crews 2 and 31, who were originally allocated as standby crews at the airport, joined the scheduled flights.Due to rescheduling and crew reductions, there was a delay in five flights. The delay affected flights 1, 3, 6, 8, and 10. However, only passengers with Flight 1 are entitled to compensation, with a delay of 200 minutes, which exceeds the permitted delay time by 50 minutes; therefore the airline is obliged to pay compensation to passengers. It follows that the value of the objective function corresponds to the product of the number of passengers on Flight 1 (N1) and the cost of compensation for one passenger on that flight (o1) 160·250=40000 monetary units.The value of the objective function is 40000.2. The occurrence of value of 0.2 is only due to minimizing the range between variablesh¯k and h¯¯k delimiting the lower and upper limit of day duty for each crew. This is only an ancillary value and does not affect the cost of the irregularity.When rescheduling crews as a result of an irregularity situation while operating Flight 1, the following changes in flights occurred:(a)
A decrease in the number of crews from 6 to 5(b)
Exclusion of crews 7, 25, and 39, which were included in the original plan crew(c)
Inclusion of crews 2 and 31 in the new flight management planThe comparison of the crews’ rosters during irregularity situations is clearly summarized in Table9. Symbol X labels the crews that are not assigned to any flight.Table 9
The crews’ rosters during irregularity situations.
CrewOriginal rosterRoster after rescheduling2X9–10–073–0X155–10–05–6–0161–2–01–0254–7–0X31X2–3–0398–9–0X416–04–7–8–0


## 6. Conclusions

The paper demonstrates the use of the optimization method in the conditions of air transport in situations where operational rescheduling of crews is necessary due to the occurrence of an irregularity operation. An irregularity operation is a situation that causes a delay and consequently a disruption of a scheduled flight schedule. The most common irregularity operations include adverse weather conditions, technical aircraft defects, or heavy traffic at take-off or landing airports. In addition to the occurrence of delays, irregularity operations may also limit the further use of crews ensuring the implementation of a delayed flight by exceeding their permitted duty time on a subsequent flight. In all the above cases, it is necessary to operatively solve the resulting situations. The paper represents one of the possible approaches for operational solutions. This is an exact optimization approach, in which the objective function includes the cost of nonproductive transfer of pilots to the departure point and the cost of compensating passengers in the event of a delay. The resulting solution takes into account the temporal feasibility of crew transfers, limitation of daily time in the service of individual crews, and interpersonal relationships between pilots forming individual crews, which is a factor that is often neglected in literature. Unlike the frequently used heuristic approaches, the exact approach presented in the article guarantees finding the optimal solution. The certainty of finding the optimal solution also predetermines this model as a validation tool for heuristic methods, with which it will subsequently be possible to solve very large tasks.Computational experiments have shown that the presented optimization approach can serve as a tool to support decision-making of the operations center staff. In particular, it can help them decide on rescheduling of crews to minimize the cost of dealing with the irregularity operation. Thanks to this tool, each small airline can save considerable financial resources in dealing with emergencies without the need for purchasing expensive software used by large airlines.The resolution of this issue is far from complete. In the future, we want to focus on other important operational factors, such as incorporating the possibility of operational crew forming based on mutual contraindications between pilots, incorporating the existence of free slots at airports or airspace, or incorporating the availability of an available aircraft when deploying a new crew.



---

*Source: 5372567-2020-05-30.xml*