الگوریتم مبتنی بر بهینه‌سازیِ کلونی مورچه برای مسئله‌ی زبمان‌بندیِ کارکنان هواپیمایی

Airline crew scheduling is an NP-hard constrained combinatorial optimization problem, and an effective crew scheduling system is essential for reducing operating costs in the airline industry. Ant colony optimization algorithm (ACO) has successfully applied to solve many difficult and classical optimization problems especially on traveling salesman problems (TSP). Therefore, this paper formulated airline crew scheduling problem as Traveling Salesman Problem and then introduce ant colony optimization algorithm to solve it. Performance was evaluated by performing computational tests regarding real cases as the test problems. The results showed that ACO-based algorithm can be potential technique for airline crew scheduling.

Crew cost, second to fuel cost is essential to airline carrier operations. The scheduling of crew members, which is the assignment of crew members to a flight for some period of time, is generally divided into crew scheduling problem and crew rostering problem. The objective of crew scheduling problem is to construct a set of feasible pairings that minimizes the total crew assigning cost and also satisfies the given flight schedule, the fleet routes, labor union and government regulations, and the company’s own policy. For rostering problems, the pairings are assigned to crew members that satisfy their skills, vacations, and other requirements. This paper focuses on the problem of crew scheduling problem because crew scheduling results influence crew operating costs seriously and directly (Yan & Chang, 2002). Airline crew scheduling problem (ACSP) is a difficult combinatorial optimization problem that is traditionally formulated as the set cover problem (SCP) or the set partition problem (SPP) and then used heuristic or mathematic programming to solve it. The vast studies applied this approach to ACSP include (Gamache et al., 2007, Levine, 1996, Park and Ryu, 2006, Yan and Tu, 2002 and Yan and Chang, 2002). However, this approach has significant drawbacks. First, such an approach is computationally unsatisfactory, especially when the number of flights is large. Second, approaches using column generation techniques attempt to keep the best columns for SCP or SPP but may sometimes need suboptimal columns to produce better solution. For above question, Ozdemir and Mohan (2001) applied flight-based scheduling approach to ACSP and then used Genetic Algorithms to solve. The computational experiments showed that the flights scheduling approach can get better results than the SCP-based approach. Ant colony optimization (ACO) algorithm that was proposed by Dorigo in 1992 is a meta-heuristic for combinatorial optimization problems. ACO that mimics a real ant colony with positive feedback characteristics has been noticed by researchers in the field of optimization (Bonabeau et al., 1999, Dorigo et al., 1999 and Engelbrecht, 2005). Many researchers in related fields have successfully applied ACO to solve many difficult and classical optimization problems such as the traveling salesman problems (TSP) (Dorigo and Gambardella, 1997 and Wu et al., 2009), quadratic assignment problems (QAP) (Maniezzo & Colorni, 1999) constraint satisfaction problems (CSP), (Solnon, 2002) and multimodal problems (ToksarI, 2009). When airline crew scheduling problems formulate as flight-based scheduling model, we find that this model is actually in the same form as the Traveling Salesman Problem with constrained. Therefore, this paper proposed ACO to solve airline crew scheduling problem by applying the flight-based scheduling representation and attempt to search shortest path from the flight graph such as TSP. The performance evaluation results indicate that ACO is an effective and efficient heuristic algorithm to minimize the total crew costs by effectively scheduling flights to reduce overnight stay in hotels, deadhead times and sitting time for solving airline crew scheduling problems. The rest of this paper is organized as follows. Section 2 describes the constraints and cost function of our optimizing airline crew scheduling problems. Section 3 present details of the ACO-based algorithm solving the airline crew scheduling problem. In Section 4 the analysis of the performance of ACO-base algorithm is provided. Conclusions are finally drawn in Section 5, along with recommendations for future research.

In this paper, a powerful and robust algorithm which is based on ant colonies, that is used to solve airline crew scheduling problems is proposed. Performance of the proposed ACO-based algorithm is examined on real cases of airline companies. When compared with the GA used to solve airline crew scheduling problem, results show that the ACO-based algorithm has a noticeable performance to minimize the total crew costs by effectively scheduling flights to reduce overnight stay in hotels, deadhead times and sitting time for airline companies. A further study will be done on that to expand the ACO-based algorithm to consider the habits and requirements of crew members to increase satisfaction of crew members.