Keywords

1 Introduction

In post Covid-19 era in China, any inevitable imported cases may lead to regional quarantine and circuit breaker mechanisms for airlines. Moreover, abnormal weather may also introduce abnormal situations. It’s vital for airlines to quickly schedule their irregular flights in face of flight delays or cancellations.

According to the Normal Statistical Method of Civil Aviation Flight released by the Civil Aviation Administration of China [1], normal flights refer to those depart 10 min or shorter after scheduled departure time without sliding back, veering or preparing for landing, or arriving within 10 min before scheduled arrival time. And irregular flights refer to those who do not obey the above conditions. When irregular flight occurs, how to quickly recover the flight plan becomes an urgent problem. The irregular flight recovery problem could be separated into several parts, including the route, flight, aircraft, crew and passenger recoveries [2]. In this paper, we mainly focus on the crew recovery problem. The crew recovery serves as a connecting link between the preceding and the following. A good crew recovery plan allows for the perfect implementation of the recovered route and maximizes the convenience of subsequent passenger recovery [3]. If there are problems with crew assignments, the flight route needs to be re-routed. It can cause huge losses to the airline, while also reducing passenger satisfaction with the airline and affecting its reputation. Therefore, airlines need a comprehensive crew recovery system to deal with the negative impact of irregular flights.

In recent years, several scholars have studied this problem in numerous perspectives. Doi et al. [4] and Quesnel et al. [5] separately considered fair working time and crews’ preferences. Antunes et al. [6] focused on the robustness of primary schedules. Sun et al. [7] considered the impact of flying time on the irregular flight. Zhou et al. [8] developed an ant colony system for multiple objectives taking fairness and satisfaction into account. However, those papers indeed take many humanized objectives into consideration, and the measurement of cost and consistency of flights can be further polished. To solve this problem, in our model, we introduced variable costs to lower the complexity of calculation and reflect time-space constraints to embody the continuity of the flight task list.

As the crew recovery problem holds NP-hard characteristics, normal mathematics methods are difficult to get a satisfying solution, especially for the large-scale case. However, heuristic algorithms are outstanding for their large searching scales and fast calculating speed, which exactly fits our requirements. Among the heuristic algorithms, particle swarm optimization is remarkable for its easier implementation and fewer adjustment parameters. Xia et al. [9] proposed triple archives particle swarm optimization to obtain higher solution accuracy and faster convergence speed. Xu et al. [10] and Kiran [11] separately introduced dimensional learning strategy and distribution-based update rule to the primary PSO. Ibrahim et al. [12] combined the slap swarm algorithm with PSO to solve the feature selection problem. Zhang et al. [13] introduced a dynamic neighborhood-based learning strategy and competition mechanism to improve PSO’s performance in solving multi-objective problems. Overall, the improved PSO algorithms have superior performance and they have successfully applied to industrial engineering problems. However, few papers use PSO to solve the crew recovery problem. There is a large research space to solve the crew recovery problem based on a new PSO algorithm. Thus, we purpose an improved PSO combining crossover and mutation mechanisms to solve the crew recovery problem in this paper.

The main contributions of this paper include three aspects. Firstly, crossover and variation mechanisms are introduced to address the problems of traditional PSO and improve the performance of the algorithm. Secondly, to further verify the effectiveness of the new algorithm, the variation mechanism is also led separately for comparison with the improved PSO that introduces both crossover and variation mechanisms. Thirdly, a new coding scheme is established based on the characteristic of the problem and interfaced with the new algorithm.

The remainder of this paper is listed as follows. Section 2 states the model of the crew recovery problem. Section 3 describes the improved particle swarm optimization. Section 4 explains the encoding scheme. Section 5 presents the simulation results against comparative algorithms. Section 6 concludes the paper and points out the future directions (Table 1).

Table 1. Definition of symbols
Full size table

2 Model of Crew Recovery Problem

This section introduces the model of the crew recovery problem. The objective function is described below.

$$ \min z = \sum_{s \in C} {\sum_{m \in T} {v_m^s } }\, x_m^s + \sum_{n \in F} {c_n }\, y_n . $$
(1)

This optimization objective function demands the lowest cost of crew recovery, including (i) the variable cost of two crew tasks; (ii) the cost of canceling one flight. Moreover, constraints (2)–(8) are listed below.

$$ s.t.\sum_{s \in C} {\sum_{m \in T} {b_{nm} \,x_m^s + y_n } = 1} , $$
(2)
$$ \sum_{m \in T} {x_m^s \le 1} ,\forall s \in C, $$
(3)
$$ t_m^s < t_s ,\forall s \in C,\forall m \in T, $$
(4)
$$ t_{n_1 }^m < t_{n_2 }^m ,\forall m \in T,\forall n_1 \in F,\forall n_2 \in F, $$
(5)
$$ a_{n_1 }^m = a_{n_2 }^m ,\forall m \in T,\forall n_1 \in F,\forall n_2 \in F, $$
(6)
$$ x_m^s \in \{ 0,1\} ,\forall s \in C,\forall m \in T, $$
(7)
$$ y_n \in \{ 0,1\} ,\forall n \in F. $$
(8)

Constraint (2) ensures each flight can only be executed by one crew or be canceled. Constraint (3) restricts that each crew can only execute at most one crew task list. Constraint (4) imposes that the total flight time of a crew executing one crew task list must be shorter than the crew flight time regulated by airlines. Constraint (5) restricts that, in the same crew task list, the former flight’s arrival time must be earlier than the latter one’s departure time. Constraint (6) prescribes, in the same crew task list, that the former flight’s arrival airport must be the same as the latter one’s departure airport. Constraints (7)–(8) are the range of decision variables.

3 Improved Particle Swarm Optimization

This section presents the proposed improved particle swarm optimization by introducing crossover and mutation mechanisms to the primary particle swarm optimization.

3.1 Primary Particle Swarm Optimization

In the primary particle swarm optimization (PSO), we firstly initialize particles’ scale, dimensions, velocity and location according to the optimization problem. Then calculate the solution in their present conditions, picking their own best solution as the personal best and the best solution of the swarm as the global best. After that, update particles’ velocity and location according to certain formulas. And calculate the new solution with the new velocity and location. Finally, iterate the above processes until the termination criteria is met and output the best solution and its location.

3.2 PSO with Crossover and Mutation Mechanisms

Due to the shortcomings of prematurity and local optima, we improve the algorithm by introducing crossover and mutation to the primary PSO.

Crossover Mechanism.

Crossover is a method that generates a new individual by recombining certain parts of its parent individuals. The operation is to randomly pick two individuals from the swarm, select the crossover location and choose whether to crossover according to the crossover rate pc, which is between 0.25 and 1.

Mutation Mechanism.

Mutation is an operation that changes the value in a certain dimension of the individual with a relatively small probability. The detailed operation is to generate a random number between 0 and 1. If the number is smaller than the mutation probability, which is between 0.001 and 0.01, in this iteration each dimension of this particle will randomly mutate within constraint.

We name the improved PSO as Mutation Crossover Particle Swarm Optimization (MCPSO). Moreover, we will introduce an algorithm with only a mutation mechanism as a comparing algorithm (Mutation Particle Swarm Optimization, MPSO). Compared with the primary PSO, MCPSO adds mutation and crossover operations after the update of velocity and location. And, due to the introduction of the crossover mechanism, neighboring particles can learn from each other through a crossover in each dimension. This enhances the region learning ability of the particles and facilitates the algorithm to escape from the local optimum. Figure 1 shows the process of the improved PSO and Fig. 2 shows the process of solving the crew recovery problem with MCPSO.

Fig. 1.
figure 1

Flow chart of MCPSO

Full size image
Fig. 2.
figure 2

Flow chart of MCPSO solving crew recovery problem

Full size image

4 Encoding Scheme

According to the time-space network diagram and multi-commodity flow model, the crew recovery problem can be converted into reallocating crews for each flight. For each flight, they can only choose one crew, meanwhile satisfying related constraints. Combining the characteristics of PSO, the solution to the crew recovery problem can be treated as the sequence number of executable crews selected by each flight. Each particle in the swarm represents a feasible solution, each dimension of the particle represents the flight and the value is the crew’s number picked by the flight.

Based on this coding idea, in the swarm, \(x_i = (x_{i1} ,x_{i2} ,x_{i3} ......x_{in} )\) is the location of ith particle, among which the dimension n should be equal to the total number of flights, xin represents the value of nth dimension in ith particle. Corresponding to the crew recovery problem, xin refers to the crew number selected by nth flight in ith flight schedule. Figure 3 illustrates the encoding method for the crew recovery problem.

Fig. 3.
figure 3

Encoding method of crew recovery problem

Full size image

5 Experiments and Results

5.1 Parameter Settings

This paper used data in Table 2 and Table 3 [14] to verify the performance of MCPSO in solving the crew recovery problem. Table 2 is the primary flight schedule list. Table 3 is the primary crew schedule list, including 6 crews and a backup crew.

Table 2. Primary flight schedule list
Full size table
Table 3. Primary crew schedule list
Full size table
Table 4. Parameter list
Full size table
Table 5. Optimal crew recovery strategy usage table using different algorithms
Full size table

Table 4 is the parameter settings of the algorithms. Note that, the parameter settings are based on the PSO original papers. And the canceling cost is 100 thousand yuan per time, the crew switching cost is 20 thousand yuan per time and the backup crew using cost is 30 thousand yuan per time. In the experiment, flight 1867 is canceled due to weather reason. It is preferred that the recovery crew’s schedule holds the lowest cost and the minimum change compared against the original schedule.

5.2 Experimental Results

We calculated the data 10 times with PSO, MPSO, MCPSO and two variants of MCPSO respectively, and compared their results. Note that, to validate the sensitivity of MCPSO to the crossover rate, the crossover rates of the two variants are set to 0.6 and 0.9, respectively, while the rest of the parameters are the same as MCPSO settings. Table 5 shows the number of times each strategy is used. Figure 4 is the cost of three algorithms. Figure 6 presents the average convergence of the three algorithms with multiple runs. Figure 5 and Fig. 7 display the comparison between MCPSO and the two variants, where the crossover rate is 0.6 for MCPSO_1 and 0.9 for MCPSO_2. Based on the results, it can be seen that the original PSO has a poor optimal-seeking ability, and its final solution has the highest crew recovery cost and a large number of exchange crew tasks so such a recovery scheme is not satisfactory. The performances of the MPSO and MPCSO with additional variation mechanisms have been significantly improved. As shown in Fig. 6, MCPSO and MPSO have an approximate average convergence capacity. However, by comparing the optimal result between the two algorithms in Fig. 4, we can find that the strategy found by MCPSO is better than MPSO. The reason is that the additional crossover mechanism in MCPSO can increase the diversity of solutions, thus sometimes helping the algorithm to find better solutions beyond the local optimum. Furthermore, as shown in Fig. 5 and Fig. 7, the optimal solution of MCPSO is better than the two variants. This illustrates that a moderate crossover rate can improves the diversity of solutions.

Fig. 4.
figure 4

Optimal crew recovery cost comparison among different algorithms

Full size image
Fig. 5.
figure 5

Optimal crew recovery cost comparison among different pc

Full size image
Fig. 6.
figure 6

Average crew recovery cost comparison among different algorithms

Full size image
Fig. 7.
figure 7

Average crew recovery cost comparison among different pc

Full size image

6 Conclusions and Future Directions

In this paper, we studied the irregular flight crew recovery problem, established a crew recovery model and proposed MCPSO and corresponding coding strategy to solve it. By analyzing the improved PSO with comparison algorithms in actual flight instances, it can be concluded that the improved PSO can effectively solve the irregular flight crew recovery problem and finally output a new crew schedule with the lowest recovery cost. In the future, we will utilize MCPSO to solve other irregular flight recovery problems, such as aircraft recovery, passenger recovery, and so on. Moreover, multi-objective optimization is another direction to further explore the considered problem.