Abstract
Air transportation is eminent for its fast speed and low cargo damage rate among other ways. However, it is greatly limited by emergent factors like bad weather and current COVID-19 epidemic, where irregular flights may occur. Confronted with the negative impact caused by irregular flight, it is vital to rearrange the preceding schedule to reduce the cost. To solve this problem, first, we established a multi-objective model considering cost and crew satisfaction simultaneously. Secondly, due to the complexity of irregular flight recovery problem, we proposed a tabu-based multi-objective particle swarm optimization introducing the idea of tabu search. Thirdly, we devised an encoding scheme focusing on the characteristic of the problem. Finally, we verified the superiority of the tabu-based multi-objective particle swarm optimization through the comparison against MOPSO by the experiment based on real-world data.
Access provided by Autonomous University of Puebla. Download conference paper PDF
Similar content being viewed by others
Keywords
1 Introduction
In the third year of facing COVID-19, the world is still suffering under the highly infectious variant Omicron. Though the dynamic clearing policy adopted by Chinese government reduces the loss greatly, the following lockdown and quarantine lead to flight circuit breaker mechanism. Moreover, weather anomaly generated by global warming may also cause irregular situation.
According to the Normal Statistical Method of Civil Aviation Flight [1] released by Civil Aviation Administration of China, normal flights can be defined as follows “flights depart 10 min or shorter after scheduled departure time without sliding back, veering or preparing for landing, or arrive within 10 min before scheduled arrival time.” And irregular flights refer to those do not obey above conditions. Usually, the occurrence of irregular flight happens days or even hours before takeoff, which requires airline to recover it correctly and timely. The recovery is composed of route, flight, aircraft and crew recovery. And only crew recovery problem takes humanistic factors into account amongst them, which is a channel to exhibit airline’s corporate responsibility and also a crucial means to improve onboard services. Hence the main question addressed in this paper is crew recovery problem.
Plenty of scholars have studied the irregular flight recovery problem from a wide variety of angles. Chutima et al. [2] considered cost, workload and pilots’ preference at the same time. Wen et al. [3] took flight flying time variability into account. Zeighami et al. [4] and Zhou et al. [5] separately developed an algorithm based on alternating Lagrangian decomposition and ant colony algorithm in solving the problem. Doi et al. [6] and Quesnel et al. [7] respectively studied the impact of fair working time and crews’ preferences on crew recovery problem. Antunes et al. [8] emphasized the robustness of schedule. Wen et al. [9] studied the relationship between manpower availability and crew scheduling strategies. Evler et al. [10] and Jin et al. [11] adopted rolling horizon algorithm and column generation method respectively in cope with the recovery problem. However, each of them indeed had come up with a way to either actualize the problem or speed the convergence velocity. In this paper, we introduced crew’s satisfaction of work time to the previous single objective model of cost, which was highly associated with the efficiency and effectiveness of rearrangement. In addition, it also enriched the diversity of the original recovery problem.
When solving models with more than one objective, it usually fails to meet the demand of accuracy and timeliness by merely changing the multi-objective problem into single-objective one. And multi-objective algorithms, like MOPSO, can satisfy the needs of multiple objectives and show their merits like fewer adjustment parameters. However, it also inherits the shortcomings like easily falling into local optimum, which is the main focus of recent studies. Zhang et al. [12] developed a competitive mechanism to further improve the global and personal best particles. Luo et al. [13] introduced an indicator and direction vectors to enhance the capability of local exploration and maintain the non-dominated solution. Cui et al. [14] proposed a two-archive mechanism to emphasize convergence and diversity separately. Devaraj et al. [15] hybridized MOPSO and firefly algorithm to minimize the search space. Qu et al. [16] and Liang et al. [17] both introduced a self-organized based MOPSO to locate multiple Pareto optimal solutions. Liu et al. [18] used objective space division method to find Pbest and Gbest. Mohd et al. [19] hybridized dynamic boundary search method with MOPSO. Goyal et al. [20] came up with a hybrid algorithm of RSM (Response Surface Methodology) and MOPSO. Mahapatra et al. [21] introduced a hesitant fuzzy MOPSO algorithm to MORRA problem. Sellami et al. [22] suggested a MOPSO combined with MATPOWER toolbox. Whereas, recent studies in the field of MOPSO have only focused on the improvement of its internal mechanism and search methods, but few attempt to integrate other algorithms into MOPSO. Therefore, in this paper, we combined MOPSO with tabu search to improve the local optimum problem.
The main contributions of this paper include three parts. First, the crew recovery model would be closer to real-world situation after we considered the satisfaction of crew members besides recovery cost. Secondly, we proposed a tabu-based multi-objective particle swarm optimization enabling the primary algorithm to overcome the local optimum problem. Thirdly, we established a coding scheme based on the characteristics of the problem.
The paper has been organized in the following way. Section 2 states the multi-objective model. Section 3 describes the tabu-based multi-objective 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.
2 Model of Multi-objective Crew Recovery Problem
This section describes the model of crew recovery problem. The model considering cost and satisfaction is listed below. Table 1 explains the meaning of parameters displayed in the mathematical model.
Our model includes two objective functions. Objective function (1) demands the lowest executing cost and canceling cost. Objective function (2) requires the minimum of crew member’s worktime variance, which means the fairness of the worktime of each crew is preferred.
Constraint (3) ensures each flight can only be executed by single crew, or canceled. Constraint (4) guarantees each crew can execute at most one task list. Constraint (5) requires the duration of crew executing task every month is less than 100 h. Constraint (6) restricts the rest time of crew between two consecutive tasks is more than 1 h. Constraint (7) ensures the ending airport of preceding task is the same as the following task’s airport.
3 Improved Multi-objective Particle Swarm Algorithm
In this section, we present our tabu-based multi-objective particle swarm algorithm, abbreviated as MOPSO-TS, which combining the primary MOPSO and tabu search.
3.1 Primary MOPSO
Multi-objective particle swarm optimization is based on single-objective PSO, finding global excellent solution set through establishing non-dominant solution set and selecting one particle in non-dominant set as guiding solution. Through randomizing the location of each point, iterating and updating towards different directions and broadly exploring the unknown space, a Pareto front will be obtained finally.
3.2 Tabu-Based Multi-objective Particle Swarm Algorithm
Due to MOPSO’s drawback of prematurity and local optima, we introduced tabu search to the primary MOPSO.
Tabu search algorithm is an iterative search algorithm simulating human intelligence. It can avoid roundabout searching by setting up tabu list and tabu principle, therefore escape from local optimal point and enhance the ability of global search.
Targeting at the shortcoming of MOPSO, we combine the MOPSO with tabu search. Since the initial solution shows a great impact on the effectiveness of tabu search algorithm, firstly, we introduce tabu search algorithm after optimizing iteratively by MOPSO. Then updating the tabu list on the basis of comparatively excellent group which is constituted by non-dominant solution and partly dominant solution. And searching in the neighborhood until the terminal condition is met. The process in detail is presented in Fig. 1 and the improvement is circled in red.
3.3 Tests and Results
Intending to verify the performance of MOPSO-TS, we adopted the ZDT1, ZDT2 and ZDT3 as test functions forwarded by famous scholar Deb [23].
This paper compared MOPSO-TS with primary MOPSO under the same test functions and conditions, and evaluated these algorithms through IGD and HV. Table 2 shows the average number of each index after 30 times of independent experiments.
According to the table, the Pareto fronts concluded by MOPSO-TS in the three test functions are all better than MOPSO. And among the algorithms, MOPSO-TS has the smallest IGD and biggest HV, indicating that MOPSO-TS is better in convergency, diversity and overall performance.
4 Encoding Scheme
According to the model and the characteristic of the problem, we adopted the encoding scheme in Fig. 2.
Each particle in the group represents one scheduling scheme. The number of particle’s dimension refers to the total number of flights. For each dimension which equals to k, it represents the corresponding flight is executed by the \(k\)th crew. If the dimension value is 0, it means the flight is canceled.
5 Experiments and Results
In this section, we simulated the rescheduling process due to the cancelation of certain flight under the force majeure like inclement weather and natural disaster on MATLAB2020a, while balancing the minimal recovery cost and even worktime.
5.1 Parameter Setting
This paper used data in Table 3 and Table 4 [24] to verify the performance of MOPSO-TS in solving irregular flight recovery problem, involving 18 flights and 6 crews. The total flying time must be less than 100 h and the gap between two continual flights is ought to be longer than one hour. The canceling cost is 100 thousand yuan and switching cost is 20 thousand yuan. Table 5 is the detailed parameter setting of MOPSO-TS. To simulate abnormal situation, we assume that flight 1720 is canceled due to epidemic.
5.2 Experiment Result
We adopted MOPSO-TS and MOPSO to solve the problem independently for thirty times, and compared the Pareto Front of them. Pareto front has many points, and we choose one of the point with the lowest cost to exhibit the specific recovery scheme, which is shown as Table 6.
According to the Pareto Front curves in Fig. 3, the front of MOPSO-TS was closer to the bottom left of target space than MOPSO, which demonstrated MOPSO-TS performed better in the solution of our model.
6 Conclusions and Future Directions
In this paper, we studied irregular flight recovery problem, created a multi-objective model considering the fare and satisfaction concurrently and proposed an improved multi-objective particle swarm optimization hybridizing tabu search. In the future, we will apply our algorithm to other problems with multiple objectives and come up with new elements to enrich our model.
References
Notice on the issuance of Normal Statistical Method of Civil Aviation Flight[R]. Communique of Civil Aviation Administration of China (2003)
Chutima, P., Arayikanon, K.: Many-objective low-cost airline cockpit crew rostering optimisation. Comput. Ind. Eng. 150, 106844 (2020)
Wen, X., Ma, H.L., Chung, S.H., et al.: Robust airline crew scheduling with flight flying time variability. Transp. Res. Part E: Logist. Transp. Rev. 144, 102132 (2020)
Zeighami, V., Saddoune, M., Soumis, F.: Alternating Lagrangian decomposition for integrated airline crew scheduling problem. Eur. J. Oper. Res. 287(1), 211–224 (2020)
Zhou, S.Z., Zhan, Z.H., Chen, Z.G., et al.: A multi-objective ant colony system algorithm for airline crew rostering problem with fairness and satisfaction. IEEE Trans. Intell. Transp. Syst. 22(11), 6784–6798 (2020)
Doi, T., Nishi, T., Voß, S.: Two-level decomposition-based matheuristic for airline crew rostering problems with fair working time. Eur. J. Oper. Res. 267(2), 428–438 (2018)
Quesnel, F., Desaulniers, G., Soumis, F.: Improving air crew rostering by considering crew preferences in the crew pairing problem. Transp. Sci. 54(1), 97–114 (2020)
Antunes, D., Vaze, V., Antunes, A.P.: A robust pairing model for airline crew scheduling. Transp. Sci. 53(6), 1751–1771 (2019)
Wen, X., Chung, S.H., Ji, P., et al.: Individual scheduling approach for multi-class airline cabin crew with manpower requirement heterogeneity. Transp. Res. Part E: Logist. Transp. Rev. 163, 102763 (2022)
Evler, J., Lindner, M., Fricke, H., et al.: Integration of turnaround and aircraft recovery to mitigate delay propagation in airline networks. Comput. Oper. Res. 138, 105602 (2022)
Jin, H., Chen, S., Ran, X., et al.: Column generation-based optimum crew scheduling incorporating network representation for urban rail transit systems. Comput. Ind. Eng. 169, 108155 (2022)
Zhang, X., Zheng, X., Cheng, R., et al.: A competitive mechanism based multi-objective particle swarm optimizer with fast convergence. Inf. Sci. 427, 63–76 (2018)
Luo, J., Huang, X., Yang, Y., et al.: A many-objective particle swarm optimizer based on indicator and direction vectors for many-objective optimization. Inf. Sci. 514, 166–202 (2020)
Cui, Y., Meng, X., Qiao, J.: A multi-objective particle swarm optimization algorithm based on two-archive mechanism. Appl. Soft Comput. 119, 108532 (2022)
Devaraj, A.F.S., Elhoseny, M., Dhanasekaran, S., et al.: Hybridization of firefly and improved multi-objective particle swarm optimization algorithm for energy efficient load balancing in cloud computing environments. J. Parallel Distrib. Comput. 142, 36–45 (2020)
Qu, B., Li, C., Liang, J., et al.: A self-organized speciation based multi-objective particle swarm optimizer for multimodal multi-objective problems. Appl. Soft Comput. 86, 105886 (2020)
Liang, J., Guo, Q., Yue, C., Qu, B., Yu, K.: A self-organizing multi-objective particle swarm optimization algorithm for multimodal multi-objective problems. In: Tan, Y., Shi, Y., Tang, Q. (eds.) ICSI 2018. LNCS, vol. 10941, pp. 550–560. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-93815-8_52
Liu, J., Zhang, H., He, K., et al.: Multi-objective particle swarm optimization algorithm based on objective space division for the unequal-area facility layout problem. Expert Syst. Appl. 102, 179–192 (2018)
bin Mohd Zain, M.Z., Kanesan, J., Chuah, J.H., et al.: A multi-objective particle swarm optimization algorithm based on dynamic boundary search for constrained optimization. Appl. Soft Comput. 70, 680–700 (2018)
Goyal, K.K., Sharma, N., Dev Gupta, R., et al.: A soft computing-based analysis of cutting rate and recast layer thickness for AZ31 alloy on WEDM using RSM-MOPSO. Materials 15(2), 635 (2022)
Mahapatra, G.S., Maneckshaw, B., Barker, K.: Multi-objective reliability redundancy allocation using MOPSO under hesitant fuzziness. Expert Syst. Appl. 198, 116696 (2022)
Sellami, R., Farooq, S., Rafik, N.: An improved MOPSO algorithm for optimal sizing & placement of distributed generation: a case study of the Tunisian offshore distribution network (ASHTART). Energy Rep. 8, 6960–6975 (2022)
Deb, K., Pratap, A., Agarwal, S., et al.: A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)
Wei, G., Yu, G., Song, M.: Optimization model and algorithm for crew management during airline irregular operations. J. Comb. Optim. 1(3), 305–321 (1997)
Acknowledgment
The study was supported in part by the Natural Science Foundation of China Grant No. 62103286, No. 71971143, No. 62001302, in part by Social Science Youth Foundation of Ministry of Education of China under Grant 21YJC630181, in part by Guangdong Provincial Philosophy and Social Sciences Planning Project under Grant GD22XGL22, in part by Guangdong Basic and Applied Basic Research Foundation under Grant 2019A1515110401, 2021A1515011348, 2019A1515111205, in part by Guangdong Province Philosophy and Social Science Planning Discipline Co-construction Project under Grant GD22XGL22, in part by Natural Science Foundation of Guangdong Province under Grant 2020A1515010749, 2020A1515010752, in part by Key Research Foundation of Higher Education of Guangdong Provincial Education Bureau under Grant 2019KZDXM030, in part by Natural Science Foundation of Shenzhen under Grant JCYJ20190808145011259, in part by Shenzhen Science and Technology Program under Grant RCBS20200714114920379, in part by Guangdong Province Innovation Team Intelligent Management and Interdisciplinary Innovation under Grant 2021WCXTD002, in part by Special Projects in Key Fields of Ordinary Colleges and Universities in Guangdong Province under Grant 2022ZDZX2054.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Zhou, T., Lai, Y., Huang, X., Chen, X., Zhong, H. (2023). A Tabu-Based Multi-objective Particle Swarm Optimization for Irregular Flight Recovery Problem. In: Xu, Y., Yan, H., Teng, H., Cai, J., Li, J. (eds) Machine Learning for Cyber Security. ML4CS 2022. Lecture Notes in Computer Science, vol 13657. Springer, Cham. https://doi.org/10.1007/978-3-031-20102-8_10
Download citation
DOI: https://doi.org/10.1007/978-3-031-20102-8_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-20101-1
Online ISBN: 978-3-031-20102-8
eBook Packages: Computer ScienceComputer Science (R0)