Research On Crew Rostering Problem Based On Multi-population Multi-objective Ant Colony Algorithm

With the continuous development of modern society,airplane has become more and more people’s travel choice.Faced with the continuous growth of civil aviation passenger traffic,more flights are needed to meet the needs of the public.Due to the shortage of pilots in our country,how to maximum utilization of crew members has become the key to solve the problem.The unreasonable rostering may lead to pilot fatigue,which not only affects the working status of members,but also reduces the flight quality and thus lays a hidden danger for the public to travel.Therefore,it is of great significance to optimize the resource allocation between flight and crew members for the high-quality development of civil aviation industry.Existing studies mainly optimize the airline crew rostering problem(CRP)from the perspective of maximizing airline profits.However,CRP is also related to the vital interests of crew members,especially the fairness and satisfaction of crew scheduling have an important impact on the work efficiency and emotional state of crew members.To solve this problem,this study proposes a new practical model for CRP from the perspective of crew member that takes both fairness and satisfaction into account simultaneously.To solve the multi-objective CRP efficiently,this study develops an ant colony system(ACS)algorithm based on the multiple populations for multiple objectives(MPMO)framework,termed multi-objective ACS(MOACS).The main contributions of MOACS lie in three aspects.Firstly,two ant colonies are utilized to optimize fairness and satisfaction objectives,respectively.Secondly,in order to avoid ant colonies focusing only on their own optimization objectives,this study proposes a new hybrid complementary heuristic strategy with three kinds of heuristic information schemes to help explore the Pareto front(PF)sufficiently.The three kinds of heuristic information schemes include the heuristic information of fairness,the heuristic information of satisfaction,and the aggregated heuristic information.Thirdly,a local search strategy with two types of local search respectively for fairness and satisfaction is designed to further approach the global PF.The MOACS is applied to seven real-world monthly CRPs with different sizes from a major NorthAmerican airline.Experimental results show that MOACS generally outperforms the greedy algorithm and some existing multi-objective optimization algorithms,especially on large-scale instances.