Keywords

1 Introduction

Affected by the policy of restricting travel due to epidemic, the whole civil aviation industry is facing serious challenges. In particular, as an important part of operating costs, crew labor costs affect the market competitiveness of the airline. Moreover, the disruption of circadian rhythms usually leads to a decrease in crew alertness along with weakened decision abilities [1]. Therefore, airlines should try to take into account the preferences of the crew and balance their workload. This paper tries to present the crew rostering problem (CRP) from the crews’ perspective by balancing the relationship between crew satisfaction and fairness.

Many studies have previously explored fairness and satisfaction metrics. Fairness refers to the balanced distribution of all crews and pairings. Doi et al. [2] regarded the sum of the deviation of each crew members’ working hours from the standard working hours as a evaluation of fairness. De Armas et al. [3] also used working hours as a metric of work balance and introduced three criteria. However, simply using flight time to measure fairness is not comprehensive. Therefore, two attributes were additionally considered in Zhou et al. [4], including duty time and overnight time far away from base, to better reflects the degree of balance in workload distribution. In terms of satisfaction, Gamache et al. [5] argued that a series of weighted bids reflecting crew preferences should be added when obeying the relevant regulations. Dawid et al. [6] suggested taking crew members’ preferences such as days off when setting work lines. Kasirzadeh et al. [7] set a constraint on the lower limit of the number of crews’ preferred flights and vacations. Based on the above analysis, this paper tries to utilize crews’ preferred flights and vacations to describe satisfaction.

Since CRP is a NP-hard problem, evolutionary algorithm is one of the potential solvers. For example, Ezzinbi et al. [8] proposed to use PSO algorithm to build CRP model and it had better relatively performance compared to GA algorithm. Banerjee et al. [9] extended the existing non-dominated ranking genetic algorithm (NSGA-II) with interval fitness and column exchange crossover and mutation. Nevertheless, single improved algorithm is limited by the underlying theoretical and algorithmic framework. It is difficult to present an optimization algorithm based on natural mechanisms. Therefore, algorithm hybridization is the preferred method to improve algorithm performance. Shi et al. [10] used the hybrid PSO-GA optimization algorithm in determining biomass pyrolysis kinetics. Sun et al. [11] proposed a distributed cooperative evolutionary algorithm for the flexible job shop scheduling problem by combining GA and PSO. The chromosome crossover and mutation of GA are employed to update individual particles.

However, the above two hybrid strategies have some defects. They ignore the relationship between information sharing among particles and the convergence speed acceleration. Moreover, in some variants of PSO, barebones particle swarm optimization (BBPSO) [12] only utilized to update the position of particles without velocity. In this study, we tried to add BBPSO algorithm in the framework of NSGA-II to accelerate convergence speed. The contributions of this study are listed as follows:

  1. (1)

    The initial solutions are generated randomly according to one of the important time constraints of CRP. And a penalty function is added to the two fitness functions to reduce the feasible domain boundary.

  2. (2)

    The hybrid multi-objective genetic-particle swarm optimization algorithm, abbreviated as hMOBBPSO-GA, is proposed based on BBPSO. Selection operation is improved to avoid premature maturation of individuals. And BBPSO is embedded in NSGA-II as a mutation operator to accelerate convergence speed.

  3. (3)

    We bridge the gap between problem and algorithm through integer and binary encoding.

The remaining of this paper is arranged as follows. In Sect. 2, we introduce CRP mathematical model containing the definition of CRP, airline regulations and the objective function. In Sect. 3, we specify the improved algorithm process and coding methods. Section 4 presents the simulation experiments and the experimental results compared with other algorithms. Finally, in Sect. 5, we provide the conclusion and point out the directions for future research improvements.

2 Problem Definition and Formulation

In this section, CRP model is thoroughly studied. Firstly, the relative definitions of models are explained. Then a specific expression is presented according to the definition of the objective function. Finally, the time constraints are proposed based on the requirements of CCAR121-R5 document [13].

2.1 Notations

The definitions of symbols used in CRP are listed as follows:

2.2 Problem Description

We use \(({{s}}_{{j}} \user2{,e}_{{j}} \user2{,f}_{{j}} \user2{,d}_{{j}} \user2{,o}_{{j}} )\) as the attributes of pairings, where j denotes the number of pairings. In this model, the other three attributes need to be preprocessed to gain the flight time \({{f}}_{{j}}\), duty time \(d_{{j}}\), and departure overnight time \({{o}}_{{j}}\). The required attribute values can be calculated according to the related definitions in Fig. 1.

Fig. 1.
figure 1

Schematic diagram of attribute calculation for the pairing

Full size image

In the CRP model, \(({{pf}}_i, {pv}_i, {cf}_i, {cd}_i, {co}_i )\) represents the attributes of the crew members. The first two attributes denote the crew members’ preferred flights and preferred holidays, respectively. In this study, crew members’ preferred flights are associated with their bases, which generally means that crew members prefer flights that are based at the departure or arrival airport. It saves time for positioning and avoids additional workload. There are two ways to improve crew satisfaction. One is to assign pairings of the preferred flight to the corresponding crew member. The other is to avoid assignments during preferred holidays.

2.3 Objective Formulation

Unlike most existing crew rostering problem models that consider cost in the airline’s perspective, we propose a model that takes into account both fairness and satisfaction goals in the crews’ perspective [4]. Since standard deviation is the most commonly used index to measure the workload balance of different members, we calculate the deviation of three time indicators from the average values of crews to determine the fairness and is expressed as:

$$ g_1 (X) = \sqrt {\frac{1}{E}\sum_{i \in E} {dev_i } } $$
(1)

where

$$ dev_i = (cf_i - \overline{f})^2 + (cd_i - \overline{d})^2 + (co_i - \overline{o})^2 $$
(2)
$$ cf_i = \sum_{j = 1}^{n_i } {\hat{f}_{i,j} } $$
(3)
$$ cd_i = \sum_{j = 1}^{n_i } {\hat{d}_{i,j} } $$
(4)
$$ co_i = \sum_{j = 1}^{n_i } {\hat{o}_{i,j} } $$
(5)
$$ \overline{f} = \frac{1}{{\text{E}}}\sum_{i \in E} {cf_i } $$
(6)
$$ \overline{d} = \frac{1}{E}\sum_{i \in E} {cd_i } $$
(7)
$$ \overline{o} = \frac{1}{E}\sum_{i \in E} {co_i } $$
(8)

In this manuscript, the sum of the percentage of preferred flights and preferred vacation being satisfied is applied to represent the satisfaction of the pairing assignments of the crews. And the satisfaction function is expressed as:

$$ g_2 (X) = \frac{sppn}{{PPN}} + \frac{sapn}{{APN}} $$
(9)

To facilitate subsequent model evaluation as well as calculation, it is turned into two minimization bi-objective problems. The specific objectives are defined as:

$$ optimize \, G(X) = \left\{ \begin{gathered} \min \, g_1 (X) \hfill \\ \min { 2 - }g_2 (X) \hfill \\ \end{gathered} \right. $$
(10)

2.4 Constraints Formulation

As we known, the scheduling must meet the regulations of CAAC and airlines. And the assignments distributed to each set of crew should meet the requirements of transit time connection and the limit of worktime, which ensures the best working condition of the crew for rest and related preparations.

  1. (1)

    Specifically, the rest time between two backward and forward connected pairings assigned to the same crew member should not be less than 10 h.

    $$ \hat{s}_{i,j + 1} - \hat{e}_{i,j} \ge 10,\forall i \in \{ 1,2,...,CN\} \, \forall j \in \{ 1,2,...,n_i - 1\} $$
    (11)
  1. (2)

    No crew member can fly more than 100 h in any one natural month.

    $$ \sum_{d = 1}^{30} {cfd_{d,i} \le 100,\forall i \in \left\{ {1,2,...,CN} \right\}} $$
    (12)
  1. (3)

    The cumulative time on duty cannot exceed 60 h in any seven consecutive natural days.

    $$ \sum_{d = 1 + k}^{7{ + }k} {cdd_{d,i} \le 60,\forall i \in \left\{ {1,2,...,CN} \right\}} \, \forall k \in \left\{ {1,2,...,23} \right\} $$
    (13)
  1. (4)

    Cumulative duty time cannot exceed 210 h in any one natural month.

    $$ \sum_{d = 1}^{30} {cdd_{d,i} \le 210,\forall i \in \left\{ {1,2,...,CN} \right\}} \, $$
    (14)
  1. (5)

    Each crew member should be scheduled for at least 48 consecutive hours of rest during 144 h prior to the flight mission. The constraint formula is Eq. (15), where \({{checkRest}}_{{{i}}{.j}}\) is an indicator of whether the crew member’s \(j^{th}\) pairing satisfies this requirements and \(rest_{i,j,k}\) is used to check whether the rest time of crew member satisfies a minimum of 48 consecutive hours during the 144-h period prior to the start of the \(j^{th}\) pairing.

    $$ \sum_{j = 2}^{n_i } {checkRest_{i,j} = 0,\forall i \in \left\{ {1,2,...,CN} \right\}} $$
    (15)

where

$$ checkRest_{i,j} { = }\left\{ {\begin{array}{*{20}c} {1,if\sum\nolimits_{k = 0}^{j - 1} {rest_{i,j,k} = 0} } \\ {0,if\sum\nolimits_{k = 0}^{j - 1} {rest_{i,j,k} \ne 0} } \\ \end{array} } \right. $$
(16)
$$ rest_{i,j,k} = \left\{ {\begin{array}{*{20}c} {1,if \, \min (\hat{s}_{i,k + 1} - \hat{e}_{i,k} ,\hat{s}_{i,k + 1} - (\hat{s}_{i,j} - 144)) \ge 48} \\ {0,if \, \min (\hat{s}_{i,k + 1} - \hat{e}_{i,k} ,\hat{s}_{i,k + 1} - (\hat{s}_{i,j} - 144)) < 48} \\ \end{array} } \right. $$
(17)

3 Proposed Algorithm for Solving CRP

In this paper, the NSGA-II algorithm is suitably improved to meet the features of the CRP model, including population initialization, genetic operation and coding method.

3.1 Algorithm Flow of NSGA-II

The specific computational process is shown in Fig. 2. And the algorithm runs as follows:

  • Step 1 Population initialization: Generate the initial population.

  • Step 2 Fitness calculation: Calculate the fitness of each chromosome according to the relevant parameters.

  • Step 3 Non-dominated sorting and calculation of crowding degree: The parent population is non-dominated to obtain the frontier sorting value and crowding degree.

  • Step 4 Selection operation: Half of the chromosomes are selected from the parent population according to the tournament mechanism.

  • Step 5 Crossover operation: Generate offspring by randomly generating crossover points.

  • Step 6 Mutation operation: Randomly select a certain number of offspring and randomly change the gene values with a certain probability.

  • Step 7 Merge operation: merge the offspring population with the parent population.

  • Step 8 Fast non-dominated sorting and calculation of crowding degree: Fast non-dominated sorting of the entire population to obtain the frontier sorting value and crowding degree.

  • Step 9 Pareto filtering operation: Based on the ranking value and crowding degree, half of the population is selected to form a sub-population to replace the original population.

  • Step 10 Termination condition: If the number of iterations does not exceed the maximum number of iterations, then go to Step 5; If not, then terminate the evolutionary process.

Fig. 2.
figure 2

Algorithm process of NSGAII

Full size image

3.2 Proposed Algorithm

Fig. 3.
figure 3

Algorithm process of hMOBBPSO-GA

Full size image

The flow of hMOBBPSO-GA is shown in Fig. 3. The red part indicates the improved steps.

3.2.1 Population Initialization

In order to satisfy the constraints related to the solution of the crew rostering problem, the random generation method was not adopted. Instead, we first randomly assign crew members to the first few pairings and ensure that each crew member is matched with one pairing. After that, we roughly select feasible crews for subsequent pairings based on the constraints of Eq. (11). This contributes to the speed and the probability of converging into a feasible solution.

3.2.2 Selection Operator

The purpose of selection is to pick superior individuals from the exchanged population so that they have the opportunity to act as parents to reproduce offspring for the next generation. However, in order to avoid premature convergence and choose individuals with more chances of survival, the following strategy is adopted in this study [14]. First, two individuals are randomly selected from the population. If the random number generated between 0 and 1 is less than the probability r which is usually set to 0.8, then we select the better one; otherwise, we select the worse one. Next the selected individual is released back into the population and can be selected as a parent again.

3.2.3 BBPSO-Based Mutation Operator

Based on the idea that position updating of particle swarm can be treated as a mutation operation [15], together with the fact that the velocity vector in the standard PSO cannot match with the individuals after the genetic operation, position update is designed in Eq. (18) according to the idea of BBPSO.

(18)

where \({{p}}_{{{best}}} ({{k}})\) denotes the individual historical optimal position; \({{g}}_{{{best}}} {(}{{k}}{)}\) represents the global best particle; C(1,0) is the random number generated by the standard Cauchy distribution; k shows the number of current iterations of the population.

$$ \alpha = \alpha_{\min } + {(}\alpha_{\max } - \alpha_{\min } {)} \times k{/}Gn $$
(19)

where \({{\alpha}} \, ({{\alpha}} \in ({0,1}))\) is a control factor. Gn is the maximum number of iterations. \({{\alpha}}_{{{max}}}\) is the maximum of control factor, while \({{\alpha}}_{{{min}}}\) is the minimum of control factor. Larger or smaller values of \({{\alpha}}\) correspond to more discrete or more clustered particle populations, respectively. In this study, a linearly decreasing value of \({\varvec{\alpha}}\) is employed to accelerate the convergence at the early stage of evolution and to improve the probability of escaping the local optimum at the late stage of evolution.

3.3 Coding

Fig. 4.
figure 4

Coding of crew rostering problem

Full size image

To simplify the model, we consider only the allocation of pilots and assume that only one pilot is needed for each flight in our model. For each pairing, only one crew member can be selected among the executable crews. Combining the problem with the characteristics of the genetic algorithm, the solution of the crew rostering problem can be viewed as a sequence of crew members selected for each pairing from the set of available duty crews, as shown in Fig. 4. Each chromosome in the population represents a feasible solution.

In the part algorithm solving steps, we also convert the integer encoding to a fixed-length binary encoding for convenience, as shown in Eq. (20). Specifically, the binary variable expresses whether a crew performs the pairing or not.

$$ x = \left[ {\begin{array}{*{20}c} {x_{1,1} } & {x_{2,1} } & \cdots & {x_{CN,1} } \\ {x_{1,2} } & {x_{2,2} } & \cdots & {x_{CN,2} } \\ \cdots & \cdots & \ddots & \cdots \\ {x_{1,PN} } & {x_{2,PN} } & \cdots & {x_{CN,PN} } \\ \end{array} } \right] $$
(20)

4 Experiments and Comparisons

4.1 Experimental Settings

In this paper, experimental tests are conducted to verify the performance of hMOBBPSO-GA to solve the crew rostering problem based on a real data set. All algorithms are implemented in MATLAB R2021b and run on a computer with an eight-core processor R7-5700U and 16.0 GB RAM. We collected flight data for three routes of China Southern Airlines based at Shenzhen Airport in December 2021. And Table 2 shows a summary of the collected flight data. Meanwhile, the relevant parameters in the improved model are listed in Table 3.

Table 1. The definition of symbols
Full size table
Table 2. Size of instance data
Full size table
Table 3. Parameters setting
Full size table

4.2 Experimental Results

To illustrate the efficiency of our proposed algorithm, MOPSO and NSGA-II are utilized as comparison algorithms. Each of these three algorithms are iterated for 100 generations. We pick out the non-dominated solutions from the results obtained from 10 independent runs and draw Pareto front comparisons against the other algorithms in Fig. 5. Two performance metrics, including hypervolume (HV) and C-metric, are employed for performance evaluations in Table 4 and Table 5. The HV value of hMOBBPSO-GA is significantly higher compared with MOPSO and NSGA-II, which reflects the better convergence and wider range distribution between its non-dominated solutions. In addition, C(hMOBBPSO-GA, NSGA-II) = 1.000 and C(hMOBBPSO-GA, MOPSO) = 1.000 mean that all the non-dominated solutions in NSGA-II and MOPSO are dominated by the non-dominated solutions of hMOBBPSO-GA. The comparisons indicate that solution set from hMOBBPSO-GA covers a wider range and the improved algorithm has better performance.

Fig. 5.
figure 5

Performance of hMOBBPSO-GA, NSGA-II and MOPSO

Full size image
Table 4. Comparison between hMOBBPSO-GA and other algorithms on C-metric
Full size table
Table 5. Comparison of hMOBBPSO-GA with other algorithms on HV
Full size table

5 Conclusion

We propose an improved hybrid algorithm hMOBBPSO-GA based on the idea of BBPSO to solve the crew rostering problem with satisfaction and fairness objectives. The initial solution are generated randomly according to one of the important time constraints of CRP, which efficiently avoids some infeasible solutions and improves the quality of the initial solution. The selection operation of the genetic algorithm is modified to avoid falling into local optimum prematurely. Furthermore, depending on the basic idea of BBPSO, the learning direction is provided for the individual mutation operation to accelerate the convergence of the algorithm. Experiments are conducted on a real-world monthly instance. The results verify the superiority of hBBPSO-GA in solving multi-objective CRP compared against NSGA-II and MOPSO. In the future, we will further consider flight crews with different classes and cabin crews in CRP.