1 Introduction
We have considered a problem faced by Garuda Indonesia, the flag carrier of Indonesia, in expanding their business. Although global economic conditions are still unfavorable, the market for the airline industry in Indonesia is still expanding. Garuda Indonesia has responded to this conducive environment by expanding its fleet, increasing flight frequencies on specific routes and opening several new routes for both domestic and international flights.
A larger flight network leads to a more complex crew rostering problem. Rostering means assigning each cockpit crew pairing, which is an element of
Received March 8th, 2012, 1st Revision May 27th, 2013, 2nd Revision September 6th, 2013, Accepted for publication September 11th, 2013. Copyright © 2013 Published by ITB Journal Publisher, ISSN: 2337-5760, DOI: 10.5614/j.math.fund.sci.2013.45.3.2
<sup>1</sup> A pairing is a sequence of flights starting and ending at the cockpit crew base.
the minimum set of pairings,2 to a group of cockpit crews in such a way that no labor regulations are violated when the cockpit crew runs their assignments. Over time, cockpit crew rostering in the airline industry has become a slightly cumbersome process, being carried out semi-manually by experienced staff members. This approach is surely inefficient and furthermore we may find unfair assignments to cockpit crew. A roster can give some cockpit crews a very tight schedule, while others get a much less tight schedule. The rostering needs to be carried out in such a way that it results in a relatively equal workload for each crew member in an efficient way.
The crew rostering problem at Garuda Indonesia is extra complex because of a number of internal crew labor regulations on the top of crew labor regulations issued by international, regional and national airline regulators. These internal regulations represent the wish of the cockpit crews to avoid exhausting assignments. It is clear that they are more restrictive than the other regulations, otherwise it would not have been necessary to issue them.
In our study we have developed an optimization model for the cockpit crew rostering problem at Garuda Indonesia. We have derived mathematical expressions for the cockpit crew labor regulations and a number of technical matters.3 Some are corrected expressions for similar constraints proposed by Lucic and Teodorovic [1]. Using the expressions from [1] may lead to errors in counting the working time of the cockpit crews (see fourth paragraph of Section 3 for details) that result in incompact rosters. Moreover, in the case of a rostering problem where the number of cockpit crews is very restricted, the use of the expressions from [1] leads to an infeasible problem. The expressions become the constraints of the optimization model. We have used the average relative deviation of the monthly flight time from the average ideal monthly flight time as the objective function. We think that minimization of this objective function, while respecting all other constraints, will result in a roster in which the workloads of the cockpit crews are relatively equal.
An enormous amount of papers on airline crew rostering problems has been published. Studies by Chang [2], Gamache, et al. [3], Kovari [4], Lederer and Nambimadom [5], Medard and Sawhney [6], Vance, et al. [7], Yan and Tu [8] are concerned with the modeling of airline crew rostering problems. Many solution methods for crew rostering problems have been proposed, for example in AhmadBeygi, et al. [9], Barnhart, et al. [10], Deng and Lin [11], Goumopoulos and Housos [12], Gamache [13], Hoffman and Padberg, [14].
The minimum set of pairings covers all flights in the schedule and is constructed by solving the crewpairing problem.
The presence of internal labor regulations creates more constraints in the present optimization model than there are in cockpit crew rostering models from other studies.
Like we have done in this paper, most of them construct the roster in two stages: first solve the crew-pairing problem and then solve the crew rostering problem. A new approach where the crew pairing problem and the crew rostering problem are solved simultaneously has been proposed in Souai and Teghem [15].
We still rely on the two-stage approach because we have developed an efficient algorithm for constructing the minimum set of crew pairings in a short amount of time. The second reason is, as stated before, that Garuda Indonesia has a number of internal crew labor regulations which are very restricting so that deriving mathematical expressions for these regulations is very challenging. The derivation of the proper mathematical expressions (and the optimization problem as a whole) is the subject of this paper. We need to ensure that the mathematical expressions result in a satisfactory roster before we proceed to the process of simultaneously constructing crew pairings and crew roster.
We can apply the simulated annealing method as proposed in [1] for solving the optimization. An initial feasible solution for the simulated annealing method can be obtained by applying a pairing-by-pairing algorithm that mimics the pilot-by-pilot method from [1], whereby we exchange the position of the pairings and the cockpit crews from the pilot-by-pilot method. We have applied the pairing-by-pairing method and the simulated annealing method to all classes of cockpit crews of Garuda Indonesia and obtained satisfactory rosters in a short amount of time. We checked that all cockpit crew labor regulations were satisfied, so that we can say that our optimization model is well-defined and ready for application in day-to-day operation by the airline.
This paper is organized as follows. After this introduction, in Section 2, we present the labor regulations whose mathematical expressions are part of the constraints of the optimization problem. The mathematical model will be presented in Section 3. In Section 4 we present the pairing-by-pairing method that was used for determining feasible pairings. In Section 5, we present the implementation of the optimization model to a class of cockpit crew, including the numerical results. This paper ends with the conclusion in Section 6. The nomenclature is given in Section 7.
2 Cockpit Crew Labor Regulations
Altogether, the cockpit crew regulations of Garuda Indonesia can be classified as the regulations for one day, two days, three days, seven days, one month, three months, and one year of working time; regulations for two consecutive pairings run by the same crew; and regulations for medical examinations, training, and annual leave. The regulations for one day and two days of working
time have been considered in the construction of crew pairings. In the following we only consider the remaining regulations, for which the mathematical expressions are presented in Section 3.
a. Flight time
If an airline has a number of aircrafts with different licenses for flying them, we have a number of classes of crews, consisting of the crews with the same license. The maximum cumulative flight time during a time period depends on the class of crew. For example, for one class of crew the maximum cumulative flight time can be 24 hours for every consecutive three calendar days, 30 hours for every seven consecutive days, 110 hours for every calendar month, 300 hours for every three calendar months, and 1050 hours for one calendar year.
b. Days off
(i) One day off will be given to a cockpit crew following six consecutive days of assignment. Every cockpit crew has a number of days off after assignment to a pairing which takes the cockpit crew 'away from base' (AFB). The amount of days off is described in Table 1.
Table 1 Number of days off according to length of AFB.
| Length of AFB (days) | Minimum Days Off (days) | Length of AFB (days) | Minimum Days Off (days) |
|---|---|---|---|
| 5 | 2 | 13 - 15 | 6 |
| 6 – 8 | 3 | 16 - 18 | 7 |
| 9 – 10 | 4 | 19 - 20 | 8 |
| 11 – 12 | 5 |
(ii) One or more days off will be given to a cockpit crew after attending a training, course, seminar or activity other than flight duty. The amount of days off depends on the length of the activity, as described in Table 2.
Table 2 Number of days off according to length of activity.
| Length of Activity (days) | Days Off (days) |
|---|---|
| 3 - 6 | 1 |
| 7 - 14 | 2 |
| 15 - 22 | 3 |
| 23 - 30 | 5 |
| > 30 | 7 |
(iii)Every cockpit crew has a minimum of (in total) eight days off in one calendar month.
c. Rest Period
A minimum rest period of nine hours will be given to a crew member who has finished performing an assignment prior to the next assignment. This rest period is calculated from 180 minutes after the end of the last assignment. In total, this type of rest period takes 15 hours and is called 'lay over time'. A minimum rest period of 18 hours will also be given if during a 72-hour period a cockpit crew has reached 24 flight hours or more.
These regulations are some of the internal regulations we have mentioned before.
d. Annual Leave
Every cockpit crew is entitled to annual leave, whereby its length depends on the aggregate working period at the airline.
e. Training
Every cockpit crew has to attend training twice in every calendar year. The length of the training is five days in one calendar year.
f. Medical Examination
Every cockpit crew has to attend a one-day medical examination once in every six calendar months.
3 Mathematical Model
In this section, we derive an optimization model for the cockpit crew rostering problem at Garuda Indonesia. The constraints of the optimization model are a representation of the labor regulations that have been described in the previous section and some technical constraints. We assume that the number of cockpit crews is sufficient for running the flight schedule. Later in this section we discuss how to choose the objective function that represents a measure of fairness for all cockpit crews.
We assume that each cockpit crew member always works with the same group of cockpit crew members. We also assume that each cockpit crew member in the same group has the same schedule for training, medical examination, and annual leave. Relaxation of these assumptions will not change the optimization model, but in the more general model we have to consider individual cockpit crew members instead of groups of cockpit crew members. For brevity, we call a group of cockpit crew members as a cockpit crew.
Given the minimum set of cockpit crew pairings and the set of cockpit crews, with cardinality n and m, respectively, we assume that there are DM days in the month to consider. We define the decision variable ,which has value 1 if pairing i is served by cockpit crew j, and 0 otherwise. We define some parameters, listed in Section 7 (Nomenclature). For readability, we also define the following functions of some constraints.
For i = 1, ..., n and j = 1, ..., m, define
\[nt_{i}(j) = t_{i} - \sum_{i_{1}=i+1}^{n} x_{i_{1},j} \ p_{i,i_{1}}\] (1)
The value of \(nt_i(j)\) counts the number of working days that cockpit crew j takes if it is assigned to pairing i, excluding the (possible) overlapping working day due to assignment to another pairing. As an illustration, suppose that cockpit crew j is assigned to pairing 1, which starts on day 1 and ends on day 2; and pairing 4, which starts on day 2 and ends on day 5. Both pairings overlap on day 2. We get \(nt_i(j) = 2 - 1 = 1\). The number of working days on day 2 is calculated in \(nt_4(j)\) where its value can be established once we know the other pairings assigned to cockpit crew j. With this function, we can avoid the double counting-error regarding working day 2 that we found in [1]. This parameter will be used later for calculating the (net) number of working days of the cockpit crews.
In order to obtain a feasible roster, the following constraints must be satisfied.
a. Each pairing must be served by exactly one cockpit crew
For \[i = 1, ..., n\]
\[\sum_{i=1}^{m} x_{i,j} = 1. (2)\]
b. No-overlap constraint between two pairings assigned to one cockpit crew
For \[i = 1, ..., (n - 1)\] and \(j = 1, ..., m\),
\[x_{i,j} \sum_{i,j=i+1}^{n} x_{i,j} s_{i,i_1} = 0.\] (3)
c. For each cockpit crew, the accumulative flight time during a certain time period may not exceed the maximum accumulative flight time
For \[j = 1, ..., m\] and \(d = 1, ..., DM\),
\[\sum_{i=1}^{n} x_{i,j} \sum_{l=d}^{d+6} ft_{i,l} \le M_1.\] (4)
\[\sum_{i=1}^{n} ft_i x_{i,j} \le M_2. \tag{5}\]
\[\sum_{i=1}^{n} ft_i x_{i,j} \le M_2. \tag{6}\]
\[\sum_{i=1}^{n} ft_i x_{i,j} \le M_4 - aft_{j,y}. \tag{7}\]
Constraint (4) expresses the flight time limitation on seven consecutive days, constraint (5) expresses the monthly flight time limitation, while (6) and (7) ensure that the assignment in the month under consideration will not violate flight time limitations in three consecutive calendar months and in one calendar year, respectively.
d. One day off after an assignment in the last six consecutive working days
For j = 1, ..., m, and d = 1, ..., DM - 6,
\[\sum_{i=1}^{n} x_{i,j} \sum_{l=d}^{d+6} q_{i,l} \min \{ nt_i(j), p+6-(l-1) \} \le 6.\] (8)
This expression is a correction of a similar constraint in [1], which for the Garuda Indonesia case will be given by:
\[\sum_{i=1}^{n} x_{i,j} \sum_{l=d}^{d+6} q_{i,l} \ t_{j} \le 6.\] (9)
We use \(min \{nt_i(j), p + 6 - (l - 1)\}\) instead of \(t_j\), for the following two reasons. Firstly, the use of \(t_j\) will lead to a double-counting error in the calculating process of the cockpit crews' working days. This can occur on a certain day when a cockpit crew is assigned to two different pairings on that same day, as illustrated in the example right after the definition of \(nt_i(j)\). Secondly, we need to use the minimum of \(nt_i(j)\) and the number of days to go to the end of the time period under consideration as the net number of working days cockpit crew j takes if it carries out pairing i.
e. Minimum of eight days off in one month
For \[j=1,\ldots,m\],
\[\sum_{i=1}^{n} x_{i,j} \, nt_i(j) \le DM - 8. \tag{10}\]
Note that the function \(nt_i(j)\) is used in the expression above for the reason explained in (d).
f. 18 hours of rest time after a minimum of 24 flying hours in three consecutive days
For j = 1, ..., m and d = 1, ..., DM - 2,
\[\left(\sum_{i=1}^{n} x_{i,j} \sum_{l=d}^{d+2} ft_{i,l} - 24\right) \left(\sum_{i=1}^{n} \sum_{i_1 \in J_d}^{n} x_{i_1,j} (q_{i,(d+3)} - 1)(w_{i,i_1} - 1)\right) \ge 0,\] (11)
where \(J_d\) is the set of pairings that starts on day d+3 or later. For j=1,...,m, the first term of the left-hand side of (11) has a non-negative value if during three consecutive days starting on day d, the cockpit crew j each have an accumulative flight time of more than 24 hours. If this is the case, we have to make sure that they take a minimum of 18 hours rest time. Since the maximal flight time in one day is nine hours, they had a maximum of 18 hours flight time on days 1 and 2, therefore on the third day the cockpit crews have flown at least six hours. Taking the minimum 18 hours of rest time means that the next pairing assigned to them will start on the fourth day. This is why in the second term of the left-hand side of (11) we only consider the pairings that start on the fourth day, which is denoted by \(J_d\).
g. Each cockpit crew gets \(l_{d_1}\) days off after assignment to a long AFB pairing
For i = 1, ..., n, and j = 1, ..., m
\[x_{i,j}to_{i,d_1}\sum_{l=1}^{DM}q_{i,l}\sum_{i_1=i+1}^{n}\sum_{l_1=d_1}^{d_1+l_{d_1}-1}q_{i,l+l_1}x_{i_1,j}=0,\] (12)
where \(d_1\) is the length of the AFB pairing. Its value and the length of the days off following the pairing are described in Table 1.
\[x_{i,j}to_{i,d_1} \sum_{l=1}^{DM} q_{i,l} \sum_{l_{1=1}}^{d_1+l_{d_1}-1} me_{j,l+l_1} = 0,\] (13)
\[x_{i,j}to_{i,d_1} \sum_{l=1}^{DM} q_{i,l} \sum_{l=1}^{d_1+l_{d_1}-1} tr_{j,l+l_1} = 0.\] (14)
h. Each cockpit crew gets \(L_{d_2}\) day-off after attending training, courses, seminars or activities other than flight duty
For \[j = 1, ..., m, l = 1, ..., DM\],
\[\left(\sum_{l_{1=l}}^{l+d_2-1} \left(me_{j,l} + tr_{j,l}\right) - d_2 + 1\right) \left(\sum_{i=1}^{n} \sum_{l_1=1}^{L_{d_2}} x_{i,j} \ q_{i,l+d_2+l_1}\right) \le 0, \quad (15)\] where \(d_2\) is the length of the activity.
i. No assignment on days of training
For i = 1, ..., n and j = 1, ..., m,
\[\sum_{l=1}^{DM} x_{i,j} \, tr_{j,l} c_{i,l} = 0. \tag{16}\]
j. No assignment on days of medical examination
For i = 1, ..., n and j = 1, ..., m,
\[\sum_{l=1}^{DM} x_{i,j} \, m e_{j,l} c_{i,l} = 0. \tag{17}\]
k. No assignment on days of annual leave
For i = 1, ..., n and j = 1, ..., m,
\[\sum_{l=1}^{DM} x_{i,j} \, al_{j,l} c_{i,l} = 0. \tag{18}\]
The input parameters \(tr_{j,l}, me_{j,l}\) and \(al_{j,l}\), for \(j=1,\ldots,m\), must satisfy the following conditions:
\[\sum_{l=1}^{DM} me_{j,l} \le me_j - ame_j, \tag{19}\]
\[\sum_{l=1}^{DM} tr_{j,l} \le tr_j - atr_j, \tag{20}\]
\[\sum_{l=1}^{DM} al_{j,l} \le al_j - aal_j, \tag{21}\]
\[\sum_{l=1}^{DM} me_{j,l} + tr_{j,l} + al_{j,l} = 1.\] (22)
Satisfaction of constraints (19), (20), and (21) means that a cockpit crew's planned medical examination, training and annual leave do not violate regulations. Constraint (22) ensures that in one day a cockpit crew can only be at a training or a medical examination or on annual leave. We can check the satisfaction of these constraints before we proceed to solve the optimization model that will be presented in the following, to that ensure we have proper input for the optimization model.
The ideal average monthly flight time of each cockpit crew is
\[W = \frac{\sum_{i=1}^{n} ft_i}{m}.\] (23)
The average relative deviation of the monthly flight time from the ideal average flight time is then given by
\[D(\mathbf{x}) = \frac{\sum_{j=1}^{m} \left| \left( \sum_{i=1}^{n} f t_i x_{ij} - W \right) \right|}{m},\] (24)
where x is a vector with elements \(x_{i,j}\), i = 1, ..., n, j = 1, ..., m
The crew rostering problem can then be written as minimize \(D(\mathbf{x})\)
subject to (2) - (22),
\[x_{i,j} = 0 \text{ or } 1, i = 1, ..., n, j = 1, ..., m\] (25)
where \(D(\mathbf{x})\) is given in (24). Note that the deviation \(D(\mathbf{x})\) is only one of many measures of fairness among cockpit crews. We can choose other measures, such as the deviations proposed in [1], as the objective function without loss of generality. We can also choose the deviation and the crews' cost as the objective functions, so that the optimization model becomes a multi-objective optimization model.
4 Solution Method
The optimization problem (25) can be solved with several solution methods. We have used simulated annealing, because we think that heuristic methods are more efficient compared to exact methods and because simulated annealing is very easy to apply to our optimization problem.
Each iteration of the simulated annealing algorithm has to produce a feasible roster. For constructing a feasible roster, we use the pairing-by-pairing method as described in the following. This algorithm mimics the pilot-by-pilot method in [1], whereby we exchange the position of the pairings and the cockpit crews from the pilot-by-pilot method. We think the pairing-by-pairing method can be used to determine a feasible roster more efficiently compared to the pilot-bypilot method if the set of cockpit crew pairings is sorted with respect to the departure times from the earliest to the latest. We try to assign the first pairing to a certain cockpit crew that is available, then we try to assign the second pairing to another cockpit crew, and so on. With this approach, the sequence of pairings that is assigned to a certain cockpit crew will be a sequence of pairings sorted with respect to departure time. Therefore, when attempting to assign another pairing to the candidate cockpit crew, checking satisfaction of a number of constraints related to labor regulations on a certain number of consecutive days does not have to happen from the first day of the month, but only from a specific day prior to the last pairing that has been assigned to the candidate cockpit crew. The efficiency of our method comes from this process.
The pairing-by-pairing method comprises of the following steps:
Algorithm Pairing-by-Pairing
Step 1. k = 1.
Step 2. Assign pairing k to a specific cockpit crew randomly chosen from the list of cockpit crew except the cockpit crew assigned to pairing k-1, such that all constraints are satisfied.
Step 3. k = k + 1.
Step 4. If k > n, stop. Otherwise go to Step 2.
We can refer to [1] for a brief explanation of the application of simulated annealing for the optimization of rostering problems.
5 Numerical Results
We have tested the optimization problem for all classes of cockpit crews of Garuda Indonesia and obtained satisfactory rosters in a short amount of time. Here, we present the results of the application of our model to an Airbus 330 cockpit crew for the winter 2010 schedule. The rostering of this class of cockpit crew is challenging since most of the pairings are multi-day pairings. In the instant month, there are 287 cockpit crew pairings, one of them is a six-day pairing in which the cockpit crews assigned to such a pairing must have three days off after the assignment, and 21 of them are five-day pairings in which the cockpit crews assigned to such a pairing must have two days off after the assignment.
The total flight time of all pairings is 3012.5 hours. There are 43 cockpit crews to carry out all pairings. The ideal average monthly flight time is 70.05 hours, which is less than the maximum accumulative flight time for one month.
We are given the cockpit crew's plans for medical examination, training, annual leave and (mandatory) days off as described in Table 3, 4, and 5.
Table 3 Cockpit crew's plans for medical examination.
| Crew Number | Start Day of Medical Examination | Length of Medical Examination |
|---|---|---|
| 8 | 11 | 1 |
| 12 | 16 | 1 |
| 16 | 23 | 1 |
| 20 | 31 | 1 |
| 26 | 9 | 1 |
| 33 | 17 | 1 |
Table 4 Cockpit crew's plan for training.
| Crew Number | Start Day of Training | Length of Training |
|---|---|---|
| 3 | 23 | 2 |
| 16 | 5 | 3 |
| 29 | 23 | 2 |
| 39 | 5 | 3 |
Table 5 Cockpit crew's plans for annual leave.
| Crew Number | Start Day of Annual Leave | Length of Anual Leave |
|---|---|---|
| 1 | 8 | 1 |
| 2 | 26 | 1 |
| 3 | 29 | 1 |
| 4 | 19 | 1 |
| 5 | 12 | 1 |
The total flight time and days off in the instant month are shown in Table 6 and day-to-day assignments are shown in Figure 1.
| Crew | Day | 8 | |||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Number | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 3] |
| 1 | 39 | 39 | 39 | 39 | AL | AL | AL | 117 | 117 | 117 | 164 | 164 | 164 | 164 | 213 | 239 | 239 | 239 | 239 | 239 | |||||||||||
| 2 | 40 | 40 | 70 | 70 | 70 | 127 | 127 | 151 | 151 | 151 | 183 | 235 | 235 | 235 | AL | AL | |||||||||||||||
| 3 | 43 | 43 | 43 | 43 | 96 | 96 | 121 | 121 | 121 | _ | 156 | 156 | 2 2 | 199 | T | T | 269 | 269 | AL | AL | L | ||||||||||
| 4 | 1 | 53 | 53 | 53 | 89 | 89 | 89 | 132 | 165 | 165 | 8 | AL | AL | AL | AL | 245 | 245 | 265 | L | L | |||||||||||
| 5 | 23 | 23 | 23 | Week. | T G S | 84 | 84 | 10.70 | lovo S | AL | AL | AL | 171 | 171 | 171 | 171 | 900000 | 237 | 237 | AN 2000 | 267 | 267 | |||||||||
| 6 | 26 | 26 | 26 | 26 | 26 | 100 | 100 | 100 | - | 100 | 190 | 190 | 190 | 233 | 233 | 250 | 250 | - | _ | ||||||||||||
| 7 | 34 | 34 | 34 | 34 | 8 | 105 | 105 | 105 | 149 | 234 | 9 9 | 258 | 258 | 258 | L | ||||||||||||||||
| 8 | - | 17 | 54 | 54 | 54 | 54 | 95 | 95 | ME | 129 | 129 | 129 | 129 | 179 | 179 | 179 | 212 | 212 | 253 | 253 | 100 | - | |||||||||
| 9 | - | 15 | 15 | 888 | 57 | 57 | 57 | San Alice | 93 | 93 | 93 | 1,00000 | 136 | 2000 | 136 | Service Si | 180 | 180 | Summer | - | 227 | 227 | 259 | · V 3 3 3 3 3 3 | 259 | 259 | - | - | |||
| 10 | _ | 29 | 29 | 29 | 66 | 66 | 66 | 109 | 109 | 109 | 138 | 172 | 172 | 172 | 172 | - | 224 | 224 | 224 | - | _ | ||||||||||
| 11 | 8 | 8 | 8 | 50 | 50 | 74 | 74 | 74 | 115 | 115 | 143 | 143 | 159 | 2 0 | 188 | 188 | 207 | 251 | 251 | 284 | |||||||||||
| 12 | 5 | 5 | 5 | 10 | ** | 59 | 59 | 70 | 91 | 0.7 | 122 | 122 | 122 | * 40 | ME | 1.10 | 194 | 194 | 194 | 216 | 247 | 247 | 247 | 261 | 286 | 286 | 28 | ||||
| 13 | 13 | 13 | 13 | 13 | _ | 78 | 97 | 97 | 97 | 100 | 140 | 140 | 140 | 140 | - | 175 | 170 | 216 | 10000 | 222 | 264 | 264 | 287 | 287 | 287 | 287 | 20 | ||||
| 14 | 3 | 3 | 3 | 3 | 3 | 10 | - | 00 | 102 | 102 | _ | 102 | 102 | 100 | 175 | 1/5 | 222 | 222 | 222 | 222 | 280 | 280 | 280 | 280 | 28 | ||||||
| 15 | 2 | 2 | 25 | 25 | 49 m | 49 T | Т | 82 | 82 | 82 | 123 | 123 | 2 - 5 | 117 | 1.47 | 169 | 1000000000 | 169 | 204 | 204 | 230 | 251 | 275 | 275 | |||||||
| 16 | - | 25 | 25 | 25 | T | T | 1 | C1 | 98 | 98 | 98 | 124 | 124 | 147 | 147 | 167 | 1 1 | 174 | 100 | 200 | 214 | 1 | Same? | 254 | 254 | 205 | 205 | 205 | 205 | ||
| 17 | 18 | 27 | - | 48 | 61 48 | 61 | 83 | 101 | 101 99 | 99 | 154 | 134 142 | 142 | 167 | 167 177 | 189 177 | 201 | 209 | 209 | 240 242 | 240 242 | 240 242 | 272 | 273 | 285 | 283 | |||||
| 19 | 18 | 18 28 | 28 | 48 | 62 | 62 | 62 | 103 | 108 | 108 | 142 | 146 | 146 | 146 | 1// | 184 | 184 | 201 | 219 | 219 | 2/3 | 2/3 | 2/3 | - | |||||||
| 20 | 35 | 35 | 35 | 0.2 | 02 | 80 | 80 | 111 | 111 | 111 | - | 144 | 157 | 157 | 104 | 104 | 211 | 219 | 219 | 211 | 419 | 281 | 281 | 281 | М | ||||||
| 21 | 7 | 7 | 7 | 33 | 56 | 56 | 56 | 80 | 92 | 92 | 118 | 157 | 137 | 137 | 196 | 186 | 211 | 226 | 226 | 226 | 282 | 202 | IVL | ||||||||
| 22 | 9 | 9 | _ | 30 | 60 | 60 | 79 | 79 | 79 | 110 | 2492009 | 133 | V-12 | 133 | - | 187 | 187 | 187 | 220 | 243 | 243 | 243 | 243 | 202 | 202 | 202 | 202 | ||||
| 23 | , | , | 42 | 42 | 42 | 72 | 72 | 72 | 12 | 124 | 124 | 124 | 124 | 133 | 170 | 170 | 107 | 101 | 107 | 232 | 232 | 232 | 271 | 271 | 271 | ||||||
| 24 | 36 | 36 | 36 | 36 | 87 | 87 | 110 | 110 | 110 | 127 | 158 | 158 | 158 | 10000000 | 229 | 252 | 252 | 252 | |||||||||||||
| 25 | 22 | 22 | - | 63 | 75 | 75 | 75 | -10 | 116 | 116 | 154 | 154 | 154 | 150 | W | 210 | 257 | Sec. 3 | 278 | 278 | |||||||||||
| 26 | 6 | 6 | 44 | 44 | - | 555 | 114 | 125 | 125 | 161 | Same | 161 | - | 197 | 197 | 231 | 231 | 231 | 263 | ||||||||||||
| 27 | 37 | 55 | 55 | 55 | 55 | 126 | 126 | 160 | 220 | 220 | 220 | 220 | |||||||||||||||||||
| 28 | 12 | 12 | 12 | 12 | 65 | 65 | 65 | 65 | 65 | 137 | 137 | 10001010 | 178 | 178 | 206 | 0.000 | 100000 | 249 | 249 | 249 | 249 | 249 | |||||||||
| 29 | 10 | 10 | 46 | 46 | 46 | 69 | 69 | 69 | 131 | 131 | 131 | 162 | 162 | 200 | 200 | 200 | T | T | 266 | ||||||||||||
| 30 | 30 | 30 | 30 | 71 | 71 | 107 | 107 | 130 | 130 | Sec. 1 | 130 | 182 | 182 | 182 | 182 | 228 | 228 | 261 | 261 | 261 | 261 | ||||||||||
| 31 | 24 | 24 | 24 | 67 | 81 | 81 | 81 | 119 | 119 | 150 | 150 | 150 | 205 | 205 | 246 | 246 | 246 | ||||||||||||||
| 32 | 31 | 31 | 58 | 58 | 58 | 58 | 106 | 106 | 106 | 139 | 139 | 139 | 203 | 203 | 203 | 203 | 241 | 241 | 277 | 277 | 277 | ||||||||||
| 33 | 32 | 32 | 52 | 52 | 68 | 68 | 112 | 112 | 112 | 112 | ME | 195 | 195 | 195 | 244 | 244 | 262 | 262 | 262 | ||||||||||||
| 34 | 20 | 20 | 20 | 20 | 77 | 77 | 77 | 77 | 77 | 168 | 168 | 192 | 208 | 208 | 208 | 256 | 256 | 279 | 279 | 279 | |||||||||||
| 35 | 4 | 4 | 4 | 45 | 45 | 76 | 76 | 76 | 76 | 128 | 128 | 128 | 173 | 173 | 218 | 218 | 218 | 218 | 272 | 272 | |||||||||||
| 36 | 41 | 41 | 41 | 86 | 86 | 86 | 86 | 135 | 135 | 163 | 163 | 163 | 185 | 185 | 185 | 225 | 225 | 270 | 270 | 270 | 270 | ||||||||||
| 37 | 38 | 85 | 85 | 85 | 145 | 145 | 145 | 198 | 198 | 221 | 221 | 221 | 268 | 268 | 283 | 283 | 283 | ||||||||||||||
| 38 | 21 | 21 | 64 | 64 | 64 | 113 | 113 | 141 | 141 | 141 | 196 | 196 | 196 | 196 | 255 | 255 | 255 | ||||||||||||||
| 39 | 19 | 19 | 19 | T | T | T | 90 | 90 | 90 | 90 | 148 | 148 | 148 | 191 | 191 | 191 | 223 | 223 | 223 | 223 | 223 | Ĺ | |||||||||
| 40 | 11 | 11 | 11 | 47 | 47 | 47 | 88 | 88 | 88 | 88 | 88 | 166 | 166 | 166 | 166 | 193 | 193 | 236 | 236 | 236 | 236 | 276 | 276 | L | |||||||
| 41 | 14 | 51 | 51 | 51 | 94 | 94 | 94 | 94 | 152 | 152 | 152 | 152 | 202 | 202 | 202 | 238 | 274 | 274 | 274 | 274 | 274 | ||||||||||
| 42 | 16 | 16 | 16 | 16 | 16 | 104 | 120 | 120 | 155 | 176 | 176 | 176 | 217 | 217 | 248 | 248 | 248 | ||||||||||||||
| 43 | 33 | 33 | 33 | 73 | 73 | 73 | 73 | 73 | 153 | 153 | 181 | 181 | 181 | 215 | 215 | 215 | 260 | 260 | 260 | l. |
Figure 1 Day-to-day assignment.
We can see in Figure 1 that every cockpit crew that is assigned to a five-day pairing (pairings no. 3, 16, 23, 65, 73, 77, 88, 100,102, 140, 149, 158, 171, 211, 219, 220, 223, 224, 239, 249, 274, 288) has two days off after the assignment. In the next month, two days off must be given to cockpit crew 11 and three days off must be given to cockpit crew 14 after assignment to pairings 286 and 280, respectively. These mandatory days off must be considered as input for the next month's rostering.
| Table 6 | The total flight time and days off. |
|---|
| Crew Number | Total Flying Time | Total Days Off | Crew Number | Total Flying Time | Total Days Off |
|---|---|---|---|---|---|
| 1 | 45,3 | 11 | 23 | 80,3 | 12 |
| 2 | 59,9 | 15 | 24 | 54,5 | 10 |
| 3 | 73,3 | 10 | 25 | 77,6 | 10 |
| 4 | 52,3 | 10 | 26 | 49,7 | 13 |
| 5 | 53,2 | 13 | 27 | 66,4 | 15 |
| 6 | 54,1 | 13 | 28 | 64,6 | 10 |
| 7 | 67,4 | 14 | 29 | 79,5 | 9 |
| 8 | 66,1 | 11 | 30 | 75,0 | 10 |
| 9 | 91,9 | 10 | 31 | 77,0 | 14 |
| 10 | 60,0 | 14 | 32 | 80,6 | 10 |
| 11 | 78,4 | 8 | 33 | 58,4 | 12 |
| 12 | 84,1 | 10 | 34 | 71,6 | 11 |
| 13 | 80,0 | 9 | 35 | 68,5 | 11 |
| 14 | 48,2 | 8 | 36 | 77,4 | 10 |
| 15 | 78,5 | 12 | 37 | 78,9 | 13 |
| 16 | 61,0 | 12 | 38 | 76,7 | 14 |
| 17 | 78,3 | 10 | 39 | 52,0 | 10 |
| 18 | 88,5 | 10 | 40 | 70,7 | 8 |
| 19 | 72,9 | 13 | 41 | 92,9 | 9 |
| 20 | 68,4 | 10 | 42 | 58,7 | 14 |
| 21 | 80,5 | 8 | 43 | 83,3 | 12 |
| 22 | 74,4 | 13 |
If we use the expressions in [1] for constraints (8) and (9), instant testing becomes infeasible. This means that the schedule cannot be carried out by 43 cockpit crews. This proves that the mathematical expressions (8) and (9) are correct and with these expressions we can obtain compact rosters.
6 Conclusion
In this paper, an optimization model for the cockpit crew rostering problem at Garuda Indonesia was presented. The optimization problem has a large number of constraints that represent international, regional, national and internal cockpit crew labor regulations. Some of the constraints have a non-linear form, so that the optimization problem is a large-size non-linear binary problem that needs an appropriate solution method. We have applied a simulated annealing method for solving the problem, where feasible rosters are constructed by applying a random method called pairing-by-pairing. The satisfactory roster presented in Figure 1 was obtained in a short amount of computing time, although we realize that some techniques can be added in order to make the pairing-by-pairing method run more efficiently. For example, making a list of constraints from the hardest to the easiest (in satisfying), and performing the pairing-by-pairing method in such a way that in assigning a cockpit crew pairing to a candidate cockpit crew we check satisfaction of the hardest constraint first, then if it is satisfied we proceed to checking satisfaction of the next constraint in the list, and so on.
Nomenclature
For = 1, … , ,
1, if cockpit crew starts annual leave on day , alj,l = / 0, otherwise
aalj = The accumulative number of days of annual leave that have been taken by cockpit crew j
aftj,2 = The accumulative flight time of cockpit crew j during the two previous months
aftj,y = The accumulative flight time of cockpit crew j during the current year
amej = The accumulative days of medical examination that have been taken by cockpit crew j
atrj = The accumulative days of training that have been taken by cockpit crew j 1, if pairing covers on day , ci,l = / 0, otherwise
fti = The total flight time of pairing i
fti,l = The net flight time of pairing i on its lth day 1, if cockpit crew starts medical examination on day ,
-, = / 0, otherwise
M1 = The maximum accumulative flight time in seven consecutive days M2 = The maximum accumulative flight time in one calendar month
M3 = The maximum accumulative flight time in three consecutive
calendar months
M4 = The maximum accumulative flight time in one calendar year
(1, if pairing i_1 and i_2 have a common working day,
p_{i_1,i_2}
(0, otherwise
(1, if pairing i is started on day l,
q_{i,l}
(0, otherwise
(1, if pairing i_2 starts earlier than the end of pairing i_1 plus
the lay over time,
S_{i_1,i_2}
0. otherwise
The number of days covered by pairing i
t_i
(1, if cockpit crew j starts training on day l,
tr_{i,l}
=
0, otherwise
(1, if pairing i covers d working days
to_{i,d}
(0, otherwise
(1, if pairing i_2 starts earlier than the end of pairing i_1 plus
the lay over time,
S_{i_1,i_2}
(0, otherwise
(1, if the time difference between the end of pairing i_1 and
the beginning of pairing i_2 at least 18 hours,
(0. otherwise
Acknowledgements
This research was funded by Hibah Desentralisasi ITB 2013 and Garuda Indonesia. The authors thank to Garuda Indonesia and the research assistants that were involved for their committed work during the research.